操作系統(tǒng)經(jīng)典問題.doc

操作系統(tǒng)經(jīng)典問題介紹一 生產(chǎn)者-消費(fèi)者問題擴(kuò)展1.擴(kuò)展一設(shè)有一個(gè)可以裝A、B兩種物品的倉(cāng)庫(kù),其容量無限大，但要求倉(cāng)庫(kù)中A、B兩種物品的數(shù)量滿足下述不等式：-M（A物品數(shù)量B物品數(shù)量）N其中M和N為正整數(shù)。試用信號(hào)量和PV操作描述A、B兩種物品的入庫(kù)過程。問題分析：若只放入A，而不放入B，則A產(chǎn)品最多可放入N次便被阻塞；若只放入B，而不放入A，則B產(chǎn)品最多可放入M次便被阻塞；每放入一次A，放入產(chǎn)品B的機(jī)會(huì)也多一次；同理，每放入一次B，放入產(chǎn)品A的機(jī)會(huì)也多一次。The P,V code Using Pascal Semaphore mutex=1，sa=N，sb=M; cobegin procedure A: procedure B: while(TURE) while(TURE) begin begin p(sa); p(sb); p(mutex); p(mutex); A產(chǎn)品入庫(kù)； B產(chǎn)品入庫(kù)； V(mutex); V(mutex); V(sb); V(sa); end end coend2.擴(kuò)展二設(shè)有一個(gè)可以裝A、B兩種物品的倉(cāng)庫(kù)，其容量有限（分別為N），但要求倉(cāng)庫(kù)中A、B兩種物品的數(shù)量滿足下述不等式:-MA物品數(shù)量B物品數(shù)量N其中M和N為正整數(shù)。另外，還有一個(gè)進(jìn)程消費(fèi)A,B，一次取一個(gè)A，B組裝成C。試用信號(hào)量和PV操作描述A、B兩種物品的入庫(kù)過程。問題分析：已知條件-MA物品數(shù)量B物品數(shù)量N可以拆成兩個(gè)不等式，即A物品數(shù)量B物品數(shù)量NB物品數(shù)量A物品數(shù)量M這兩個(gè)不等式的含義是：倉(cāng)庫(kù)中A物品可以比B物品多，但不能超過N個(gè)；物品可以比A物品多，但不能超過M個(gè)。The P,V code Using Pascalsemaphore mutex=1,a,b=m,empty1,empty2=N,full1,full2=0;cobegin process(A); process(B); process(C)coend A物品入庫(kù)：process A begin while(TRUE) begin p(empty1); P(a); p(mutex);2.擴(kuò)展二設(shè)有一個(gè)可以裝A、B兩種物品的倉(cāng)庫(kù)，其容量有限（分別為N），但要求倉(cāng)庫(kù)中A、B兩種物品的數(shù)量滿足下述不等式:-MA物品數(shù)量B物品數(shù)量N其中M和N為正整數(shù)。另外，還有一個(gè)進(jìn)程消費(fèi)A,B，一次取一個(gè)A，B組裝成C。試用信號(hào)量和PV操作描述A、B兩種物品的入庫(kù)過程。問題分析：已知條件-MA物品數(shù)量B物品數(shù)量N可以拆成兩個(gè)不等式，即A物品數(shù)量B物品數(shù)量NB物品數(shù)量A物品數(shù)量M這兩個(gè)不等式的含義是：倉(cāng)庫(kù)中A物品可以比B物品多，但不能超過N個(gè)；物品可以比A物品多，但不能超過M個(gè)。The P,V code Using Pascalsemaphore mutex=1,a,b=m,empty1,empty2=N,full1,full2=0;cobegin process(A); process(B); process(C)coend A物品入庫(kù)：process A begin while(TRUE) begin p(empty1); P(a); p(mutex);3.擴(kuò)展三設(shè)P,Q,R共享一個(gè)緩沖區(qū)，P，Q構(gòu)成一對(duì)生產(chǎn)者-消費(fèi)者，R既為生產(chǎn)者又為消費(fèi)者。使用P,V實(shí)現(xiàn)其同步。問題分析：略。The P,V code Using Pascalvar mutex,full,empty:semaphore;full:=1;empty:=0;mutex:=1;cobegin Procedure P Procedure Q Procedure R begin begin begin while true while true if empty:=1 then p(empty); p(full); begin P(mutex); P(mutex); p(empty); Product one； consume one； P(mutex); v(mutex); v(mutex); product； v(full); v(empty); v(mutex); end end v(full); endif full:=1 then beginp(full); p(mutex);消費(fèi)一個(gè)產(chǎn)品； v(mutex); v(empty); endcoend2.讀者一寫者問題(Readers-Writers Problem)問題描述：有一個(gè)許多進(jìn)程共享的數(shù)據(jù)區(qū)，這個(gè)數(shù)據(jù)區(qū)的一塊空間；有一些只讀取這個(gè)數(shù)據(jù)區(qū)的進(jìn)程（Reader）和一程(Writer)，此外還需要滿足以下條件：（1）任意多個(gè)讀進(jìn)程可以同時(shí)讀這個(gè)文件；（2）一次只有一個(gè)寫進(jìn)程可以往文件中寫；（3）如果一個(gè)寫進(jìn)程正在進(jìn)行操作，禁止任何讀進(jìn)程度文件。實(shí)驗(yàn)要求用信號(hào)量來實(shí)現(xiàn)讀者寫者問題的調(diào)度算法。實(shí)驗(yàn)類通過P()、V()兩個(gè)方法實(shí)現(xiàn)了P、V原語(yǔ)的功能。實(shí)驗(yàn)的任務(wù)法以及Writer類的Write方法。我們需要分兩種情況實(shí)現(xiàn)該問題：讀優(yōu)先：要求指一個(gè)讀者試圖進(jìn)行讀操作時(shí)，如果這時(shí)正有其直接開始讀操作，而不需要等待。寫優(yōu)先：一個(gè)讀者試圖進(jìn)行讀操作時(shí)，如果有其他寫者在等寫操作，他要等待該寫者完成寫操作后才開始讀操作。The P,V code Using Pascal讀者優(yōu)先算法：rwmutex 用于寫者與其他讀者/寫者互斥的訪問共享數(shù)據(jù)rmutex 用于讀者互斥的訪問readcount 讀者計(jì)數(shù)器var rwmutex,rmutex：semaphore:=1,1；int readcount=0;cobeginprocedure reader_ibegin /i=1,2,.P(rmutex);Readcount+;if(readcount=1) P(rwmutex);V(rmutex);讀數(shù)據(jù)；P(rmutex);Readcount-;if(readcount=0) V(rwmutex);V(rmutex);endprocedure Writer_jbegin /j=1,2,.P(rwmutex);寫更新；V(rwmutex);endCoend寫者優(yōu)先：1）多個(gè)讀者可以同時(shí)進(jìn)行讀2）寫者必須互斥（只允許一個(gè)寫者寫，也不能讀者寫者同時(shí)進(jìn)3）寫者優(yōu)先于讀者（一旦有寫者，則后續(xù)讀者必須等待，喚醒如果讀者數(shù)是固定的，我們可采用下面的算法：rwmutex： 用于寫者與其他讀者/寫者互斥的訪問共享數(shù)據(jù)rmutex： 該信號(hào)量初始值設(shè)為10，表示最多允許10個(gè)讀者var rwmutex,rmutex：semaphore:=1,10；cobeginprocedure reader_ibegin /i=1,2,.P(rwmutex); /讀者、寫者互斥P(rmutex);V(rwmutex); /釋放讀寫互斥信號(hào)量，允許其它讀、寫進(jìn)程訪問資源讀數(shù)據(jù)；V(rmutex);endprocedure Writer_jbegin /j=1,2,.P(rwmutex);for(i=1;i=10;i+) P(rmutex); /禁止新讀者，并等待已進(jìn)入的讀者退出寫更新；for(i=1;i=10;i+)V(rmutex);/恢復(fù)允許rmutex值為10V(rwmutex);endCoend問題擴(kuò)展如果讀者寫者均是平等的即二者都不優(yōu)先，如何實(shí)現(xiàn)？3.哲學(xué)家進(jìn)餐問題問題描述：(由Dijkstra首先提出并解決)5個(gè)哲學(xué)家圍繞一張圓桌而坐，桌子上放著5支筷子，每?jī)蓚€(gè)哲學(xué)家之間放一支；哲學(xué)家的動(dòng)作包括思考和進(jìn)餐，進(jìn)餐時(shí)需要同時(shí)拿起他左邊和右邊的兩支筷子，思考時(shí)則同時(shí)將兩支筷子放回原處。如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行？如：不出現(xiàn)相鄰者同時(shí)要求進(jìn)餐；不出現(xiàn)有人永遠(yuǎn)拿不到筷子；The P,V code Using Pascal解法一：semaphore Forki:=1(i=0,1,2,3,4)begin Thiking; Being hangery; P(Forki mod 5); p(Fork(i+1)mod 5); Eating; v(Forki mod 5); v(Fork(i+1)mod 5);end解法二：semaphore c0?c4,初值均為1；Integer i=0,1,.,4;procedure philosopher_ibegin if i mod 2=0 then begin p(ci); p(ci+1mod 5); Eating; v(ci); v(ci+1mod 5); end else begin p(ci+1mod 5); p(ci); Eating; v(ci+1mod 5); v(ci); endend4.理發(fā)師問題問題描述：理發(fā)店理有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子如果沒有顧客，理發(fā)師便在理發(fā)椅上睡覺一個(gè)顧客到來時(shí)，它必須叫醒理發(fā)師如果理發(fā)師正在理發(fā)時(shí)又有顧客來到，則如果有空椅子可坐，就坐下來等待，否則就離開。The P,V code Using Pascal1)控制變量waiting用來記錄等候理發(fā)的顧客數(shù)，初值均為0；2)信號(hào)量customers用來記錄等候理發(fā)的顧客數(shù)，并用作阻塞理發(fā)師進(jìn)程，初值為0；3)信號(hào)量barbers用來記錄正在等候顧客的理發(fā)師數(shù)，并用作阻塞顧客進(jìn)程，初值為0；4)信號(hào)量mutex用于互斥，初值為1int waiting=0；/等候理發(fā)的顧客數(shù)int chairs=n；/為顧客準(zhǔn)備的椅子數(shù)semaphore customers=0,barbers=0,mutex=1;cobegin barber() begin while(TRUE);/理完一人,還有顧客嗎? P(cutomers);/若無顧客,理發(fā)師睡眠 P(mutex);/進(jìn)程互斥 waiting:=waiting1;/等候顧客數(shù)少一個(gè) V(barbers);/理發(fā)師去為一個(gè)顧客理發(fā) V(mutex);/開放臨界區(qū) cut-hair();/正在理發(fā) end customer() begin P(mutex);/進(jìn)程互斥 if(waiting) begin waiting:=waiting+1;/等候顧客數(shù)加1 V(customers);/必要的話喚醒理發(fā)師 V(mutex);/開放臨界區(qū) P(barbers);/無理發(fā)師,顧客坐著養(yǎng)神 get-haircut();/一個(gè)顧客坐下等理/ end else V(mutex);/人滿了,走吧! endcoend5.吸煙者問題問題描述：三個(gè)吸煙者在一間房間內(nèi)，還有一個(gè)香煙供應(yīng)者。為了制造并抽掉香煙，每個(gè)吸煙者需要三樣?xùn)|西：煙草、紙和火柴。供應(yīng)者有豐富的貨物提供。三個(gè)吸煙者中，第一個(gè)有自己的煙草，第二個(gè)有自己的紙，第三個(gè)有自己的火柴。供應(yīng)者將兩樣?xùn)|西放在桌子上，允許一個(gè)吸煙者進(jìn)行對(duì)健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再放兩樣?xùn)|西（隨機(jī)地）在桌面上，然后喚醒另一個(gè)吸煙者。試為吸煙者和供應(yīng)者編寫程序解決問題。問題分析：k供應(yīng)者seller隨即產(chǎn)生兩樣?xùn)|西，提供它們，這里用普通變量來表示k吸煙者進(jìn)程smoker根據(jù)其排號(hào)不同，擁有不同的一件東西。假設(shè)1號(hào)吸煙者擁有煙草tobacco，2號(hào)吸煙者擁有紙paper，3號(hào)吸煙者擁有火柴match。其他號(hào)碼錯(cuò)誤返回。k吸煙者的序號(hào)代表他們擁有的東西，用他們的序號(hào)和供應(yīng)者產(chǎn)生的兩樣?xùn)|西比較，如果都不相等，則說明他擁有的東西和供應(yīng)者產(chǎn)生的東西匹配，它可以吸煙。如果其中一個(gè)相等，則推出，繼續(xù)排隊(duì)。k mutex信號(hào)量代表一個(gè)只能進(jìn)入的門，每次只有一個(gè)吸煙者可以進(jìn)入進(jìn)行比較和吸煙。k每個(gè)吸煙者在吸煙完畢之后出門之前要叫醒供應(yīng)者，調(diào)用seller進(jìn)程。The P,V code Using Pascalvar s, S1, S2, S3; semaphore;S:=1; S1:=S2:=S3:=0;fiag1,flag2,fiag3:Boolean;fiag1:=flag2:=flag3:=true;cobegin process 供應(yīng)者 begin repeat P(S); 取兩樣香煙原料放桌上，由flagi標(biāo)記； /nago1、nage2、nage3 代表煙草、紙、火柴5.吸煙者問題1問題描述：三個(gè)吸煙者在一間房間內(nèi)，還有一個(gè)香煙供應(yīng)者。為了制造并抽掉香煙，每個(gè)吸煙者需要三樣?xùn)|西：煙草、紙和火柴。供應(yīng)者有豐富的貨物提供。三個(gè)吸煙者中，第一個(gè)有自己的煙草，第二個(gè)有自己的紙，第三個(gè)有自己的火柴。供應(yīng)者將兩樣?xùn)|西放在桌子上，允許一個(gè)吸煙者進(jìn)行對(duì)健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再放兩樣?xùn)|西（隨機(jī)地）在桌面上，然后喚醒另一個(gè)吸煙者。試為吸煙者和供應(yīng)者編寫程序解決問題。問題分析：k供應(yīng)者seller隨即產(chǎn)生兩樣?xùn)|西，提供它們，這里用普通變量來表示k吸煙者進(jìn)程smoker根據(jù)其排號(hào)不同，擁有不同的一件東西。假設(shè)1號(hào)吸煙者擁有煙草tobacco，2號(hào)吸煙者擁有紙paper，3號(hào)吸煙者擁有火柴match。其他號(hào)碼錯(cuò)誤返回。k吸煙者的序號(hào)代表他們擁有的東西，用他們的序號(hào)和供應(yīng)者產(chǎn)生的兩樣?xùn)|西比較，如果都不相等，則說明他擁有的東西和供應(yīng)者產(chǎn)生的東西匹配，它可以吸煙。如果其中一個(gè)相等，則推出，繼續(xù)排隊(duì)。k mutex信號(hào)量代