【正文】 …… mutex=1,empty=n,full=0。x,y:condition。end 141說明u 局部于管程的數(shù)據(jù)結(jié)構(gòu)，僅能被局部于管程的過程所訪問，任何管程外的過程都不能訪問它；u 局部于管程的過程也僅能訪問管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)；u 管程被請求和釋放資源的進(jìn)程所調(diào)用；u 管程把共享變量和對它進(jìn)行的若干過程圍了起來，所有進(jìn)程要訪問臨界資源時(shí)，都必須經(jīng)過管程才能進(jìn)入，而管程每次只準(zhǔn)許一個(gè)進(jìn)程進(jìn)入，從而既便于系統(tǒng)管理共享資源，又能保證進(jìn)程互斥。end。管程被請求和釋放資源的進(jìn)程所調(diào)用。wait(j)。wait(d)。wait(a)。}。S4。signal(b)。remainder一般 “信號(hào)量集 ”的幾種特殊情況129利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥利用信號(hào)量來描述前趨關(guān)系 信號(hào)量的應(yīng)用130semaphoresii++){si…amp。readythistheA:wait(Emutex)://Emutex=1wakeup(s,L)。ofwhile(true){s1:{while(true){noop。– 指在任何條件下都不使之中斷或處于不完整狀態(tài)的操作。（ 4）讓權(quán)等待如何保證諸進(jìn)程互斥地訪問臨界資源？114v一個(gè)訪問臨界資源的循環(huán)進(jìn)程的描述while(true){entry counter++。(register1=5)//其實(shí)一個(gè)例子足以說明問題！register1++。生產(chǎn)者 — 消費(fèi)者問題的實(shí)現(xiàn)109o 生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程在分別看時(shí)都是正確的；o 它們在順序執(zhí)行時(shí)的結(jié)果也是沒有問題的；o 并發(fā)執(zhí)行時(shí)就會(huì)出現(xiàn)差錯(cuò)。 //空操作，重復(fù)測試 buffer[in]=nextp。in==out生產(chǎn)者 — 消費(fèi)者問題的實(shí)現(xiàn)106u整型變量 counter167。有 一群 生產(chǎn)者進(jìn)程 在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給 一群 消費(fèi)者進(jìn)程 去消費(fèi)。在多道程序環(huán)境下，當(dāng)程序并發(fā)執(zhí)行時(shí)，由于 資源共享 和 進(jìn)程合作 ，使同處于一個(gè)系統(tǒng)中的諸進(jìn)程之間可能存在著以下兩種形式的制約關(guān)系。? 進(jìn)程是程序的一次執(zhí)行過程，它是動(dòng)態(tài)地創(chuàng)建和消亡的，具有一定的生命期，是暫時(shí)存在的；而程序則是一組代碼的集合，它是永久存在的，可長期保存。? 如果在某進(jìn)程中調(diào)用了阻塞原語，則必須在與之相合作的另一進(jìn)程中或其他相關(guān)的進(jìn)程中，安排喚醒原語，以能喚醒阻塞進(jìn)程；否則，被阻塞進(jìn)程將會(huì)因不能被喚醒而長久地處于阻塞狀態(tài)，從而再無機(jī)會(huì)繼續(xù)運(yùn)行。? 例如， 請求進(jìn)程 請求使用某資源（如打印機(jī)），由于系統(tǒng)已將打印機(jī)分配給其他進(jìn)程而不能分配給 請求進(jìn)程 ，這時(shí) 請求進(jìn)程只能被阻塞，僅在其他進(jìn)程在釋放出打印機(jī)的同時(shí)，才將 請求進(jìn)程 喚醒。– 操作員或 OS干預(yù)。這是指進(jìn)程試圖去訪問一個(gè)不允許訪問的資源或文件，或者以不適當(dāng)?shù)姆绞竭M(jìn)行訪問，例如，進(jìn)程試圖去寫一個(gè)只讀文件。– 對于批處理作業(yè)，其大小可在用戶提出創(chuàng)建進(jìn)程要求時(shí)提供。進(jìn)程圖2.5PCB– 對就緒隊(duì)列常按進(jìn)程優(yōu)先級的高低排列，把優(yōu)先級高的進(jìn)程的 PCB排在隊(duì)列前面。– Linux用 task_struct數(shù)據(jù)結(jié)構(gòu)來描述每個(gè)進(jìn)程的 PCB。? 對于處于創(chuàng)建狀態(tài)的進(jìn)程，獲得了其所必需的資源，以及對其 PCB初始化工作完成后，進(jìn)程狀態(tài)便可由創(chuàng)建狀態(tài)轉(zhuǎn)入就緒狀態(tài)。– 若此時(shí)用戶進(jìn)程正處于就緒狀態(tài)而未執(zhí)行，則該進(jìn)程暫不接受調(diào)度，以便用戶研究其執(zhí)行情況或?qū)Τ绦蜻M(jìn)行修改。?狀態(tài)轉(zhuǎn)換 2必然立即引發(fā)狀態(tài)轉(zhuǎn)換 1：狀態(tài)轉(zhuǎn)換 2發(fā)生后，進(jìn)程調(diào)度程序必然要選出一個(gè)新的就緒進(jìn)程投入運(yùn)行，該新進(jìn)程可能是其他進(jìn)程，也可能是剛從執(zhí)行狀態(tài)轉(zhuǎn)換成就緒狀態(tài)的那個(gè)進(jìn)程。20阻塞（ Blocked）狀態(tài)? 又稱等待狀態(tài)、封鎖狀態(tài)。Controla=x+2S2: P1?P2,P1?P3,P1?P4,P2?P5,P3?P5,P4?P6,P4?P7, P5?P8， P6?P8,P7?P9,P8?P9v 或表示為：167。?，可寫成 PiOrder）或前趨關(guān)系（Precedence4 進(jìn)程的基本概念beforePi的 直接后繼v初始結(jié)點(diǎn) Initial?Pi1) N++在 printf(N)和 N=0之前，此時(shí)得到的 N值分別為 n+1,n+1,02) N++在 printf(N)和 N=0之后，此時(shí)得到的 N值分別為 n, 0 , 13) N++在 printf(N)和 N=0之間，此時(shí)得到的 N值分別為 n,n+1,0– 結(jié)論：失去了可再現(xiàn)性11 進(jìn)程的特征與狀態(tài)1.5）異步性– 進(jìn)程各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)，或說進(jìn)程實(shí)體按異步方式運(yùn)行。此外，在可剝奪的 OS中，當(dāng)有更高優(yōu)先級的進(jìn)程就緒時(shí)，調(diào)度程序?qū)⒄龍?zhí)行的進(jìn)程轉(zhuǎn)換為就緒狀態(tài)，讓更高優(yōu)先級的進(jìn)程執(zhí)行。處于該狀態(tài)的進(jìn)程在其所期待的事件出現(xiàn)后，將從靜止阻塞變?yōu)殪o止就緒。? PCB的作用：使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序（含數(shù)據(jù)），成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其他進(jìn)程并發(fā)執(zhí)行的進(jìn)程。處理機(jī)在運(yùn)行時(shí)，許多信息都放在寄存器中。7 9PCB它是一個(gè)不可分割的基本單位，因此在執(zhí)行過程中不允許被中斷。702. 引起創(chuàng)建進(jìn)程的事件（ 4）應(yīng)用請求（由應(yīng)用進(jìn)程自己創(chuàng)建）– 前面三種情況都是由系統(tǒng)內(nèi)核為它創(chuàng)建一個(gè)新進(jìn)程；此處則是基于應(yīng)用進(jìn)程的需求，由它自己創(chuàng)建 一個(gè) 新進(jìn)程，以便使新進(jìn)程以并發(fā)運(yùn)行方式完成特定任務(wù)。當(dāng)程序運(yùn)行到 Holt指令時(shí)，將產(chǎn)生一個(gè) 中斷 ，去 通知OS本進(jìn)程已經(jīng)完成。– 等待超時(shí)。832. 進(jìn)程的終止過程（ 3）若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其所有子進(jìn)程予以終止，以防它們成為不可控的進(jìn)程。902. 進(jìn)程阻塞過程? 正在執(zhí)行的進(jìn)程，當(dāng)發(fā)現(xiàn)上述某事件時(shí)，由于無法繼續(xù)執(zhí)行，于是進(jìn)程便通過調(diào)用 阻塞原語 Block()把自己阻塞。這時(shí)，系統(tǒng)將利用 Active()原語將指定進(jìn)程激活。（ 1）若干同學(xué)去圖書館借書是間接制約，其中書是臨界資源。n167。buffer[n]。? Noop是一條空操作指令。(counter為了預(yù)防這種錯(cuò)誤，關(guān)鍵是把變量 counter作為臨界資源處理，就是令生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程互斥地訪問變量 counter。v因此，必須在臨界區(qū)前面增加一段用于進(jìn)行上述檢查的代碼，把這段代碼稱為進(jìn)入?yún)^(qū)。所有同步機(jī)制都應(yīng)遵循下述 4條準(zhǔn)則：（ 1）空閑讓進(jìn)在長期且廣泛的應(yīng)用中，信號(hào)量機(jī)制又得到了很大的發(fā)展，它從整型信號(hào)量經(jīng)記錄型信號(hào)量，進(jìn)而發(fā)展為 “信號(hào)量集 ”機(jī)制。此外，在wait操作中，對 s值的測試和做 s操作時(shí)都不可中斷。{Processamp。withi=n。theintheprocesssignal(mutex)。wait(mutex)。{wait(b)。}。{}。{135? 系統(tǒng)中的各種硬件資源和軟件資源，均可用數(shù)據(jù)結(jié)構(gòu)加以抽象的描述，即用少量信息和對該資源所執(zhí)行的操作來表征該資源，而忽略了它們的內(nèi)部結(jié)構(gòu)和實(shí)現(xiàn)細(xì)節(jié)。（ 4）管程被欲使用共享資源的所有進(jìn)程所調(diào)用，管程和調(diào)用它的進(jìn)程不能并發(fā)執(zhí)行；而進(jìn)程之間能夠并發(fā)工作，并發(fā)性是其固有特性。 Q等待，直至 P離開管程，或 P等待另一條件?！?}wait(full)。signal(mutex)。 P等待，直至 Q離開管程，或 Q等待另一條件。143管程與進(jìn)程的不同點(diǎn)（ 1）管程所定義的是公用數(shù)據(jù)結(jié)構(gòu)，如消息隊(duì)列等，進(jìn)程所定 義的是私有數(shù)據(jù)結(jié)構(gòu) PCB；（ 2）管程把共享變量上的同步操作集中起來統(tǒng)一管理，而 PV同步中的 PV操作分散在每個(gè)進(jìn)程中。– 不僅給系統(tǒng)的管理帶來麻煩，而且還會(huì)因同步操作的使用不當(dāng)而導(dǎo)致系統(tǒng) 死鎖 。signal(k)。S3。a,b,c,d,e,f,g,j,k,l:semaphore:=0,0,0,0,0,0,0,0,0。signal(g)。}。分析132利用信號(hào)量來描述的前趨關(guān)系 S1S2 S3S4 S5S6Varprocess2:{while(true){allcounterexecutingwaitingoperation.sisi。(s1=1A:wait(Dmutex)。//請求一個(gè)單位的資源semaphore和 signal(s)是原子操作，因此它們在執(zhí)行時(shí)是不可中斷的。s。例如，考慮某個(gè)采取高優(yōu)先權(quán)優(yōu)先調(diào)度原則的系統(tǒng)，目前有 2個(gè)進(jìn)程 A和 B共享某個(gè)臨界資源， A的優(yōu)先權(quán)較高， B的優(yōu)先權(quán)較低，且 B已處于臨界區(qū)內(nèi)，而 A欲進(jìn)入自己的臨界區(qū)，則 A、 B都不可能繼續(xù)向前推進(jìn)，陷入 “死等 ”狀態(tài)。section。v每個(gè)進(jìn)程在進(jìn)入臨界區(qū)之前，應(yīng)先對欲訪問的臨界資源進(jìn)行檢查，看它是否正被訪問。(register2=4)counter=register1。 //計(jì)數(shù) consume the item in nextc。item=…。v循環(huán)緩沖：167。102補(bǔ)充例題? 進(jìn)程之間存在著哪幾種制約關(guān)系？各是什么原因引起的？下列活動(dòng)分別屬于哪種制約關(guān)系？（ 1）若干同學(xué)去圖書館借書；（ 2）兩隊(duì)舉行籃球比賽；（ 3）流水線生產(chǎn)的各道工序；（ 4）商品生產(chǎn)和社會(huì)消費(fèi)。97 進(jìn)程同步? 主要任務(wù)：對多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，以使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。 942.894）無新工作可做? 系統(tǒng)往往設(shè)置一些具有某特定功能的 系統(tǒng)進(jìn)程 ，每當(dāng)這種進(jìn)程完成任務(wù)后，便把自己阻塞起來以等待新任務(wù)到來。（ 1）根據(jù)被終止進(jìn)程的標(biāo)識(shí)符，從 PCB集合中檢索出該進(jìn)程的 PCB，從中讀出該進(jìn)程的 狀態(tài) 。– 運(yùn)行超時(shí)。進(jìn)程的終止過程（進(jìn)程終止原語）771. 引起進(jìn)程終止的事件1）正常結(jié)束2）異常結(jié)束3）外界干預(yù)781）正常結(jié)束? 在任何計(jì)算機(jī)系統(tǒng)中，都應(yīng)有一個(gè)用于表示進(jìn)程已經(jīng)運(yùn)行完成的指示。692. 引起創(chuàng)建進(jìn)程的事件（ 3）提供服務(wù)（由系統(tǒng)內(nèi)核創(chuàng)建新進(jìn)程）– 當(dāng)運(yùn)行中的用戶程序提出某種請求后，系統(tǒng)將專門創(chuàng)建一個(gè)進(jìn)程來提供用戶所需要的服務(wù)。Operation）。5 0PCB此外，還可設(shè)置用戶標(biāo)識(shí)，以指示擁有該進(jìn)程的用戶。46 PCB進(jìn)程控制塊的作用進(jìn)程控制塊中的信息進(jìn)程控制塊的組織方式47 PCB的作用? 為了描述和控制進(jìn)程的運(yùn)行，系統(tǒng)為每個(gè)進(jìn)程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu) ——PCB ， PCB是進(jìn)程實(shí)體的一部分，是 OS中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)。352）進(jìn)程狀態(tài)的轉(zhuǎn)換（ 2）活動(dòng)阻塞 → 靜止阻塞–活動(dòng)阻塞狀態(tài) Blockeda：進(jìn)程處于未被掛起的阻塞狀態(tài)時(shí)。22進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換進(jìn)程調(diào)度就緒運(yùn)行阻塞時(shí) 間片完I/O請求I/O完成23三種基本狀態(tài)之間的轉(zhuǎn)換? 就緒狀態(tài) ?運(yùn)行狀態(tài)（進(jìn)程調(diào)度）– 處于就緒狀態(tài)的進(jìn)程，在調(diào)度程序?yàn)橹峙淞颂幚頇C(jī)之后，該進(jìn)程便可執(zhí)行，相應(yīng)地，它就由就緒狀態(tài)轉(zhuǎn)變?yōu)閳?zhí)行狀態(tài)。15 進(jìn)程的特征與狀態(tài)4）獨(dú)立性– 進(jìn)程實(shí)體是一個(gè)能獨(dú)立運(yùn)行的基本單位、獨(dú)立分配資源和獨(dú)立接受調(diào)度的基本單位。程序 A每執(zhí)行一次時(shí)，都要做 N++操作；程序 B則每執(zhí)行一次時(shí)，都要執(zhí)行 printf(N)操作，然后 N=0，程序 A和 B以不同的速度運(yùn)行。Ii+1, mustI1 C1 P1 I2 C2 P2程序順序執(zhí)行時(shí)的前趨圖S1： a:=x+yS2： b:=a5S3： c:=b+1前趨關(guān)系： Ii?Ci?Pi3程序順序執(zhí)行時(shí)的特征? 順序性– 處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每一操作必須在上一個(gè)操作結(jié)束之后開始。PjPj ?={(P1,P2),(P1,P3),(P1,P4),(P2,P5),(P3,P5), (P4,P6),(P4,P7),(P5,P8) (P6,P8),(P7,P9),(P8,P9) }P1P2P3P4P5P6P7不存在循環(huán)！P9P86圖 21 具有循環(huán)的圖? 前趨關(guān)系：167。c=a+bS4:– 進(jìn)程 =進(jìn)程實(shí)體– 創(chuàng)建進(jìn)程 =創(chuàng)建進(jìn)程實(shí)體中的 PCB– 撤消進(jìn)程 =撤消進(jìn)程實(shí)體中的 PCB13 進(jìn)程的特征與狀態(tài)2）動(dòng)態(tài)性– 進(jìn)程的實(shí)質(zhì)是進(jìn)程實(shí)體的一次執(zhí)行過程，因此，動(dòng)態(tài)性是進(jìn)程的最基本的特征。即使CPU空閑，該進(jìn)程也不能運(yùn)行。?狀態(tài)轉(zhuǎn)換 4可能引發(fā)狀態(tài)轉(zhuǎn)換 1：狀態(tài)轉(zhuǎn)換 4發(fā)生后，若 CPU空閑，并且沒有其他進(jìn)程競爭 CPU，則該進(jìn)程將被立即調(diào)度。32（ 3）負(fù)荷調(diào)節(jié)的需要：當(dāng)實(shí)時(shí)系統(tǒng)中的工作負(fù)荷較