《操作系統(tǒng)概念》第六版作業(yè)解答7-8章

《《操作系統(tǒng)概念》第六版作業(yè)解答7-8章》由會員分享，可在線閱讀，更多相關(guān)《《操作系統(tǒng)概念》第六版作業(yè)解答7-8章（23頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,Chapter 7,進(jìn)程同步,進(jìn)程的同步隱含了系統(tǒng)中并發(fā)進(jìn)程之間存在的兩種相互制約關(guān)系：競爭（互斥）與協(xié)作（同步）,互斥：,兩個并行的進(jìn)程,A、B，,如果當(dāng),A,進(jìn)行某個操作時，,B,不能做這一操作，進(jìn)程間的這種限制條件稱為進(jìn)程互斥，這是引起資源不可共享的原因。,同步：,我們把進(jìn)程間的這種必須互相合作的協(xié)同工作關(guān)系，稱為進(jìn)程同步。,進(jìn)程之間的互斥是由于共享系統(tǒng)資源而引起的一種間接制約關(guān)系,進(jìn)程之間的同步是并發(fā)進(jìn)程由于要協(xié)作完成同一個任務(wù)而引起的一種直接制約關(guān)系,如果無進(jìn)程在使用共享資源時，可允許任何一個進(jìn)

2、程去使用共享資源（即使某個進(jìn)程剛用過也允許再次使用），這是通過,進(jìn)程互斥,的方式來管理共享資源,如果某個進(jìn)程,通過共享資源得到指定消息,時，在指定消息未到達(dá)之前，即使無進(jìn)程在共享資源仍不允許該進(jìn)程去使用共享資源，這是通過采用,進(jìn)程同步,的方式來管理共享資源。,有些問題是互斥問題，有些是同步問題，有些是互斥同步混合問題,實現(xiàn)臨界區(qū)互斥的基本方法,臨界資源：一些被,共享的資源,，具有,一次僅允許一個進(jìn)程使用,的特點,臨界區(qū)：,并發(fā)進(jìn)程訪問臨界資源,的那段,必須互斥執(zhí)行的程序,實現(xiàn)臨界區(qū)互斥一個遵循的準(zhǔn)則,有空讓進(jìn)，臨界區(qū)空閑時，允許一個進(jìn)程進(jìn)入執(zhí)行,無空等待，有進(jìn)程在臨界區(qū)執(zhí)行時，要進(jìn)入的進(jìn)程必須

3、等待,讓權(quán)等待，有進(jìn)程在臨界區(qū)執(zhí)行時，要求進(jìn)入的進(jìn)程必須立即釋放,CPU,而等待,有限等待，不應(yīng)該使進(jìn)入臨界區(qū)的進(jìn)程無限期地等待在臨界區(qū)之外,實現(xiàn)方法：軟件方法、硬件方法,臨界區(qū)問題的解決方案,-,滿足三個基本條件,Mutual Exclusion(,互斥條件,)：,If process,P,i,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

4、wish to enter their,CSs,then only those processes that are not executing in 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 proce

5、sses are allowed to enter their,CSa,after a process has made a request to enter its CS and before that request is granted.,信號量,信號量表示資源的物理實體,typedef,struct,int,value;/,系統(tǒng)初始化時根據(jù)代表資源類可用的數(shù)量給其賦值,struct,process*L;/,等待使用該資源的進(jìn)程列表,semaphore,信號量的操作：,P,（,wait,）、,V,（,signal,）,P,相當(dāng)于申請資源,V,相當(dāng)于釋放資源,操作系統(tǒng)利用信號量的狀態(tài)對進(jìn)程

6、和資源進(jìn)行管理，根據(jù)用途不同，可以把信號量分為,公用信號量,和,私有信號量,公用信號量,，用于解決進(jìn)程之間,互斥,進(jìn)入臨界區(qū),私有信號量,，用于解決異步環(huán)境下進(jìn)程之間的,同步,，,利用信號量解決臨界區(qū)互斥，設(shè)置一個公用信號量,Mutext,，初始值為,1,，任何要使用臨界區(qū)資源的進(jìn)程：調(diào)用,P(Mutext,),，使用臨界區(qū)，調(diào)用,V(Mutex,),利用信號量和,PV,操作實現(xiàn)進(jìn)程同步，對所有協(xié)作關(guān)系的并發(fā)進(jìn)程，他們在使用共享資源時必須,互通消息,，僅當(dāng)進(jìn)程收到指定的消息后才能使用共享資源，否則需等待，直到指定的消息到達(dá)。,經(jīng)典同步問題,生產(chǎn)者,-,消費者,同步，生產(chǎn)者將生產(chǎn)的產(chǎn)品放入緩存區(qū)

7、，消費者從緩存區(qū)取用產(chǎn)品，所以他們要互通消息，生產(chǎn)者放之前要測試緩存區(qū)是不是滿，消費者在從緩存區(qū)取之前要測試是不是為空。,互斥，任何時候只有一個生產(chǎn)者或者消費者可以訪問緩存區(qū),讀者,-,寫者,讀寫互斥訪問,寫寫互斥訪問,允許多個讀者同時讀，多個讀者共享讀者計數(shù)器變量，互斥操作,哲學(xué)家就餐,讀者,-,寫者（寫者優(yōu)先）,int,readcount,=0,writecount,=0;/,讀者、寫者計數(shù),semaphore,rmutex,=1,wmutex,=1;/,讀者、寫者分別互斥訪問,readcount,writecount,semaphore,rwmutex,=1;/,讀者、寫者互斥訪問文件,

8、semaphore r=1;/,所有讀者排隊,semaphore,rw,=1;/,一個讀者與一個寫者競爭訪問文件,/,讀者,do,wait(r,);/,其他讀進(jìn)程在,r,上排隊,wait(rw,);/,一個讀進(jìn)程與一個寫進(jìn)程在,rw,上競爭,wait(rmutex,);,readcount,+;,if(readcount,=1),wait(rwmutex,);,signal(rmutex,);,signal(rw,);,signal(r,);,讀數(shù)據(jù),/CS,wait(rmutex,);,readcount,-;,if(readcount,=0),signal(rwmutex,);,signa

9、l(rmutex,);,while(1);,/,寫者,Do,wait(wmutex,);,writecount,+;,if(writecount,=1),wait(rw,);/,一個寫進(jìn)程在,rw,競爭,signal(wmutex,);,wait(rwmutex,);/,其他寫進(jìn)程在,rwmutex,上排隊,寫數(shù)據(jù),/CS,wait(wmutex,);,writecount,-;,if(writecount,=0),signal(rw,);/,都寫完通知讀進(jìn)程,signal(wmutex,);,While(1),讀者,-,寫者（兩者公平）,int,readcount,=0;/,讀者計數(shù),sem

10、aphore,rmutex,=1;/,讀者互斥訪問,readcount,semaphore,rwmutex,=1;/,讀者、寫者互斥訪問文件,semaphore,rw,=1;/,讀者與寫者競爭訪問文件,/,讀者,do,wait(rw,);/,讀進(jìn)程與寫進(jìn)程在,rw,上競爭,wait(rmutex,);,readcount,+;,if(readcount,=1),wait(rwmutex,);,signal(rmutex,);,signal(rw,);,讀數(shù)據(jù),/CS,wait(rmutex,);,readcount,-;,if(readcount,=0),signal(rwmutex,);,s

11、ignal(rmutex,);,while(1);,/,寫者,Do,wait(rw,);/,讀者寫者競爭,wait(rwmutex,);,寫數(shù)據(jù),/CS,signal(wmutex,);,signal(rw,);,While(1),哲學(xué)家就餐,共享變量,semaphore chopstick5,mutex,;/Initially all values are 1,Philosopher i:,do,wait(mutex,);,wait(chopsticki,),wait(chopstick(i+1)%5),signal(mutex,);,eat,signal(chopsticki,);,sig

12、nal(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,T,0 and,T,1,share the following variables:,Boolean flag2;/*initially false*/,int,turn;,The structure of thread,T,i(i=

13、0 or 1),with,T,j,(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=j;,flag i=false;,remainder section,while(1);,Prove that the algorithm satisfies all three requirements for the critical-section probl

14、em.,互斥：只能有一個在臨界區(qū),Pi,在臨界區(qū)，,Pj,想進(jìn)，看,flag,某進(jìn)程進(jìn)入臨界區(qū)之前，,Pi,、,Pj,都置,flag,為,true,，看,turn,，只有進(jìn)了的進(jìn)程退出臨界區(qū)以后另一個才能進(jìn),進(jìn)度：,當(dāng)前沒有進(jìn)程在臨界區(qū)，只有一個進(jìn)程試圖進(jìn)，看,flag,兩個都試圖進(jìn)，看,turn,，進(jìn)了進(jìn)程在有限時間內(nèi)復(fù)位,flag,有限等待：,Pi,被拒絕進(jìn)入臨界區(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

15、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,want in,in,csg,;,pstate,flagn,;,int,turn;,All the elements of,flag,are initially idle;the initial value of,tu

16、rn,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,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 goes to sleep.I