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

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

1、,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級(jí),第三級(jí),第四級(jí),第五級(jí),*,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)程間的這種限制條件稱為進(jìn)程互斥，這是引起資源不可共享的原因。,同步：,我們把進(jìn)程間的這種必須互相合作的協(xié)同工作關(guān)系，稱為進(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)

2、程去使用共享資源（即使某個(gè)進(jìn)程剛用過(guò)也允許再次使用），這是通過(guò),進(jìn)程互斥,的方式來(lái)管理共享資源,如果某個(gè)進(jìn)程,通過(guò)共享資源得到指定消息,時(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)程必須

3、等待,讓權(quán)等待，有進(jìn)程在臨界區(qū)執(zhí)行時(shí)，要求進(jìn)入的進(jìn)程必須立即釋放,CPU,而等待,有限等待，不應(yīng)該使進(jìn)入臨界區(qū)的進(jìn)程無(wú)限期地等待在臨界區(qū)之外,實(shí)現(xiàn)方法：軟件方法、硬件方法,臨界區(qū)問(wèn)題的解決方案,-,滿足三個(gè)基本條件,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.,信號(hào)量,信號(hào)量表示資源的物理實(shí)體,typedef,struct,int,value;/,系統(tǒng)初始化時(shí)根據(jù)代表資源類可用的數(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)程

6、和資源進(jìn)行管理，根據(jù)用途不同，可以把信號(hào)量分為,公用信號(hào)量,和,私有信號(hào)量,公用信號(hào)量,，用于解決進(jìn)程之間,互斥,進(jìn)入臨界區(qū),私有信號(hào)量,，用于解決異步環(huán)境下進(jìn)程之間的,同步,，,利用信號(hào)量解決臨界區(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ū)

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

8、semaphore r=1;/,所有讀者排隊(duì),semaphore,rw,=1;/,一個(gè)讀者與一個(gè)寫者競(jìng)爭(zhēng)訪問(wèn)文件,/,讀者,do,wait(r,);/,其他讀進(jìn)程在,r,上排隊(duì),wait(rw,);/,一個(gè)讀進(jìn)程與一個(gè)寫進(jìn)程在,rw,上競(jìng)爭(zhēng),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,);/,一個(gè)寫進(jìn)程在,rw,競(jìng)爭(zhēng),signal(wmutex,);,wait(rwmutex,);/,其他寫進(jìn)程在,rwmutex,上排隊(duì),寫數(shù)據(jù),/CS,wait(wmutex,);,writecount,-;,if(writecount,=0),signal(rw,);/,都寫完通知讀進(jìn)程,signal(wmutex,);,While(1),讀者,-,寫者（兩者公平）,int,readcount,=0;/,讀者計(jì)數(shù),sem

10、aphore,rmutex,=1;/,讀者互斥訪問(wèn),readcount,semaphore,rwmutex,=1;/,讀者、寫者互斥訪問(wèn)文件,semaphore,rw,=1;/,讀者與寫者競(jìng)爭(zhēng)訪問(wèn)文件,/,讀者,do,wait(rw,);/,讀進(jìn)程與寫進(jìn)程在,rw,上競(jìng)爭(zhēng),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,);/,讀者寫者競(jìng)爭(zhēng),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.,互斥：只能有一個(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)入臨界區(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