操作系統(tǒng)第二章的主線是回答一個問題多個程序同時運行時操作系統(tǒng)如何管理它們、分配處理機、協(xié)調共享資源并處理資源互相等待的情況本文從進程和線程出發(fā)依次梳理進程控制、進程通信、處理機調度、同步互斥、信號量、管程和死鎖。理解這些概念時建議始終抓住三個對象進程狀態(tài)、PCB 信息、資源分配關系。一、進程的基本概念1.1 程序、進程與進程實體程序是靜態(tài)的指令集合通常以可執(zhí)行文件的形式保存在磁盤中。進程是程序的一次執(zhí)行過程是動態(tài)產生、運行和結束的過程。進程實體也叫進程映像由三部分組成PCB進程控制塊操作系統(tǒng)管理進程所需的信息例如 PID、當前狀態(tài)、寄存器現(xiàn)場、調度信息和資源清單。程序段進程要執(zhí)行的程序代碼。數(shù)據(jù)段運行過程中使用的全局變量、臨時數(shù)據(jù)等。進程是系統(tǒng)進行資源分配和處理機調度的獨立單位。操作系統(tǒng)并不直接用一段程序代碼代表一個正在運行的任務而是通過 PCB 把代碼、數(shù)據(jù)、狀態(tài)和資源聯(lián)系起來。1.2 進程的特征動態(tài)性進程有創(chuàng)建、運行、阻塞和終止等過程這是進程區(qū)別于靜態(tài)程序的根本特征。并發(fā)性內存中可以同時存在多個進程它們在宏觀上同時推進。獨立性進程可以獨立獲得資源、獨立運行并接受調度。異步性每個進程按照自己的速度推進執(zhí)行順序和完成時間具有不確定性。結構性每個進程都配置 PCB進程實體由 PCB、程序段和數(shù)據(jù)段構成。二、進程狀態(tài)與進程控制2.1 五種基本狀態(tài)創(chuàng)建態(tài)操作系統(tǒng)正在建立進程分配資源并初始化 PCB。就緒態(tài)進程已經具備運行條件只等待處理機。運行態(tài)進程正在占用 CPU 執(zhí)行。阻塞態(tài)進程因等待 I/O、信號或其他事件而暫時不能運行。終止態(tài)進程執(zhí)行結束或發(fā)生異常操作系統(tǒng)正在回收資源。PCB 中的 State 字段記錄進程當前狀態(tài)。典型轉換包括就緒態(tài)到運行態(tài)由調度程序觸發(fā)運行態(tài)到阻塞態(tài)通常由等待事件觸發(fā)阻塞態(tài)到就緒態(tài)由等待事件完成觸發(fā)運行態(tài)到終止態(tài)則可能由 exit 或異常引起。2.2 進程的組織方式鏈式組織方式按照進程狀態(tài)建立多個隊列例如就緒隊列、等待打印機的阻塞隊列和等待磁盤的阻塞隊列操作系統(tǒng)保存各隊列的指針。索引組織方式則為不同狀態(tài)建立索引表再由操作系統(tǒng)保存各索引表的入口。兩種方式的目的相同讓操作系統(tǒng)能夠快速找到處于某種狀態(tài)的 PCB。2.3 原語與進程控制進程控制會改變進程狀態(tài)、更新 PCB、調整隊列并可能分配或回收資源。完成這些操作時必須保證中間狀態(tài)不會被其他程序觀察到因此需要使用原語。原語是一段執(zhí)行過程具有原子性的程序執(zhí)行期間不能被中斷。操作系統(tǒng)通常通過關中斷指令和開中斷指令保證原語一氣呵成。創(chuàng)建原語申請空白 PCB。為新進程分配所需資源。初始化 PCB。將 PCB 插入就緒隊列。用戶登錄、作業(yè)調度、系統(tǒng)提供服務以及應用程序請求都可能觸發(fā)進程創(chuàng)建。終止原語找到目標進程的 PCB。如果進程仍在運行先剝奪其 CPU。終止其子進程或子線程。回收進程占有的資源。刪除 PCB。阻塞與喚醒原語阻塞時操作系統(tǒng)保護進程運行現(xiàn)場將狀態(tài)改為阻塞態(tài)再把 PCB 放入對應事件的等待隊列。喚醒時操作系統(tǒng)將 PCB 從等待隊列移出改為就緒態(tài)并插入就緒隊列。阻塞和喚醒必須成對出現(xiàn)阻塞表示等待某個事件喚醒表示該事件已經發(fā)生。喚醒后進程進入的是就緒態(tài)不會直接占用 CPU。切換原語進程切換包括保存原進程的運行環(huán)境、將其 PCB 放入相應隊列、選擇新進程、更新新進程 PCB并恢復新進程的運行環(huán)境。切換本身有開銷過于頻繁會降低系統(tǒng)有效執(zhí)行時間。三、進程通信與線程3.1 進程通信不同進程擁有相互獨立的地址空間進程之間不能直接讀寫對方的內存因此需要操作系統(tǒng)提供進程通信機制IPC。共享存儲操作系統(tǒng)在內存中劃出共享區(qū)域讓多個進程通過該區(qū)域交換數(shù)據(jù)。基于數(shù)據(jù)結構的共享限制較多屬于低級通信方式基于存儲區(qū)的共享由進程自行決定數(shù)據(jù)格式和存放位置速度更快屬于高級通信方式。共享區(qū)同時只能被一個進程以互斥方式訪問否則會出現(xiàn)數(shù)據(jù)覆蓋和讀寫沖突。同步工具可以使用信號量等機制。消息傳遞消息傳遞以格式化消息為單位通過發(fā)送和接收原語完成數(shù)據(jù)交換。直接通信時發(fā)送方直接指定接收進程間接通信時發(fā)送方和接收方通過信箱交換消息。管道通信管道是由系統(tǒng)調用建立的特殊共享文件通常對應內存中的固定大小緩沖區(qū)。管道具有單向、先進先出和半雙工特點需要雙向同時通信時應建立兩個管道。當管道寫滿時寫進程阻塞當管道讀空時讀進程阻塞。管道中的數(shù)據(jù)被讀出后就會消失因此多個進程讀取同一管道時需要特別注意數(shù)據(jù)分配和同步。3.2 線程線程是程序執(zhí)行流的最小單位也是基本的 CPU 執(zhí)行單位。引入線程后進程主要負責分配除 CPU 之外的系統(tǒng)資源線程負責接受處理機調度。用戶級線程由線程庫管理線程切換可以在用戶態(tài)完成開銷較小缺點是一個用戶級線程阻塞時整個進程可能被阻塞而且多個用戶級線程不能真正并行使用多核 CPU。內核級線程由操作系統(tǒng)內核管理內核為每個線程建立 TCB。一個線程阻塞后同一進程中的其他線程仍可能運行也可以在多核處理機上并行執(zhí)行代價是線程切換需要進入核心態(tài)管理開銷更大。多線程模型描述用戶級線程與內核級線程的映射關系一對一一個用戶級線程對應一個內核級線程并發(fā)能力強但內核線程數(shù)量多。多對一多個用戶級線程對應一個內核級線程切換開銷小但一個線程阻塞可能導致整個進程阻塞。多對多多個用戶級線程映射到多個內核級線程在并發(fā)能力和管理開銷之間折中。四、處理機調度4.1 三個調度層次高級調度作業(yè)調度從外存后備隊列選擇作業(yè)調入內存并建立進程。每個作業(yè)通常只調入一次、調出一次。低級調度進程調度從就緒隊列選擇進程把 CPU 分配給它。它是最基本、發(fā)生頻率最高的調度。中級調度決定哪些掛起進程重新調入內存一個進程可能多次被調出和調入。調度程序需要決定兩個問題讓哪個進程運行以及它可以運行多長時間。沒有可運行的普通進程時系統(tǒng)會安排優(yōu)先級最低的閑逛進程運行避免 CPU 空轉。4.2 調度時機與調度方式進程主動放棄 CPU 的情況包括正常終止、運行異常終止和主動請求阻塞例如等待 I/O。時間片用完、更高優(yōu)先級進程進入就緒隊列或發(fā)生緊急 I/O 事件則屬于被動放棄。處理中斷、執(zhí)行操作系統(tǒng)內核程序臨界區(qū)以及執(zhí)行原語時不能隨意進行進程調度和切換否則可能破壞內核數(shù)據(jù)結構的一致性。非剝奪調度只允許進程主動釋放 CPU實現(xiàn)簡單、開銷小但響應緊急任務的能力較弱。剝奪調度允許系統(tǒng)暫停當前進程并分配 CPU 給更緊急的進程更適合分時系統(tǒng)和實時系統(tǒng)。4.3 調度算法的評價指標CPU 利用率 CPU 忙碌時間 ÷ 總時間。吞吐量 單位時間內完成的作業(yè)數(shù)。周轉時間 完成時間 - 到達時間。帶權周轉時間 周轉時間 ÷ 實際運行時間。等待時間 進程處于等待處理機狀態(tài)的時間總和。響應時間 提交請求到首次得到響應的時間。評價算法時不能只看一個指標?？s短平均等待時間的算法未必能同時提供最好的公平性和響應速度。4.4 常見調度算法先來先服務FCFS按照到達先后順序調度規(guī)則簡單且公平。缺點是長作業(yè)排在前面時會讓后續(xù)短作業(yè)等待很久。短作業(yè)優(yōu)先SJF每次選擇當前已到達且運行時間最短的進程目標是降低平均等待時間。它需要預估運行時間長作業(yè)可能長期得不到服務產生饑餓。搶占式短作業(yè)優(yōu)先也叫最短剩余時間優(yōu)先。就緒隊列發(fā)生變化時如果新進程的剩余時間更短就搶占當前進程。最高響應比優(yōu)先HRRN響應比計算公式為響應比 等待時間 要求服務時間÷ 要求服務時間等待時間越長響應比越高因此 HRRN 在兼顧短作業(yè)的同時可以緩解長作業(yè)饑餓。它通常屬于非搶占式調度。時間片輪轉RR就緒隊列中的進程輪流執(zhí)行一個時間片常用于分時系統(tǒng)。時間片過大時算法接近 FCFS時間片過小時進程切換頻繁保存和恢復運行環(huán)境的開銷增加。優(yōu)先級調度每次選擇優(yōu)先級最高的進程可以是搶占式也可以是非搶占式。系統(tǒng)進程通常高于用戶進程前臺進程通常高于后臺進程I/O 型進程也可能獲得更高優(yōu)先級。優(yōu)先級長期不變時同樣可能發(fā)生饑餓。多級反饋隊列系統(tǒng)設置多個就緒隊列隊列優(yōu)先級從高到低時間片從小到大。新進程先進入高優(yōu)先級隊列時間片用完仍未結束時降到下一級隊列。只有高優(yōu)先級隊列為空低一級隊列才獲得 CPU。多級反饋隊列不要求事先準確知道進程運行時間能夠較快響應新進程也能讓短作業(yè)較早完成同時降低 CPU 密集型進程對交互式進程的影響。五、進程同步與互斥5.1 同步、互斥與臨界區(qū)同步是進程之間為完成共同任務而形成的直接制約關系例如生產者必須先生產消費者才能消費?；コ馐嵌鄠€進程訪問臨界資源時形成的間接制約關系。臨界資源是一次只允許一個進程使用的資源訪問臨界資源的代碼稱為臨界區(qū)。一個正確的互斥方案應滿足空閑讓進臨界區(qū)空閑時請求進程可以進入。忙則等待已有進程進入臨界區(qū)時其他進程必須等待。有限等待請求進程不能無限期等待。讓權等待等待時應釋放 CPU避免忙等。5.2 軟件實現(xiàn)方法單標志法通過輪流賦予進入權限實現(xiàn)互斥但臨界區(qū)空閑時可能仍不允許某個進程進入違反空閑讓進。雙標志先檢查法先檢查對方標志再設置自己的標志。檢查和上鎖不是原子操作兩個進程可能同時通過檢查違反忙則等待。雙標志后檢查法先上鎖再檢查避免了同時進入但兩個進程可能都先上鎖造成長期等待違反空閑讓進和有限等待。Peterson 算法結合標志和謙讓變量能夠滿足空閑讓進、忙則等待和有限等待但仍可能忙等不能完全滿足讓權等待。5.3 硬件實現(xiàn)方法中斷屏蔽通過關中斷保護臨界區(qū)簡單高效但只適合內核程序且不適用于多處理機環(huán)境。TestAndSet 和 Swap 指令由硬件保證原子性把檢查和上鎖合并為不可分割的操作適合多處理機系統(tǒng)。它們的共同缺點是可能讓等待進程持續(xù)占用 CPU形成忙等。六、信號量與管程6.1 信號量信號量是表示系統(tǒng)中某類資源數(shù)量的變量進程通過 wait 和 signal 原語對它進行操作。記錄型信號量除了記錄 value還維護等待進程隊列。典型操作可以概括為wait(S)S.value 減一若結果小于 0當前進程進入阻塞隊列 signal(S)S.value 加一若仍有進程等待則喚醒其中一個wait 用于申請資源signal 用于釋放資源。操作必須是原子的否則多個進程同時修改信號量會產生競態(tài)。6.2 用信號量實現(xiàn)互斥與同步實現(xiàn)互斥時把互斥信號量初始化為 1。進程進入臨界區(qū)前執(zhí)行 wait離開臨界區(qū)后執(zhí)行 signal因此同一時刻最多只有一個進程通過。實現(xiàn)同步時把同步信號量初始化為 0。前驅進程完成任務后執(zhí)行 signal后繼進程執(zhí)行 wait由于初始值為 0后繼進程必須等前驅進程先釋放信號。前驅關系可以抽象為前一個操作末尾執(zhí)行 V后一個操作開頭執(zhí)行 P。分析題目時先找出“誰必須先完成”再把 V 放在前驅操作之后把 P 放在后繼操作之前。6.3 管程管程把共享數(shù)據(jù)、對數(shù)據(jù)操作的過程以及同步機制封裝在一起并保證同一時刻只有一個進程在管程內執(zhí)行某個內部過程。相比直接在業(yè)務代碼中分散使用信號量管程更容易集中維護互斥規(guī)則。七、死鎖及其處理7.1 死鎖與饑餓死鎖是并發(fā)進程相互等待對方占有的資源導致所有相關進程都無法繼續(xù)運行的狀態(tài)通常至少涉及兩個進程。饑餓是某個進程長期得不到所需資源或服務但系統(tǒng)中其他進程仍可能繼續(xù)運行。死鎖強調循環(huán)等待饑餓強調某個進程長期得不到機會。7.2 死鎖的四個必要條件互斥條件資源一次只能被一個進程占用。不剝奪條件資源未使用完之前不能被強行奪走。請求和保持條件進程已經保持部分資源又繼續(xù)請求其他資源。循環(huán)等待條件存在進程資源的循環(huán)等待鏈。四個條件同時成立死鎖才可能發(fā)生。因此預防死鎖的基本思路就是破壞其中至少一個條件。7.3 預防死鎖破壞互斥條件使用 SPOOLing 等技術把獨占設備改造成共享使用形式但并非所有資源都能這樣處理。破壞不剝奪條件當進程申請不到新資源時主動釋放已經占有的資源或允許系統(tǒng)剝奪部分資源。破壞請求和保持條件采用靜態(tài)分配讓進程運行前一次性申請全部資源。破壞循環(huán)等待條件規(guī)定資源的順序進程必須按編號遞增順序申請資源。預防方法通常會降低資源利用率或并發(fā)度所以實際系統(tǒng)還會結合避免和檢測方法。7.4 避免死鎖銀行家算法銀行家算法在每次資源分配前先假設分配發(fā)生再檢查系統(tǒng)能否找到一個安全序列。如果存在安全序列說明所有進程仍有可能依次完成可以進行分配如果進入不安全狀態(tài)則暫緩本次分配。安全狀態(tài)不等于當前沒有資源競爭而是表示系統(tǒng)仍存在一條讓所有進程完成的資源分配順序。做題時應先計算各進程的剩余需求再用當前可用資源逐步嘗試滿足某個進程釋放其資源后繼續(xù)尋找下一個進程。7.5 檢測與解除死鎖系統(tǒng)也可以先允許資源分配定期檢測是否形成死鎖。檢測到死鎖后常見解除方式包括資源剝奪從部分進程中奪取資源分配給其他進程。進程撤銷撤銷一個或多個進程并回收其資源。進程回退讓進程回退到足夠安全的檢查點再重新運行。選擇解除方式時需要綜合考慮進程優(yōu)先級、已完成工作量、回退代價和系統(tǒng)損失?？偨Y本章可以按一條鏈路理解進程通過 PCB 被操作系統(tǒng)管理線程提高程序的并發(fā)度調度算法決定處理機的分配順序進程通信解決數(shù)據(jù)交換同步互斥解決共享資源競爭信號量和管程提供協(xié)作工具當資源分配形成循環(huán)等待時就需要通過預防、避免或檢測解除死鎖。遇到具體題目時可以先判斷進程狀態(tài)和資源關系再選擇對應工具狀態(tài)變化看原語CPU 分配看調度算法共享資源看互斥與信號量資源互相等待看死鎖四條件和安全序列。參考資料王道操作系統(tǒng)第二章。