多線程技術 單線程結構進程 傳統進程是單線程結構進程 單線程結構進程的問題: 單線程結構進程在併發程式設計上存在的問題,進程切換開銷大,進程通信開銷大,限制了進程併發的粒度,降低了並行計算的效率 解決問題的思路: 把進程的兩項功能，即“獨立分配資源”與“被調度分派執行”分離開來,進程作為系統資源分配 ...
多線程技術
單線程結構進程
傳統進程是單線程結構進程
單線程結構進程的問題:
單線程結構進程在併發程式設計上存在的問題,進程切換開銷大,進程通信開銷大,限制了進程併發的粒度,降低了並行計算的效率
解決問題的思路:
把進程的兩項功能，即“獨立分配資源”與“被調度分派執行”分離開來,進程作為系統資源分配和保護的獨立單位，不需要頻繁地切換,線程作為系統調度和分派的基本單位，能輕裝運行，會被頻繁地調度和切換,線程的出現會減少進程併發執行所付出的時空開銷，使得併發粒度更細、併發性更好
多線程結構進程
多線程環境下進程的概念:
在多線程環境中，進程是操作系統中進行保護和資源分配的獨立單位。具有:用來容納進程映像的虛擬地址空間,對進程、文件和設備的存取保護機制
線程是進程的一條執行路徑，是調度的基本單位，同一個進程中的所有線程共用進程獲得的主存空間和資源。它具有：線程執行狀態,受保護的線程上下文，當線程不運行時，用於存儲現場信息,獨立的程式指令計數器,執行堆棧,容納局部變數的靜態存儲器
多線程環境下線程的狀態與調度
線程狀態有運行、就緒和睡眠，無掛起,與線程狀態變化有關的線程操作有：孵化、封鎖、活化、剝奪、指派、結束,OS感知線程環境下：處理器調度對象是線程,進程沒有三狀態（或者說只有掛起狀態）,OS不感知線程環境下：處理器調度對象仍是進程,用戶空間中的用戶調度程式調度線程
併發多線程程式設計的優點:快速線程切換,減少（系統）管理開銷,(線程）通信易於實現,並行程度提高,節省記憶體空間
多線程技術的應用:前臺和後臺工作,C/S應用模式,加快執行速度,設計用戶介面
KLT和ULT
內核級線程KLT,Kernel-LevelThreads
線程管理的所有工作由OS內核來做,OS提供了一個應用程式設計介面API，供開發者使用KLT,OS直接調度KLT用戶空間P內核空間P
內核級線程的特點
進程中的一個線程被阻塞了，內核能調度同一進程的其它線程占有處理器運行,多處理器環境中，內核能同時調度同一進程中多個線程並行執行,內核自身也可用多線程技術實現，能提高操作系統的執行速度和效率,應用程式線程在用戶態運行，線程調度和管理在內核實現，在同一進程中，控制權從一個線程傳送到另一個線程時需要模式切換，系統開銷較大
用戶級線程ULT,User-LevelThreads
用戶空間運行的線程庫，提供多線程應用程式的開發和運行支撐環境,任何應用程式均需通過線程庫進行程式設計，再與線程庫連接後運行,線程管理的所有工作都由應用程式完成，內核沒有意識到線程的存在P用戶空間線程庫內核空間
用戶級線程的特點
所有線程管理數據結構均在進程的用戶空間中，線程切換不需要內核模式，能節省模式切換開銷和內核的寶貴資源，允許進程按應用特定需要選擇調度演算法，甚至根據應用需求裁剪調度演算法，能運行在任何OS上，內核在支持ULT方面不需要做任何工作，不能利用多處理器的優點，OS調度進程，僅有一個ULT能執行，一個ULT的阻塞，將引起整個進程的阻塞
Jacketing技術
把阻塞式系統調用改造成非阻塞式的，當線程陷入系統調用時，執行jacketing程式，由jacketing程式來檢查資源使用情況，以決定是否執行進程切換或傳遞控制權給另一個線程
ULT適用於解決邏輯並行性問題,KLT適用於解決物理並行性問題
多線程實現的混合式策略
線程創建是完全在用戶空間做的,單應用的多個ULT可以映射成一些KLT，通過調整KLT數目，可以達到較好的並行效果
多線程實現混合式策略的特點
組合用戶級線程/內核級線程設施，線程創建完全在用戶空間中完成，線程的調度和同步也在應用程式中進行，一個應用中的多個用戶級線程被映射到一些(小於等於用戶級線程數目)內核級線程上，程式員可以針對特定應用和機器調節內核級線程的數目，以達到整體最佳結果，該方法將會結合純粹用戶級線程方法和內核級線程方法的優點，同時減少它們的缺點
線程混合式策略下的線程狀態
KLT三態，系統調度負責，ULT三態，用戶調度負責，活躍態ULT代表綁定KLT的三態，活躍態ULT運行時可激活用戶調度，非阻塞系統調用可使用Jacketing啟動用戶調度，調整活躍態ULT
多線程實現的各種策略總結
處理器調度的層次
高級調度：又稱長程調度，作業調度,決定能否加入到執行的進程池中
中級調度，又稱平衡負載調度,決定主存中的可用進程集合
低級調度：又稱短程調度，進程調度,決定哪個可用進程占用處理器執行
高級調度
分時OS中，高級調度決定：是否接受一個終端用戶的連接,命令能否被系統接納並構成進程,新建態進程是否加入就緒進程隊列
批處理OS中，高級調度又稱為作業調度，功能是按照某種原則從後備作業隊列中選取作業進入主存，併為作業做好運行前的準備工作和完成後的善後工作
中級調度
引進中級調度是為了提高記憶體利用率和作業吞吐量,中級調度決定那些進程被允許駐留在主存中參與競爭處理器及其他資源，起到短期調整系統負荷的作用,中級調度把一些進程換出主存，從而使之進入“掛起”狀態，不參與進程調度，以平順系統的負載
低級調度
低級調度：又稱處理器調度、進程調度、短程調度，按照某種原則把處理器分配給就緒態進程或內核級線程,進程調度程式：又稱分派程式，操作系統中實現處理器調度的程式，是操作系統的最核心部分,處理器調度策略的優劣直接影響到整個系統的性能
低級調度的主要功能:
- 記住進程或內核級線程的狀態
- 決定某個進程或內核級線程什麼時候獲得處理器，以及占用多長時間
- 把處理器分配給進程或內核級線程
- 收回處理器
處理器調度演算法
選擇處理器調度演算法的原則
- 資源利用率：使得CPU或其他資源的使用率儘可能高且能夠並行工作
- 響應時間：使互動式用戶的響應時間儘可能小，或儘快處理實時任務
- 周轉時間：提交給系統開始到執行完成獲得結果為止的這段時間間隔稱周轉時間，應該使周轉時間或平均周轉時間儘可能短
- 吞吐量：單位時間處理的進程數儘可能多
- 公平性：確保每個用戶每個進程獲得合理的CPU份額或其他資源份額
優先數調度演算法
根據分配給進程的優先數決定運行進程：搶占式優先數調度演算法（對實時的適用），非搶占式優先數調度演算法（對大多數適合）
優先數的確定准則：進程負擔任務的緊迫程度，進程的交互性，進程使用外設的頻度，進程進入系統的時間長短
與進入系統時間相關的優先數
- 計算時間短(作業/進程)優先
- 剩餘計算時間短進程優先
- 響應比高者(作業/進程)優先響應比=等待時間/進入時間
- 先來先服務：先進隊先被選擇
- 多用於高級調度；低級調度中，以計算為主的進程過於優越
時間片輪轉調度演算法
- 根據各個進程進入就緒隊列的時間先後輪流占有CPU一個時間片
- 時間片中斷
- 時間片的確定：選擇長短合適的時間片,過長則退化為先來先服務演算法,過短則調度開銷大
- 單時間片，多時間片和動態時間片
分級調度演算法
又稱多隊列策略，反饋迴圈隊列，基本思想是建立多個不同優先順序的就緒進程隊列，多個就緒進程隊列間按照優先數調度，高優先順序就緒進程，分配的時間片短，單個就緒進程隊列中進程的優先數和時間片相同
分級調度演算法的分級原則
- 一般分級原則
- 外設訪問，交互性，時間緊迫程度，系統效率，用戶立場，...
- 現代操作系統的實現模型
- 多個高優先順序的實時進程隊列，如：硬實時、網路、軟實時
- 多個分時任務的進程隊列，根據基準優先數和執行行為調整
- 隊列數可能多達32-128個
彩票調度演算法
基本思想：為進程發放針對系統各種資源（如CPU時間）的彩票；當調度程式需要做出決策時，隨機選擇一張彩票，持有該彩票的進程將獲得系統資源,合作進程之間的彩票交換
