《操作系統(tǒng)（OS）》課件-第二章

第二章進程與處理器管理學習目標理解程序并發(fā)運行引起的問題，掌握進程的定義和特征，熟練掌握進程的狀態(tài)轉(zhuǎn)換及其管理方法。理解進程同步與互斥的含義，熟練掌握P、V原語實現(xiàn)的同步與互斥控制，了解進程的高級通信機制。學習目標理解處理器管理的目標和任務(wù)，掌握處理器調(diào)度的分類和基本原則；熟練掌握進程調(diào)度的方法及效率分析。理解死鎖的含義，掌握死鎖預防、死鎖避免和死鎖檢測與解除的方法。了解線程的概念和特征，理解線程、進程與程序的區(qū)別。順序執(zhí)行并發(fā)執(zhí)行2.1進程的概念及其引入2.1進程的概念及其引入程序的順序執(zhí)行2.1進程的概念及其引入程序順序執(zhí)行時的特征（1）程序運行的順序性：一個程序在處理器上的運行是嚴格按順序進行的，即每個操作必須在下一個操作開始之前結(jié)束。（2）程序運行環(huán)境的封閉性：程序一旦開始執(zhí)行，其計算結(jié)果不受外界的影響，當程序的初始條件給定之后，其后的狀態(tài)只能由程序本身確定，即只有本程序才能改變它。2.1進程的概念及其引入程序順序執(zhí)行時的特征（3）計算過程的可再現(xiàn)性：程序運行的結(jié)果與初始條件有關(guān)，而與運行時間、運行速度無關(guān)。即只要程序的初始條件相同，它的執(zhí)行結(jié)果是相同的，不論它在什么時間執(zhí)行，也不管計算機的運行速度如何。這樣當程序中出現(xiàn)了錯誤時，往往可以重現(xiàn)錯誤，以便進行分析。

程序順序執(zhí)行時的特性，為程序員檢測和校正程序的錯誤帶來了很大的方便。2.1進程的概念及其引入程序的并發(fā)執(zhí)行在該例中存在下述前趨關(guān)系：Ii→Ci，Ii→Ii+1，Ci→Pi，Ci→Ci+1，Pi→Pi+1

而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行。對于具有下述四條語句的程序段：S1:a=x+2S2:b=y+4S3:c=a+bS4:d=c+b2.1進程的概念及其引入程序并發(fā)執(zhí)行時的特征（1）間斷性程序在并發(fā)執(zhí)行時，由于它們共享系統(tǒng)資源，以及為完成同一項任務(wù)而相互合作，致使在這些并發(fā)執(zhí)行的程序之間，形成了相互制約的關(guān)系。相互制約將導致并發(fā)程序具有“執(zhí)行—暫?！獔?zhí)行”這種間斷性的活動規(guī)律。（2）失去封閉性程序在并發(fā)執(zhí)行時，是多個程序共享系統(tǒng)中的各種資源，因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運行失去了封閉性。這樣，某程序在執(zhí)行時，必然會受到其它程序的影響。（3）不可再現(xiàn)性程序在并發(fā)執(zhí)行時，由于失去了封閉性，也將導致其再失去可再現(xiàn)性。2.1進程的概念及其引入程序并發(fā)執(zhí)行時的特征（4）程序與計算不再一一對應(yīng)在程序的并發(fā)運行時，可能有多用戶共享使用同一個程序，但處理（計算）的對象卻是不同的。[例2-1]在多用戶環(huán)境下，可能同時有多個用戶調(diào)用C語言的編譯程序，這就是典型的一個程序?qū)?yīng)多個用戶源程序的情況，如圖2-3所示。2.1進程的概念及其引入二、進程的定義火車-列車(1)進程是程序的一次執(zhí)行。(2)進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動。(3)進程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。我國學者給出的定義：進程是一個有一定獨立功能的程序在某個數(shù)據(jù)集合上的一次運行活動。2.1進程的概念及其引入三、進程的特征（1）動態(tài)性進程的實質(zhì)是進程實體的一次執(zhí)行過程，因此，動態(tài)性是進程的最基本的特征。動態(tài)性還表現(xiàn)在：“它由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤消而消亡”?？梢?，進程實體有一定的生命期，而程序則只是一組有序指令的集合，并存放于某種介質(zhì)上，其本身并不具有運動的含義，因而是靜態(tài)的。2.1進程的概念及其引入三、進程的特征（2）并發(fā)性這是指多個進程實體同存于內(nèi)存中，且能在一段時間內(nèi)同時運行。并發(fā)性是進程的重要特征，同時也成為OS的重要特征。引入進程的目的也正是為了使其進程實體能和其它進程實體并發(fā)執(zhí)行；而程序是不能并發(fā)執(zhí)行的。2.1進程的概念及其引入三、進程的特征（3）獨立性

進程是CPU調(diào)度的一個獨立單位，即每個進程的程序都是相對獨立的順序程序，可以按照自己的方向和速度獨立地向前推進。（4）交互性

指進程在執(zhí)行過程中可能與其他進程產(chǎn)生直接或間接的關(guān)系。2.1進程的概念及其引入三、進程的特征（5）制約性（或異步性）

由于進程是系統(tǒng)中資源分配和運行調(diào)度的單位，因此在對資源共享和競爭中，必然會相互制約，影響了各自向前推進的速度，且向前推進的速度是不可預知的。（6）結(jié)構(gòu)性

進程是有結(jié)構(gòu)的，它由程序、數(shù)據(jù)、進程控制塊（PCB）組成。程序規(guī)定了進程所要運行的任務(wù)，數(shù)據(jù)是程序的處理對象，而控制結(jié)構(gòu)中含有進程的描述信息和控制信息，是進程組成的關(guān)鍵部分。2.1進程的概念及其引入程與程序的聯(lián)系和區(qū)別（1）進程是程序在處理器上的一次運行的過程，是動態(tài)的概念；程序是指令的集合，在多道程序設(shè)計環(huán)境下，它不涉及“運行”，因此程序是靜態(tài)的概念。（2）進程是有生命周期的，它的存在是暫時的；程序可以作為軟件資料長期保存，程序的存在是永久的。（3）進程是有結(jié)構(gòu)的。進程是程序的運行，所以進程應(yīng)該包括程序和數(shù)據(jù)，還包括記錄進程狀態(tài)信息的數(shù)據(jù)結(jié)構(gòu)——進程控制塊（PCB）。2.1進程的概念及其引入程與程序的聯(lián)系和區(qū)別（4）進程與程序之間，不存在一一對應(yīng)的關(guān)系。一個程序可以作為多個進程的運行程序，一個進程也可以運行多個程序。例如，一個編譯程序同時被多個用戶調(diào)用，各個用戶程序的源程序是編譯程序的處理對象（即數(shù)據(jù)集合）。于是系統(tǒng)中形成了一個個不同的進程，它們都運行編譯程序，只是每個加工的對象不同。（5）進程可以生成其他進程，而程序不能生成新的程序。2.1進程的概念及其引入在計算機系統(tǒng)中，進程不僅是最基本的并發(fā)運行的單位，而且也是分配資源的基本單位。intn=1;//全局變量程序AfunA(){ n++; printf(“%d\n”,n);}程序BfunB(){ printf(“%d\n”,n); n=0;}并發(fā)執(zhí)行的可能順序：1-2-3-4 結(jié)果：221-3-4-2 結(jié)果：023-1-2-4 結(jié)果：21①②③④2.2進程狀態(tài)和管理一、進程狀態(tài)及其轉(zhuǎn)換進程狀態(tài)1.運行2.就緒3.等待（阻塞）+創(chuàng)建終止掛起

進程執(zhí)行時的間斷性決定了進程可能具有多種狀態(tài)。事實上，運行中的進程可能具有以下三種基本狀態(tài)。

1.就緒(Ready)狀態(tài)當進程已分配到除CPU以外的所有必要資源后，只要再獲得CPU，便可立即執(zhí)行，進程這時的狀態(tài)稱為就緒狀態(tài)。在一個系統(tǒng)中處于就緒狀態(tài)的進程可能有多個，通常將它們排成一個隊列，稱為就緒隊列。

2.執(zhí)行狀態(tài)進程已獲得CPU，其程序正在執(zhí)行。在單處理機系統(tǒng)中，只有一個進程處于執(zhí)行狀態(tài)；在多處理機系統(tǒng)中，則有多個進程處于執(zhí)行狀態(tài)。

3.阻塞狀態(tài)正在執(zhí)行的進程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機而處于暫停狀態(tài)，亦即進程的執(zhí)行受到阻塞，把這種暫停狀態(tài)稱為阻塞狀態(tài)，有時也稱為等待狀態(tài)或封鎖狀態(tài)。致使進程阻塞的典型事件有：請求I/O，申請緩沖空間等。通常將這種處于阻塞狀態(tài)的進程也排成一個隊列。有的系統(tǒng)則根據(jù)阻塞原因的不同而把處于阻塞狀態(tài)的進程排成多個隊列。進程的三種基本狀態(tài)及其轉(zhuǎn)換

就緒->執(zhí)行執(zhí)行->就緒執(zhí)行->阻塞阻塞->就緒進程狀態(tài)的轉(zhuǎn)換問題：操作系統(tǒng)如何找到進程？如何來刻畫一個進程在各個不同時期所處的狀態(tài)？如何來描述一個進程和其他進程以及系統(tǒng)資源的關(guān)系呢？2.2.2進程的描述——進程控制塊1.

進程控制塊（PCB）的概念所謂進程控制塊（PCB，ProcessControlBlock），就是描述進程與其他進程、系統(tǒng)資源的關(guān)系以及進程在各個不同時期所處的狀態(tài)的數(shù)據(jù)結(jié)構(gòu)。2.2.2進程的描述——進程控制塊3.進程控制塊（PCB）的內(nèi)容

進程名（ID） 進程狀態(tài) 程序存放位置 數(shù)據(jù)存放位置 通用寄存器內(nèi)容 控制寄存器內(nèi)容 斷點地址 進程優(yōu)先數(shù) 隊列指針 標志信息說明信息現(xiàn)場信息管理信息圖2-5PCB所包含的信息2.

進程控制塊（PCB）的作用操作系統(tǒng)是通過PCB來對并發(fā)運行的進程進行控制和管理的。具體表現(xiàn)如下：（1）創(chuàng)建進程，就是創(chuàng)建PCB，PCB是系統(tǒng)感知進程存在的唯一標志。（2）進程與PCB是一一對應(yīng)的，每一個進程都有自己的進程控制塊。2.2.2進程的描述——進程控制塊2.

進程控制塊（PCB）的作用（3）PCB集中地反映了一個進程的動態(tài)特征。（4）在進程并發(fā)運行時，由于資源共享，帶來各進程之間的相互制約。為了反映這些制約關(guān)系和資源共享關(guān)系，是根據(jù)PCB中的信息對進程實施有效的管理和控制的。2.2.2進程的描述——進程控制塊擴展：創(chuàng)建狀態(tài)和終止狀態(tài)

1)創(chuàng)建狀態(tài)創(chuàng)建一個進程一般要通過兩個步驟：首先，為一個新進程創(chuàng)建PCB，并填寫必要的管理信息；其次，把該進程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊列之中。當一個新進程被創(chuàng)建時，系統(tǒng)已為其分配了PCB，填寫了進程標識等信息，但由于該進程所必需的資源或其它信息，如主存資源尚未分配等，一般而言，此時的進程已擁有了自己的PCB，但進程自身還未進入主存，即創(chuàng)建工作尚未完成，進程還不能被調(diào)度運行，其所處的狀態(tài)就是創(chuàng)建狀態(tài)。引入創(chuàng)建狀態(tài)，是為了保證進程的調(diào)度必須在創(chuàng)建工作完成后進行，以確保對進程控制塊操作的完整性。同時，創(chuàng)建狀態(tài)的引入，也增加了管理的靈活性，操作系統(tǒng)可以根據(jù)系統(tǒng)性能或主存容量的限制，推遲創(chuàng)建狀態(tài)進程的提交。對于處于創(chuàng)建狀態(tài)的進程，獲得了其所必需的資源，以及對其PCB初始化工作完成后，進程狀態(tài)便可由創(chuàng)建狀態(tài)轉(zhuǎn)入就緒狀態(tài)。

2)終止狀態(tài)進程的終止也要通過兩個步驟：首先等待操作系統(tǒng)進行善后處理，然后將其PCB清零，并將PCB空間返還系統(tǒng)。當一個進程到達了自然結(jié)束點，或是出現(xiàn)了無法克服的錯誤，或是被操作系統(tǒng)所終結(jié)，或是被其他有終止權(quán)的進程所終結(jié)，它將進入終止狀態(tài)。進入終止態(tài)的進程以后不能再執(zhí)行，但在操作系統(tǒng)中依然保留一個記錄，其中保存狀態(tài)碼和一些計時統(tǒng)計數(shù)據(jù)，供其它進程收集。一旦其它進程完成了對終止狀態(tài)進程的信息提取之后，操作系統(tǒng)將刪除該進程。

5.掛起狀態(tài)

1)引入掛起狀態(tài)的原因在不少系統(tǒng)中進程只有上述三種狀態(tài)，但在另一些系統(tǒng)中，又增加了一些新狀態(tài)，最重要的是掛起狀態(tài)。引入掛起狀態(tài)的原因有：

(1)終端用戶的請求。當終端用戶在自己的程序運行期間發(fā)現(xiàn)有可疑問題時，希望暫時使自己的程序靜止下來。亦即，使正在執(zhí)行的進程暫停執(zhí)行；若此時用戶進程正處于就緒狀態(tài)而未執(zhí)行，則該進程暫不接受調(diào)度，以便用戶研究其執(zhí)行情況或?qū)Τ绦蜻M行修改。我們把這種靜止狀態(tài)稱為掛起狀態(tài)。

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

(3)負荷調(diào)節(jié)的需要。當實時系統(tǒng)中的工作負荷較重，已可能影響到對實時任務(wù)的控制時，可由系統(tǒng)把一些不重要的進程掛起，以保證系統(tǒng)能正常運行。

(4)操作系統(tǒng)的需要。操作系統(tǒng)有時希望掛起某些進程，以便檢查運行中的資源使用情況或進行記賬。加入創(chuàng)建、終止、掛起狀態(tài)的進程狀態(tài)轉(zhuǎn)換

擴展的進程狀態(tài)及轉(zhuǎn)化如圖，引進創(chuàng)建、終止、掛起狀態(tài)后，在進程狀態(tài)轉(zhuǎn)換時，需要增加考慮下面的幾種情況。

(1)NULL→創(chuàng)建：一個新進程產(chǎn)生時，該進程處于創(chuàng)建狀態(tài)。

(2)創(chuàng)建→活動就緒：在當前系統(tǒng)的性能和內(nèi)存的容量均允許的情況下，完成對進程創(chuàng)建的必要操作后，相應(yīng)的系統(tǒng)進程將進程的狀態(tài)轉(zhuǎn)換為活動就緒狀態(tài)。

(3)創(chuàng)建→靜止就緒：考慮到系統(tǒng)當前資源狀況和性能要求，并不分配給新建進程所需資源，主要是主存資源，相應(yīng)的系統(tǒng)進程將進程狀態(tài)轉(zhuǎn)為靜止就緒狀態(tài)，對換到外存，不再參與調(diào)度，此時進程創(chuàng)建工作尚未完成。

(4)執(zhí)行→終止：當一個進程到達了自然結(jié)束點，或是出現(xiàn)了無法克服的錯誤，或是被操作系統(tǒng)所終結(jié)，或是被其他有終止權(quán)的進程所終結(jié)，進程即進終止狀態(tài)。

(5)活動就緒→靜止就緒。當進程處于未被掛起的就緒狀態(tài)時，稱此為活動就緒狀態(tài)，表示為Readya。當用掛起原語Suspend將該進程掛起后，該進程便轉(zhuǎn)變?yōu)殪o止就緒狀態(tài)，表示為Readys，處于Readys狀態(tài)的進程不再被調(diào)度執(zhí)行。

(6)活動阻塞→靜止阻塞。當進程處于未被掛起的阻塞狀態(tài)時，稱它是處于活動阻塞狀態(tài)，表示為Blockeda。當用Suspend原語將它掛起后，進程便轉(zhuǎn)變?yōu)殪o止阻塞狀態(tài)，表示為Blockeds。處于該狀態(tài)的進程在其所期待的事件出現(xiàn)后，將從靜止阻塞變?yōu)殪o止就緒。

(7)靜止就緒→活動就緒。處于Readys狀態(tài)的進程，若用激活原語Active激活后，該進程將轉(zhuǎn)變?yōu)镽eadya狀態(tài)。

(8)靜止阻塞→活動阻塞。處于Blockeds狀態(tài)的進程，若用激活原語Active激活后，該進程將轉(zhuǎn)變?yōu)锽lockeda狀態(tài)。進程狀態(tài)轉(zhuǎn)換小結(jié)Null->創(chuàng)建創(chuàng)建->活動就緒創(chuàng)建->靜止就緒活動就緒->執(zhí)行活動就緒->靜止就緒靜止就緒->活動就緒執(zhí)行->靜止就緒執(zhí)行->活動阻塞活動阻塞->活動就緒活動阻塞->靜止阻塞靜止阻塞->活動阻塞靜止阻塞->靜止就緒執(zhí)行->終止4.進程隊列

操作系統(tǒng)要管理、控制好進程，就必須首先組織好PCB。

系統(tǒng)把所有PCB組織在一起，并把它們放在主存的固定區(qū)域，就構(gòu)成了PCB表。

PCB表的大小決定了系統(tǒng)中最多可同時存在的進程個數(shù)，稱為系統(tǒng)的并發(fā)度?？誔CB運行態(tài)就緒態(tài)阻塞1阻塞2PCB1PCB2PCB3PCB4PCB5PCB6PCB7PCBn......6751015PCB的組織方式進程隊列的組織方式線性方式鏈接方式索引方式PCB表——線性方式線性方式組織形式簡單、易于實現(xiàn)，此種方式的優(yōu)缺點？PCB1PCB2PCB3PCB4……PCBn-2PCBn-1PCBn圖2-7PCB線性隊列結(jié)構(gòu)示意圖PCB表——鏈接方式鏈接方式鏈接方式是常采用的方式，不同狀態(tài)的進程分別鏈接組成自己的隊列PCB表——鏈接方式PCB2PCB3PCB7PCB6-1PCB5PCB8-1PCB4-1PCB10PCB9PCB1運行隊列指針運行隊列:就緒隊列頭指針就緒隊列:阻塞隊列1頭指針阻塞隊列1:阻塞隊列2頭指針阻塞隊列2:圖2-8PCB鏈接隊列結(jié)構(gòu)示意圖PCB表——索引方式索引方式索引方式是利用索引表記載相應(yīng)狀態(tài)進程的PCB地址。各個索引表在主存中的起始地址存放在專用指針單元中。PCB表——索引方式圖2-9PCB索引隊列結(jié)構(gòu)示意圖運行指針就緒表指針阻塞表指針阻塞索引表阻塞索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7…2.2.3進程的控制與管理進程控制的功能完成創(chuàng)建和撤消進程，掛起和激活進程等完成進程狀態(tài)的轉(zhuǎn)換。原語的引入問題：操作系統(tǒng)如何保證進程在執(zhí)行時的絕對正確呢？關(guān)鍵進程在執(zhí)行時要以一個整體出現(xiàn)，不可分割。原語(primitive)：由若干條指令構(gòu)成的“原子操作(atomicoperation)”過程，作為一個整體而不可分割--要么全都完成，要么全都不做。進程控制的主要原語進程創(chuàng)建與撤消原語進程阻塞與喚醒原語進程掛起與激活原語1.“創(chuàng)建進程”原語父進程借助于創(chuàng)建原語來創(chuàng)建進程。創(chuàng)建一個進程的主要任務(wù)是形成進程的控制塊PCB。調(diào)用者必須提供PCB中的相關(guān)參數(shù)，以便在創(chuàng)建時填入。進程控制的主要原語——進程創(chuàng)建原語進程樹ABCDJFGHIEKLM進程樹是有向樹父子關(guān)系表示創(chuàng)建與被創(chuàng)建的關(guān)系父子關(guān)系不表示執(zhí)行的先后關(guān)系1.“創(chuàng)建進程”原語進程的創(chuàng)建過程描述如下：在主進程表中增加一項，并從PCB池中申請一個空白PCB。為新進程的進程映像分配地址空間。對于進程創(chuàng)建操作還需要傳遞環(huán)境變量，構(gòu)造共享地址空間。為新進程分配資源，除內(nèi)存空間外，還有其他各種資源。查找輔助存儲器，找到進程正文段并裝入到進程地址空間的正文區(qū)。

1.“創(chuàng)建進程”原語進程的創(chuàng)建過程描述如下：初始化進程控制塊（如狀態(tài)、PSW、棧等），為新進程分配一個唯一的進程標識符。把進程加入某一就緒進程隊列（這時子進程就緒），或直接將進程投入運行（這時父進程就緒）。通知操作系統(tǒng)的某些模塊，如記賬程序、性能監(jiān)控程序。

API中的CreateProcessTheCreateProcessfunctioncreatesanewprocessanditsprimarythread.Thenewprocessrunsthespecifiedexecutablefile.BOOLCreateProcess(LPCTSTRlpApplicationName,//nameofexecutablemoduleLPTSTRlpCommandLine,//commandlinestringLPSECURITY_ATTRIBUTESlpProcessAttributes,//SD-SecurityDescriptorLPSECURITY_ATTRIBUTESlpThreadAttributes,//SD-SecurityDescriptorBOOLbInheritHandles,//handleinheritanceoptionDWORDdwCreationFlags,//creationflagsLPVOIDlpEnvironment,//newenvironmentblockLPCTSTRlpCurrentDirectory,//currentdirectorynameLPSTARTUPINFOlpStartupInfo,//startupinformationLPPROCESS_INFORMATIONlpProcessInformation//processinformation);2.“撤銷進程”原語當一個進程在完成其任務(wù)后應(yīng)予以撤銷，以便及時釋放它所占用的資源（外部設(shè)備、主存空間等）。導致進程被撤消的原因一個進程在完成任務(wù)而正常終止由于錯誤導致非正常終止祖先進程要求撤消某個子進程2.“撤銷進程”原語進程的撤銷原語的操作過程：（1）查找要被撤消的PCB；（2）如果該進程存在，且有子進程存在，則需要先行撤消子進程；（3）釋放該進程所占全部資源；（4）釋放該PCB結(jié)構(gòu)本身。2.3進程同步與通信進程同步是操作系統(tǒng)管理共享資源和避免并發(fā)進程產(chǎn)生與時間有關(guān)的錯誤的一種手段。進程同步包括進程的互斥和進程的同步兩個方面。2.3.1進程的互斥引例教室分配問題多道程序共用一臺打印機飛機航班售票系統(tǒng)解決方法：為了使并發(fā)進程能正確地運行，必須對獨占的共享資源的使用加以限制。進程間的關(guān)系——并發(fā)執(zhí)行舉例

例：飛機訂票系統(tǒng)，兩個終端，運行T1、T2進程

T1:T2:......Read(x);Read(x);y1=x;y2=x;ify1>=1ify2>=1y1=y1-1;y2=y2-1;x=y1;x=y2;write(x);write(x);......設(shè)x的當前值為：1001.若執(zhí)行順序為：先T1;后T2;

則結(jié)果：x=982.若執(zhí)行順序為：T1:Read(x);T2:Read(x);T1:ify1>=1theny1:=y1-1;T2:ify2>=1theny2:=y2-1;T1:write(x);T2:write(x);則結(jié)果x=99分析：產(chǎn)生錯誤的原因是不加控制地訪問共享變量x2.3.1進程的互斥進程的互斥是指并發(fā)進程在競爭共享資源時，任何時刻最多只允許一個進程去使用，其他欲使用該資源的進程必須等待，直至使用者釋放了該資源后才能讓另一個進程去使用。進程的互斥即并發(fā)進程對于共享資源的使用，必須是排他的、互斥的。互斥的特點（1）互斥進程彼此在邏輯上是完全無關(guān)的，各自單獨運行都是正確的；（2）它們的運行不具有時間次序的特征。（3）互斥是進程之間的一種“間接制約”關(guān)系。2.3.1進程的互斥操作系統(tǒng)通過對獨占的共享資源實行互斥的使用，來解決并發(fā)進程出現(xiàn)“系統(tǒng)資源的競爭”問題。問題：獨占的共享資源的互斥使用是如何實現(xiàn)的呢？引入了臨界資源和臨界區(qū)兩個概念3.臨界資源與臨界區(qū)（1）臨界資源所謂臨界資源（CriticalResource）是指一次僅允許一個進程使用的資源。計算機系統(tǒng)中的臨界資源很多，如有物理設(shè)備的輸入機、打印機、磁帶機等，稱為硬臨界資源，還有公用變量、數(shù)據(jù)、表格、隊列等軟臨界資源。3.臨界資源與臨界區(qū)（2）臨界區(qū)所謂臨界區(qū)（CriticalSection）是指在每個進程中訪問臨界資源的那段程序，簡稱CS區(qū)。3.臨界資源與臨界區(qū)

Q進程AAB進程BCD進程CEF圖2-12并發(fā)進程訪問臨界資源示意圖（3）臨界區(qū)的管理準則①當有若干進程同時要用到同一個臨界資源時，每次至多允許一個進程進入臨界區(qū)；其余的進程必須等待。②任何一個進入臨界區(qū)運行的進程必須在有限的時間內(nèi)退出臨界區(qū)，即任何進程都不能無限制的在自己的臨界區(qū)內(nèi)逗留。③不能強迫一個進程無限地等待進入它的臨界區(qū)，即有進程退出臨界區(qū)時應(yīng)該讓一個等待進入臨界區(qū)的進程進入它的臨界區(qū)運行。2.3.2進程的同步引例公交車的司機和乘務(wù)員協(xié)作問題

司機P1

售票員P2

REPEATREPEAT

啟動關(guān)門

正常運行售票

到站停開門

UNTILFALSEUNTILFALSE

2.3.2進程的同步引例進程A把讀入的數(shù)據(jù)記錄存入緩沖器，進程B從緩沖器中取出數(shù)據(jù)記錄加工數(shù)據(jù)記錄緩沖器BA讀存取加工圖2-13進程協(xié)作示意圖進程的同步概念進程的同步（Synchronization）是指并發(fā)進程之間存在的一種制約關(guān)系，一個進程的運行依賴其他進程的運行情況，即一個進程在沒有收到其他進程的消息時必須等待，直至另一進程送來消息后才繼續(xù)運行下去。同步的特點同步是進程間共同完成一項任務(wù)時直接發(fā)生相互作用的關(guān)系，具有以下特點：（1）同步進程間具有合作關(guān)系，在邏輯上有某種聯(lián)系；（2）在執(zhí)行時間上必須按一定的順序協(xié)調(diào)進行。2.3.3進程同步機制并發(fā)進程之間互斥與同步的相互制約關(guān)系都是要在時間順序上對并發(fā)進程的操作加以某種限制?；コ狻荒芡瑫r進入臨界區(qū)。同步——執(zhí)行時有先后順序。進程之間的互斥是一種特殊的同步關(guān)系進程同步機制可分為硬件機制和軟件機制。1.加鎖機制解決進程互斥的最簡單的辦法是加鎖。對每個臨界區(qū)設(shè)置一把“鎖”，就可以解決并發(fā)進程互斥進入臨界區(qū)的問題。（1）加鎖機制原理通過為每個臨界區(qū)或其他互斥資源設(shè)置一個布爾變量作為鎖，用來代表某個臨界資源的可用狀態(tài)。例如，布爾變量W，其值為0時表示臨界資源未被使用，處于可用狀態(tài)（開鎖）；其值為1時表示臨界資源正被使用，處于不可用狀態(tài)（加鎖）。（1）加鎖機制原理

加鎖原語Lock(w)定義如下：①測試W是否為0。②若W為0，則將W設(shè)為1。③若W為1，則返回到①。整個操作是一條原語，即不可以中斷，中間也不允許其他進程來改變W的狀態(tài)。（2）加鎖/開鎖偽代碼①加鎖Lock(w)Lock(w)L: ifw=1thengotoL;elsew:=1;②開鎖Unlock(w)Unlock(w)w:=0;Lock(w)Unlock(w)（3）加鎖機制存在的問題當某個進程進入臨界區(qū)后，其他進程一旦想進入就要不斷測試鎖的狀態(tài)，直到鎖的狀態(tài)為0，才可進入臨界區(qū)。這樣就會使得CPU出現(xiàn)“忙等”狀態(tài)，造成CPU的時間浪費，使得系統(tǒng)效率降低。2.信號量與P、V操作信號量semaphore——信號量和P、V原語1968年，由荷蘭學者Dijkstra提出（所以P、V分別是荷蘭語的test(proberen)和increment(verhogen)），是一種卓有成效的進程同步機制。2.信號量與P、V操作信號量：semaphore是一個數(shù)據(jù)結(jié)構(gòu)，定義如下：

typedefstruct{ intcount; Pointer_PCBQueue;}Semaphore;信號量說明：

Semaphores;2.信號量與P、V操作指針數(shù)值(-3)PCB1PCB2PCB3信號量進程隊列圖2-14信號量的一般結(jié)構(gòu)2.信號量與P、V操作在一個信號量S上，只能做規(guī)定的兩種操作：P操作，記為P（S）和V操作，記為V（S），也僅能由這兩個操作才能改變S的值。1）信號量S上的P操作定義當一個進程調(diào)用P（S）時，應(yīng)該順序做下面兩個不可分割的動作：①S=S-1，即把當前信號量S的取值減1。②若S>=0，則調(diào)用進程繼續(xù)運行；若S<0，則調(diào)用進程由運行狀態(tài)變?yōu)樽枞麪顟B(tài)，到與該信號量有關(guān)的隊列Q上排隊等待，直到其他進程在S上執(zhí)行V操作將其釋放為止。1）信號量S上的P操作定義信號量S代表系統(tǒng)的資源，若S為正值表示可用資源的數(shù)量，而P（S）操作是申請一個物理資源，所以做S-1操作若S-1操作后S值仍然大于等于0，表示系統(tǒng)可以滿足申請的需求，所以申請資源的進程繼續(xù)運行；若P(S)操作后，S的值小于0，則表示進程的申請沒有得到滿足，進程就只好進入阻塞狀態(tài)，并被插入到相應(yīng)的隊列中等待。2）信號量S上的V操作定義當一個進程調(diào)用V（S）時，應(yīng)該順序做下面兩個不可分割的動作：①S=S+1，即把當前信號量S的取值加1。②若S>0，則調(diào)用進程繼續(xù)運行；若S<=0，則先從與該信號量有關(guān)的隊列Q上摘下一個等待進程，讓它從阻塞狀態(tài)變?yōu)榫途w狀態(tài)，到就緒隊列里排隊，然后調(diào)用進程繼續(xù)運行。2）信號量S上的V操作定義做一次V（S）操作意味著釋放一個資源，因此對信號量S做加1操作。S加1操作后，若S的值大于0，說明沒有進程在等待該資源；而S值為負值時，它的絕對值表示的是等待此資源的進程數(shù)，2）信號量S上的V操作定義所以，在V（S）操作后，S的值小于等于0時，表示有進程在等待該資源，執(zhí)行V（S）操作的進程將從等待該資源的隊列中喚醒一個等待進程，然后自己繼續(xù)執(zhí)行后面的操作。P、V示意PV2.信號量與P、V操作綜上所述，在解決互斥問題時，如果把信號量S的初始值，理解為是系統(tǒng)中某種資源的數(shù)目，那么：在它的上面做P操作，即是申請一個資源；在它的上面做V操作，即是釋放一個用完的資源。2.信號量與P、V操作與信號量S有關(guān)的隊列，是資源等待隊列。信號量S的值與相應(yīng)資源的使用情況有關(guān)。信號量S的值僅由P、V操作改變，P、V操作都是原語操作，且P、V操作必須成對出現(xiàn)。用信號量實現(xiàn)兩個進程共享一臺打印機實現(xiàn)進程的互斥示例

設(shè)信號量mutex表示打印機，其初值為1，表示打印機可用（也可理解為有一臺打印機）。Pa（）、Pb（）表示A、B兩個進程，兩個進程及其臨界區(qū)代碼可按下述形式組成：Pa（）Pb（）{{…………P（mutex）；P（mutex）；使用打印機；使用打印機；V（mutex）；V（mutex）；…………}}用信號量實現(xiàn)三個進程分工協(xié)作完成讀入數(shù)據(jù)、加工處理和打印輸出的同步示例。緩沖區(qū)B1緩沖區(qū)B2R進程C進程P進程圖2-15同步使用緩沖區(qū)示意圖一般來說，處理進程的同步需要兩個信號量，一個用于協(xié)調(diào)合作進程的推進速度，一個用于臨界區(qū)的互斥。設(shè)四個信號量及初值為：①B1empty——緩沖區(qū)B1空信號，初值為1；②B1full-——緩沖區(qū)B1滿信號，初值為0；③B2empty——緩沖區(qū)B2空信號，初值為1；④B2full-——緩沖區(qū)B2滿信號，初值為0；各進程的執(zhí)行步驟如下：

P(B1empty)輸入數(shù)據(jù)寫入緩沖區(qū)B1

V(B1full)

P(B1full)從B1中取出數(shù)據(jù)

V(B1empty)

加工數(shù)據(jù)

P(B2empty)

結(jié)果送入B2

V(B2full)

P(B2full)從B2中取出數(shù)據(jù)進行打印

V(B2empty)R進程C進程P進程P、V練習有一家四口：爸爸、媽媽、兒子和女兒。兒子愛吃香蕉，有爸爸負責購買。女兒愛吃桔子，有媽媽負責購買。已知家中有一個果盤，而且一次只能放一個香蕉或者一個桔子，試用P、V操作描述水果的傳遞過程。信號量及初值：empty=1full=0banana_in=0orange_in=0banana_out=1orange_out=1過程：fputmputsgetdget

fput: P(banana_out) P(empty) putbanana V(full) V(banana_in)

mput:

P(orange_out) P(empty) putorange V(full) V(orange_in)

sget: P(banana_in) P(full) getbanana V(empty) V(banana_out)

dget: P(orange_in) P(full) getorange V(empty) V(orange_out)信號量及初值：clear=1bananaready=0orangeready=0過程：fputmputsgetdget

fput: wait(clear) putbanana signal(bananaready)

mput:

wait(clear) putorange signal(orangeready)

sget: wait(bananaready) getbanana signal(clear)

dget: wait(orangeready) getorange signal(clear)3.幾個典型的互斥、同步問題生產(chǎn)者－消費者問題哲學家進餐問題理發(fā)師睡眠問題生產(chǎn)者－消費者問題

問題描述：若干進程通過有限的共享緩沖區(qū)交換數(shù)據(jù)。其中，"生產(chǎn)者"進程不斷寫入，而"消費者"進程不斷讀出；共享緩沖區(qū)共有N個；任何時刻只能有一個進程可對共享緩沖區(qū)進行操作。共享緩沖區(qū)生產(chǎn)指針消費指針Producer1Producer2...ProducerMConsumer1Consumer2...ConsumerN滿空指針移動方向緩沖區(qū)不滿，生產(chǎn)者才能寫入；緩沖區(qū)不空，消費者才能讀出——同步互斥

設(shè)信號量：

full是“滿”數(shù)目，初值為0，

empty是“空”數(shù)目，初值為N。實際上，full和

empty是同一個含義：full+empty==N

mutex用于訪問緩沖區(qū)時的互斥，初值是1ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=5Full=0Mutex=1緩沖區(qū)等待隊列ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=5Full=0Mutex=1緩沖區(qū)Producermakesanewunit等待隊列ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=4Full=0Mutex=1緩沖區(qū)Producerappliesa“empty”等待隊列ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=4Full=0Mutex=0緩沖區(qū)Producerappliescriticalsection等待隊列ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=4Full=0Mutex=0緩沖區(qū)Producerputsunitintobuffer等待隊列ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=4Full=0Mutex=1緩沖區(qū)Producergoesoutcriticalsection等待隊列ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=4Full=1Mutex=1緩沖區(qū)Producerreleasesa“full”等待隊列ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=0Full=5Mutex=1緩沖區(qū)Repeat4timesagain…等待隊列ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=0Full=5Mutex=1緩沖區(qū)Producermakesnewunitagain…等待隊列ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=-1Full=5Mutex=1緩沖區(qū)Producerappliesa“empty”等待隊列P1ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=-1Full=4Mutex=1緩沖區(qū)Consumerappliesa“full”等待隊列P1ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=-1Full=4Mutex=0緩沖區(qū)Consumerappliescriticalsection等待隊列P1ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=-1Full=4Mutex=0緩沖區(qū)Consumergetsaunitfrombuffer等待隊列P1ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=-1Full=4Mutex=1緩沖區(qū)Consumergoesoutcriticalsection等待隊列P1ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=0Full=4Mutex=1緩沖區(qū)Consumerreleasesa“empty”等待隊列P1ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=0Full=4Mutex=0緩沖區(qū)Producerappliescriticalsection等待隊列ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=0Full=4Mutex=0緩沖區(qū)Producerputsunitintobuffer等待隊列ProducerP(empty);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(full);//退出區(qū)ConsumerP(full);P(mutex);//進入?yún)^(qū)oneunit

buffer;V(mutex);V(empty);//退出區(qū)P1...PnC1...Cn變量：Empty=0Full=4Mutex=0緩沖區(qū)生產(chǎn)者與生產(chǎn)者互斥消費者與消費者互斥生產(chǎn)者與消費者同步操作的順序很重要，不當會產(chǎn)生死鎖。如假定Producer和Consumer如下：Consumer：Producer：P(empty);P(mutex);

oneunit

buf;V(mutex);V(full);P(full);P(mutex);//進入?yún)^(qū)

oneunit

buf;V(mutex);V(empty);//退出區(qū)當full=0,mutex=1時，執(zhí)行順序：

Consumer.P(mutex);Consumer.P(full);//C阻塞，等待Producer發(fā)出的full信號

Producer.P(empty);Producer.P(mutex);//P阻塞，等待Consumer發(fā)出的empty信號死鎖，還有其他的執(zhí)行序列可以產(chǎn)生死鎖嗎？形式化描述Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,n-1]ofitem;in,out:integer:=0,0;beginparbeginproducer:beginrepeatproduceanitem;

P(empty);P(mutex);buffer(in):=item;in:=(in+1)modn;

V(mutex);V(full);untilfalse;endconsumer:beginrepeat

P(full);P(mutex);item:=buffer(out);out:=(out+1)modn;

V(mutex);V(empty);

consumetheitem;untilfalse;endparendendfull是“滿”數(shù)目，初值為0，

empty是“空”數(shù)目，初值為N。

mutex用于訪問緩沖區(qū)時的互斥，初值是1哲學家進餐問題問題描述：（由Dijkstra首先提出并解決）5個哲學家圍繞一張圓桌而坐，桌子上放著5支筷子，每兩個哲學家之間放一支；哲學家的動作包括思考和進餐，進餐時需要同時拿起他左邊和右邊的兩支筷子，思考時則同時將兩支筷子放回原處。哲學家進餐問題哲學家的生活規(guī)律Repeat

思考；取fork[(i-1)mod5]；取fork[(i+1)mod5]；

進食；放fork[(i-1)mod5]；放fork[(i+1)mod5]；Untilfalse;哲學家進餐問題考慮問題：如何保證哲學家們的動作有序進行？如：

不出現(xiàn)相鄰者同時要求進餐；不出現(xiàn)有人永遠拿不到筷子；參考代碼#defineN5 //哲學家數(shù)目#defineLEFT(i-1)%N //i的左鄰居號#defineRIGHT(i+1)%N //i的右鄰居號#defineTHINKING0 //哲學家正在思考#defineHUNGRY1 //哲學家想取筷子#defineEATING2 //哲學家正在吃飯typedefintsemaphore; //信號量intstate[N]; //記錄每個人狀態(tài)的數(shù)組semaphore

mutex=1; //臨界區(qū)互斥信號量semaphores[N]; //每個哲學家一個信號量參考代碼voidphilosopher(inti)//i為哲學家編號,0—N-1{while(TRUE){ //無限循環(huán)

think(); //哲學家正在思考

take_forks(i); //取用兩支筷子或阻塞

eat(); //進餐

put_forks(i)//把兩支筷子同時放回桌子上}參考代碼voidtake_forks(inti)//i為哲學家編號,0—N-1{down(&mutex); //進入臨界區(qū)state[i]=HUNGRY; //記錄哲學家的饑餓情況test(i); //試圖得到兩支筷子up(&mutex); //離開臨界區(qū)down(&s[i]); //如果得不到筷子則阻塞}參考代碼voidput_forks(inti) //i為哲學家編號,0—N-1{down(&mutex); //進入臨界區(qū)state[i]=THINKING; //哲學家進餐結(jié)束test(LEFT); //看一下左鄰居現(xiàn)在是否能進餐test(RIGHT);//看一下右鄰居現(xiàn)在是否能進餐up(&mutex); //離開臨界區(qū)}參考代碼voidtest(inti){if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){state[i]=EATING;up(&s[i]);}}理發(fā)師睡眠問題問題描述：理發(fā)店里有一位理發(fā)師、1把理發(fā)椅子和n把供等候理發(fā)的顧客坐的椅子。如果沒有顧客，理發(fā)師便在理發(fā)椅子上睡覺。當一個顧客到來時，他必須叫醒理發(fā)師，如果理發(fā)師正在理發(fā)時又有顧客來到，而如果有空閑的等待椅子，他就坐下來等待；如果沒有空閑的等待椅子，他就離開。理發(fā)師睡眠問題要求：為理發(fā)師和顧客各編寫一段程序來描述他們的行為，但不能帶有競爭條件。設(shè)三個信號量：customers，用來記錄等候理發(fā)的顧客數(shù)（不包括正在理發(fā)的m顧客）；barbers，記錄正在等待顧客的理發(fā)師數(shù)，為0或1；mutex，用于互斥。理發(fā)師睡眠問題#defineCHAIRS5//等候的顧客準備椅子數(shù)typedefintsemaphore; semaphorecustomers=0;//等候服務(wù)的顧客數(shù)semaphorebarbers=0;//等候服務(wù)的理發(fā)師數(shù)semaphoremutex=1; //互斥信號intwaiting=0; //還沒理發(fā)的等候顧客理發(fā)師睡眠問題voidbarbers(void){while(TRUE){down(customers); //如果顧客數(shù)是0，則睡覺

down(mutex); //要求進程等候

waiting=waiting-1; //等候顧客數(shù)減1up(barbers); //一個理發(fā)師現(xiàn)在開始理發(fā)

up(mutex); //釋放等候

cut_hair(); //理發(fā)(非臨界區(qū)操作)}}

理發(fā)師睡眠問題voidcustomers(void){down(mutex); //進入臨界區(qū)if(waiting<CHAIRS)//如果沒有空位置，則離開{waiting=waiting+1; //等候顧客數(shù)加1up(customers); //如果必要,喚醒理發(fā)師

up(mutex); //釋放訪問等候

down(barbers); //如果barbers為0，則睡覺

get_haircut(); //坐下等候服務(wù)}else{up(mutex);} //店里人滿，離開}2.3.4進程通信進程之間互相交換信息的工作稱之為進程通信IPC(InterProcessCommunication)并發(fā)進程間可以通過PV操作交換信息,但信息量是有限的，通信的效率也很低，因而稱之為低級通信。進程間高級通信主要有消息傳遞、管道文件方式和共享主存等。1.消息傳遞消息傳遞模式分兩大類：消息緩沖（直接通信）信箱通信（間接通信）。（1）消息緩沖（直接通信）

發(fā)送進程發(fā)消息時要指定接收進程的名字，反過來，接收時要指明發(fā)送進程的名字。系統(tǒng)提供兩條原語：Send(P,message)Receiver(Q,message)（1）消息緩沖（直接通信）一個進程可以與多個進程通信，它可以向多個進程發(fā)送消息，也可以接受多個不同的相關(guān)進程發(fā)來的消息。如果進程在一段時間內(nèi)收到多個消息而來不及處理，就可以將這些消息組織成消息隊列。對于消息隊列的管理屬于臨界區(qū)的管理。（2）信箱通信（間接通信）收發(fā)雙方進程通過某種中間實體，作為通信進程間的媒介，即信箱（MailBox）發(fā)送進程發(fā)消息時不指定接收進程的名字，而是指定一個中間媒介。通常收方和發(fā)方的數(shù)目可以是任意的。這種方式廣泛應(yīng)用于多機系統(tǒng)和計算機網(wǎng)絡(luò)中。（2）信箱通信（間接通信）發(fā)送原語：send(信箱,Message)接收原語：receive(信箱,Message)信箱頭信箱體發(fā)送進程接收進程2.管道（Pipe）文件方式利用共享文件實現(xiàn)進程間通信。如UNIX中的管道（PIPE）。寫進程讀進程PIPE管道與消息緩沖的區(qū)別（1）管道是以文件為傳輸介質(zhì)，因此可以進行大量的數(shù)據(jù)傳輸，消息則適用于少量數(shù)據(jù)的傳輸。（2）管道是以自然流的方式讀寫，而消息通信是以消息為單位的。（3）管道是以先寫進的先被讀出（FIFO）方式工作，而消息通信則不是。管道通信機制必須提供三個方面的協(xié)調(diào)能力

互斥：當一個進程正在對PIPE進行讀寫時，另一個必須等待（一次只有一個進程可以訪問）同步：當寫進程把一定量的數(shù)據(jù)（如4KB）寫入PIPE后，便睡眠等待，直到讀進程取走數(shù)據(jù)后再喚醒它；當讀進程讀一個空PIPE時，也應(yīng)睡眠等待，直到寫進程將消息寫入管道為止，才將它喚醒。對方是否存在。只有已確定對方存在時，方能進行通信。3.共享主存主存中開辟一個共享存儲區(qū)，一組進程向該共享存儲區(qū)中寫數(shù)據(jù)，另一組進程從共享存儲區(qū)中讀數(shù)據(jù)。ProcessASharedmemoryProcessBKerruel—共享主存的特點由一個進程創(chuàng)建，但多個進程都可以訪問。速度快，效率高往往與其他通信機制，如信號量，配合使用，來實現(xiàn)進程間的同步和通信。2.4處理器調(diào)度處理機管理的工作是對CPU資源進行合理的分配使用，以提高處理機利用率，并使各用戶公平地得到處理機資源。要解決的問題WHAT：按什么原則分配CPU—進程調(diào)度算法WHEN：何時分配CPU—進程調(diào)度的時機HOW：如何分配CPU—CPU調(diào)度過程（進程的上下文切換）2.4.1處理器的調(diào)度級別高級調(diào)度（作業(yè)調(diào)度）中級調(diào)度（交換調(diào)度）低級調(diào)度（進程調(diào)度）1.高級調(diào)度（作業(yè)調(diào)度）主要功能是根據(jù)一定的算法，從輸入的一批作業(yè)中選出若干個作業(yè)，為它們分配必要的資源。為它們建立相應(yīng)的用戶作業(yè)進程和為其服務(wù)的系統(tǒng)進程（如輸入、輸出進程）最后把它們的程序和數(shù)據(jù)調(diào)入主存，等待進程調(diào)度程序?qū)ζ鋱?zhí)行調(diào)度，并在作業(yè)完成后作善后處理工作。2.中級調(diào)度（交換調(diào)度）功能是在主存使用情況緊張時，將一些暫時不能運行的進程從主存對換到輔存上等待。當主存有足夠的空閑空間時，再將合適的進程重新?lián)Q入主存，等待進程調(diào)度。引入中級調(diào)度的主要目的是為了提高主存的利用率和系統(tǒng)吞吐量。它實際上就是存儲器管理中的交換功能。3.低級調(diào)度（進程調(diào)度）主要功能是按照某種調(diào)度策略從進程的就緒隊列中選擇一個進程，讓它占用處理器。進程調(diào)度程序確定什么時間將處理器給哪一個進程，并確定使用的時間，最終實現(xiàn)處理器在進程間的切換。2.4.2作業(yè)與作業(yè)調(diào)度1.作業(yè)概述2.作業(yè)調(diào)度與進程調(diào)度的比較1.作業(yè)概述作業(yè)就是用戶在一次計算過程中，或者一次事務(wù)處理過程中，要求計算機系統(tǒng)所做的全部工作。作業(yè)由程序、數(shù)據(jù)和作業(yè)說明書構(gòu)成。一個作業(yè)可劃分成若干個部分，每個部分稱為一個作業(yè)步，各作業(yè)步之間存在著相互聯(lián)系。1.作業(yè)概述從作業(yè)提交給系統(tǒng)，到作業(yè)運行完畢被撤消，就是一個作業(yè)的生命周期。作業(yè)在整個生命周期中存在著四種狀態(tài)，即提交狀態(tài)、后備狀態(tài)、運行狀態(tài)和完成狀態(tài)。作業(yè)的狀態(tài)與狀態(tài)的轉(zhuǎn)換提交狀態(tài)后備狀態(tài)完成狀態(tài)執(zhí)行就緒阻塞運行狀態(tài)輸入作業(yè)調(diào)度作業(yè)調(diào)度作業(yè)控制塊JCB

在把一個作業(yè)提交給系統(tǒng)時，系統(tǒng)也要開辟一個作業(yè)控制塊JCB（JobControlBlock），它是存放作業(yè)控制和管理信息的數(shù)據(jù)結(jié)構(gòu)。JCB是作業(yè)存在的唯一標志，它是作業(yè)調(diào)度和資源分配的依據(jù)。當作業(yè)完成時，系統(tǒng)將它的JCB從現(xiàn)行作業(yè)隊列中刪除，同時收回作業(yè)所占資源。JCB中包含的信息用戶名作業(yè)名作業(yè)類別作業(yè)現(xiàn)行狀態(tài)主存需求量作業(yè)優(yōu)先數(shù)外設(shè)類型與需求數(shù)量作業(yè)提交時間作業(yè)運行時間（估計）作業(yè)控制塊（JCB）指針其它作業(yè)和進程的關(guān)系（1）作業(yè)是任務(wù)實體，進程是完成任務(wù)的執(zhí)行實體。（2）沒有作業(yè)任務(wù)，進程無事可干，沒有進程，作業(yè)任務(wù)沒法完成。（3）作業(yè)的概念更多地用在批處理操作系統(tǒng)中，而進程則可以用于各種多道程序設(shè)計系統(tǒng)。2.作業(yè)調(diào)度與進程調(diào)度的比較作業(yè)調(diào)度職責是從后備作業(yè)隊列中按一定的算法選擇一個或幾個作業(yè)裝入主存若有多個作業(yè)被裝入主存，則系統(tǒng)將相繼創(chuàng)建多個進程，這些進程都處于就緒狀態(tài)

2.作業(yè)調(diào)度與進程調(diào)度的比較進程調(diào)度的實質(zhì)就是實現(xiàn)處