2.1 進程與線程
2.1.1 概念和特征
概念
- 進程：在多道程序環(huán)境下，并發(fā)執(zhí)行的多個程序失去封閉性，具有間斷性和不可再現(xiàn)性，因此引入進程來更好描述和控制程序的并發(fā)執(zhí)行，實現(xiàn)操作系統(tǒng)的并發(fā)和共享。
- 進程控制塊（Precess Control Block， PCB）描述進程的基本情況和運行狀態(tài)的數(shù)據(jù)結(jié)構(gòu)，進而控制和管理進程。
- 進程映像（進程實體）：程序段、數(shù)據(jù)段、PCB構(gòu)成。
- 創(chuàng)建進程的實質(zhì)是創(chuàng)建一個進程控制塊。
- vice versa，撤銷進程的實質(zhì)是撤銷進程的PCB。即，PCB是進程存在的唯一標(biāo)志。
- 進程映像是靜態(tài)的，進程是動態(tài)的
- 進程可以有如下幾種定義：
- 程序的一次執(zhí)行過程
- 程序及其數(shù)據(jù)在處理器順序執(zhí)行發(fā)生的活動
- 具有獨立功能的程序在數(shù)據(jù)集合上運行的過程，是系統(tǒng)機型資源分配和調(diào)度的獨立單位。
- 進程實體的運行過程，系統(tǒng)進行資源分配和調(diào)度的一個獨立單位
特征
- 動態(tài)性：最基本特征。進程有創(chuàng)建、活動、暫停、終止等過程，具有生命周期，是動態(tài)產(chǎn)生、變化和消亡的；
- 并發(fā)性：多個進程實體可以在內(nèi)存中同時存在并并發(fā)執(zhí)行
- 獨立性：進程實體是一個能獨立運行、獨立獲得資源和接受調(diào)度的基本單位
- 異步性：不同進程相互制約，使其具有運行時的間斷性，各自獨立，運行時間未定。
- 結(jié)構(gòu)性：進程實體由程序段、數(shù)據(jù)段、PCB共同組成。
2.1.2 進程的狀態(tài)和轉(zhuǎn)換
五種狀態(tài)，其中包括三種基本狀態(tài)。
- 運行狀態(tài)
- 就緒狀態(tài)
- 阻塞狀態(tài)（等待狀態(tài)）
- 創(chuàng)建狀態(tài)
- 結(jié)束狀態(tài)
就緒和等待的區(qū)別：就緒狀態(tài)獲得處理器資源立即執(zhí)行；等待狀態(tài)則還需要額外等待其他進程結(jié)束。
狀態(tài)的轉(zhuǎn)換：
- 就緒狀態(tài) → 運行狀態(tài)：獲得時間片，立即轉(zhuǎn)換
- 運行狀態(tài) → 就緒狀態(tài)：用完時間片，讓出資源
- 運行狀態(tài) → 等待狀態(tài)：進程請求其他資源，如系統(tǒng)調(diào)用時
- 等待狀態(tài) → 就緒狀態(tài)：進程等待的事件到來時，可以繼續(xù)
只有就緒和運行兩個狀態(tài)可以雙向。從等待狀態(tài)出來只能是就緒狀態(tài)。只有運行中才能再處于等待狀態(tài)（就緒狀態(tài)本就未在運行，無從等待）
2.1.3 進程控制
對系統(tǒng)中所有進程實施有效的管理，具有創(chuàng)建新進程、撤銷已有進程、實現(xiàn)進程狀態(tài)轉(zhuǎn)換等功能。進程控制程序是原語（原子化、不允許中斷）。
當(dāng)一個進程創(chuàng)建另一個，則創(chuàng)建者為父進程，被創(chuàng)建者為子進程。子進程可繼承父進程資源，撤銷時也需要歸還資源。撤銷父進程必須撤銷所有子進程。
進程的創(chuàng)建
- 分配PID，申請一個空白的PCB（PCB有限），申請失敗則創(chuàng)建失敗
- 分配資源（如數(shù)據(jù)、程序、用戶棧所需內(nèi)存空間），如失敗會進入等待狀態(tài)
- 初始化PCB，包括初始化標(biāo)志信息、處理器狀態(tài)信息、處理器控制信息、優(yōu)先級
- 如果進程就緒隊列可容納該新進程則進入就緒隊列等待調(diào)度執(zhí)行。
進程的終止
- 正常結(jié)束：完成并自行結(jié)束運行
- 異常結(jié)束：發(fā)生存儲區(qū)越界、非法指令、特權(quán)指令錯、IO故障等情況
終止進程會運行一系列撤銷原語：
- 根據(jù)進程標(biāo)識符檢索PCB，讀取進程狀態(tài)
- 若該進程處于執(zhí)行狀態(tài)，則立即終止，將處理器資源分配給其他進程
- 若該進程還有子進程，則全部終止
- 將該進程的全部資源歸還父進程或操作系統(tǒng)
- 將該PCB從所在隊列（PCB）中刪除
進程的阻塞和喚醒
若進程期待的某些事件未發(fā)生（請求資源失敗、等待其他操作完成），則系統(tǒng)主動執(zhí)行阻塞原語（Block）
- 找到將要被阻塞進程的標(biāo)識對應(yīng)的PCB
- 若該進程為運行狀態(tài)則保護現(xiàn)場，改為阻塞狀態(tài)并停止運行
- 將該PCB插入當(dāng)相應(yīng)事件的等待隊列中。
而反之，喚醒原語（Wakeup）的執(zhí)行順序為：
- 在事件的等待隊列中尋找相應(yīng)PCB
- 將其從等待隊列中移除，設(shè)置為就緒狀態(tài)
- 將此PCB插入就緒隊列中，等待調(diào)度。
Block和Wakeup原語作用恰好相反，因此需要成對使用。
- Block原語是由被阻塞進程自我調(diào)用實現(xiàn)的
- Wakeup原語是有一個與被喚醒進程相關(guān)的進程調(diào)用實現(xiàn)的。
進程切換
進程切換與前三項一樣都是通過內(nèi)核實現(xiàn)的。具體步驟如下：
- 保存處理器上下文，包括程序計數(shù)器和其他寄存器內(nèi)容
- 更新PCB信息
- 將進程PCB移入相應(yīng)隊列，如就緒、阻塞等。
- 選擇另一個進程執(zhí)行，并更新其PCB
- 更新內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)
- 恢復(fù)處理器上下文
進程切換不同于處理器模式切換。
- 模式切換時處理器邏輯上可能還在同一個進程中運行，如果進程進入核心態(tài)運行后回到用戶態(tài)，操作系統(tǒng)只需要恢復(fù)進入內(nèi)核前保存的現(xiàn)場，當(dāng)前進程的環(huán)境信息不必改變。
- 切換進程時，由于發(fā)生了進程的改變，當(dāng)前進程的環(huán)境信息需要改變。
2.1.4 進程的組織
進程時操作系統(tǒng)的資源分配和獨立運行的基本單位，一般有以下三個部分組成：進程控制塊、程序段和資源。
PCB
創(chuàng)建進程時就會新建一個空白PCB，之后就會常駐內(nèi)存并可在任意時間進行存取，并在程序結(jié)束后刪除。PCB是進程實體的一部分，是進程存在的唯一標(biāo)志。
操作系統(tǒng)通過PCB表來管理和控制進程。
- 進程描述信息
- PID、UID
- 進程控制和管理信息
- 當(dāng)前狀態(tài)、優(yōu)先級、代碼入口地址、程序外存地址、進入內(nèi)存時間、占用時間、信號量使用
- 資源分配清單
- 代碼段指針、數(shù)據(jù)段指針、堆棧段指針、文件描述符、IO設(shè)備
- 處理器相關(guān)信息
- 通用寄存器值、地址寄存器值、控制寄存器值、標(biāo)志寄存器值、程序狀態(tài)字
程序段
程序段就是能被進程調(diào)度程序調(diào)度到CPU執(zhí)行的程序代碼段。程序段可以被多個程序共享：多個進程可以運行同一個程序。
數(shù)據(jù)段
進程對應(yīng)的程序處理的原始數(shù)據(jù)或中間和最終結(jié)果。
2.1.5 進程的通信
1. 共享存儲
進程間存在一塊可以直接訪問的共享空間，榮國這篇共享空間進行信息交換，在對共享空間進行讀寫操作時，需要使用同步互斥工具（P操作、V操作）進行控制。
用戶進程空間一般是獨立的，進程運行期間一般不能訪問其他進程的空間，除非使用特殊的系統(tǒng)調(diào)用。而進程內(nèi)的線程可以共享進程空間。
- P操作：
- ① 將信號量S的值減1，即S=S-1；
- ② 如果S>=0，則該進程繼續(xù)執(zhí)行；否則該進程置為等待狀態(tài)，排入等待隊列。
- V操作：
- ①將信號量S的值加1，即S=S+1；
- ②如果S>0，則該進程繼續(xù)執(zhí)行；否則釋放隊列中第一個等待信號量的進程。
2.消息傳遞
消息傳遞系統(tǒng)中，進程間數(shù)據(jù)交換是以格式化的消息為單位的。通過發(fā)送原語和接受原語進行數(shù)據(jù)交換
- 直接通信方式：發(fā)送進程直接將消息發(fā)送給接受進程，并將其掛在接收進程的消息緩沖隊列熵，接收進程從該隊列取得消息。
- 間接通信方式：發(fā)送進程將消息發(fā)送到某個中間實體（一般稱為信箱），接收進程從該中間實體取得消息。（計算機網(wǎng)絡(luò)中稱為電子郵件系統(tǒng)）
3.管道通信
“管道”就是用于鏈接一個讀進程和一個寫進程來實現(xiàn)其通信的一個共享文件，又名Pipe文件。相關(guān)到提供輸入的發(fā)送進程以字符流形式將數(shù)據(jù)送入寫管道，接受管道輸出端的接收進程則從中讀取數(shù)據(jù)。為協(xié)調(diào)雙方通信，管道機制必須提供以下三方面的協(xié)調(diào)能力：
- 互斥
- 同步
- 確定對方存在
無名管道：半雙工，只能用于親緣關(guān)系的進程之間
有名管道：半雙工，允許無親緣關(guān)系的進程之間。
其他
- 套接字（Socket）通信：可用于不同進程的通信
- 信號量（Semaphore）：主要用于實現(xiàn)進程間互斥和同步
2.1.6 線程概念、多線程模型
線程的概念
- 線程的組成：線程ID、程序計數(shù)器、寄存器集合、堆棧
- 線程的狀態(tài)：就緒、運行、阻塞
- 線程的概念：線程是進程中的一個實體，是被系統(tǒng)獨立調(diào)度和分配的基本單位，其自身不擁有系統(tǒng)資源，但可以與同一個進程之間的線程共享資源。線程之間互相制約，可并發(fā)運行，可相互撤銷
線程和進程
- 調(diào)度：線程是獨立調(diào)度的基本單位，進程是擁有資源的基本單位。
- 擁有資源：線程不擁有系統(tǒng)資源，但具有維持運行的一些資源，但可以通過訪問其他線程的資源。
- 并發(fā)性：都可以并發(fā)運行。
- 系統(tǒng)開銷：線程在創(chuàng)建和撤銷時需要分配或回收資源，且切換時也需要大量開銷保存現(xiàn)場。而線程切換時只需要保存少量寄存器內(nèi)容，開銷較小。
- 地址空間和其他資源：進程的地址空間和其他資源之間相互獨立，而一個進程之間多個線程之間可以共享以上內(nèi)容。
線程的屬性
- 輕型實體，不擁有系統(tǒng)資源，但都應(yīng)具備標(biāo)識符和線程控制塊TCB
- 不同線程可以執(zhí)行相同程序
- 容易進程的不同線程共享資源
- 線程是處理器獨立調(diào)度的最小單位，多個線程可以并發(fā)執(zhí)行。
- 線程同樣在創(chuàng)建后開始生命周期，具有就緒、運行、阻塞態(tài)。
線程的實現(xiàn)方式
- 用戶級線程（ULT，User-level thread），應(yīng)用程序執(zhí)行線程管理
- 內(nèi)核級線程（KLT，Kernel-level thread），內(nèi)核執(zhí)行線程管理
- 組合方式，二者兼有
多線程模型
- 多對一：多個用戶級線程映射到一個內(nèi)核級線程，在用戶空間進行管理
- 效率較高，但內(nèi)核中有一個線程阻塞則全部進程阻塞，多線程不能并行運行在多處理器上
- 一對一：每個用戶級線程映射到一個內(nèi)核級線程
- 一個線程被阻塞后可以繼續(xù)其他線程執(zhí)行，并發(fā)能力較強。線程但創(chuàng)建開銷較大
- 多對多：n個用戶及線程映射到m個內(nèi)核級線程，m<=n
- 二者折中。
2.2 處理器調(diào)度
2.2.1 調(diào)度的概念
基本概念
進程之間往往會存在資源競爭，因此，從就緒隊列中，按照一定算法選擇繼承并分配處理器給其運行來實現(xiàn)進程的并發(fā)執(zhí)行就是處理器調(diào)度。
處理器調(diào)度是多道程序操作系統(tǒng)的基礎(chǔ)，是操作系統(tǒng)設(shè)計的核心。
調(diào)度的層次
作業(yè)從提交到完成需要三級調(diào)度：
- 作業(yè)調(diào)度：又稱高級調(diào)度，按一定原則從外存上出獄后被狀態(tài)的作業(yè)中挑選一個或多個，給其分配內(nèi)存、IO設(shè)備等，并建立相應(yīng)進程，使其獲得競爭處理器的權(quán)利：內(nèi)存與外存之間的調(diào)度。對于每個作業(yè)，只調(diào)入一次、調(diào)出一次。
- 內(nèi)存調(diào)度：又稱中級調(diào)度，將暫時不運行的進程放入外存等待，此時的進程為掛起狀態(tài)。再將外存其他具備條件的就緒進程調(diào)入內(nèi)存，掛在就緒隊列上等待。是為了提高內(nèi)存利用率和系統(tǒng)吞吐量
- 進程調(diào)度：又稱低級調(diào)度，按照算法從就緒隊列選取進程并分配處理器。是操作系統(tǒng)中被基本的一種調(diào)度，在操作系統(tǒng)中都必須具備。頻率很高，幾十毫秒一次。
三級調(diào)度的聯(lián)系
- 作業(yè)調(diào)度為進程活動做準(zhǔn)備，進程調(diào)度使進程正?；顒樱屑壵{(diào)度將暫時不用的進程掛起。
- 越低級的調(diào)度頻率越高
- 進程調(diào)度在操作系統(tǒng)中不可或缺
2.2.2 調(diào)度的時機、切換、過程
不會進行進程調(diào)度和切換的情況：
- 處理中斷：并不發(fā)生進程切換，因此不應(yīng)被剝奪處理器資源
- 進程處于內(nèi)核程序的臨界區(qū)：進入臨界段需要獨占訪問數(shù)據(jù)，需要加鎖來防止其他并行程序進入。
- 其他屏蔽中斷的原子操作（加鎖、解鎖、現(xiàn)場保護和恢復(fù)）同樣不能中斷，因而不會發(fā)生進程的切換。
應(yīng)該進行進程調(diào)度和切換的情況：
- 發(fā)生引起調(diào)度的條件且當(dāng)前進程無法繼續(xù)運行下去
- 中斷處理結(jié)束或自陷處理結(jié)束返回執(zhí)行現(xiàn)場前，可以馬上進行調(diào)度和切換（剝奪方式的調(diào)度）
2.2.3 進程調(diào)度方式
- 非剝奪調(diào)度：非搶占方式。當(dāng)前進程完成或等待時才進入其他進程，實現(xiàn)簡單且開銷小
- 剝奪調(diào)度：搶占方式，一個進程執(zhí)行時若有另一個更重要的需要使用處理器則立即暫停當(dāng)前進程。提高了系統(tǒng)吞吐率和效率，用在實時操作系統(tǒng)中。
2.2.4 調(diào)度的基本準(zhǔn)則
選擇調(diào)度算法的準(zhǔn)則：
- CPU利用率
- 系統(tǒng)吞吐量：單位時間CPU完成作業(yè)量
- 周轉(zhuǎn)時間：作業(yè)從提交到完成的時間，帶權(quán)周轉(zhuǎn)時間：周轉(zhuǎn)時間/實際運行時間
- 等待時間：進程處于等待狀態(tài)時間之和
- 響應(yīng)時間：從提交請求到首次產(chǎn)生響應(yīng)的時間
2.2.5 典型調(diào)度算法
1. 先來先服務(wù)（FCFS，F(xiàn)irst come first service）
非剝奪算法。簡單但效率低
2. 短作業(yè)優(yōu)先（SJF，Short job first）
對長作業(yè)不利：饑餓現(xiàn)象（Starvation）
非剝奪算法。最短的平均等待時間和平均周轉(zhuǎn)時間
3. 優(yōu)先級調(diào)度
可用于作業(yè)調(diào)度、進程調(diào)度。
按是否搶占分為：
- 非剝奪優(yōu)先級調(diào)度
- 剝奪優(yōu)先級調(diào)度
按優(yōu)先級是否可以改變分為：
- 靜態(tài)優(yōu)先級
- 動態(tài)優(yōu)先級
4. 高響應(yīng)比優(yōu)先級調(diào)度算法
主要用于作業(yè)調(diào)度。通過響應(yīng)比平衡了FCFS和SJF調(diào)度算法
響應(yīng)比 = (等待時間+要求服務(wù)時間)/要求服務(wù)時間
長作業(yè)的等待時間長，從而獲得高響應(yīng)比避免饑餓；
等待時間相同，則要求服務(wù)時間短的響應(yīng)比高，實現(xiàn)短作業(yè)優(yōu)先；
要求服務(wù)時間相同，則等待時間長的響應(yīng)比高，實現(xiàn)先來先服務(wù)。
5. 時間片輪轉(zhuǎn)調(diào)度算法
主要用于分時系統(tǒng)，將所有就緒進程按到達(dá)先后排為隊列，總是選擇第一個執(zhí)行（FCFS），但在一個時間片后必須被剝奪而處理下一個就緒的進程。被剝奪的進程則被放到隊列末尾。
時間片過長，則退化為FCFS；過短則進程切換開銷過大。由系統(tǒng)響應(yīng)時間、就緒隊列中的進程數(shù)和系統(tǒng)處理能力確定。
6. 多級反饋隊列調(diào)度算法
時間片輪轉(zhuǎn)和優(yōu)先級調(diào)度算法的綜合和發(fā)展。
- 設(shè)置多個就緒隊列，給這些隊列賦予不同優(yōu)先級，1級最高
- 賦予各隊列進程的時間片大小各不相同
- 每當(dāng)存在新進程，進入隊列1，若在一個時間片中未完成，則放入隊列2，以此類推，最終在隊列n按時間片輪轉(zhuǎn)調(diào)度
- 僅前面所有隊列為空，才調(diào)度下一級隊列的進程，
2.3 進程同步
2.3.1 基本概念
進程之間存在相互制約的關(guān)系。為了協(xié)調(diào)制約關(guān)系，需要進行進程同步。
1.臨界資源
臨界資源是一次僅允許一個進程使用的資源。如物理設(shè)備、某些變量和數(shù)據(jù)。
臨界資源必須互斥訪問。訪問臨界資源的代碼段稱為臨界區(qū)或臨界段
臨界資源的訪問過程：
- 進入?yún)^(qū)：檢查是否可以進入臨界區(qū)
- 臨界區(qū)：進程中訪問臨界資源的代碼
- 退出區(qū)：將正在訪問臨界區(qū)的標(biāo)志清除
- 剩余區(qū)：代碼中的剩余部分
while(true){
entry section;
critical section;
exit section;
remainder section;
}
2.同步
同步又稱直接制約關(guān)系，是指未完成某種任務(wù)而建立的兩個或多個進程由于需要在某些位置上協(xié)調(diào)工作秩序而等待、傳遞信息所產(chǎn)生的制約關(guān)系。
例如：進程A通過單緩沖，向進程B提供數(shù)據(jù)。當(dāng)該緩沖區(qū)空時，B取不到則阻塞；反之，緩沖區(qū)滿時，A寫不入則阻塞。
3. 互斥
互斥又稱間接制約關(guān)系：一個進程進入臨界段時，另一個進程必須等待直至使用臨界資源的進程退出臨界區(qū)，才能訪問臨界資源。、
例如：僅有一臺打印機的系統(tǒng)中，A在打印時B只能先阻塞直到打印機釋放。
為禁止兩個進程同時進入臨界區(qū)，同步機制的準(zhǔn)側(cè)有：
- 空閑讓進：臨界區(qū)空閑時，允許任意請求
- 忙則等待：已有臨界區(qū)進程時，其他等待
- 有限等待：保證請求訪問的進程在有限時間內(nèi)進入臨界區(qū)
- 讓權(quán)等待：不能進入臨界區(qū)時立即釋放處理器，防止忙等待（反復(fù)檢查）
2.3.2 實現(xiàn)臨界區(qū)互斥的基本方法
1.軟件實現(xiàn)方法
-
單標(biāo)志法：設(shè)置一個公用整形變量turn用于指示被用于進入臨界區(qū)的進程編號。僅僅在進入?yún)^(qū)進行檢查而不鎖定。但是必須多個進程交替進入臨界區(qū)，否則會卡?。ㄟ`背空閑讓進原則）：如P0執(zhí)行完畢后turn改為1，但P1并無進入臨界區(qū)的打算，則此時turn一直不變，其他進程一直等待。
//Process0: while(turn != 0){} //進入 ciritical section; //臨界 turn = 1; //退出 remainder section; //剩余 //Process1: while(turn != 1){} critical section; turn = 0; remainder section; -
雙標(biāo)志先檢查：在每個進程訪問臨界區(qū)資源之前，查看臨界資源是否正被訪問。數(shù)據(jù)
flag[i]為true表示第i個進程進入臨界區(qū)，否則未進入。解決了單標(biāo)志法必須教體進入的問題，但是由于檢查和修改不能同時進行，在檢查對方flag和改變自己flag之間會出現(xiàn)兩個進程同時進入臨界區(qū)的情況，違背了忙則等待。//Process i: while(flag[j]){} //進入 flag[i] = true; critical section; //臨界 flag[i] = false; //退出 remainder section; //剩余 //Process j: while(flag[i]){} flag[j] = true; critical section; flag[j] = false; remainder section; -
雙標(biāo)志后檢查：在進入?yún)^(qū)先設(shè)置自己的狀態(tài)，再判斷對方的狀態(tài)，即將先檢查的進入?yún)^(qū)代碼交換。容易在同時運行第一行后使得二者flag都為True，造成饑餓狀態(tài)。違背了有限等待和空則讓進即：先檢查則搶入，后檢查則謙讓。
//Process i: flag[i] = true; //進入 while(flag[j]){} critical section; //臨界 flag[i] = false; //退出 remainder section; //剩余 //Process j: flag[j] = true; while(flag[i]){} critical section; flag[j] = false; remainder section; -
Peterson's Algorithm：防止雙標(biāo)志先檢查的同時進入臨界區(qū)和后檢查的饑餓現(xiàn)象，該算法設(shè)置了變量turn，每個進程在先設(shè)置自己的標(biāo)志后再設(shè)置turn標(biāo)志，再同時檢測另一個進程的狀態(tài)標(biāo)志和不允許進入標(biāo)志，保證只有一個進入臨界區(qū)。flag表示是否想進，可以有多個true，而turn表示唯一進入的。表示自己想進后將進入讓給另一個，如果另一個不想進則直接進，如果另一個也想進則進，當(dāng)前這個進入檢查循環(huán)。
//Process i: flag[i] = true; //進入?yún)^(qū) turn = j; while(flag[j] && turn == j); //缺一則直接往下 critical section; //臨界區(qū) flag[i] = false; //退出區(qū) remainder section; //剩余區(qū) //Process j: flag[j] = true; turn = i; while(flag[i] && turn == i); critical section; flag[j] = false; remainder section;
2.硬件實現(xiàn)方法
-
中斷屏蔽：在有進程訪問臨界段時，禁止一切中斷的發(fā)生。由于限制了處理器交替執(zhí)行程序的能力，會降低程序執(zhí)行效率。
... 關(guān)中斷 臨界區(qū) 開中斷 ... 硬件指令方法
-
TestAndSet指令：是一個原子操作，執(zhí)行該代碼時不允許被中斷。功能是讀出指定標(biāo)志后將其設(shè)置為真。
可以為每個臨界資源設(shè)置共享的變量lock來表示是否被占用。每當(dāng)進程在訪問臨界資源之前都需要運行TestAndSet檢查和修改標(biāo)志lock，若有進程正在占用則重復(fù)檢查直至解除占用，該部分代碼為：bool TestAndSet(bool* lock){ bool old = *lock; *lock = true; return old; }while(TestAndSet(&lock)); critical section; lock = false;
-
TestAndSet指令：是一個原子操作，執(zhí)行該代碼時不允許被中斷。功能是讀出指定標(biāo)志后將其設(shè)置為真。
-
Swap指令：交換兩個字或字節(jié)的內(nèi)容。
為每個臨界資源設(shè)置共享布爾變量void swap(bool* a, bool* b){ bool temp = *a; *a = *b; *b = temp; }lock，初值為false，再設(shè)置一個局部變量key用于和lock交換信息，當(dāng)進入臨界區(qū)前首先使用swap交換lock和key的內(nèi)容并檢查key的狀態(tài)，當(dāng)進程在臨界區(qū)時重復(fù)交換和檢查直至不再占用。利用swap實現(xiàn)進程互斥的算法如下：key = true; while(key == false){ swap(&lock, &key); } critical section; lcok = false;
-
Swap指令：交換兩個字或字節(jié)的內(nèi)容。
硬件方法的優(yōu)點：適用于任意數(shù)目的進程，支持多個臨界區(qū)或一到多個處理器，僅需為每個臨界區(qū)設(shè)置一個布爾變量；簡單且容易驗證。
硬件方法的缺點：等待進入臨界區(qū)需要耗費處理器時間，不能實現(xiàn)讓權(quán)等待。從等待進程中隨機選擇進入臨界區(qū)，可能造成饑餓現(xiàn)象。
2.3.3 信號量Semaphore
信號量可以解決互斥和同步的問題，只能被兩個標(biāo)準(zhǔn)的原語wait(s)以及signal(S)訪問，記作P操作和V操作。
1.整型信號量
整型信號量用于表示資源數(shù)目，wait和signal操作可描述為：
wait(S){
while(s<=0);
S = S-1;
}
signal(S){
S = S+1;
}
只要信號量小于等于0則不斷測試，因此不遵循“讓權(quán)等待”，而是出于“忙等”狀態(tài)。
2.記錄型信號量
除了整數(shù)變量value外再增加一個進程鏈表L來鏈接所有等待該資源的進程。
//信號量實現(xiàn)方式
typedef struct{
int value;
struct process *L;
} semaphore;
//P和V操作
void wait(semaphore S){
--S.value;
if(S.value<0){
/* add this process to S.L; */
block(S.L);
}
}
void signal(semaphore S){
++S.value;
if(S.value<=0){
/* remove process P from S.L; */
wakeup(P);
}
}
wait中減少value表示進程請求一個此類資源，value小于0則表示該類資源分配完畢，應(yīng)該調(diào)用block原語進行阻塞，放棄處理器并將該進程插入到等待隊列S.L中，實現(xiàn)了“讓權(quán)等待”。
signal表示釋放資源，使系統(tǒng)中可供分配的該類資源數(shù)目+1，若增加后仍然非正，則表示還有等待該資源的進程在S.L中，因此需要調(diào)用wakeup原語將鏈表中第一個的進程P喚醒。
3.利用信號量實現(xiàn)同步
設(shè)信號量初值為0
P操作為Passeren，即通過；V操作為vrijgeven，即釋放。二者成對出現(xiàn)，與wait-signal等價。P減V加，wait減signal加。
semaphore S = 0;
//單純P2等待P1的情況
P1(){
...
x;
V(S); //用信號量表示x已經(jīng)運行完畢
...
}
P2{
...
P(S); //檢查P1是否運行完x，未完成則P2處于阻塞隊列，否則移入就緒隊列
y;
...
}
4.利用信號量實現(xiàn)進程互斥
設(shè)信號量初始值為1（可用資源數(shù)為1）
semaphore S = 1;
P1(){
...
P(S);
ciritical section of P1;
V(S);
...
}
P2(){
...
P(S);
critical section of P2;
V(S);
...
}
信號量與同步互斥的總結(jié)
- 同步問題中，若某個行為需要使用資源，則在那個行為之前先P一下；若某個行為會提供某個資源，則在那個行為之后V一下
- 互斥問題中，需要將臨界段加入P和V之間，中間不能有冗余代碼。
5.利用信號量實現(xiàn)前驅(qū)關(guān)系
為保證按照某個圖的執(zhí)行順序進行程序執(zhí)行，可以將信號量設(shè)為0，并按照同步的方法，前一個V->后一個P逐個向后。
注意：有幾個兩兩之間的進程傳遞關(guān)系則創(chuàng)建幾個信號量，且P和V需要成對出現(xiàn)。
semaphore s12=s13=s24=s25=s36=s46=s56=0;
S1(){
...
V(s12); //V通S2
V(s13); //V通S3
}
S2(){
P(s12); //P檢查S1
...
V(s24);
V(s25);
}
S3(){
P(s13);
...
V(s36);
}
S4(){
P(s24);
...
V(s46);
}
S5(){
P(s25);
...
V(s56);
}
S6(){
P(s36);
P(s46);
P(s56);
...
}
6.分析進程同步和互斥問題的方法步驟
- 關(guān)系分析：進程數(shù)、同步和互斥關(guān)系
- 整理
- 設(shè)置信號量
2.3.4 管程monitor
1. 管程定義
系統(tǒng)中的硬軟件資源都可以使用數(shù)據(jù)結(jié)構(gòu)抽象描述而忽略實現(xiàn)細(xì)節(jié)。管程則是由一組數(shù)據(jù)以及定義在這組數(shù)據(jù)之上的對這組數(shù)據(jù)的操作組成的軟件模塊：這組操作初始化并改變管程中的數(shù)據(jù)和同步進程。
2. 管程組成
- 局部于管程的共享結(jié)構(gòu)數(shù)據(jù)說明
- 對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程
- 對局部與管程的共享數(shù)據(jù)設(shè)置初始值的語句
管程實質(zhì)上是一個抽象類，其中有多個成員變量，系統(tǒng)中任何設(shè)備都可以通過這幾個成員變量區(qū)分和描述；管程中還有對這些成員變量操作的一組成員函數(shù)。
2.3.5 經(jīng)典同步問題
1.生產(chǎn)者-消費者問題
生產(chǎn)者和消費者進程共享一個初值為空、大小為n的緩沖區(qū)。
只有緩沖區(qū)未滿時，生產(chǎn)者將消息放入緩沖區(qū)，否則等待；
只有緩沖區(qū)非空時，消費者才能從中取出消息，否則等待。
semaphore muted = 1; //臨界區(qū)互斥量
semaphore empty = n; //空閑緩沖區(qū)
semaphore full = 0; //緩沖區(qū)初始化為空
producer(){
while(1){
produce an item in nextp;
P(empty); //P一下empty，獲取空緩沖單元
P(mutex); //進入臨界區(qū)
add nextp to buffer; //數(shù)據(jù)入緩沖區(qū)
V(mutex); //離開臨界區(qū)，釋放互斥量
V(full); //滿緩沖區(qū)信號量+1
}
}
consumer(){
while(1){
P(full); //獲取滿緩沖區(qū)單元
P(mutex); //進入臨界區(qū)
remove an item from buffer; //取走數(shù)據(jù)
V(mutex); //離開臨界區(qū)，釋放互斥量
V(empty); //空緩沖區(qū)信號量+1
consume the item； //消費數(shù)據(jù)
}
}
empty為n，表示如果多次運行producer，在P了n次empty之后保證進入等待。
full為0，表示一開始運行consumer一定會處于等待，直到運行producer直到V到了這個full。
mutex為1，即標(biāo)準(zhǔn)的互斥信號量，保證只有一個程序進入臨界段。
- 示例：父母子女，蘋果橘子
該問題的特點：盤子只有一個，則寫入不必獨占，因此不必加入進入臨界的互斥量。semaphore plate=1, apple=0, orange=0; dad(){ while(1){ prepare an apple; P(plate); put apple in plate; V(apple); } } mom(){ while(1){ prepare an orange; P(plate); put orange in plate; V(orange); } } son(){ while(1){ P(apple); pick apple from plate; V(plate); eat apple; } } daughter(){ while(1){ P(orange); pick orange form plate; V(plate); eat orange; } }
2. 讀者-寫者問題
讀者和寫者共享一個文件，允許兩個以上的讀進程訪問共享數(shù)據(jù)，但不允許某個寫進程和其它任何進程同時訪問共享數(shù)據(jù)，也就是獨占寫、共享讀。
int count = 0; //記錄讀者量
semaphore mutex = 1; //保護更新count時處于互斥
semaphore rw = 1; //保證讀者和寫者互斥
writer(){
while(1){
P(rw); //阻止讀
writing;
V(rw); //允許讀
}
}
reader(){
while(1){
P(mutex); //保證獨占寫count
if(count == 0) //當(dāng)?shù)谝粋€讀進程開始讀就要
P(rw); //阻止寫
++count;
V(mutex); //釋放count
reading;
P(mutex); //獨占count
--count; //讀完后讀者數(shù)-1
if(count == 0) //確保想讀的全部讀完才讓寫
V(rw); //允許寫
V(mutex); //釋放count
}
}
mutex保證讀者和讀者之間的count被獨占修改（寫者只對是否寫入負(fù)責(zé)），因此count的變動和檢查都需要P一下mutex，完成后V。
只要有一個讀進程運行，寫進程則一直處于循環(huán)等待狀態(tài)，因此只要有一個讀，就不能寫，容易導(dǎo)致寫進程餓死。
一種改進是寫進程優(yōu)先：只要有寫進程運行就讓給寫進程，則需要在甲一組信號量w用于實現(xiàn)。
int count=0;
semaphore mutex=1;
semaphore rw=1;
semaphore w=1;
writer(){
while(1){
P(w);
P(rw);
writing;
V(rw);
V(w);
}
}
reader(){
while(1){
P(w); //其他讀進程在寫時等待
P(mutex);
if(count == 0)
P(rw);
++count;
V(mutex);
V(w); //一個讀進程開始時立即釋放，保證寫進程可以進入
reading;
P(mutex);
--count;
if(count==0)
V(rw);
V(mutex);
}
}
寫進程并非完全優(yōu)先，因此更準(zhǔn)確稱為讀寫公平法。
3. 哲學(xué)家進餐問題
兩個哲學(xué)家之間放著一個筷子，當(dāng)需要進餐時，需要拿起左右兩根才能開始，否則等待。
假設(shè)問題中有五個哲學(xué)家：
semaphore chopstick[5] = {1,1,1,1,1}; //互斥量
process(){
do{
P(chopstick[i]); //取左邊
P(chopstick[(i+1)%5]); //取右邊
eat;
V(chopstick[i]);
V(chopstick[(i+1)%5]);
think;
}whilel(1);
}
問題在于，如果同時發(fā)生取左邊筷子的情況，則所有人都只拿到左邊而不放回，產(chǎn)生死鎖，因此一種解決方式為：
對哲學(xué)家也進行編號，奇數(shù)哲學(xué)家拿走左邊筷子，偶數(shù)哲學(xué)家拿走右邊筷子。
-
或者：直接將拿走兩個筷子的行為設(shè)為獨占，每次只允許一個哲學(xué)家同時拿走左邊和右邊兩個筷子：
semaphore chopstick[5] = {1,1,1,1,1}; semaphore mutex = 1; //互斥為1，保證獨占拿走 process(){ while(1){ P(mutex); P(chopstick[i]); P(chopsitck[(i+1)%5]); V(mutex); eat; V(chopstick[i]); V(chopstick[(i+1)%5]); think; } }
不同于貪心算法，解決該類問題必須考慮下一步更下一步的后果。
4. 吸煙者問題
供應(yīng)者不斷提供抽煙者所需的三種材料，三個抽煙者分別擁有其中的一種材料。每個吸煙者需要同時獲得三種才能吸煙；但供應(yīng)者每次只放兩種材料在桌上。當(dāng)擁有某種材料的吸煙者完成抽煙給供應(yīng)者一個信號，則供應(yīng)者提供給另外兩個吸煙者的材料搭配。
int random;
semaphore offerBC = 0; //組合B&C，供A抽煙
semaphore offerAC = 0; //組合A&C，供B抽煙
semaphore offerAB = 0; //組合A&B，供C抽煙
process Producer(){
while(1){
random = rand()%3;
if(random==0)
V(offerBC);
else if(random==1)
V(offerAC);
else
V(offerAB);
P(finish); //等待抽煙完成
}
}
process PA(){
while(1){
P(offerBC);
smoke;
V(finish);
}
}
process PB(){
while(1){
P(offerAC);
smoke;
V(finish);
}
}
process PC(){
while(1){
P(offerAB);
smoke;
V(finish);
}
}
2.4 死鎖
2.4.1 概念
1. 定義
多個進程因競爭資源而造成的互相等待，若無外力作用則這些進程都無法向前推進。
2. 產(chǎn)生原因
- 系統(tǒng)資源的競爭（不可剝奪的資源的競爭）
- 進程推進順序非法（循環(huán)等待）
- 四個必要條件：
- 互斥：一段時間內(nèi)某資源僅被一個進程占有
- 非剝奪：進程未完成時，資源不會被其他進程奪走（只能主動釋放）
- 請求和保持：進程已經(jīng)請求并保持到了一個資源，但需要繼續(xù)請求其他被占有的資源
- 循環(huán)等待：存在循環(huán)等待鏈
2.4.2 死鎖處理
- 死鎖預(yù)防：限制某些限制條件破壞四個必要條件之一。
- 死鎖避免：分配資源時防止系統(tǒng)進入不安全狀態(tài)。
- 死鎖檢測和解除：允許發(fā)生死鎖，但是可以檢測到并解除之。
對比
2.4.3 死鎖預(yù)防
- 破壞互斥條件：由于大多數(shù)資源只能獨占訪問，破壞互斥不太可行。
- 破壞不剝奪條件：使已經(jīng)保持了某個資源的進程在無法取得新的資源時釋放已有的資源。實現(xiàn)比較復(fù)雜，系統(tǒng)開銷大，適用于易保存和恢復(fù)的資源，如CPU寄存器、內(nèi)存資源
- 破壞請求和保持條件：預(yù)先采用靜態(tài)分配方法，在運行前一次申請所有所需資源，未成功則等待，取得后一直獨占且不提出其他請求。實現(xiàn)簡單，但浪費系統(tǒng)資源，易導(dǎo)致其他進程饑餓。
- 破壞循環(huán)等待條件：采用順序資源分配法，為資源編號，規(guī)定每個進程必須按照編號順序請求資源且一次申請完同類資源。（申請Ri后只能申請標(biāo)號大于i的其他資源）。要求編號穩(wěn)定，因而限制了新設(shè)備的增加開銷。
2.4.4 死鎖避免
死鎖避免也是事先預(yù)防，但不會實現(xiàn)采取限制，而是在資源動態(tài)分配時防止系統(tǒng)進入不安全狀態(tài)。限制條件比死鎖預(yù)防弱。
1.安全狀態(tài)
安全狀態(tài)指系統(tǒng)可以按某種順序推進程序，為每個進程分配所需資源直到滿足每個進程的最大需求，每個進程都可以按順序完成。此時稱進程序列P1，P2...Pn為安全序列。如沒有安全序列，則系統(tǒng)不安全。（不安全未必死鎖，但安全一定不死鎖）
2.銀行家算法
把操作系統(tǒng)看作銀行家，資源為所管理的資金，請求資源相當(dāng)于貸款。每次請求資源需要測試想最大需求量，若現(xiàn)存資源可以滿足則分配，否則推遲分配。
-
數(shù)據(jù)結(jié)構(gòu)：（假設(shè)m類資源，n個進程）
- 可利用資源矢量Available：含有m個元素的數(shù)組，Available[k]代表資源k的可用數(shù)目
- 最大矩陣需求Max：nxm矩陣，定義了系統(tǒng)中每類資源分配給各進程對m類資源的最大需求，Max[i,j]代表進程i對資源j的最大需求。
- 分配矩陣Allocation：和Max同型，用來表示當(dāng)前分配給各進程的各類資源數(shù)目。
-
需求矩陣Need：和Max同型，用來表示各進程還需要的各類資源需求數(shù)目。易得
Need=Max-Allocation
-
算法描述
每個進程都可以發(fā)送請求矢量Request_i，表示對每類資源的需求量。如
Request_i[j] = KRequest_i[j] <= Need[i, j]：進入下一步，否則錯誤：需求超過應(yīng)需求量。Request_i[j] <= Available[j]：進入下一步，否則等待：系統(tǒng)沒有足夠資源。-
系統(tǒng)嘗試分配資源給進程
P_i，并更新以下數(shù)值：Avaliable = Available - Request_i; Allocation[i, j] = Allocation[i, j] + Request_i[j]; Need[i, j] = Need[i, j] - Request_i[j]; 系統(tǒng)執(zhí)行安全性算法，檢測系統(tǒng)在該次分配后是否出于安全狀態(tài)，否則將本次嘗試作廢，并讓Pi等待。
-
安全性算法
- ① 初始狀態(tài)：安全序列為空
- ② 從Need中找出
對應(yīng)進程不在安全序列 && 該行小于等于Available的行，并將該行對應(yīng)進程Pi加入安全序列，找不到則進入④ - ③ Pi進入安全序列后就可以執(zhí)行直到完成，并釋放出所分配的資源，執(zhí)行：
Available = Available + Allocation[i];返回② - ④ 如果安全序列中有所有進程，則系統(tǒng)處于安全狀態(tài)，否則不安全。
2.4.5 死鎖檢測和解除
該算法最為寬松，在分配資源時不采取任何措施，但可以在運行時檢測并解除死鎖。
1.資源分配圖
系統(tǒng)死鎖可以使用資源分配圖描述。圓圈代表一個進程，框代表一類資源，框中的一個點表示一類中的一個資源，從資源到進程的邊稱為分配邊，表示該資源已經(jīng)有一個資源被分配給了此進程。
2.死鎖定理
- 在資源分配圖中，找出既不阻塞又不是孤點的進程Pi（有一條有向邊與其相連，且該有向邊對應(yīng)的資源申請數(shù)小于等于已有的空閑資源），若所有連接該進程的邊都滿足上述條件，則該進程可以運行直到完成釋放資源。此時可以消去該進程的所有有向邊，使其孤立。
注意：判斷資源是否有空間，應(yīng)該用資源總數(shù)減去資源分配圖中的“出度” - 消去某個進程的邊后，如果可以循環(huán)該過程消去所有進程的邊，則稱該圖是完全可簡化的。
死鎖定理：當(dāng)且僅當(dāng)資源分配圖不可完全簡化。
3.死鎖解除
- 資源剝奪法：掛起死鎖進程并搶占資源，將這些資源分配給其他進程，但應(yīng)防止被掛起進程餓死
- 撤銷進程法：強制撤銷部分甚至全部死鎖進程并剝奪這些進程的資源，撤銷的原則可以按進程優(yōu)先級和撤銷進程的代價高低進行。
- 進程回退法：讓一個或多個進程回退到回避死鎖的地步（資源釋放資源而不是被剝奪），要求系統(tǒng)可以設(shè)置還原點。
