2.1 進(jìn)程與線程

2.1.1 進(jìn)程的概念與特征

1.進(jìn)程的概念：

多個(gè)程序并發(fā)運(yùn)行，它們失去封閉性，且具有間斷性和不可再現(xiàn)性的特征，所以引入進(jìn)程（Process）的概念，描述和控制程序的并發(fā)執(zhí)行，實(shí)現(xiàn)了操作系統(tǒng)的并發(fā)性和共享性。

配置專門(mén)的數(shù)據(jù)結(jié)構(gòu)—進(jìn)程控制塊（Process Control Block，PCB）保證并發(fā)的程序獨(dú)立地運(yùn)行，PCB描述進(jìn)程的基本情況和運(yùn)行狀態(tài)，以此來(lái)進(jìn)行控制和管理進(jìn)程。由程序段、相關(guān)數(shù)據(jù)段和PCB三部分構(gòu)成了進(jìn)程映像（進(jìn)程實(shí)體）。進(jìn)程的創(chuàng)建與撤銷的實(shí)質(zhì)是創(chuàng)建與撤銷進(jìn)程映像中的PCB，但進(jìn)程映像是靜態(tài)的，進(jìn)程是動(dòng)態(tài)的，而PCB是進(jìn)程唯一存在的標(biāo)志。

進(jìn)程有多種定義方式，比較典型的是：

1）進(jìn)程是程序的一次執(zhí)行過(guò)程；

2）進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)；

3）進(jìn)程時(shí)具有獨(dú)立功能的程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過(guò)程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。

系統(tǒng)資源是指處理機(jī)、存儲(chǔ)器和其他設(shè)備服務(wù)于某個(gè)進(jìn)程的“時(shí)間片”，以進(jìn)程為單位將這些時(shí)間片分配給不同進(jìn)程。

2.進(jìn)程的特征

進(jìn)程與程序是兩個(gè)不同的概念，基本特征有：

1）動(dòng)態(tài)性：是程序的一次執(zhí)行，有創(chuàng)建、活動(dòng)、暫停、中止等過(guò)程，有一定的生命周期，是最基本的特征。

2）并發(fā)性：多個(gè)進(jìn)程實(shí)體同時(shí)存于內(nèi)存中，在一段時(shí)間內(nèi)同時(shí)運(yùn)行，引入進(jìn)程的目的就是使程序并發(fā)執(zhí)行，提高資源利用率。

3）獨(dú)立性：進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立獲取資源和接受獨(dú)立接受調(diào)度的基本單位，未建立PCB的程序，不能作為一個(gè)獨(dú)立的單位參與運(yùn)行。

4）異步性：進(jìn)程按個(gè)自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)，異步性導(dǎo)致結(jié)果的不可再現(xiàn)性，在操作系統(tǒng)中應(yīng)配置相應(yīng)的進(jìn)程同步機(jī)制。

5）結(jié)構(gòu)性：每個(gè)進(jìn)程都配置一個(gè)PCB對(duì)其進(jìn)行描述，進(jìn)程實(shí)體由程序段、數(shù)據(jù)段和進(jìn)程控制塊三部分組成。

2.1.2 進(jìn)程的狀態(tài)與轉(zhuǎn)換

進(jìn)程的5個(gè)狀態(tài)：

1）運(yùn)行態(tài)：進(jìn)程在處理機(jī)上運(yùn)行，在單處理機(jī)環(huán)境下，每個(gè)時(shí)刻最多只有一個(gè)進(jìn)程處于運(yùn)行狀態(tài)。

2）就緒態(tài)：進(jìn)程獲取了除處理機(jī)外的一切所需資源，一旦處理機(jī)就緒，便可立即運(yùn)行，多個(gè)處于就緒態(tài)的進(jìn)程可以形成一個(gè)就緒隊(duì)列。

3）阻塞態(tài)：又稱等待態(tài)，進(jìn)程正在等待某資源可用或輸入/輸出完成而暫停運(yùn)行。

4）創(chuàng)建態(tài)：正在被創(chuàng)建，尚未轉(zhuǎn)到就緒態(tài)。創(chuàng)建的過(guò)程先申請(qǐng)一個(gè)PCB，向PCB中寫(xiě)入控制和管理進(jìn)程的信息，然后為其分配資源，最后轉(zhuǎn)入就緒態(tài)。

5）結(jié)束態(tài)：進(jìn)程因?yàn)檎＝Y(jié)束或中斷而退出運(yùn)行，系統(tǒng)先置進(jìn)程為結(jié)束態(tài)，然后釋放和回收資源。

就緒態(tài)和等待態(tài)的區(qū)別：就緒態(tài)是只等待處理機(jī)，而等待態(tài)是等待除處理機(jī)外的其他資源，兩個(gè)完全不同。

5個(gè)狀態(tài)的轉(zhuǎn)換過(guò)程：

就緒轉(zhuǎn)運(yùn)行：就緒的進(jìn)程獲得處理機(jī)資源后轉(zhuǎn)為運(yùn)行態(tài)。

運(yùn)行轉(zhuǎn)就緒：運(yùn)行的進(jìn)程在將處理機(jī)時(shí)間片用完之后，讓出處理機(jī)，轉(zhuǎn)為就緒態(tài)。

運(yùn)行轉(zhuǎn)阻塞：進(jìn)程請(qǐng)求某一資源的使用或等待某一事件的發(fā)生，從運(yùn)行轉(zhuǎn)換為阻塞態(tài)。

阻塞轉(zhuǎn)就緒：進(jìn)程請(qǐng)求的資源得到分配時(shí)或事件完成時(shí)，中斷處理程序必須把相應(yīng)進(jìn)程的狀態(tài)轉(zhuǎn)換為就緒態(tài)。

運(yùn)行變阻塞是主動(dòng)的行為，阻塞變成就緒是被動(dòng)行為。

2.1.3 進(jìn)程控制

進(jìn)程控制主要是對(duì)進(jìn)程實(shí)施有效的管理，具有創(chuàng)建新進(jìn)程、撤銷已有進(jìn)程、實(shí)現(xiàn)進(jìn)程狀態(tài)轉(zhuǎn)換等功能，進(jìn)程控制用的程序段稱為原語(yǔ)，它在執(zhí)行期間不允許中斷，是一個(gè)不可分割的單位。

1.進(jìn)程的創(chuàng)建：

運(yùn)行一個(gè)進(jìn)程（父進(jìn)程）創(chuàng)建另一個(gè)進(jìn)程（子進(jìn)程），子進(jìn)程可以繼承父進(jìn)程所擁有的資源，當(dāng)子進(jìn)程被撤銷時(shí)，應(yīng)將資源全部還給父進(jìn)程，而撤銷父進(jìn)程，必須撤銷子進(jìn)程。

操作系統(tǒng)創(chuàng)建新進(jìn)程的過(guò)程（創(chuàng)建原語(yǔ)）：

1）分配進(jìn)程識(shí)別號(hào)和申請(qǐng)PCB；

2）分配資源，若資源不夠進(jìn)程處于阻塞狀態(tài)，等待資源；

3）初始化PCB，主要包括初始化標(biāo)志信息，初始化處理機(jī)狀態(tài)信息、初始化處理機(jī)控制信息、設(shè)置優(yōu)先級(jí)；

4）進(jìn)程進(jìn)入就緒隊(duì)列等待被調(diào)度運(yùn)行。

2.進(jìn)程的終止：

引起進(jìn)程終止的原因：正常結(jié)束，進(jìn)程運(yùn)行完畢正常退出；異常結(jié)束，發(fā)生了某種異常事件導(dǎo)致進(jìn)程不能繼續(xù)運(yùn)行，如存儲(chǔ)區(qū)越界、非法指令、運(yùn)行超時(shí)等；外界干預(yù)，進(jìn)程應(yīng)外界的請(qǐng)求而終止運(yùn)行，如操作員或操作系統(tǒng)的干預(yù)、父進(jìn)程請(qǐng)求和父進(jìn)程終止。

終止進(jìn)程過(guò)程（撤銷原語(yǔ)）：

1）根據(jù)被終止進(jìn)程的標(biāo)示符，檢索PCB，從中讀出該進(jìn)程的狀態(tài)；

2）若進(jìn)程處于執(zhí)行狀態(tài)，立即終止，將資源重新分配；

3）若其還有子孫進(jìn)程，終止子孫進(jìn)程；

4）將子孫進(jìn)程的資源歸還父進(jìn)程或操作系統(tǒng)；

5）將PCB刪除。

3.進(jìn)程的阻塞和喚醒：

在執(zhí)行過(guò)程中，若期待的事件未發(fā)生，系統(tǒng)執(zhí)行阻塞原語(yǔ)（block），轉(zhuǎn)為阻塞態(tài)，屬于主動(dòng)行為，阻塞原語(yǔ)執(zhí)行過(guò)程如下：

1）根據(jù)進(jìn)程標(biāo)示號(hào)找到PCB；

2）若為運(yùn)行態(tài)，保護(hù)現(xiàn)場(chǎng)，轉(zhuǎn)為阻塞態(tài)，停止運(yùn)行；

3）把該P(yáng)CB插入相應(yīng)事件的等待隊(duì)列，將處理機(jī)資源交給其他就緒程序。

當(dāng)所期待的事情發(fā)生時(shí)，調(diào)用喚醒原語(yǔ)（wakeup），等待進(jìn)程喚醒，喚醒過(guò)程：

1）在該事件的等待隊(duì)列中找到PCB；

2）從等待隊(duì)列移出，轉(zhuǎn)換為就緒態(tài)；

3）把PCB插入就緒隊(duì)列，等待調(diào)度執(zhí)行。

block和wakeup必須成對(duì)使用，前者是自我調(diào)用，后者是被其他調(diào)用。

4.進(jìn)程切換

進(jìn)程是在操作系統(tǒng)內(nèi)核的支持下完成的，與內(nèi)核緊密相關(guān)。進(jìn)程切換是指處理機(jī)從一個(gè)進(jìn)程的運(yùn)行轉(zhuǎn)到另一個(gè)進(jìn)程上運(yùn)行，在此過(guò)程中進(jìn)程運(yùn)行的環(huán)境產(chǎn)生了實(shí)質(zhì)性的變化，過(guò)程如下：

1）保存處理機(jī)上下文，包括程序計(jì)數(shù)器和其他寄存器；

2）更新PCB信息；

3）把進(jìn)程的PCB移入相應(yīng)的隊(duì)列，如就緒隊(duì)列或阻塞隊(duì)列；

4）選擇另一個(gè)進(jìn)程執(zhí)行，并更新PCB；

5）更新內(nèi)存管理的數(shù)據(jù)結(jié)構(gòu)；

6）恢復(fù)處理機(jī)上下文。

注意：進(jìn)程切換與處理機(jī)模式切換是不同的，模式切換時(shí)，處理機(jī)邏輯上可能還在同一進(jìn)程中運(yùn)行。若進(jìn)程因中斷或異常進(jìn)入核心態(tài)運(yùn)行，執(zhí)行完又回到用戶態(tài)繼續(xù)執(zhí)行該進(jìn)程，操作系統(tǒng)只需恢復(fù)進(jìn)程進(jìn)入內(nèi)核前所保存的CPU現(xiàn)場(chǎng)，無(wú)需改變當(dāng)前進(jìn)程的環(huán)境信息；但切換進(jìn)程，運(yùn)行環(huán)境信息也需要改變。

調(diào)度與切換的區(qū)別：調(diào)度指決定資源分配給哪個(gè)進(jìn)程的行為，是一種決策行為；切換是指實(shí)際分配的行為，是執(zhí)行行為。

2.1.4 進(jìn)程的組織

進(jìn)程是一個(gè)獨(dú)立的運(yùn)行單位，也是資源分配和調(diào)度的基本單位。由三部分組成，最核心的是PCB。

1.進(jìn)程控制塊

創(chuàng)建時(shí)，新建PCB，存儲(chǔ)進(jìn)程運(yùn)行狀態(tài)和優(yōu)先級(jí)，常駐內(nèi)存，任意時(shí)刻都可存取，并在進(jìn)程結(jié)束時(shí)刪除，PCB是進(jìn)程實(shí)體的一部分，是進(jìn)程存在的唯一標(biāo)志，系統(tǒng)通過(guò)PCB表來(lái)管理和控制進(jìn)程。

當(dāng)操作系統(tǒng)欲調(diào)度某進(jìn)程運(yùn)行時(shí)，從該進(jìn)程的PCB中查出運(yùn)行狀態(tài)和優(yōu)先級(jí)；在調(diào)度到某進(jìn)程之后，根據(jù)其PCB中所保存的處理機(jī)狀態(tài)信息，設(shè)置恢復(fù)現(xiàn)場(chǎng)，并根據(jù)PCB中存儲(chǔ)的程序和數(shù)據(jù)的地址，找到程序和數(shù)據(jù)；在運(yùn)行過(guò)程中，需要和與之相關(guān)的進(jìn)程進(jìn)行同步、通信或訪問(wèn)文件時(shí)，也需訪問(wèn)PCB；當(dāng)進(jìn)程由于某種原因而暫停運(yùn)行時(shí)，又需將其斷點(diǎn)的處理機(jī)環(huán)境保存在PCB中。在整個(gè)進(jìn)程運(yùn)行的生命周期中，系統(tǒng)唯有經(jīng)過(guò)PCB才能感知該進(jìn)程的存在。

下圖是一個(gè)PCB實(shí)例：

1）進(jìn)程描述信息。進(jìn)程標(biāo)識(shí)符：各個(gè)進(jìn)程的唯一標(biāo)志。用戶標(biāo)識(shí)符：標(biāo)示進(jìn)程所屬的用戶，為共享和保護(hù)服務(wù)。

2）進(jìn)程控制和管理信息。進(jìn)程當(dāng)前狀態(tài)：描述進(jìn)程的狀態(tài)信息，作為處理機(jī)分配調(diào)度的依據(jù)。進(jìn)程優(yōu)先級(jí)：描述搶占處理機(jī)的優(yōu)先級(jí)。

3）資源分配清單，說(shuō)明有關(guān)內(nèi)存地址空間或虛擬地址空間的狀況，所打開(kāi)文件的列表和所使用的輸入/輸出設(shè)備信息。

4）處理機(jī)相關(guān)信息，主要指處理機(jī)中各寄存器的值，當(dāng)進(jìn)程被切換時(shí)，處理機(jī)狀態(tài)信息都必須保存在相應(yīng)的PCB中，方便重新執(zhí)行。

為了方便進(jìn)程的調(diào)度和管理，需要將各進(jìn)程的PCB用適當(dāng)?shù)姆椒ńM織起來(lái)，常用的組織方式有鏈接方式和索引方式，鏈?zhǔn)绞菍⑼粻顟B(tài)的PCB鏈接成一個(gè)隊(duì)列，不同狀態(tài)對(duì)應(yīng)不同隊(duì)列，也可把阻塞原因不同的隊(duì)列根據(jù)其原因分成若干個(gè)。索引方式是將同一狀態(tài)的進(jìn)程組織在一個(gè)索引表中，索引表的表項(xiàng)指向相應(yīng)的PCB，不同狀態(tài)對(duì)應(yīng)不同索引表。

2.程序段

能被進(jìn)程調(diào)度程序調(diào)度到CPU執(zhí)行的程序代碼段，程序可被多個(gè)進(jìn)程共享。

3.數(shù)據(jù)段

一個(gè)進(jìn)程的數(shù)據(jù)段，可以是進(jìn)程對(duì)應(yīng)的程序加工處理的原始數(shù)據(jù)，也可以是程序執(zhí)行后產(chǎn)生的中間或最終結(jié)果數(shù)據(jù)。

2.1.5 進(jìn)程的通信

通信指進(jìn)程之間信息的交換，PV是低級(jí)通信方式，高級(jí)通信方式是以較高的效率傳輸大量數(shù)據(jù)的通信方式，有以下三類：

1.共享存儲(chǔ)：進(jìn)程之間存在一塊可直接訪問(wèn)的共享空間，對(duì)這個(gè)空間的讀/寫(xiě)操作實(shí)現(xiàn)進(jìn)程之間的信息交換，在讀/寫(xiě)操作時(shí)，需要用同步互斥（P/V操作）進(jìn)行控制。共享存儲(chǔ)又分兩種：低級(jí)方式的共享基于數(shù)據(jù)結(jié)構(gòu)的共享；高級(jí)方式的共享基于存儲(chǔ)區(qū)的共享，操作系統(tǒng)只提供空間和工具，交換由用戶自己安排完成。

注意，用戶進(jìn)程空間一般是獨(dú)立的，運(yùn)行期間一般不能訪問(wèn)其他進(jìn)程空間，要想讓兩個(gè)用戶進(jìn)程共享空間，必須通過(guò)特殊的系統(tǒng)調(diào)用實(shí)現(xiàn)，而進(jìn)程內(nèi)的線程是自然共享進(jìn)程空間的。

2.消息傳遞

在消息傳遞系統(tǒng)中，進(jìn)程間的數(shù)據(jù)交換以格式化的消息（Message）為單位的。若通信的進(jìn)程之間不存在可直接訪問(wèn)的共享空間，則必須利用操作系統(tǒng)提供的消息傳遞方法實(shí)現(xiàn)進(jìn)程通信。進(jìn)程通過(guò)系統(tǒng)提供的發(fā)送消息原語(yǔ)與接收消息原語(yǔ)進(jìn)行數(shù)據(jù)交換。

1）直接通信方式。發(fā)送進(jìn)程直接把消息發(fā)送給接收進(jìn)程，并將它掛在接收進(jìn)程的消息緩沖隊(duì)列上，接收進(jìn)程從消息緩沖隊(duì)列中取得消息，如下圖。

2）間接通信方式。發(fā)送進(jìn)程把消息發(fā)送到某個(gè)中間實(shí)體，接收進(jìn)程從中間實(shí)體取得消息。中間實(shí)體一般稱為信箱，這種通信方式又稱為信箱通信方式。該通信方式廣泛應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)中，稱為電子郵件系統(tǒng)。

3.管道通信

管道通信是消息傳遞的一種特殊方式，管道指用于連接一個(gè)讀進(jìn)程和一個(gè)寫(xiě)進(jìn)程以實(shí)現(xiàn)它們通信的一個(gè)共享文件（pipe文件）。向pipe提供輸入的發(fā)送進(jìn)程（寫(xiě)進(jìn)程），以字符流形式將大量的數(shù)據(jù)送入寫(xiě)管道；接收管道輸出的接收進(jìn)程（讀進(jìn)程）則從管道中接收（讀）數(shù)據(jù)。為了協(xié)調(diào)雙方的通信，管道機(jī)制必須提供互斥、同步、確定對(duì)方存在的協(xié)調(diào)能力。

管道只能采用半雙工通信——某一時(shí)刻只能單向傳輸，要實(shí)現(xiàn)父子進(jìn)程雙向互動(dòng)，要定義兩個(gè)管道。它通過(guò)限制管道大小和規(guī)定讀進(jìn)程比寫(xiě)進(jìn)程快克服使用文件進(jìn)行通信的缺點(diǎn)。

管道可以理解為共享存儲(chǔ)的優(yōu)化和發(fā)展。在共享存儲(chǔ)中，某進(jìn)程要訪問(wèn)共享存儲(chǔ)空間，必須沒(méi)有其他進(jìn)程在該共享存儲(chǔ)空間進(jìn)行讀/寫(xiě)操作。否則會(huì)被阻塞。在管道通信中存儲(chǔ)空間進(jìn)化成緩沖區(qū)，允許一邊寫(xiě)入，另一邊讀出，只要緩沖區(qū)中有數(shù)據(jù)，數(shù)據(jù)就能被進(jìn)程讀出，不用擔(dān)心其他進(jìn)程正在讀數(shù)據(jù)而阻塞。

2.1.6 線程概念和多線程模型

1.線程的基本概念

引入進(jìn)程是為了使多道程序并發(fā)執(zhí)行，提高資源利用率和系統(tǒng)吞吐量；引入線程為了減少程序在并發(fā)執(zhí)行時(shí)所付出的時(shí)空開(kāi)銷，提高并發(fā)執(zhí)行的性能。

線程是一個(gè)輕量級(jí)進(jìn)程，是一個(gè)基本的CPU執(zhí)行單元，也是程序執(zhí)行流的最小單元，它由線程ID、程序計(jì)數(shù)器、寄存器集合和堆棧組成。線城是進(jìn)程中的一個(gè)實(shí)體，是被系統(tǒng)獨(dú)立調(diào)度和分派的基本單位，線程可與同屬一個(gè)進(jìn)程的其它線程共享資源。一個(gè)線程可以創(chuàng)建和撤銷另一個(gè)線程，同一進(jìn)程中的多個(gè)線程可以并發(fā)執(zhí)行。線程之間有相互制約，所以線程運(yùn)行會(huì)呈現(xiàn)間斷性。線程的狀態(tài)也有就緒、阻塞、運(yùn)行。

進(jìn)程只作為除CPU外的系統(tǒng)資源的分配單元，線程作為處理機(jī)的分配單元，一個(gè)進(jìn)程內(nèi)部有多個(gè)線程，線程的切換位于同一個(gè)進(jìn)程內(nèi)，需要的時(shí)空開(kāi)銷很小。

2.線程和進(jìn)程的比較

1）調(diào)度：無(wú)線程時(shí)，進(jìn)程是擁有資源和獨(dú)立調(diào)度的基本單位，有線程時(shí)，線程是獨(dú)立調(diào)度的基本單位，但進(jìn)程依舊是擁有資源的基本單位。同一進(jìn)程中，線程的切換不會(huì)引起進(jìn)程的切換，在不同進(jìn)程中進(jìn)行線程切換，則會(huì)引起進(jìn)程切換。

2）擁有資源：進(jìn)程擁有資源，線程不擁有資源，但線程可以訪問(wèn)其奴隸進(jìn)程的系統(tǒng)資源，若線程也是擁有資源的單位，則切換線程時(shí)需要較大的時(shí)空開(kāi)銷。

3）并發(fā)性：進(jìn)程之間可以并發(fā)執(zhí)行，多個(gè)線程之間也可并發(fā)執(zhí)行。

4）系統(tǒng)開(kāi)銷：創(chuàng)建撤銷進(jìn)程時(shí)所需開(kāi)銷，比對(duì)線程進(jìn)行同樣操作時(shí)所需的開(kāi)銷大。

5）地址空間和其他資源（如打開(kāi)的文件）：進(jìn)程的地址空間相互獨(dú)立，同一進(jìn)程的線程共享同一地址空間。

6）通信方面：進(jìn)程間的通信（IPC）需要進(jìn)程同步和互斥手段的輔助，保證數(shù)據(jù)一致，線程間的通信通過(guò)直接讀/寫(xiě)進(jìn)程數(shù)據(jù)段實(shí)現(xiàn)。

3.線程的屬性

1）輕型實(shí)體：不擁有系統(tǒng)資源，有標(biāo)識(shí)符、線程控制塊，線程控制塊記錄了線程執(zhí)行的寄存器和棧等現(xiàn)場(chǎng)狀況。

2）同一個(gè)服務(wù)被不同用戶調(diào)用時(shí)，操作系統(tǒng)把它們創(chuàng)建成不同的線程。

3）進(jìn)程中的線程共享此進(jìn)程的資源。

4）線程是處理機(jī)的調(diào)度單位，線程可并發(fā)。

5）線程被創(chuàng)建之后，開(kāi)始它的生命周期，會(huì)經(jīng)歷阻塞態(tài)、就緒態(tài)和運(yùn)行態(tài)的變化。

4.線程的實(shí)現(xiàn)方式

線程分為用戶級(jí)線程（User-Level Thread，ULT）和內(nèi)核級(jí)線程（Kernel-Level Thread，KLT）（內(nèi)核支持的線程）。

用戶級(jí)線程中，線程管理由應(yīng)用程序完成，內(nèi)核意識(shí)不到線程的存在。應(yīng)用程序通過(guò)使用線程庫(kù)設(shè)計(jì)成多線程程序，從單線程開(kāi)始，在該線程中開(kāi)始運(yùn)行，在其運(yùn)行的任何時(shí)刻，通過(guò)調(diào)用線程庫(kù)中的派生例程創(chuàng)建新線程。如下圖（a）。

內(nèi)核級(jí)線程中，管理由內(nèi)核完成，應(yīng)用程序沒(méi)有進(jìn)行線程管理的代碼，只有一個(gè)內(nèi)核級(jí)線程的編程接口。內(nèi)核為其進(jìn)程及內(nèi)部的每個(gè)線程維護(hù)上下文信息，調(diào)度也在內(nèi)核基于線程架構(gòu)的基礎(chǔ)上完成。如下圖（b）。

一些系統(tǒng)使用組合方式實(shí)現(xiàn)。創(chuàng)建在用戶空間中完成，調(diào)度和同步在應(yīng)用程序中進(jìn)行。應(yīng)用程序中的多個(gè)用戶線程被映射到內(nèi)核級(jí)線程上。如下圖（c）

5.多線程模型

1）多對(duì)一：多個(gè)用戶級(jí)線程映射到一個(gè)內(nèi)核級(jí)線程，線程管理在用戶空間內(nèi)完成，用戶線程對(duì)操作系統(tǒng)不透明。這樣做的優(yōu)點(diǎn)是：線程管理在用戶空間內(nèi)進(jìn)行，效率高。缺點(diǎn)是：線程在使用內(nèi)核服務(wù)時(shí)被阻塞，整個(gè)進(jìn)程都會(huì)被阻塞；多個(gè)線程不能并行地運(yùn)行在多處理機(jī)上。

2）一對(duì)一：每個(gè)用戶級(jí)線程映射到相應(yīng)單獨(dú)的內(nèi)核級(jí)線程上。這樣做的優(yōu)點(diǎn)是：當(dāng)一個(gè)線程被阻塞時(shí)，允許另一個(gè)線程繼續(xù)執(zhí)行，并發(fā)能力強(qiáng)。缺點(diǎn)是：每創(chuàng)建一個(gè)用戶級(jí)線程都需要?jiǎng)?chuàng)建一個(gè)內(nèi)核級(jí)線程，開(kāi)銷大。

3）多對(duì)多：n個(gè)用戶級(jí)線程映射到m個(gè)內(nèi)核級(jí)線程上（m≤n）。是上兩個(gè)模型的折中，集兩者所長(zhǎng)。

2.2 處理機(jī)調(diào)度

2.2.1 調(diào)度的概念

1.基本概念

處理機(jī)調(diào)度是對(duì)處理機(jī)進(jìn)行分配，即從就緒隊(duì)列中按照一定的算法，選擇一個(gè)進(jìn)程，將處理機(jī)分配給它使用，實(shí)現(xiàn)進(jìn)程并發(fā)執(zhí)行。是操作系統(tǒng)的基礎(chǔ)，是操作系統(tǒng)設(shè)計(jì)的核心問(wèn)題。

2.調(diào)度的層次

三級(jí)調(diào)度：

1）作業(yè)調(diào)度（高級(jí)調(diào)度）：按照一定原則從外存上處于后備狀態(tài)的作業(yè)中挑選作業(yè)，給他們分配資源，建立進(jìn)程，使它們獲得競(jìng)爭(zhēng)處理機(jī)的權(quán)利。多道批處理系統(tǒng)中大多配置，其它操作系統(tǒng)不需配置，執(zhí)行頻率低，幾分鐘一次。

2）終極調(diào)度（內(nèi)存調(diào)度）：提高內(nèi)存利用率和吞吐量，將暫時(shí)不運(yùn)行的進(jìn)程調(diào)至外存，成為掛起態(tài)，當(dāng)具備運(yùn)行條件時(shí)，從外存調(diào)度到內(nèi)存，成為就緒態(tài)。

3）進(jìn)程調(diào)度（低級(jí)調(diào)度）：按照算法從就緒隊(duì)列中選取進(jìn)程，分配給其處理機(jī)，操作系統(tǒng)都配置，且調(diào)度頻率高，幾十毫秒一次。

3.三級(jí)調(diào)度的聯(lián)系

作業(yè)調(diào)度為進(jìn)程活動(dòng)做準(zhǔn)備，進(jìn)程調(diào)度使進(jìn)程正?；顒?dòng)，中級(jí)調(diào)度掛起暫時(shí)不能運(yùn)行的進(jìn)程，處于之間；三者調(diào)度頻率依次上升；進(jìn)程調(diào)度最基本，不可或缺。

2.2.2 調(diào)度的時(shí)機(jī)、切換與過(guò)程

現(xiàn)代操作系統(tǒng)中，不能進(jìn)行進(jìn)程的調(diào)度與切換的情況有：

1）處理中斷的過(guò)程中：處理中斷的過(guò)程復(fù)雜，難以做到進(jìn)程切換，在中斷執(zhí)行時(shí)，處理器資源不應(yīng)被剝奪。

2）進(jìn)程在操作系統(tǒng)內(nèi)核程序的臨界區(qū)中：進(jìn)入臨界區(qū)后需要獨(dú)占式的訪問(wèn)共享數(shù)據(jù)，必須加鎖。

3）其它需要完全屏蔽中斷的原子操作過(guò)程：如加鎖、解鎖、中斷現(xiàn)場(chǎng)保護(hù)、恢復(fù)等。

若在上述過(guò)程中發(fā)生了引起調(diào)度的條件，不能馬上進(jìn)行調(diào)度與切換，應(yīng)置系統(tǒng)的請(qǐng)求調(diào)度標(biāo)志，上述過(guò)程完成后再進(jìn)行。

應(yīng)進(jìn)行調(diào)度與切換的情況：

1）發(fā)生引起調(diào)度條件且當(dāng)前進(jìn)程無(wú)法繼續(xù)運(yùn)行下去，立即調(diào)度和切換。若操作系統(tǒng)只在這種情況下進(jìn)行調(diào)度，屬于非剝奪調(diào)度。

2）中斷處理結(jié)束或自陷處理結(jié)束后，返回被中斷進(jìn)程的用戶態(tài)程序執(zhí)行現(xiàn)場(chǎng)前，若置上請(qǐng)求調(diào)度標(biāo)志，則可馬上進(jìn)行調(diào)度與切換。若操作系統(tǒng)支持這種狀態(tài)下的運(yùn)行調(diào)度程序，則實(shí)現(xiàn)了剝奪方式調(diào)度。

進(jìn)程切換在調(diào)度完成后立刻發(fā)生，要求保存原進(jìn)程當(dāng)前切換點(diǎn)的現(xiàn)場(chǎng)信息，恢復(fù)被調(diào)度進(jìn)程的現(xiàn)場(chǎng)信息。現(xiàn)場(chǎng)切換時(shí)，操作系統(tǒng)內(nèi)核將原進(jìn)程的現(xiàn)場(chǎng)信息推入當(dāng)前進(jìn)程的內(nèi)核堆棧來(lái)保存它們，并更新堆棧指針。內(nèi)核完成從新進(jìn)程的內(nèi)核棧中裝入新進(jìn)程的現(xiàn)場(chǎng)信息、更新當(dāng)前運(yùn)行進(jìn)程空間指針、重設(shè)PC寄存器等相關(guān)工作之后，開(kāi)始運(yùn)行新的進(jìn)程。

2.2.3 進(jìn)程調(diào)度方式

當(dāng)某個(gè)進(jìn)程正在處理機(jī)上執(zhí)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程需要處理，進(jìn)程調(diào)度的方式，分兩種：

1）非剝奪調(diào)度方式（非搶占方式）：等待正在執(zhí)行的進(jìn)程執(zhí)行完畢或進(jìn)入阻塞狀態(tài)時(shí)，把處理機(jī)分配給更為重要的進(jìn)程。優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單、系統(tǒng)開(kāi)銷少，適用于大多數(shù)批處理系統(tǒng)；缺點(diǎn)是不能用于分時(shí)系統(tǒng)和大多數(shù)的實(shí)時(shí)系統(tǒng)。

2）剝奪調(diào)度方式（搶占方式）：立即暫停正在執(zhí)行的進(jìn)程，將處理機(jī)分配給優(yōu)先級(jí)更高的進(jìn)程。優(yōu)點(diǎn)是提高系統(tǒng)吞吐和響應(yīng)效率；缺點(diǎn)是對(duì)資源的剝奪要設(shè)置更合理的規(guī)則。

2.2.4 調(diào)度的基本準(zhǔn)則

不同調(diào)度算法有不同的特性，為了比較算法性能，人們提出了評(píng)價(jià)準(zhǔn)則。

1）CPU利用率：要保持CPU始終處于利用率高的狀態(tài)。

2）系統(tǒng)吞吐量：表示單位時(shí)間內(nèi)CPU完成作業(yè)的數(shù)量。

3）周轉(zhuǎn)時(shí)間：從作業(yè)提交到作業(yè)完成所經(jīng)歷的時(shí)間，是作業(yè)等待、在就緒隊(duì)列中排隊(duì)、在處理機(jī)上運(yùn)行、輸入/輸出操作所花費(fèi)的時(shí)間的總和。

周轉(zhuǎn)時(shí)間公式：周轉(zhuǎn)時(shí)間=作業(yè)完成時(shí)間—作業(yè)提交時(shí)間

平均周轉(zhuǎn)時(shí)間（多個(gè)作業(yè)周轉(zhuǎn)時(shí)間的平均值）：

平均周轉(zhuǎn)時(shí)間=（作業(yè)1的周轉(zhuǎn)時(shí)間+……+作業(yè)n的周轉(zhuǎn)時(shí)間）/n

帶權(quán)周轉(zhuǎn)時(shí)間是指作業(yè)周轉(zhuǎn)時(shí)間與實(shí)際作業(yè)時(shí)間的比值：

帶權(quán)周轉(zhuǎn)時(shí)間=（作業(yè)周轉(zhuǎn)時(shí)間）/（作業(yè)實(shí)際運(yùn)行時(shí)間）

平均帶權(quán)周轉(zhuǎn)時(shí)間是指多個(gè)作業(yè)帶權(quán)周轉(zhuǎn)時(shí)間的平均值：

平均帶權(quán)周轉(zhuǎn)時(shí)間=（作業(yè)1的帶權(quán)周轉(zhuǎn)時(shí)間+……+作業(yè)n帶權(quán)周轉(zhuǎn)時(shí)間）/n

4）等待時(shí)間：指進(jìn)程處于等處理機(jī)狀態(tài)的時(shí)間之和，等待時(shí)間越長(zhǎng)，用戶滿意度越低。處理機(jī)調(diào)度算法實(shí)際上并不影響作業(yè)執(zhí)行或輸入/輸出操作的時(shí)間，只影響作業(yè)在就緒隊(duì)列中等待所花的時(shí)間。因此，衡量一個(gè)調(diào)度算法的優(yōu)劣，常常只需考察等待時(shí)間。

5）響應(yīng)時(shí)間：從用戶提交請(qǐng)求到系統(tǒng)首次產(chǎn)生響應(yīng)所用的時(shí)間。在交互式系統(tǒng)，用響應(yīng)時(shí)間作為衡量調(diào)度算法的重要準(zhǔn)則之一。

2.2.5 典型的調(diào)度算法

1.先來(lái)先服務(wù)（FCFS）調(diào)度算法

最簡(jiǎn)單，即可用于作業(yè)調(diào)度，又可用于進(jìn)程調(diào)度。在作業(yè)調(diào)度中，算法按照在隊(duì)列里的順序，調(diào)入內(nèi)存，分配資源，創(chuàng)建進(jìn)程并放入就緒隊(duì)列。

屬于不可剝奪算法，表面上看公平，但有時(shí)作業(yè)等待時(shí)間過(guò)長(zhǎng)，因此它不能作為分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)的主要調(diào)度策略。但可與其它策略聯(lián)合使用，如在以優(yōu)先級(jí)為調(diào)度策略中，優(yōu)先級(jí)相同，以先到先服務(wù)為策略。

FCFS調(diào)度算法的特點(diǎn)是簡(jiǎn)單，但效率低；對(duì)長(zhǎng)作業(yè)比較有利，對(duì)短作業(yè)不利；有利于繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)。

2.短作業(yè)優(yōu)先（SJF）調(diào)度算法

從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行；短進(jìn)程優(yōu)先（SPF）調(diào)度算法從就緒隊(duì)列中選擇一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，為其分配處理機(jī)，使之立即執(zhí)行，直到進(jìn)程完成或阻塞，之后釋放處理機(jī)。

SJF調(diào)度算法也存在缺點(diǎn)：

1）對(duì)長(zhǎng)作業(yè)不利：長(zhǎng)作業(yè)的周轉(zhuǎn)時(shí)間會(huì)增加，甚至有些長(zhǎng)作業(yè)不會(huì)被處理，因?yàn)榭赡芤恢庇泻蟮降亩套鳂I(yè)優(yōu)先被處理。

2）該算法完全未考慮作業(yè)的緊迫程度，不能保證急迫的任務(wù)被優(yōu)先處理。

3）由于作業(yè)的長(zhǎng)短是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定，而用戶會(huì)縮短作業(yè)的估計(jì)運(yùn)行時(shí)間，可能不能真正做到短作業(yè)優(yōu)先調(diào)度。SJF的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間最少。

3.優(yōu)先級(jí)調(diào)度算法

又稱優(yōu)先權(quán)調(diào)度算法，即可用于作業(yè)調(diào)度，又可用于進(jìn)程調(diào)度。優(yōu)先級(jí)用于描述作業(yè)運(yùn)行的緊迫程度。

在作業(yè)調(diào)度中，每次從作業(yè)后備隊(duì)列中選取優(yōu)先級(jí)最高的一個(gè)或幾個(gè)，調(diào)入內(nèi)存，分配資源，創(chuàng)建進(jìn)程并放入就緒隊(duì)列。在進(jìn)程調(diào)度中，每次從就緒隊(duì)列中選取優(yōu)先級(jí)最高的進(jìn)程，分配處理機(jī)，執(zhí)行。

根據(jù)能否搶占正在執(zhí)行的進(jìn)程，分為非剝奪式優(yōu)先級(jí)調(diào)度算法，先等待正在運(yùn)行的作業(yè)運(yùn)行完畢或這阻塞，之后再執(zhí)行；剝奪式優(yōu)先級(jí)調(diào)度算法，暫停正在執(zhí)行的任務(wù)，執(zhí)行優(yōu)先級(jí)高的任務(wù)。

根據(jù)優(yōu)先級(jí)是否可改，分為靜態(tài)和動(dòng)態(tài)優(yōu)先級(jí)，靜態(tài)是優(yōu)先級(jí)一直不變，動(dòng)態(tài)是優(yōu)先級(jí)在任務(wù)執(zhí)行過(guò)程中，根據(jù)動(dòng)態(tài)情況調(diào)整優(yōu)先級(jí)。

優(yōu)先級(jí)高低比較：

1）系統(tǒng)＞用戶。

2）交互＞非交互。

3）I/O（頻繁用I/O）型＞計(jì)算（頻繁用CPU）型。

4.高響應(yīng)比優(yōu)先調(diào)度算法

主要用于作業(yè)調(diào)度，是對(duì)FCFS和SJF的一種綜合平衡，同時(shí)考慮了每個(gè)作業(yè)的等待時(shí)間和估計(jì)的運(yùn)行時(shí)間，每次進(jìn)行調(diào)度時(shí)，先計(jì)算響應(yīng)比，找出最高的，優(yōu)先運(yùn)行。

響應(yīng)比R=（等待時(shí)間+要求服務(wù)時(shí)間）/要求服務(wù)時(shí)間

根據(jù)公式：

1）作業(yè)的等待時(shí)間相同時(shí)，要求服務(wù)時(shí)間越短，響應(yīng)比越高，越有利于短作業(yè)。

2）要求服務(wù)時(shí)間相同時(shí)，作業(yè)的響應(yīng)比由其等待時(shí)間決定，等待時(shí)間越長(zhǎng)，其響應(yīng)比越高，因而它實(shí)現(xiàn)的是先來(lái)先服務(wù)。

3）對(duì)于長(zhǎng)作業(yè)，作業(yè)的響應(yīng)比可以隨等待時(shí)間的增加而提高，等待時(shí)間足夠長(zhǎng)時(shí)，其響應(yīng)比便可升到很高，從而也可獲得處理機(jī)，因此，克服了饑餓狀態(tài)，兼顧了長(zhǎng)作業(yè)。

5.時(shí)間片輪轉(zhuǎn)調(diào)度算法

適用于分時(shí)系統(tǒng)，就緒進(jìn)程按到達(dá)時(shí)間排隊(duì)，依次給每個(gè)進(jìn)程分配一個(gè)時(shí)間片，輪流進(jìn)行執(zhí)行。時(shí)間片的長(zhǎng)短由響應(yīng)時(shí)間、進(jìn)程數(shù)目、處理能力等因素決定。

6.多級(jí)反饋隊(duì)列調(diào)度算法（融合算法）

是時(shí)間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級(jí)調(diào)度算法的綜合與發(fā)展。

算法實(shí)現(xiàn)思想如下：

1）設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)，優(yōu)先級(jí)依次降低。

2）給不同優(yōu)先級(jí)隊(duì)列分配的時(shí)間片不同。優(yōu)先級(jí)越高，時(shí)間片越小。

3）新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第一季隊(duì)列（優(yōu)先級(jí)最高）的末尾，按FCFS原則調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，若它能在該時(shí)間片內(nèi)完成，可撤離系統(tǒng)；若未完成，該進(jìn)程轉(zhuǎn)入第二次隊(duì)列末尾，以此類推。

4）僅當(dāng)?shù)谝患?jí)隊(duì)列為空時(shí)，調(diào)度程序才調(diào)度第2級(jí)隊(duì)列中的進(jìn)程運(yùn)行，以此類推。若處理機(jī)正在執(zhí)行第i隊(duì)列中的某一進(jìn)程，此時(shí)有優(yōu)先級(jí)更高的進(jìn)程進(jìn)入隊(duì)列，則此時(shí)新進(jìn)程搶占處理機(jī)，而正在運(yùn)行的進(jìn)程則被進(jìn)程調(diào)度程序放在第i隊(duì)列的末尾。

優(yōu)勢(shì)有如下幾點(diǎn)：

1）終端型作業(yè)用戶：短作業(yè)優(yōu)先。

2）短批處理作業(yè)用戶：周轉(zhuǎn)時(shí)間較短。

3）長(zhǎng)批處理作業(yè)用戶：經(jīng)過(guò)前面幾個(gè)隊(duì)列得到部分執(zhí)行，不會(huì)長(zhǎng)期得不到處理。

2.3 進(jìn)程同步

2.3.1 進(jìn)程同步的基本概念

為了協(xié)調(diào)不同進(jìn)程之間的相互制約關(guān)系，引入進(jìn)程同步。進(jìn)程同步簡(jiǎn)單理解就是進(jìn)程的執(zhí)行需要先后執(zhí)行，保證結(jié)果的正確。

1.臨界資源

一次僅允許一個(gè)進(jìn)程使用的資源稱為臨界資源，如打印機(jī)，變量或數(shù)據(jù)等，具有當(dāng)前進(jìn)程的獨(dú)占性，必須互斥的訪問(wèn)。在進(jìn)程中訪問(wèn)臨界資源的代碼稱為臨界區(qū)。臨界資源的訪問(wèn)分4個(gè)過(guò)程。

1）進(jìn)入?yún)^(qū)：為了進(jìn)入臨界區(qū)使用臨界資源，進(jìn)入時(shí)要檢查是否可進(jìn)，若能進(jìn)，需設(shè)置正在訪問(wèn)臨界區(qū)的標(biāo)志，防止其它進(jìn)程進(jìn)入臨界區(qū)。

2）臨界區(qū)：訪問(wèn)臨界資源的代碼，又稱臨界段。

3）退出區(qū)：將正在訪問(wèn)臨界區(qū)的標(biāo)志清除。

4）剩余區(qū)：代碼中的其余部分。

2.同步

也稱直接制約關(guān)系，為完成某個(gè)任務(wù)創(chuàng)建多個(gè)進(jìn)程，這些進(jìn)程執(zhí)行有先后順序，才能保證結(jié)果的正確性。制約關(guān)系源于它們之間相互合作。

3.互斥

也稱間接制約關(guān)系，一個(gè)進(jìn)程進(jìn)入臨界區(qū)時(shí)，此時(shí)臨界資源被當(dāng)前進(jìn)程獨(dú)占，其它進(jìn)程只能等待。

為禁止多個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)，同步機(jī)制應(yīng)遵循以下準(zhǔn)則：

1）空閑讓進(jìn)：臨界區(qū)空閑時(shí)，可以允許一個(gè)請(qǐng)求的進(jìn)程立即進(jìn)入臨界區(qū)。

2）忙則等待：臨界區(qū)內(nèi)有進(jìn)程時(shí)，其它必須等待。

3）有限等待：對(duì)請(qǐng)求訪問(wèn)的進(jìn)程，保證其在有限時(shí)間內(nèi)進(jìn)入臨界區(qū)。

4）讓權(quán)等待：進(jìn)程不能進(jìn)入臨界區(qū)時(shí)，立即釋放處理器。

2.3.2 實(shí)現(xiàn)臨界區(qū)互斥的基本方法

1.軟件實(shí)現(xiàn)方法

在進(jìn)入?yún)^(qū)設(shè)置并檢查一些標(biāo)志來(lái)標(biāo)明是否有進(jìn)程在臨界區(qū)中，若已有，在進(jìn)入?yún)^(qū)通過(guò)循環(huán)檢查進(jìn)行等待，進(jìn)程離開(kāi)臨界區(qū)后則在退出區(qū)修改標(biāo)志。

1）算法一：?jiǎn)螛?biāo)志法。設(shè)置一個(gè)公用整型變量turn，指示被允許進(jìn)入臨界區(qū)的進(jìn)程編號(hào)，turn=n，允許進(jìn)程n進(jìn)入。該算法可以保證一次一個(gè)進(jìn)程進(jìn)入臨界區(qū)，但兩個(gè)進(jìn)程必須交替進(jìn)入，若某個(gè)不再進(jìn)，另一個(gè)也無(wú)法進(jìn)，造成資源浪費(fèi)。

2）算法二：雙標(biāo)志法先檢查。基本思想是進(jìn)程進(jìn)入臨界區(qū)之前，檢查臨界區(qū)是否被占用（先檢查對(duì)方的進(jìn)程狀態(tài)標(biāo)志，在置自己的標(biāo)志）。需設(shè)置一個(gè)數(shù)據(jù)flag[i]，若為False，表示i進(jìn)程未進(jìn)入臨界區(qū)，True，進(jìn)入。

優(yōu)點(diǎn)：不用交替進(jìn)入，可連續(xù)使用；缺點(diǎn)：進(jìn)程i和進(jìn)程j可能同時(shí)進(jìn)入臨界區(qū)。在檢查對(duì)方的flag后和切換自己的flag前有一段時(shí)間，都通過(guò)檢查，導(dǎo)致同時(shí)進(jìn)入。

3）算法三：雙標(biāo)志法后檢查。先將自己的標(biāo)志設(shè)為T(mén)rue，再檢測(cè)對(duì)方的狀態(tài)標(biāo)志，若對(duì)方為T(mén)rue，則進(jìn)程等待，否則進(jìn)入臨界區(qū)。這樣會(huì)導(dǎo)致兩個(gè)進(jìn)程同時(shí)想進(jìn)入臨界區(qū)，但發(fā)現(xiàn)對(duì)方也想進(jìn)，兩個(gè)進(jìn)程互相謙讓，導(dǎo)致誰(shuí)也進(jìn)不了。

4）算法四：Peterson‘s Algorithm。為防止兩個(gè)進(jìn)程為進(jìn)入臨界區(qū)而無(wú)限期等待，設(shè)置變量turn，每個(gè)進(jìn)程先設(shè)置自己的標(biāo)志后再設(shè)置turn標(biāo)志，再同時(shí)檢測(cè)另一個(gè)進(jìn)程狀態(tài)標(biāo)志和不允許進(jìn)入標(biāo)志，保證只允許一個(gè)進(jìn)程進(jìn)入臨界區(qū)。

是算法一和算法三的結(jié)合，用flag解決互斥訪問(wèn)，turn解決饑餓現(xiàn)象。

2.硬件實(shí)現(xiàn)方法

計(jì)算機(jī)提供了特殊的硬件指令，允許對(duì)一個(gè)字中的內(nèi)容進(jìn)行檢測(cè)與修正，通過(guò)硬件實(shí)現(xiàn)稱為低級(jí)方法（元方法）

（1）中斷屏蔽方法

當(dāng)一個(gè)進(jìn)程正在使用處理機(jī)執(zhí)行臨界區(qū)代碼時(shí)，禁止一切中斷是防止其它進(jìn)程進(jìn)入臨界區(qū)的最好方法，我們稱這種行為為屏蔽中斷、關(guān)中斷。限制了處理機(jī)交替執(zhí)行程序的能力，效率會(huì)降低。對(duì)內(nèi)核來(lái)說(shuō)，在執(zhí)行指令期間，關(guān)中斷很方便，但不能將關(guān)中斷的權(quán)力交給用戶。

（2）硬件指令方法

TestAndSet指令：是原子操作，功能是讀出指定標(biāo)志后把標(biāo)志設(shè)置為真?？梢詾槊總€(gè)臨界資源設(shè)置共享布爾變量lock，表示資源的兩種狀態(tài)，true表示正在被占用，初值為false。

應(yīng)為每個(gè)臨界資源設(shè)置一個(gè)共享變量lock，初值為false；每一個(gè)進(jìn)程中設(shè)置一個(gè)局部變量key，用于與lock交換信息。進(jìn)入臨界區(qū)前，先利用Swap指令交換lock與key的內(nèi)容，然后檢查key的狀態(tài)；有進(jìn)程在臨界區(qū)時(shí)，重復(fù)交換和檢查過(guò)程。

硬件方法的優(yōu)點(diǎn)：適用于任意數(shù)目的進(jìn)程；簡(jiǎn)單、易驗(yàn)證其正確性。可以支持進(jìn)程內(nèi)有多個(gè)臨界區(qū)，只需為每個(gè)臨界區(qū)設(shè)置一個(gè)布爾變量。

硬件方法的缺點(diǎn)：等待進(jìn)入臨界區(qū)時(shí)耗費(fèi)處理機(jī)時(shí)間，不能實(shí)現(xiàn)讓權(quán)等待。從等待進(jìn)程中隨機(jī)選擇一個(gè)進(jìn)入臨界區(qū)，但可能有進(jìn)程一直不能被選上，導(dǎo)致饑餓現(xiàn)象。

2.3.3 信號(hào)量

信號(hào)量機(jī)制是一種功能較強(qiáng)的機(jī)制，可用來(lái)解決互斥與同步問(wèn)題，只能被兩個(gè)標(biāo)準(zhǔn)的原語(yǔ)wait（S）和signal（S）訪問(wèn)，也可記為“P操作（申請(qǐng)資源）”與“V操作（釋放資源）”。

1.整型信號(hào)量

被定義為一個(gè)用于表示資源數(shù)目的整型量S，wait操作中，信號(hào)量S≤0，就會(huì)不斷地測(cè)試，因此該機(jī)制使進(jìn)程處于“忙等的狀態(tài)”。

2.記錄型信號(hào)量，不存在“忙等”現(xiàn)象，除一個(gè)需要一個(gè)整型變量之外，再增加一個(gè)進(jìn)程鏈表L，用于鏈接所有等待該資源的進(jìn)程?？擅枋鰹椋簑ait操作，S.value表示進(jìn)程請(qǐng)求一個(gè)該類資源，當(dāng)S.value＜0時(shí)，表示資源已經(jīng)被分完，因此調(diào)用block原語(yǔ)，進(jìn)行自我阻塞，放棄處理機(jī)，并將進(jìn)程插入到該類資源的等待序列，該機(jī)制遵循了“讓權(quán)等待”的原則。

signal操作，表示進(jìn)程釋放一個(gè)資源，使系統(tǒng)中可分配的該資源數(shù)增1，若加1后S.value（可用的資源數(shù)）≤0，表示等待該資源的進(jìn)程被阻塞，調(diào)用wakeup原語(yǔ)進(jìn)行喚醒。

3.利用信號(hào)量實(shí)現(xiàn)同步

信號(hào)量機(jī)制能用于解決進(jìn)程間的各種同步問(wèn)題。設(shè)S為進(jìn)程1與進(jìn)程2的公共信號(hào)量，初值為0。進(jìn)程2中要使用進(jìn)程1運(yùn)行的結(jié)果，若進(jìn)程2先執(zhí)行，進(jìn)程2會(huì)被阻塞，當(dāng)進(jìn)程1執(zhí)行完畢后，進(jìn)程2會(huì)被置就緒態(tài)，繼續(xù)執(zhí)行。

4.利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥

信號(hào)量機(jī)制也能很方便解決互斥問(wèn)題。設(shè)S為進(jìn)程1與進(jìn)程2互斥的信號(hào)量，S的初值為1。把臨界區(qū)置于P(S)和V(S)之間。當(dāng)臨界區(qū)空閑時(shí)，進(jìn)入臨界區(qū)的進(jìn)程執(zhí)行P操作置S為0；再有進(jìn)程執(zhí)行P操作會(huì)被阻塞。

總的來(lái)說(shuō)，同步問(wèn)題中，用前要P，用后要V，兩者之間緊夾動(dòng)作。

5.利用信號(hào)量實(shí)現(xiàn)前驅(qū)關(guān)系

信號(hào)量也可用來(lái)描述程序之間或語(yǔ)句之間的前驅(qū)關(guān)系，有幾對(duì)先后順序，就應(yīng)設(shè)置幾個(gè)信號(hào)量，初值都為0，再通過(guò)判斷信號(hào)量的值，實(shí)現(xiàn)先后關(guān)系的確定。

6.分析進(jìn)程同步和互斥問(wèn)題的方法步驟

1）關(guān)系分析：找出問(wèn)題中的進(jìn)程數(shù)，分析同步與互斥關(guān)系。

2）整理思路：找出解決問(wèn)題的關(guān)鍵點(diǎn)，根據(jù)流程確定P、V操作的順序。

3）設(shè)置信號(hào)量：根據(jù)上面兩步，設(shè)置需要的信號(hào)量，確定初值，完善整理。

2.3.4 管程

在信號(hào)量機(jī)制中，大量的P、V操作容易導(dǎo)致系統(tǒng)死鎖。于是，引入新的進(jìn)程同步工具—管程，它的特性保證了進(jìn)程互斥，無(wú)需程序員自己實(shí)現(xiàn)互斥，降低死鎖發(fā)生的可能性。

1.管程的定義

用數(shù)據(jù)結(jié)構(gòu)描述硬件和軟件資源，忽略它們內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)，把對(duì)該數(shù)據(jù)結(jié)構(gòu)實(shí)施的操作定義為一組過(guò)程，進(jìn)程對(duì)資源的申請(qǐng)和釋放通過(guò)這組過(guò)程實(shí)現(xiàn)，這組過(guò)程可以通過(guò)機(jī)制保證進(jìn)程對(duì)資源的互斥訪問(wèn)，數(shù)據(jù)結(jié)構(gòu)與過(guò)程組成的資源管理程序稱為管程（monitor）。

管程由四部分組成：名稱；局部于管程內(nèi)部的共享結(jié)構(gòu)數(shù)據(jù)說(shuō)明；對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程（或函數(shù)）；對(duì)局部于管程內(nèi)部的共享數(shù)據(jù)設(shè)置初始值的語(yǔ)句。

管程很像一個(gè)類：

1）管程把對(duì)共享資源的操作封裝起來(lái)，管程內(nèi)的共享數(shù)據(jù)結(jié)構(gòu)只能被管程內(nèi)的過(guò)程所訪問(wèn)。一個(gè)進(jìn)程只有通過(guò)調(diào)用管程內(nèi)的過(guò)程才能進(jìn)入管程訪問(wèn)共享資源。對(duì)于上例，外部進(jìn)程只能通過(guò)調(diào)用take_away()過(guò)程來(lái)申請(qǐng)一個(gè)資源；歸還資源也一樣。

2）每次只允許一個(gè)進(jìn)程進(jìn)入管程，實(shí)現(xiàn)互斥。多個(gè)進(jìn)程同時(shí)調(diào)用take_away（），give_back（），則只有某個(gè)進(jìn)程運(yùn)行完它調(diào)用的過(guò)程后，下個(gè)進(jìn)程才能開(kāi)始它自己的調(diào)用過(guò)程。

2.條件變量

當(dāng)一個(gè)進(jìn)程進(jìn)入管程后被阻塞，直到阻塞的原因解除時(shí)，在此期間，如果該進(jìn)程不釋放管程，其它進(jìn)程無(wú)法進(jìn)入管程。所以將阻塞原因定義為條件變量（condition）。原因有多個(gè)，在管程中設(shè)置多個(gè)條件變量。每個(gè)條件變量保存了一個(gè)等待隊(duì)列，用于記錄因該條件變量而阻塞的所有進(jìn)程，對(duì)條件變量只能進(jìn)行兩種操作，wait和signal。

x.wait：當(dāng)x對(duì)應(yīng)的條件不滿足時(shí)，正在調(diào)用管程的進(jìn)程調(diào)用x.wait將自己插入x條件的等待隊(duì)列，并釋放管程，此時(shí)其它進(jìn)程可以使用該管程。

x.signal：x對(duì)應(yīng)的條件發(fā)生了變化，則調(diào)用x.signal，喚醒一個(gè)因x條件而阻塞的進(jìn)程。

條件變量和信號(hào)量的比較：

相似點(diǎn)：條件變量的wait/signal操作類似于信號(hào)量的P/V操作，可以實(shí)現(xiàn)進(jìn)程的阻塞/喚醒。

不同點(diǎn)：條件變量是“沒(méi)有值”的，僅實(shí)現(xiàn)了“排隊(duì)等待”功能；而信號(hào)量是“有值”的，信號(hào)量的值反映了剩余資源數(shù)，在管程中，剩余資源數(shù)用共享數(shù)據(jù)結(jié)構(gòu)記錄。

2.3.5 經(jīng)典同步問(wèn)題

1.生產(chǎn)者-消費(fèi)者問(wèn)題

問(wèn)題描述：一組生產(chǎn)者進(jìn)程和一組消費(fèi)者進(jìn)程共享一個(gè)初始為空、大小為n的緩沖區(qū)，只有緩沖區(qū)沒(méi)滿時(shí)，生產(chǎn)者才能把消息放入緩沖區(qū)，否則必須等待；只有緩沖區(qū)不空時(shí)，消費(fèi)者才能從中取出消息，否則必須等待。由于緩沖區(qū)是臨界資源，它只允許一個(gè)生產(chǎn)者放入消息，或一個(gè)消費(fèi)者從中取出消息。

問(wèn)題分析：

1）關(guān)系分析：生產(chǎn)者和消費(fèi)者對(duì)緩沖區(qū)互斥訪問(wèn)，但兩者又是相互協(xié)作關(guān)系，生產(chǎn)之后才能消費(fèi)，也是同步關(guān)系。

2）整理思路：兩個(gè)進(jìn)程同時(shí)存在互斥和同步關(guān)系，需要解決兩者的PV操作問(wèn)題。

3）信號(hào)量設(shè)置：mutex為互斥信號(hào)量，用于控制互斥訪問(wèn)緩沖池，初始為1；full記錄當(dāng)前緩沖池中狀態(tài)為滿的緩沖區(qū)數(shù)，初始為0。empty記錄緩沖區(qū)為空的緩沖區(qū)數(shù)，初始為n。

seamphore mutex=1;       //臨界區(qū)互斥信號(hào)量
    seamphore empty=n;   //空閑緩沖區(qū)
    seamphore full=0;    //緩沖區(qū)初始化為空
    producer(){          //生產(chǎn)者進(jìn)程
        while(1){
            produce an item in nextp;   // 生產(chǎn)數(shù)據(jù)
            P(empty);（用什么，p一下）     // 獲取空緩沖區(qū)單元
            P(mutex);（互斥夾緊）         // 進(jìn)入臨界區(qū)
            add nextp to buffer;  （行為）//將數(shù)據(jù)放入緩沖區(qū)
            V(mutex);（互斥夾緊）         // 離開(kāi)臨界區(qū)，釋放互斥信號(hào)量
            V(full);（提供什么，V一下）     //滿緩沖區(qū)數(shù)加1
        }
    }
    consumer(){      //消費(fèi)者進(jìn)程
        while(1){
            P(full);    //獲取滿緩沖區(qū)單元
            P(mutex);  //進(jìn)入臨界區(qū)
            remove an item from buffer;  // 從緩沖區(qū)取出數(shù)據(jù)
            V(mutex);    // 離開(kāi)臨界區(qū)，釋放互斥信號(hào)量
            V(empty);    // 空緩沖區(qū)數(shù)加 1
            consume the item;   //消費(fèi)數(shù)據(jù)
        }
    }

該類問(wèn)題要注意對(duì)緩沖區(qū)大小為n的處理，當(dāng)緩沖區(qū)中有空時(shí)，便可對(duì)empty變量執(zhí)行P操作，取走產(chǎn)品后，執(zhí)行V操作釋放空閑區(qū)。對(duì)empty和full的P必須放在對(duì)mutex的P之前。釋放信號(hào)量時(shí)，mutex、full先釋放哪一個(gè)無(wú)所謂。

2.復(fù)雜的生產(chǎn)者-消費(fèi)者問(wèn)題

問(wèn)題描述：有一盤(pán)子，每次只能向其中放入一個(gè)水果，爸爸專放蘋(píng)果，媽媽專放橘子，兒子專吃橘子，女兒專吃蘋(píng)果，只有當(dāng)盤(pán)子空時(shí)才放，當(dāng)盤(pán)中僅有自己吃的水果時(shí)，才取。

問(wèn)題分析：

1）關(guān)系分析：每次只能放一種水果，爸爸媽媽是互斥的關(guān)系，爸爸和女兒，媽媽和兒子是同步的關(guān)系。

2）思路整理：兩個(gè)生產(chǎn)者和兩個(gè)消費(fèi)者連接到大小為1的緩沖區(qū)上。

3）信號(hào)量設(shè)置：將plate設(shè)置成互斥信號(hào)量，初值為1，表示允許放入。apple表示盤(pán)子中是否有蘋(píng)果，初值為0，orange表示盤(pán)子中是否有橘子，初值為0。

semapore plate=1,apple=0,orange=0;
    dad(){
        while(1){
            prepare an apple;
            P(plate);   //互斥向盤(pán)中取、放水果
            put the apple on the plate;  //向盤(pán)中放蘋(píng)果
            V(apple);   // 允許取蘋(píng)果
        }
    }
    mom(){
        while(1){
            prepare an orange;
            P(plate);
            put the orange on the plate;
            V(orange);
        }
    }
    son(){
        while(1){
            P(orange);  //互斥從盤(pán)中取橘子
            take an orange from the plate;
            V(plate);  //允許向盤(pán)中放、取水果
            eat the orange;
        }
    }
    daughter(){
        while(1){
            P(apple);
            take an aplle from the plate;
            V(plate);
            eat the apple;
        }
    }

3.讀者-寫(xiě)者問(wèn)題

問(wèn)題描述：有讀者和寫(xiě)者兩組并發(fā)進(jìn)程，共享一個(gè)文件，當(dāng)兩個(gè)或兩個(gè)以上的讀進(jìn)程同時(shí)訪問(wèn)共享數(shù)據(jù)時(shí)不會(huì)產(chǎn)生副作用，但若某個(gè)寫(xiě)進(jìn)程和其他進(jìn)程同時(shí)訪問(wèn)共享數(shù)據(jù)時(shí)則可能導(dǎo)致數(shù)據(jù)不一致的錯(cuò)誤，因此：

1） 允許多個(gè)讀者可以同時(shí)對(duì)文件執(zhí)行讀操作；

2） 只允許一個(gè)寫(xiě)者往文件中寫(xiě)信息；

3） 任一寫(xiě)者在完成寫(xiě)操作之前不允許其他讀者進(jìn)程或?qū)懻哌M(jìn)程工作；

4） 寫(xiě)者執(zhí)行寫(xiě)操作前，應(yīng)讓已有的讀者和寫(xiě)者全部退出。

問(wèn)題分析：

1）關(guān)系分析：讀者、寫(xiě)者互斥，寫(xiě)者、寫(xiě)者互斥，讀者、讀者不互斥。

2）思路整理：寫(xiě)者和任何進(jìn)程互斥，用P、V操作解決；讀者需實(shí)現(xiàn)與寫(xiě)者互斥，與其它讀者同步，需要用到計(jì)數(shù)器，判斷當(dāng)前是否有讀者讀文件。不同讀者對(duì)計(jì)數(shù)器的訪問(wèn)也是互斥的。

3）信號(hào)量設(shè)置：count為計(jì)數(shù)器，記錄當(dāng)前讀者數(shù)量，初值為0；mutex為互斥信號(hào)量，保護(hù)更新count變量時(shí)的互斥；設(shè)置互斥信號(hào)量rw，用于保護(hù)讀者和寫(xiě)者的互斥訪問(wèn)。

int count=0;
    semaphore mutex=1;
    semaphore rw=1;
    writer(){
        while(1){
            P(rw);   // 互斥訪問(wèn)共享文件
            writing
            V(rw); // 釋放共享文件
        }
    }
    reader(){
        while(1){
            P(mutex);   // 互斥訪問(wèn) count 變量
            if(count==0)  // 當(dāng)?shù)谝粋€(gè)讀進(jìn)程讀共享文件時(shí)
                P(rw)  // 阻止寫(xiě)進(jìn)程
            count++;
            V(mutex);   // 釋放互斥變量 count
            reading;
            P(mutex); 
            count--;
            if(count==0)   // 當(dāng)最后一個(gè)讀進(jìn)程讀完共享文件
                V(rw);  // 允許寫(xiě)進(jìn)程寫(xiě)
            V(mutex);
        }
    }

此種方式下，可能導(dǎo)致寫(xiě)進(jìn)程長(zhǎng)時(shí)間等待甚至出現(xiàn)“餓死”的情況。改變上面這種讀進(jìn)程優(yōu)先，讓寫(xiě)進(jìn)程優(yōu)先，需要再增加一個(gè)信號(hào)量，并在上面的 writer() 和 reader() 函數(shù)中各增加一對(duì)PV操作。如下：

int count=0;
    semaphore mutex=1;
    semaphore rw=1;
    semaphore w=1; // 實(shí)現(xiàn)寫(xiě)者優(yōu)先
    writer(){
        while(1){
            P(w);  // 在無(wú)寫(xiě)進(jìn)程請(qǐng)求時(shí)進(jìn)入
            P(rw);   // 互斥訪問(wèn)共享文件
            writing
            V(rw); // 釋放共享文件
            V(w);   // 恢復(fù)對(duì)共享文件的訪問(wèn)
        }
    }
    reader(){
        while(1){
            P(w);  
            P(mutex);   // 互斥訪問(wèn) count 變量
            if(count==0)  // 當(dāng)?shù)谝粋€(gè)讀進(jìn)程讀共享文件時(shí)
                P(rw)  // 阻止寫(xiě)進(jìn)程
            count++;
            V(mutex);   // 釋放互斥變量 count
            V(w);
            reading;
            P(mutex); 
            count--;
            if(count==0)   // 當(dāng)最后一個(gè)讀進(jìn)程讀完共享文件
                V(rw);  // 允許寫(xiě)進(jìn)程寫(xiě)
            V(mutex);
        }
    }

此種算法又叫做讀寫(xiě)公平法。

4.哲學(xué)家進(jìn)餐問(wèn)題

問(wèn)題描述：一張圓桌上坐著5名哲學(xué)家，每?jī)擅軐W(xué)家之間的桌子上擺著一根筷子，兩根筷子之間是一碗米飯。哲學(xué)家傾注畢生精力于思考和進(jìn)餐，哲學(xué)家思考時(shí)不影響其他人。只有當(dāng)哲學(xué)家饑餓時(shí)，才試圖拿起左、右兩根筷子——一根一根地拿起。若筷子已在他人手上，則需要等待。饑餓的哲學(xué)家只有同時(shí)拿到了兩根筷子才能開(kāi)始進(jìn)餐，進(jìn)餐完畢，放下筷子繼續(xù)思考。

問(wèn)題分析：

1）關(guān)系分析：左右鄰座對(duì)其中間的筷子的訪問(wèn)是互斥關(guān)系。

2）整理思路：哲學(xué)家拿到左右兩根筷子不造成死鎖或饑餓現(xiàn)象，解決方法有兩個(gè)：第一個(gè)同時(shí)讓他們拿兩根筷子，第二個(gè)對(duì)每個(gè)哲學(xué)家的動(dòng)作制定規(guī)則。

3）信號(hào)量設(shè)定：互斥信號(hào)量數(shù)組chopstick[5]={1，1，1，1，1}，哲學(xué)家按順序編號(hào)0-4，哲學(xué)家i左邊筷子編號(hào)為i，哲學(xué)家右邊筷子編號(hào)為（i+1）%5.

semaphore chopstick[5]={1,1,1,1,1};
    Pi(){
        do{
            P(chopstick[i]);  //取左邊筷子
            P(chopstick[(i+1)%5]);// 取右邊筷子
            eat;
            V(chopstick[i]);  //放回左邊筷子
            V(chopstick[(i+1)%5]);// 放回右邊筷子
            think;
        }while(1);
    }

此算法存在的問(wèn)題就是，當(dāng)5名哲學(xué)家都想要進(jìn)餐并分別拿起左邊的筷子時(shí)，所有的筷子將被拿光，等到他們?cè)傧肽闷鹩疫叺目曜訒r(shí)，就會(huì)發(fā)生全被阻塞，出現(xiàn)死鎖。若要避免此種情況，可以增加限制條件，如至多允許4名哲學(xué)家同時(shí)進(jìn)餐；僅當(dāng)一名哲學(xué)家左右兩邊筷子都可以用時(shí)，才允許他抓起筷子；對(duì)哲學(xué)家順序編號(hào)，奇數(shù)號(hào)哲學(xué)家先拿起左邊筷子，然后拿起右邊的，而偶數(shù)哲學(xué)家相反。

用正確的規(guī)則如下：假設(shè)采用第二種方法，當(dāng)一名哲學(xué)家左右兩邊的筷子都可用時(shí)，才允許他抓起筷子。

semaphore chopstick[5]={1,1,1,1,1};
    semaphore mutex=1;
    Pi(){
        do{
            P(mutex);  // 在取筷子前獲得互斥量
            P(chopstick[i]);  //取左邊筷子
            P(chopstick[(i+1)%5]);// 取右邊筷子
            V(mutex);  // 釋放取筷子的信號(hào)量
            eat;
            V(chopstick[i]);  //放回左邊筷子
            V(chopstick[(i+1)%5]);// 放回右邊筷子
            think;
        }while(1);
    }

5.吸煙者問(wèn)題

問(wèn)題描述：假設(shè)一個(gè)系統(tǒng)有三個(gè)抽煙者進(jìn)程和一個(gè)供應(yīng)者進(jìn)程。每個(gè)抽煙者不停地卷煙并抽掉它，但要卷起一支煙，抽煙者需要三種材料：煙草、紙和膠水。三個(gè)抽煙者中，第一個(gè)擁有煙草，第二個(gè)擁有紙，第三個(gè)擁有膠水。供應(yīng)者進(jìn)程無(wú)限地提供三種材料，供應(yīng)者每次將兩種材料放到桌子上，擁有剩下那種材料的抽煙者卷一根煙并抽掉它，并給供應(yīng)者一個(gè)信號(hào)告訴已完成，此時(shí)供應(yīng)者就會(huì)將另外兩種材料放到桌子上，循環(huán)反復(fù)如此。

問(wèn)題分析：

1）關(guān)系分析：供應(yīng)者與三個(gè)抽煙者是同步關(guān)系。三個(gè)抽煙者互斥。

2）整理思路：供應(yīng)者作為生產(chǎn)者向三個(gè)抽煙者提供材料。

3）信號(hào)量設(shè)置：offer1、offer2、offer3分別表示煙草和紙組合的資源、煙草和膠水組合的資源、紙和膠水組合的資源，finish用于互斥進(jìn)行抽煙動(dòng)作。

int random;  // 存儲(chǔ)隨機(jī)數(shù)
    semaphore offer1=0;
    semaphore offer2=0;
    semaphore offer3=0;
    semaphore finish=0;
    process P1(){//供應(yīng)者
        while(1){
            random=a random num;
            random=random%3;
            if(random==0)
                V(offer1);  // 提供煙草和紙
            else if(random==1)
                V(offer2);  // 提供煙草和膠水
            else
                V(offer3); //提供紙和膠水
            put on ;  // 將材料放在桌子上
            P(finish);
        }
    }
    process P2(){//擁有煙草者
        while(1){
            P(offer3);
            working;  // 拿起紙和膠水，卷成煙，抽掉
            V(finish);
        }
    }
    process P3(){//擁有紙者
        while(1){
            P(offer2);
            working;  // 拿起煙草和膠水，卷成煙，抽掉
            V(finish);
        }
    }
    process P4(){//擁有膠水者
        while(1){
            P(offer1);
            working;  // 拿起紙和煙草，卷成煙，抽掉
            V(finish);
        }
    }

2.4 死鎖

2.4.1 死鎖的概念

1.死鎖的定義

多道程序系統(tǒng)中，雖然提高了系統(tǒng)的處理能力，但多個(gè)進(jìn)程競(jìng)爭(zhēng)同一資源會(huì)造成僵局，我們稱這種僵局為死鎖。

2.死鎖產(chǎn)生的原因

（1）系統(tǒng)資源的競(jìng)爭(zhēng)

不可剝奪的資源數(shù)量小于進(jìn)程數(shù)，此時(shí)對(duì)其的競(jìng)爭(zhēng)可能會(huì)引起死鎖，但對(duì)可剝奪資源的競(jìng)爭(zhēng)是不會(huì)引起死鎖的。

（2）進(jìn)程推進(jìn)順序非法

進(jìn)程在運(yùn)行過(guò)程中，請(qǐng)求和釋放資源的順序不當(dāng)，當(dāng)兩個(gè)進(jìn)程擁有不同資源時(shí)，這兩個(gè)進(jìn)程互相申請(qǐng)對(duì)方擁有資源時(shí)，產(chǎn)生死鎖。

信號(hào)量使用不當(dāng)也會(huì)造成死鎖，此時(shí)進(jìn)程間彼此相互等待對(duì)方發(fā)來(lái)的消息，也會(huì)引起死鎖。

（3）死鎖產(chǎn)生的必要條件

有四個(gè)，任意一個(gè)不成立，死鎖就不會(huì)發(fā)生：

（1）互斥條件：進(jìn)程要求所分配資源進(jìn)行排他性控制，若有進(jìn)程申請(qǐng)此資源，則只能等待。

（2）不剝奪條件：資源未被使用完時(shí)，不會(huì)被奪走，只能由該進(jìn)程釋放。

（3）請(qǐng)求并保持條件：進(jìn)程已經(jīng)保持了至少一個(gè)資源，但又提出了新的資源請(qǐng)求，該資源等待，同時(shí)不釋放已經(jīng)保持的資源。

（4）循環(huán)等待條件：存在一種進(jìn)程資源的循環(huán)等待鏈，鏈中每個(gè)進(jìn)程已獲得的資源同時(shí)被鏈中下一個(gè)進(jìn)程所請(qǐng)求。

2.4.2 死鎖的處理策略

必須破壞上述四個(gè)條件之一，或允許死鎖產(chǎn)生，且能檢測(cè)出死鎖，并有能力實(shí)現(xiàn)恢復(fù)。

1.預(yù)防死鎖：設(shè)置某些限制條件，破壞產(chǎn)生死鎖產(chǎn)生的必要條件。

2.避免死鎖：在資源分配過(guò)程中，用某種方法防止系統(tǒng)進(jìn)入不安全狀態(tài)，從而避免死鎖。

3.死鎖的檢測(cè)及解除：允許發(fā)生死鎖，但及時(shí)檢測(cè)發(fā)現(xiàn)死鎖，并采取某個(gè)措施解除死鎖。

預(yù)防死鎖和避免死鎖都屬于事先預(yù)防策略，預(yù)防的限制條件較嚴(yán)格，實(shí)現(xiàn)簡(jiǎn)單，但導(dǎo)致效率低；避免死鎖的限制條件相對(duì)寬松，資源分配后需要通過(guò)算法來(lái)判斷是否進(jìn)入不安全狀態(tài)，實(shí)現(xiàn)復(fù)雜。

各種資源的比較：

2.4.3 預(yù)防死鎖

防止死鎖的發(fā)生只需破壞死鎖產(chǎn)生的4個(gè)必要條件之一即可。

1.破壞互斥條件：若允許系統(tǒng)資源都能共享使用，系統(tǒng)不會(huì)死鎖，但有些資源不能同時(shí)訪問(wèn)，有些場(chǎng)合需要保護(hù)某種資源的互斥性。

2.破壞不剝奪條件：當(dāng)某個(gè)進(jìn)程保持了某個(gè)資源，它申請(qǐng)新的資源得不到滿足時(shí)，它必須釋放已經(jīng)保持的所有資源，以后需要時(shí)再申請(qǐng)。這種策略會(huì)增加系統(tǒng)開(kāi)銷，降低系統(tǒng)吞吐量，所以這種方法常用于狀態(tài)易于保存和恢復(fù)的資源，如CPU的寄存器及內(nèi)存資源。

3.破環(huán)請(qǐng)求并保持條件：采用預(yù)先靜態(tài)分配方法，即進(jìn)程在運(yùn)行前一次申請(qǐng)完它所需要的全部資源，在資源未滿足前，不把它投入運(yùn)行。一旦投入運(yùn)行，資源一直歸它所有，不再提出其它資源請(qǐng)求，保證不死鎖。此策略會(huì)導(dǎo)致系統(tǒng)資源被浪費(fèi)，并且由于個(gè)別資源長(zhǎng)期被某個(gè)進(jìn)程占用，導(dǎo)致饑餓現(xiàn)象。

4.破壞循環(huán)等待條件：采用順序資源分配法，先給資源編號(hào)，規(guī)定進(jìn)程必須按照編號(hào)申請(qǐng)資源，同類資源一次申請(qǐng)完成，例如，某個(gè)進(jìn)程申請(qǐng)5號(hào)資源，它以后只能申請(qǐng)5號(hào)之后的資源。這種策略的問(wèn)題是編號(hào)必須相對(duì)穩(wěn)定，限制了新類型設(shè)備的增加，且會(huì)經(jīng)常發(fā)生作業(yè)使用資源的順序與系統(tǒng)規(guī)定順序不同的情況，造成資源浪費(fèi)。

2.4.4 避免死鎖

在資源動(dòng)態(tài)分配過(guò)程中，防止系統(tǒng)進(jìn)入不安全的狀態(tài)，避免死鎖的發(fā)生，限制弱，系統(tǒng)性能高。

1.系統(tǒng)安全狀態(tài)

安全狀態(tài)是指系統(tǒng)能按照某種進(jìn)程推進(jìn)順序?yàn)槊總€(gè)進(jìn)程分配所需資源，直至滿足每個(gè)進(jìn)程對(duì)資源的最大需求，使每個(gè)進(jìn)程都可順序完成，反之則稱為不安全狀態(tài)。系統(tǒng)進(jìn)入不安全狀態(tài)時(shí)，可能導(dǎo)致死鎖。

2.銀行家算法

思想是把操作系統(tǒng)視為銀行家，資源相當(dāng)于資金，請(qǐng)求分配資源相當(dāng)于申請(qǐng)貸款。進(jìn)程運(yùn)行之前先聲明對(duì)各種資源的最大需求量，當(dāng)進(jìn)程在執(zhí)行中繼續(xù)申請(qǐng)資源時(shí)，先測(cè)試該進(jìn)程已占用的資源數(shù)與本次申請(qǐng)的資源數(shù)之和是否超過(guò)該進(jìn)程聲明的最大需求量，若能滿足則按當(dāng)前的申請(qǐng)量分配資源，否則要推遲分配。

（1）數(shù)據(jù)結(jié)構(gòu)描述

可利用資源向量Available：含有m個(gè)元素的數(shù)組，其中每個(gè)元素代表一類可用的資源數(shù)目。

最大需求矩陣Max：n*m矩陣，定義系統(tǒng)中n個(gè)進(jìn)程中的每個(gè)進(jìn)程對(duì)m類資源的最大需求。簡(jiǎn)單來(lái)說(shuō)，一行代表一個(gè)進(jìn)程，一列代表一類資源。

分配矩陣：Allocation：n*m矩陣，定義系統(tǒng)中每類資源當(dāng)前分配給每個(gè)進(jìn)程的資源數(shù)。

需求矩陣：Need：n*m矩陣，定義每個(gè)進(jìn)程接下來(lái)還需多少資源。

三個(gè)矩陣關(guān)系：Need=Max-Allocation

一般情況下，Max和Allocation是已知條件，求Need是第一步。

（2）銀行家算法描述：

先Request，若Request的量≤Need的量成立（不成立，則認(rèn)為出錯(cuò)。），再判斷Request的量≤Available的量成立（若不成立，該進(jìn)程必須等待），系統(tǒng)嘗試將資源分配給進(jìn)程，并修改下面數(shù)據(jù)結(jié)構(gòu)的數(shù)值，其中：

Available=Available-Request；Allocation=Allocation+Request；Need=Need-Request。

最后，系統(tǒng)執(zhí)行安全性算法，檢測(cè)此次資源分配后，系統(tǒng)是否處于安全狀態(tài)，若安全，則正式分配，不安全，放棄分配，讓進(jìn)程等待。

（3）安全性算法

設(shè)置工作向量Work，有m個(gè)元素，表示剩余的可用資源數(shù)，安全性算法開(kāi)始時(shí)，work=available。

步驟一：初始時(shí)安全序列為空；

步驟二：從Need矩陣中找出符合下面條件的行：該行對(duì)應(yīng)的進(jìn)程不在安全序列中，而且該行小于等于Work向量，找到后，把對(duì)應(yīng)進(jìn)程加入安全序列，若找不到，執(zhí)行步驟四；

步驟三：進(jìn)程進(jìn)入安全序列后，可順利執(zhí)行，直至完成，并釋放分配給它的資源，執(zhí)行Work=Work+Allocation，返回步驟二；

步驟四：若此時(shí)安全序列中已有所有進(jìn)程，則系統(tǒng)處于安全狀態(tài)，否則系統(tǒng)處于不安全狀態(tài)。

2.4.5 死鎖檢測(cè)和解除

系統(tǒng)在分配資源時(shí)不采取任何措施，應(yīng)會(huì)提供死鎖檢測(cè)和解除的手段。

1.資源分配圖

圓圈代表一個(gè)進(jìn)程，框代表一類資源。由于一種類型的資源可能有多個(gè)，框中的一個(gè)圓圈代表一類資源中的一個(gè)資源。從進(jìn)程到資源的有向邊稱為請(qǐng)求邊，表示申請(qǐng)資源；從資源到進(jìn)程的邊稱為分配邊，表示資源分配給進(jìn)程。

2.死鎖定理

簡(jiǎn)化資源分配圖可檢測(cè)系統(tǒng)狀態(tài)S是否為死鎖狀態(tài)。簡(jiǎn)化方法如下：

1）在資源分配圖中，找出既不阻塞，又不孤點(diǎn)的進(jìn)程（找出一條有向邊與它相連，且該有向邊對(duì)應(yīng)資源的申請(qǐng)數(shù)量小于等于系統(tǒng)中已有的空閑資源數(shù)量），若所有連接該進(jìn)程的邊均滿足上述條件，則這個(gè)進(jìn)程能繼續(xù)運(yùn)行直至完成，然后釋放它所占有的資源。之后消去它所有的請(qǐng)求邊和分配邊，使之稱為孤立的點(diǎn)?？偨Y(jié)為找圈消邊。

2）進(jìn)程所釋放的資源，可以喚醒某些因等待這些資源而阻塞的進(jìn)程，原來(lái)阻塞進(jìn)程可能變?yōu)榉亲枞M(jìn)程。根據(jù)1）中的方法進(jìn)行簡(jiǎn)化，若能消除所有邊，稱該圖是可完全可以簡(jiǎn)化的。S為死鎖的條件是當(dāng)且僅當(dāng)S狀態(tài)的資源分配圖是不可完全簡(jiǎn)化的，稱為死鎖條件。

3.死鎖解除

1）資源剝奪法：掛起某些死鎖的進(jìn)程，并搶占它的資源，將這些資源分配給其它的死鎖進(jìn)程。但應(yīng)防止被掛起的進(jìn)程長(zhǎng)時(shí)間得不到資源而處于資源匱乏的狀態(tài)。

2）撤銷進(jìn)程法：強(qiáng)制撤銷部分甚至全部死鎖進(jìn)程并剝奪這些進(jìn)程的資源。撤銷的原則可以按進(jìn)程優(yōu)先級(jí)和撤銷進(jìn)程代價(jià)的高低進(jìn)行。

3）進(jìn)程回退法：讓若干個(gè)進(jìn)程回退到足以回避死鎖的地步，進(jìn)程回退時(shí)自愿放棄資源而非被剝奪。要求系統(tǒng)保持進(jìn)程的歷史信息，設(shè)置還原點(diǎn)。