1第二章

進程描述和控制

程序（Program）類似：建好的工廠，未開啟運行2啟動，忙碌起來，才能反映效果。描述這個忙碌的過程---進程(process）3協同完成一個任務進程狀態4不能無休止運動下去，生命有終結時。添加“創建”和“終止”，變成5狀態的進程5線程（threshold）房間里的具體的工作人員，多個人共享一個房間（資源）6進程可包含多個線程7進程和線程關系8進程：資源擁有者，動態的。（目標：協同完成同一個任務！）9線程一般不擁有資源，是受派遣者（只負責：從這條線過的，必須繳費）10進程的基本概念

2.1前趨圖程序執行2.2

進程的描述程序并發執行時，必會共享系統資源。進程，是描述程序執行時的動態特征P3211

程序的順序執行及其特征1.程序的順序執行程序的執行：順序執行和并發執行；一個應用程序分成若干個程序段，各程序段之間，必須按照某種先后次序順序執行。用結點(Node)代表各程序段的操作(I代表輸入操作，C代表計算操作，P代表打印操作)，用箭頭指示操作的先后次序;一個程序段中的多條語句也有執行順序問題12執行順序問題對一個程序段中的多條語句來說，也有一個執行順序問題，例如對于下述三條語句的程序段:S1:a:=x+y；S2:b:=a-5；S3:c:=b+1；

其中，語句S2必須在語句S1之后(即a被賦值)才能執行；同樣，語句S3也只能在b被賦值后才能執行。因此，這三條語句應按圖所示的順序執行。

13圖2程序的順序執行

14三個程序間順序執行考慮時間上關系，如下所示:t輸入：計算：輸出：I1C1P1I2C2P2I3C3P3

t0t1t2t3t4t5t6t7t8t9t10Δt程序1：I1C1P1程序2：程序3：I2C2P2I3C3P39個Δt

15順序執行與并發執行任意程序都存在著Ii→Ci→Pi

這樣的前驅關系，因而對一個用戶程序的輸入、計算和打印這三個操作，必須順序執行。但在多道環境下并不存在或并不要求Pi→Ii+1

關系，即Ii、Cj

和Pk（i≠j≠k）之間并不存在前驅關系。因而在對一批程序處理時，可使它們并發執行，這就產生了并發操作。16三個程序并發執行的前驅圖

輸入：計算：輸出：

t0t1t2t3t4t5t6ΔttI1I2I3C1C2C3P1P2P3時間:5個Δt并行并行并行17

2.程序順序執行時的特征1.順序性

處理機的操作嚴格按照程序所規定的順序執行，即每一操作必須在上一個操作結束之后開始（可能有分支/循環）2.封閉性程序封閉的環境下運行（獨占全部資源，計算機的資源狀態只有該程序的執行邏輯決定）。程序一旦開始執行，其執行結果不受外界因素影響。3.可再現性程序執行的初始條件相同，則結果相同（連續不停頓的執行，或“停停走走”地執行）P33182.1.3程序并發執行并發（concurrency）?

并行（parallellism）

并行：兩個或者多個事件在同一時刻發生

并發：兩個或多個事件在同一時間間隔發生并行：在不同實體上的多個事件

并發：在同一實體上的多個事件并行：在多臺處理器上同時處理多個任務

并發：在一臺處理器上“同時”處理多個任務并行：三個人同時吃三個饅頭并發：一個人同時吃三個饅頭重點掌握！19處理機1處理機1處理機1處理機1處理機1處理機1處理機2處理機2處理機3處理機320212.1.3程序并發執行1.程序的并發執行

一個作業的輸入、計算和打印三個操作，必須順序執行;并不存在Pi→Ii+1的關系，在對一批程序進行處理時，可使它們并發執行22t輸入：計算：輸出：I1C1P1I2C2P2I3C3P3

t0t1t2t3t4t5t6t7t8t9t10Δt9個Δt

輸入：計算：輸出：

t0t1t2t3t4t5t6ΔttI1I2I3C1C2C3P1P2P3時間:5個Δt并行并行并行23對于具有下述四條語句的程序段：S1:a:=x+2S2:b:=y+4S3:c:=a+bS4:d:=c+b

圖2-4四條語句的前趨關系

242.程序并發執行時的特征間斷性(異步性)程序并發執行時，由于共享系統資源和相互合作，形成了相互制約的關系，導致“執行

暫停

執行”這種間斷性的活動252.程序并發執行時的特征2.失去封閉性多個程序共享系統資源，因而資源的狀態將由多個程序來改變（不一個人所有，不能關門獨占）3.不可再現性失去了封閉性，也將導致其失去可再現性(不上鎖門，沒法保證明天再來時，內容不變）262.2進程的描述1.

進程的特征和定義2.

進程的三種基本狀態3.

掛起狀態、創建狀態和終止狀態4.進程管理的數據結構P35271.進程的特征和定義為使程序能并發執行，且為了對并發執行的程序加以描述和控制，引入了“進程”。“進程”！28進程的特征與狀態進程的特征結構特征:程序段、相關數據段和PCB(進程映像)1.動態性:由創建而產生,由調度而執行,由撤消而消亡2.并發性：多進程同存于內存，在一段時間內同時運行3.獨立性：進程實體是一個能獨立運行、獨立分配資源和獨立接受調度的基本單位4.異步性：各自獨立的、不可預知的速度向前推迸（異步方式運行）29

結構特征早期的UNIX版本中，把這三部分總稱為“進程映像”。在許多情況下所說的進程，實際上是指進程實體，例如，所謂創建進程，實質上是創建進程實體中的PCB；而撤消進程，實質上是撤消進程的PCB。

通常的程序是不能并發執行的。為使程序(含數據)能獨立運行，應為之配置一進程控制塊，即PCB(ProcessControlBlock)；進程實體包含3部分：程序段、相關數據段和PCB30

1)動態性進程實體有一定的生命期，而程序則只是一組有序指令的集合，并存放于某種介質上，其本身并不具有運動的含義，因而是靜態的。進程的實質是進程實體的一次執行過程，因此，動態性是進程的最基本的特征。動態性還表現在：“它由創建而產生，由調度而執行，由撤消而消亡”。31

2)并發性引入進程的目的，正是為了使進程實體能和其它進程實體并發執行；而程序(沒有建立PCB)是不能并發執行的。

指多個進程實體同存于內存中，且能在一段時間內同時運行。并發性是進程的重要特征，同時也成為OS的重要特征。323)獨立性傳統OS中，獨立性是指進程實體是一個能獨立運行、獨立分配資源和獨立接受調度的基本單位。凡未建立PCB的程序都不能作為一個獨立的單位參與運行。4)異步性進程按各自獨立的、不可預知的速度向前推進，或說進程實體按異步方式運行。

33進程的定義許多人從不同的角度下過定義，較典型的進程定義有：(1)進程是程序的一次執行。(2)進程是一個程序及其數據在處理機上順序執行時所發生的活動。(3)進程是程序在一個數據集合上運行的過程，它是系統進行資源分配和調度的一個獨立單位。

進程是進程實體的運行過程，是系統進行資源分配和調度的一個獨立單位。34就緒(Ready)狀態進程已分配到除CPU以外的所有必要資源的狀態稱為就緒狀態。處于就緒狀態的進程可能有多個，常排成一個隊列，稱為就緒隊列。執行狀態進程已獲得CPU，其程序正在執行。阻塞狀態由于發生某事件而暫時無法繼續執行，放棄處理機而處于暫停狀態，把這種暫停狀態稱為阻塞狀態(也稱為等待/鎖狀態)。2.進程的三種基本狀態及轉換35進程阻塞的典型事件有：請求I/O，申請緩沖空間等。處于阻塞狀態的進程排成隊列。有的系統則根據阻塞原因的不同，把處于阻塞狀態的進程排成多個隊列。進程的三種基本狀態及其轉換

重點掌握！36進程掛起的原因(1)終端用戶的請求:

程序運行有問題時，希望暫時使程序靜止下來。進程暫停執行；進程處于就緒狀態,暫不調度。這種靜止狀態稱為掛起狀態。

(2)父進程請求:有時父進程希望掛起自己的某個子進程，以便考查和修改該子進程，或協調各子進程間的活動。

(3)負荷調節的需要(4)操作系統的需要:操作系統有時希望掛起某些進程，以便檢查運行中的資源使用情況或進行記賬。37進程狀態的轉換在引入掛起狀態后，將增加從掛起狀態(靜止狀態)到非掛起狀態(活動狀態)的轉換；或者相反。有以下幾種情況：(1)活動就緒

靜止就緒(Readys)[Suspend](2)活動阻塞

靜止阻塞(Blockeds)[Suspend](3)靜止就緒

活動就緒(Readya)[Active](4)靜止阻塞

活動阻塞(Blockeda)[Active]38具有掛起狀態的進程狀態圖391)創建狀態

3.創建狀態和終止狀態

創建一個進程一般要通過兩個步驟：

①

為新進程創建PCB，并填寫必要的管理信息。

②

進程轉入就緒狀態并插入就緒隊列之中。

新進程被創建時，分配PCB并填寫進程標識等信息，但由于進程所必需的資源或其它信息尚未得到，即創建工作尚未完成，進程還不能被調度運行，這時的狀態就是創建狀態。引入創建狀態，是為了保證進程調度必須在創建工作完成后進行，以確保對進程控制塊操作的完整性。402)終止狀態導致進程終止的3原因：（1）（自然死亡）進程到達了自然結束點（2）（病死）出現了無法克服的錯誤（3）（他殺）被操作系統所終結，或被其他有終止權的進程所終結

進程的終止也要通過兩個步驟：

①

等待操作系統進行善后處理。

②將其PCB清零，并將PCB空間返還系統。41

增加創建狀態和終止狀態后，進程的三種基本狀態及轉換圖衍變為五種狀態及轉換關系圖進程的五種基本狀態及轉換

重點掌握！42圖2-8

具有創建、終止和掛起狀態的進程狀態圖

(1)創建→活動就緒：系統性能和內存均允許的情況下，完成對進程創建的必要操作后，系統進程將進程的狀態轉換為活動就緒狀態。(2)創建→靜止就緒：并不分配給新建進程所需資源（主要是主存），系統進程將進程狀態轉為靜止就緒狀態，對換到外存，不再參與調度，此時進程創建工作尚未完成。P39432.

進程控制塊

(PCB,processcontrolblock)進程控制塊的作用進程控制塊中的信息進程控制塊的組織方式P40441.進程控制塊的作用為描述和控制進程的運行，系統為每個進程定義一個數據結構——進程控制塊PCB(ProcessControlBlock)，它是進程實體的一部分，是操作系統中最重要的記錄型數據結構。PCB中記錄了操作系統所需的、用于描述進程的當前情況以及控制進程運行的全部信息。作用：使一個在多道程序環境下不能獨立運行的程序(含數據)，成為一個能獨立運行的基本單位，一個能與其它進程并發執行的進程。系統利用PCB來控制和管理進程，所以PCB是系統感知進程存在的唯一標志

，進程與PCB是一一對應45涉及PCB的操作：在進程的整個生命期中，系統總是通過PCB對進程進行控制。所以PCB是進程存在的唯一標志。

1.OS要調度某進程執行時，要從進程的PCB中查出其現行狀態及優先級；2.調度到某進程后，根據PCB中保存的處理機狀態信息，設置該進程運行現場，并根據其PCB中的程序和數據的內存始址，找到程序和數據；3.進程執行過程中，合作進程間需要進程同步、通信或訪問文件時，也都要訪問PCB；4.進程由于某種原因而暫停執行時，也要將斷點的處理機環境保存在PCB中。46當系統創建一個新進程時，就為它建立了一個PCB；進程結束時又回收其PCB，進程于是也隨之消亡。PCB可被操作系統讀寫，如調度程序、資源分配程序、中斷處理程序以及監督和分析程序等讀或修改。因為PCB經常被系統訪問，尤其是被運行頻率很高的進程及分派程序訪問，故PCB應常駐內存。PCB專區:系統將所有的PCB組織成若干個鏈表(或隊列)，存放在操作系統中專門開辟的PCB區內。

如：在Linux系統中用task_struct來描述每個進程的進程控制塊，Windows操作系統中則使用一個執行體進程塊(EPROCESS)來表示進程對象的基本屬性。

472.進程控制塊中的信息進程標識符:進程標識符用于惟一地標識一個進程（內部標識符和外部標識符）處理機狀態:處理機的各種寄存器的內容組成(通用寄存器、指令計數器、程序狀態字PSW、用戶棧指針)進程調度信息：與進程調度和進程對換有關的信息,包括：①進程狀態；②進程優先級；③進程調度所需的其它信息；④事件等。進程控制信息：①程序和數據的地址②進程同步和通信機制，如消息隊列指針、信號量等③資源清單④鏈接指針482.3

進程控制1進程的創建2進程的終止3進程的阻塞和喚醒4進程的掛起和激活進程控制是進程管理中最基本的功能（1）創建新進程，（2）終止進程（終止因出現某事件而無法運行的進程），（3）進程運行中的狀態轉換進程控制一般是由OS的內核中的原語來實現的492.3.2

進程的創建1.進程圖(ProcessGraph)用于描述一個進程的家族關系的有向樹圖2-13

進程樹

50

進程的創建在進程D創建了進程I之后，稱D是I的父進程(ParentProcess)，I是D的子進程(ProgenyProcess)。子進程可以繼承父進程的資源;在PCB中設置有家族關系表項來表示父子進程關系512.引起進程創建的事件為使程序能運行，就必須為它創建進程。導致進程創建的典型事件有四類：1.用戶登錄:

分時系統中的合法用戶進入系統,將為該終端建立一個進程，并把它放入就緒隊列。2.作業調度:

調度到某作業時，將該作業裝入內存，分配必要的資源，并立即為它創建進程，放入就緒隊列中。3.提供服務:

用戶程序提出某種請求后，系統將專門創建一個進程來提供用戶所需要的服務(如打印請求)4.應用請求:

應用進程自己創建一個新進程，以便使新進程以并發運行方式完成特定任務52創建新進程,調用進程創建原語Creat(),有以下步驟：3.進程的創建(CreationofProcess)1.申請空白PCB(申請唯一的標識符)2.為新進程分配資源為新進程的程序和數據以及用戶棧分配必要的內存空間3.初始化PCB（進程控制塊）

初始化標識信息;

初始化處理機狀態信息，使程序計數器指向程序的入口地址，使棧指針指向棧頂；

初始化處理機控制信息(狀態,優先級)4.將新進程插入就緒隊列532.3.3

進程的終止1.引起進程終止的事件正常結束（壽終正寢）異常結束（病死）外界干預（被殺）2.進程的終止過程P4554異常結束運行期間，出現錯誤和故障，被迫終止。常見的異常事件：1.越界錯誤：程序所訪問的存儲區已越出進程的區域。2.保護錯：指進程試圖去訪問一個不允許訪問的資源或文件，或者以不適當的方式進行訪問，例如，進程試圖去寫一個只讀文件。3.非法指令：指程序試圖去執行一條不存在的指令。出現該錯誤的原因，可能是程序錯誤地轉移到數據區，把數據當成了指令。554.特權指令錯：用戶進程試圖去執行一條只允許OS執行的指令。5.運行超時：執行時間超過指定的最大值。6.等待超時：等待某事件的時間超過最大值。7.算術運算錯：試圖去執行一個被禁止的運算(如被0除)。8.I/O故障：I/O過程中發生了錯誤56外界干預1.OS/操作員干預如:發生了死鎖，OS/操作員終止該進程。2.父進程請求由于父進程具有終止自己的任何子孫進程的權力；當父進程提出請求時，系統將終止該進程。3.父進程終止父進程終止時，OS也將它的所有子孫進程終止。572.進程的終止過程①

Terminatewho？根據進程標識符從PCB集合檢索出該進程的PCB

②Excecute！進程處于執行狀態，則立即終止執行，并設置調度標志為真(重新調度用)

③剪除羽翼：進程若有子孫進程，則將所有子孫進程予以終止

④沒收財產：進程的所有資源歸還給系統/父進程

⑤

重新投胎：進程移出所在的PCB隊列，等待其他程序來搜集信息。582.2.4

進程的阻塞和喚醒1.誰引起的？（引起進程阻塞/喚醒的事件）2.如何阻塞？（阻塞過程）3.如何喚醒？（喚醒過程）P4659

1.誰引起的？

1.請求系統服務，需等待！請求OS提供服務時，OS在忙別的，不能滿足該進程的要求，進程只能轉變為阻塞狀態，等!

2.啟動過某操作,等它完成！進程啟動某種操作后，如果進程必須在該操作完成之后才能繼續執行，則進程必須阻塞，以等待操作完成。

3.新數據尚未到達，等！對相互合作的進程，如果一個進程需先獲得另一進程提供的數據后才能對數據進行處理，只要所需數據尚未到達，該進程只有(等待)阻塞。

4.無新工作可做，等！特定功能的系統進程，每當這種進程完成任務后，便把自己阻塞起來以等待新任務到來602.進程阻塞過程1.調用原語:進程無法繼續執行，調用阻塞原語block()把自己阻塞(進程自身的一種主動行為)2.更改狀態：進入block過程后，應先立即停止執行，把進程控制塊中的現行狀態由“執行”改為“阻塞”，并將其插入相應的阻塞隊列

3.重新投胎：轉調度程序進行重新調度，將處理機分配給另一就緒進程并進行切換，即:保留被阻塞進程的處理機狀態(在PCB中)，再按新進程的PCB中的處理機狀態設置CPU的環境。

613.進程喚醒過程阻塞進程所期待的事件出現時，則由有關進程調用喚醒原語wakeup()，將等待該事件的進程喚醒①把被阻塞的進程從等待該事件的阻塞隊列中移出，將其PCB中的現行狀態由阻塞改為就緒

②將核PCB插入到就緒隊列中block原語和wakeup原語是一對作用相反的原語。某進程調用了阻塞原語，則必須在與之相合作的另一進程中/其他相關的進程中安排喚醒原語，以能喚醒阻塞進程；否則，被阻塞進程將會因不能被喚醒而長久地處于阻塞狀態，從而再無機會繼續運行。622.3.5進程的掛起與激活1.進程的掛起檢查被掛起進程的狀態，活動就緒→靜止就緒;活動阻塞→靜止阻塞為了方便用戶或父進程考查該進程的運行情況，把該進程的PCB復制到某指定的內存區域。若被掛起的進程正在執行，則轉向調度程序重新調度。2.進程的激活過程先將進程從外存調入內存，檢查該進程的現行狀態，改為相應的活動狀態。根據優先級調度。632.4

進程同步1進程同步的基本概念2信號量機制3信號量的應用4

管程機制異步性會造成混亂，尤其是在競爭臨界資源時（如多個進程爭用共享變量、表格、鏈表時，有可能致使數據處理出錯）。進程同步的主要任務使并發執行的諸進程之間能有效共享資源和相互合作，從而使程序的執行具有可再現性。642.4.1進程同步的基本概念1.兩種形式的制約關系2.臨界資源(CriticalResouce)3.臨界區4.同步應遵循的規則P48651.兩種形式的制約關系在多道程序環境下，當程序并發執行時，由于資源共享和進程合作，使同處于一個系統中的諸進程之間可能存在著兩種形式的制約關系。間接相互制約關系（互斥）

直接相互制約關系（同步）

重點掌握！66間接相互制約關系（互斥）

對硬件資源的共享,如CPU、I/O設備等例如:有兩個進程A和B，在A進程提出打印請求時，系統已將惟一的一臺打印機分配給了進程B，則此時進程A只能阻塞；一旦進程B將打印機釋放，則A進程才能由阻塞改為就緒狀態。

67直接相互制約關系（同步）例如:

有一輸入進程A通過單緩沖向進程B提供數據。當該緩沖空時，進程B因不能獲得所需數據而阻塞，而當進程A把數據輸入緩沖區后，便將進程B喚醒；當緩沖區已滿時，進程A因不能再向緩沖區投放數據而阻塞，當進程B將緩沖區數據取走后便可喚醒A。

進程A進程BBuffer682.

臨界資源(CriticalResouce)一次只能供一個進程使用，使用完后歸還系統，才能給其他進程使用。692.

臨界資源(CriticalResouce)臨界資源(CriticalResouce)：硬件資源，譬如打印機、磁帶機等，諸進程間應采取互斥方式，實現對這種資源的共享,特征：1.一次只能供一個進程使用，使用完后歸還系統，才能給其他進程使用。2.進程對臨界資源必須互斥使用，以實現對臨界資源的共享訪問。

703.

臨界區只要是臨界資源，進程都必須互斥地對它進行訪問。在每個進程中，訪問臨界資源的那段代碼稱為臨界區若能保證諸進程互斥地進入自己的臨界區，便可實現諸進程對臨界資源的互斥訪問。71

臨界區：進程中訪問臨界資源的代碼段

進入區：臨界區前用于檢查臨界資源的代碼段

退出區：臨界區后用于恢復未被訪問標志的代碼段

repeat

entrysection

進入區criticalsection;（臨界區）

exitsection

退出區remaindersectionuntilfalse724.

同步應遵循的規則

為實現進程互斥地進入自已的臨界區，可用軟件方法，更多的是在系統中設置專門的同步機構來協調各進程間的運行。所有同步機制都應遵循下述4準則：1.空閑讓進2.忙則等待3.有限等待4.讓權等待

重點掌握！73同步應遵循的規則(1)空閑讓進當無進程處于臨界區時，表明臨界資源處于空閑狀態，應允許一個請求進入臨界區的進程立即進入自己的臨界區，以有效地利用臨界資源。忙則等待當已有進程進入臨界區時，表明臨界資源正在被訪問，因而其它試圖進入臨界區的進程必須等待，以保證對臨界資源的互斥訪問。74

同步應遵循的規則(2)有限等待對要求訪問臨界資源的進程，應保證在有限時間內能進入自己的臨界區，以免陷入“死等”狀態。

讓權等待當進程不能進入自己的臨界區時，應立即釋放處理機，以免進程陷入“忙等”狀態。752.4.3信號量機制(進程同步)1965年，荷蘭人Dijkstra首先提出信號量機制是一種卓有成效的進程同步工具，被廣泛應用于單處理機和多處理機系統，以及計算機網絡中信號量（Semaphores）是僅能被兩個原語操作wait(S)和signal(S)修改的整型變量。P5376信號量的類型1.

整型信號量S為初值非負的整型變量，描述資源狀態/可用資源的數量。2.

記錄型信號量二元組(S,Q)，Q初始狀態為空的隊列。3.AND型信號量一次需要多個共享資源，改進wait-signal操作。4.

信號量集一次需要N個多類資源，改進wait-signal操作。77整型信號量機制

最初由Dijkstra把整型信號量定義為一個用于表示資源數目的整型量與一般整型量不同，除初始化外，僅能通過兩個標準的原子操作(AtomicOperation)wait(S)和signal(S)來訪問。很長時間以來，這兩個操作一直被分別稱為P、V操作

wait(S)和signal(S)是兩個原子操作，在執行時是不可中斷的。即當一個進程在修改某信號量時，沒有其他進程可同時對該信號量進行修改。

在wait操作中，對S值的測試和做S:=S-1操作時都不可中斷。P操作：

wait(s):whiles<=0dono-op

s:=s-1;V操作：signal(s):s:=s+1;78記錄型信號量機制

整型量中,只要S≤0就不斷測試，未遵循“讓權等待”準則，而是使進程處于“忙等”的狀態。記錄型信號量機制是沒有“忙等”現象的同步機制，但出現多個進程等待訪問同一個臨界資源的情況在信號量機制中，除需要用于代表資源數目的整型變量value外，還增加一個進程鏈表指針L，用于鏈接所有的等待進程。typesemaphore=recordvalue:integer;資源數量L:listofprocess;進程等待end

79

wait(s)和signal(s)操作描述procedurewait(s)

請求一個資源

varS:semaphore;beginS.value=S.value-1;ifS.value<0thenblock(S.L);

資源分配完畢,

進程阻塞endproceduresignal(s)釋放一個資源varS:semaphore;beginS.value=S.value+1;ifS.value≤0thenwakeup(S.L);有等待資源進程從等待信號量S的阻塞隊列中喚醒一個進程end80S.value的初值表示系統中某類資源的數目，因而又稱為資源信號量。每次wait操作，意味著進程請求一個單位的資源，系統中可供分配的資源數減少一個，描述為S.value:=S.value-1；當S.value<0時，表示資源已分配完畢，因此進程調用block原語自我阻塞，放棄處理機，并插入到信號量鏈表S.L中。可見，該機制遵循了“讓權等待”準則。此時S.value的絕對值表示在該信號量鏈表中已阻塞進程的數目。81每次signal操作，表示執行進程釋放一個單位資源，系統中可供分配的資源數增加一個，故S.value=S.value+1操作表示資源數目加1。若加1后仍是S.value≤0，則表示在該信號量鏈表中，有等待該資源的進程被阻塞，還應調用wakeup原語，將S.L鏈表中的第一個等待進程喚醒。如果S.value的初值為1，表示只允許一個進程訪問臨界資源，此時的信號量轉化為互斥信號量，用于進程互斥。

82記錄型信號量是針對各進程之間只共享一個臨界資源的情況，有些應用場合，是一個進程需要先獲得兩個或更多的共享資源后方能執行其任務

AND型信號量機制對于生產者—消費者問題，也可利用AND信號量來解決，即用：

Swait(empty，mutex)→wait(empty)和wait(mutex)

Ssignal(mutex，full)→signal(mutex)和signal(full)

Swait(full，mutex)→

wait(full)和wait(mutex)

Ssignal(mutex，empty)→Signal(mutex)和Signal(empty)

83AND型信號量集是指同時需要多種資源且每種占用一個時的信號量操作基本思想AND型信號量集wait原語為SwaitAND型信號量集signal原語為Ssignal

AND型信號量機制84AND型信號量機制的基本思想

將進程在整個運行過程中需要的所有資源，一次性全部地分配給進程，待進程使用完后再一起釋放。只要尚有一個資源未能分配給進程，其它所有可能為之分配的資源也不分配給它。

85AND型信號量機制的基本思想對若干個臨界資源的分配，采取原子操作方式：要么把它所請求的資源全部分配到進程，要么一個也不分配。由死鎖理論可知，這樣就可避免上述死鎖情況的發生。在wait操作中，增加一個“AND”條件，故稱為AND同步或同時wait操作86Swait(S1,S2,…,Sn)原語

Swait(S1,S2,…,Sn)ifS1≥1and…andSn≥1then所有資源都有fori=1tondoSi=Si-1;endforelse進程放入第一個沒有資源的等待隊列

PlacetheprocessinthewaitingqueueassociatedwiththefirstSifoundwithSi<1，andsettheprogramcountofthisprocesstothebeginningofSwaitoperation.endif

87Ssignal(S1,S2,…,Sn)原語

Ssignal(S1,S2,…,Sn)釋放資源fori=1tondoSi=Si+1;RemovealltheprocesswaitinginthequeueassociatedwithSiintothereadyqueue.endfor88信號量集機制記錄型信號量機制中，wait(S)或signal(S)操作僅能對信號量施以加1或減1操作，意味著每次只能獲得或釋放一個單位的臨界資源。當一次需要N個某類臨界資源時，便要進行N次wait(S)操作，顯然是低效的。在有些情況下，當資源數量低于某一下限值時，便不予以分配。因而，每次分配之前，都必須測試該資源的數量，看其是否大于其下限值。基于上述兩點，可以對AND信號量機制加以擴充，形成一般化的“信號量集”機制。89

S為信號量，d為需求量，t為下限值Swait(S1，t1，d1，…，Sn，tn，dn)

ifSi>=t1and…andSn>=tn

thenfori=1tondoSi=Si-di；endforelse①Placetheprocessinthewaitingqueueassociatedwiththe

firstSi

foundwith

Si<ti

②settheprogramcountofthisprocesstothebeginningofSwaitoperation.endif90Ssignal(S1,d1S2,d2,…,Sn,dn)fori:=1tondo

Si:=Si+di;RemovealltheprocesswaitinginthequeueassociatedwithSi