1、Chapter 7進(jìn)程同步,進(jìn)程的同步隱含了系統(tǒng)中并發(fā)進(jìn)程之間存在的兩種相互制約關(guān)系：競(jìng)爭(zhēng)（互斥）與協(xié)作（同步） 互斥：兩個(gè)并行的進(jìn)程A、B，如果當(dāng)A進(jìn)行某個(gè)操作時(shí)，B不能做這一操作，進(jìn)程間的這種限制條件稱(chēng)為進(jìn)程互斥，這是引起資源不可共享的原因。 同步：我們把進(jìn)程間的這種必須互相合作的協(xié)同工作關(guān)系，稱(chēng)為進(jìn)程同步。 進(jìn)程之間的互斥是由于共享系統(tǒng)資源而引起的一種間接制約關(guān)系 進(jìn)程之間的同步是并發(fā)進(jìn)程由于要協(xié)作完成同一個(gè)任務(wù)而引起的一種直接制約關(guān)系 如果無(wú)進(jìn)程在使用共享資源時(shí)，可允許任何一個(gè)進(jìn)程去使用共享資源（即使某個(gè)進(jìn)程剛用過(guò)也允許再次使用），這是通過(guò)進(jìn)程互斥的方式來(lái)管理共享資源 如果某個(gè)進(jìn)程通過(guò)

2、共享資源得到指定消息時(shí)，在指定消息未到達(dá)之前，即使無(wú)進(jìn)程在共享資源仍不允許該進(jìn)程去使用共享資源，這是通過(guò)采用進(jìn)程同步的方式來(lái)管理共享資源。 有些問(wèn)題是互斥問(wèn)題，有些是同步問(wèn)題，有些是互斥同步混合問(wèn)題,實(shí)現(xiàn)臨界區(qū)互斥的基本方法,臨界資源：一些被共享的資源，具有一次僅允許一個(gè)進(jìn)程使用的特點(diǎn) 臨界區(qū)：并發(fā)進(jìn)程訪問(wèn)臨界資源的那段必須互斥執(zhí)行的程序 實(shí)現(xiàn)臨界區(qū)互斥一個(gè)遵循的準(zhǔn)則 有空讓進(jìn)，臨界區(qū)空閑時(shí)，允許一個(gè)進(jìn)程進(jìn)入執(zhí)行 無(wú)空等待，有進(jìn)程在臨界區(qū)執(zhí)行時(shí)，要進(jìn)入的進(jìn)程必須等待 讓權(quán)等待，有進(jìn)程在臨界區(qū)執(zhí)行時(shí)，要求進(jìn)入的進(jìn)程必須立即釋放CPU而等待 有限等待，不應(yīng)該使進(jìn)入臨界區(qū)的進(jìn)程無(wú)限期地等待在臨界區(qū)之

3、外 實(shí)現(xiàn)方法：軟件方法、硬件方法,臨界區(qū)問(wèn)題的解決方案-滿足三個(gè)基本條件,Mutual Exclusion(互斥條件)： If process Pi is executing in its CS, then no other processes can be executing in their CSs Progress(進(jìn)入條件)：If no process is executing in its CS and some processes wish to enter their CSs, then only those processes that are not executing in

4、 their RSs can participate in the decision on which will enter its CS next, and this selection cannot be postponed indefinitely. Bounded Waiting(有限等待的條件)：There exists a bound, or limit, on the number of times that other processes are allowed to enter their CSa after a process has made a request to e

5、nter its CS and before that request is granted.,信號(hào)量,信號(hào)量表示資源的物理實(shí)體 typedef struct int value;/系統(tǒng)初始化時(shí)根據(jù)代表資源類(lèi)可用的數(shù)量給其賦值 struct process *L;/等待使用該資源的進(jìn)程列表 semaphore 信號(hào)量的操作：P（wait）、V（signal） P相當(dāng)于申請(qǐng)資源 V相當(dāng)于釋放資源 操作系統(tǒng)利用信號(hào)量的狀態(tài)對(duì)進(jìn)程和資源進(jìn)行管理，根據(jù)用途不同，可以把信號(hào)量分為公用信號(hào)量和私有信號(hào)量 公用信號(hào)量，用于解決進(jìn)程之間互斥進(jìn)入臨界區(qū) 私有信號(hào)量，用于解決異步環(huán)境下進(jìn)程之間的同步， 利用信號(hào)量

6、解決臨界區(qū)互斥，設(shè)置一個(gè)公用信號(hào)量Mutext，初始值為1，任何要使用臨界區(qū)資源的進(jìn)程：調(diào)用P(Mutext) ，使用臨界區(qū)，調(diào)用V(Mutex) 利用信號(hào)量和PV操作實(shí)現(xiàn)進(jìn)程同步，對(duì)所有協(xié)作關(guān)系的并發(fā)進(jìn)程，他們?cè)谑褂霉蚕碣Y源時(shí)必須互通消息，僅當(dāng)進(jìn)程收到指定的消息后才能使用共享資源，否則需等待，直到指定的消息到達(dá)。,經(jīng)典同步問(wèn)題,生產(chǎn)者-消費(fèi)者 同步，生產(chǎn)者將生產(chǎn)的產(chǎn)品放入緩存區(qū)，消費(fèi)者從緩存區(qū)取用產(chǎn)品，所以他們要互通消息，生產(chǎn)者放之前要測(cè)試緩存區(qū)是不是滿，消費(fèi)者在從緩存區(qū)取之前要測(cè)試是不是為空。 互斥，任何時(shí)候只有一個(gè)生產(chǎn)者或者消費(fèi)者可以訪問(wèn)緩存區(qū) 讀者-寫(xiě)者 讀寫(xiě)互斥訪問(wèn) 寫(xiě)寫(xiě)互斥訪問(wèn) 允

7、許多個(gè)讀者同時(shí)讀，多個(gè)讀者共享讀者計(jì)數(shù)器變量，互斥操作 哲學(xué)家就餐,讀者-寫(xiě)者（寫(xiě)者優(yōu)先）,int readcount=0, writecount=0;/讀者、寫(xiě)者計(jì)數(shù) semaphore rmutex=1, wmutex=1;/讀者、寫(xiě)者分別互斥訪問(wèn)readcount, writecount semaphore rwmutex=1;/讀者、寫(xiě)者互斥訪問(wèn)文件 semaphore r=1;/所有讀者排隊(duì) semaphore rw=1;/一個(gè)讀者與一個(gè)寫(xiě)者競(jìng)爭(zhēng)訪問(wèn)文件 /讀者 do wait(r);/其他讀進(jìn)程在r上排隊(duì) wait(rw);/一個(gè)讀進(jìn)程與一個(gè)寫(xiě)進(jìn)程在rw上競(jìng)爭(zhēng) wait(rmute

8、x); readcount+; if(readcount =1) wait(rwmutex); signal(rmutex); signal(rw); signal(r); 讀數(shù)據(jù)/CS wait(rmutex); readcount-; if(readcount =0) signal(rwmutex); signal(rmutex); while(1);,/寫(xiě)者 Do wait(wmutex); writecount+; if(writecount=1) wait(rw);/一個(gè)寫(xiě)進(jìn)程在rw競(jìng)爭(zhēng) signal(wmutex); wait(rwmutex);/其他寫(xiě)進(jìn)程在rwmutex上排隊(duì)

9、寫(xiě)數(shù)據(jù)/CS wait(wmutex); writecount-; if(writecount=0) signal(rw); /都寫(xiě)完通知讀進(jìn)程 signal(wmutex); While(1),讀者-寫(xiě)者（兩者公平）,int readcount=0;/讀者計(jì)數(shù) semaphore rmutex=1;/讀者互斥訪問(wèn)readcount semaphore rwmutex=1;/讀者、寫(xiě)者互斥訪問(wèn)文件 semaphore rw=1;/讀者與寫(xiě)者競(jìng)爭(zhēng)訪問(wèn)文件 /讀者 do wait(rw);/讀進(jìn)程與寫(xiě)進(jìn)程在rw上競(jìng)爭(zhēng) wait(rmutex); readcount+; if(readcount =

10、1) wait(rwmutex); signal(rmutex); signal(rw); 讀數(shù)據(jù)/CS wait(rmutex); readcount-; if(readcount =0) signal(rwmutex); signal(rmutex); while(1);,/寫(xiě)者 Do wait(rw);/讀者寫(xiě)者競(jìng)爭(zhēng) wait(rwmutex); 寫(xiě)數(shù)據(jù)/CS signal(wmutex); signal(rw); While(1),哲學(xué)家就餐,共享變量 semaphore chopstick5, mutex;/Initially all values are 1 Philosopher

11、 i: do wait(mutex); wait(chopsticki) wait(chopstick(i+1) % 5) signal(mutex); eat signal(chopsticki); signal(chopstick(i+1) % 5); think while (1);,Chapter 7,7.4 The first known correct software solution to the critical-section problem for two threads was developed by Dekker. The two threads, T0 and T

12、1, share the following variables: Boolean flag2; /* initially false */ int turn; The structure of thread Ti (i=0 or 1), with Tj (j=1 or 0) being the other thread, is shown as: do flag i = true; while ( flag j ) if (turn = j) flag i = false; while (turn = = j); flag i = true; critical section turn =

13、j; flag i = false; remainder section while (1); Prove that the algorithm satisfies all three requirements for the critical-section problem. 互斥：只能有一個(gè)在臨界區(qū) Pi在臨界區(qū)，Pj想進(jìn)，看flag 某進(jìn)程進(jìn)入臨界區(qū)之前，Pi、Pj都置flag為true，看turn，只有進(jìn)了的進(jìn)程退出臨界區(qū)以后另一個(gè)才能進(jìn) 進(jìn)度： 當(dāng)前沒(méi)有進(jìn)程在臨界區(qū)，只有一個(gè)進(jìn)程試圖進(jìn)，看flag 兩個(gè)都試圖進(jìn)，看turn，進(jìn)了進(jìn)程在有限時(shí)間內(nèi)復(fù)位flag 有限等待： Pi被拒絕進(jìn)入

14、臨界區(qū)，Pj已在臨界區(qū)或者獲準(zhǔn)進(jìn)入，當(dāng)Pj退出臨界區(qū)，置turn為i，復(fù)位flag，Pi可以進(jìn),7-cont.,7.5 The first known correct software solution to the critical-section problem for n processes with a lower bound on waiting of n - 1 turns was presented by Eisenberg and McGuire. The processes share the following variables: enum pstate fidle, w

15、ant in, in csg; pstate flagn; int turn; All the elements of flag are initially idle; the initial value of turn is immaterial (between 0 and n-1). The structure of process Pi is shown as: Prove that the algorithm satisfies all three requirements for the critical-section problem.,7-cont.,7.7 Show that

16、, if the wait and signal operations are not executed atomically, then mutual exclusion may be violated.,7-cont.,7.8 The Sleeping-Barber Problem. A barbershop consists of a waiting room with n chairs and the barber room containing the barber chair. If there are no customers to be served, the barber g

17、oes to sleep. If a customer enters the barbershop and all chairs are occupied, then the customer leaves the shop. If the barber is busy but chairs are available, then the customer sits in one of the free chairs. If the barber is asleep, the customer wakes up the barber. Write a program to coordinate

18、 the barber and the customers. 理發(fā)師和顧客同步，理發(fā)師必須由顧客喚醒，理發(fā)師給一個(gè)顧客理發(fā)完，要讓理發(fā)完的顧客退出，讓等待顧客進(jìn)入，顧客互斥的占用n個(gè)位置 /共享變量 semaphore Scuthair, Snumchair;/ Scuthair制約理發(fā)師, Snumchair制約顧客 Scuthair=0; Snumchair=0; barber: do wait(Scuthair);/檢查是否有顧客，無(wú)就睡眠 給某個(gè)顧客理發(fā) signal(Snumchair);/讓理發(fā)完的顧客退出，讓等待的一個(gè)顧客進(jìn)入 while (1); Customer i: wai

19、t(Snumchair);/申請(qǐng)占用椅子 signal(Scuthair);/給理發(fā)師發(fā)一個(gè)信號(hào) 坐在椅子上等著理發(fā),/共享變量 semaphore Scuthair, Mutexchair;/ Scuthair給理發(fā)師, Mutexchair制約顧客對(duì)椅子的互斥占領(lǐng) int number = 0;/顧客的共享變量，記錄已經(jīng)有的顧客數(shù) Scuthair=0; Mutexchair =1; Customer i: wait(Mutexchair);/申請(qǐng)對(duì)共享變量number的操作（申請(qǐng)占用椅子） if(number = = n-1)signal(Mutexchair); exit; numbe

20、r = number +1; signal(Scuthair);/給理發(fā)師發(fā)一個(gè)信號(hào) signal(Mutexchair); 等待理發(fā) 理發(fā)完畢 wait(Mutexchair);/申請(qǐng)對(duì)共享變量number的操作 number = number -1; signal(Mutexchair); 離開(kāi)理發(fā)店 barber: do wait(Scuthair);/檢查是否有顧客，無(wú)，就睡眠 給某個(gè)顧客理發(fā) while (1);,7-cont.,7.9 The Cigarette-Smokers Problem. Consider a system with three smoker process

21、es and one agent process. Each smoker continuously rolls a cigarette and then smokes it. But to roll and smoke a cigarette, the smoker needs three ingredients: tobacco, paper, and matches. One of the smoker processes has paper, another has tobacco, and the third has matches. The agent has an infinit

22、e supply of all three materials. The agent places two of the ingredients on the table. The smoker who has the remaining ingredient then makes and smokes a cigarette, signaling the agent on completion. The agent then puts out another two of the three ingredients, and the cycle repeats. Write a progra

23、m to synchronize the agent and the smokers. 原料供應(yīng)者和三個(gè)吸煙者之間需要同步 /共享變量 semaphore Sa, Ss;/分別控制供應(yīng)者和吸煙者 Sa = 1; Ss =0; /供應(yīng)者 wait(Sa);/桌面上沒(méi)有原料 任意丟兩樣?xùn)|西到桌面 signal(Ss);/通知吸煙者 /吸煙者 wait(Ss);/查看桌面原料，同時(shí)只能有一個(gè)吸煙者查看 if(是我需要的兩種原料) 取原料，卷煙，吸煙 signal(Sa);/通知供應(yīng)者可以放新的原料 else signal(Ss);/讓別的吸煙者查看 ,吸煙者另解-更細(xì),/共享變量 semaphore

24、 Sa;/控制供應(yīng)者 semaphore S1, S2, S3;/控制三個(gè)吸煙者 Sa = 1; S1 = S2 = S3 = 0; /供應(yīng)者 flag f1, f2, f3;/三個(gè)標(biāo)記，分別代表紙，煙草，火柴 wait(Sa);/桌面上沒(méi)有原料 任意丟兩樣?xùn)|西到桌面 if(f2 /通知有火柴的吸煙者,/有紙的吸煙者 wait(S1);/等待桌面上有需要的原料 取煙草，火柴，卷煙，吸煙 signal(Sa);/通知供應(yīng)者可以放新的原料 /有煙草的吸煙者 wait(S2);/等待桌面上有需要的原料 取紙，火柴，卷煙，吸煙 signal(Sa);/通知供應(yīng)者可以放新的原料 /有火柴的吸煙者 wai

25、t(S3);/等待桌面上有需要的原料 取紙，煙草，卷煙，吸煙 signal(Sa);/通知供應(yīng)者可以放新的原料,Chapter 8,資源是有限的，對(duì)資源的需求可能是無(wú)限的 當(dāng)占有了部分資源而渴求更多的資源的時(shí)候，可能會(huì)引起deadlock（死鎖） 計(jì)算機(jī)資源具有兩類(lèi)不同的性質(zhì)：可搶占和不可搶占 可搶占資源：當(dāng)資源從占用進(jìn)程剝奪走時(shí)，對(duì)進(jìn)程不產(chǎn)生破壞性影響，CPU和主存 不可搶占資源：當(dāng)資源從占用進(jìn)程剝奪走時(shí)，可能引起進(jìn)程計(jì)算失敗，打印機(jī)、繪圖儀、 通常，死鎖涉及的是不可搶占資源 死鎖：一組進(jìn)程是死鎖的，該組中的每一個(gè)進(jìn)程正在等待這組中其他進(jìn)程占有的資源時(shí)可能引起的一種錯(cuò)誤現(xiàn)象。 死鎖產(chǎn)生的原因

26、 根本原因，系統(tǒng)資源不足 進(jìn)程推進(jìn)順序不當(dāng) 死鎖產(chǎn)生的必要條件 互斥，占有和等待，不可剝奪，循環(huán)等待,死鎖處理策略,忽略不計(jì) 預(yù)防，設(shè)法破壞四個(gè)必要條件 避免 為進(jìn)程分配資源時(shí)，每當(dāng)完成分配后，立即檢查系統(tǒng)是否處于安全狀態(tài)，若是，分配成功，否則，分配作廢，讓其阻塞等待 資源分配圖算法、銀行家算法 需要進(jìn)程對(duì)資源需求的先驗(yàn)知識(shí) 設(shè)法找到一種安全的進(jìn)程執(zhí)行序列 檢測(cè)與恢復(fù) 采用資源動(dòng)態(tài)分配算法，當(dāng)進(jìn)程請(qǐng)求分配資源時(shí)，只要系統(tǒng)有可用資源就滿足，系統(tǒng)定期啟動(dòng)死鎖檢測(cè)算法，檢查是否有環(huán)（進(jìn)程等待圖）,Chapter 8,8.4 Consider the traffic deadlock depicted

27、 in following Figure. a. Show that the four necessary conditions for deadlock indeed hold in this example. b. State a simple rule that will avoid deadlocks in this system.,8 cont.,8.6 In a real computer system, neither the resources available nor the demands of processes for resources are consistent

28、 over long periods (months). Resources break or are replaced, new processes come and go, new resources are bought and added to the system. If deadlock is controlled by the bankers algorithm, which of the following changes can be made safely (without introducing the possibility of deadlock), and unde

29、r what circumstances? a. Increase Available (new resources added) b. Decrease Available (resource permanently removed from system) c. Increase Max for one process (the process needs more resources than allowed, it may want more) d. Decrease Max for one process (the process decides it does not need that many resources) e. Increase the number of processes f. Decrease the number of processes,8-cont.,8.9 Consider a system consisting of