廈門大學(xué)操作系統(tǒng)5-6章習(xí)題講解

5-6章作業(yè)P177復(fù)習(xí)題5.8在信號量上可執(zhí)行的操作：初始化>=0（一般情況）semWait原語，值減1如果值變?yōu)樨?fù)數(shù)，則執(zhí)行semWait的進(jìn)程被阻塞semSignal原語，值加1如果值小于或等于0，則喚醒一個該信號量的阻塞進(jìn)程P177復(fù)習(xí)題5.11什么是管程？管程（Monitor）是一個程序設(shè)計語言結(jié)構(gòu)，它提供與信號量同樣的功能，但更易于操作管程是一個軟件模塊一個或多個過程一個初始化序列局部數(shù)據(jù)P177復(fù)習(xí)題5.13與讀者-寫者問題相關(guān)聯(lián)的條件：任意多的讀進(jìn)程可以同時讀一個文件一次只有一個寫進(jìn)程可以往文件中寫如果一個寫進(jìn)程正在往文件中寫時，則禁止任何讀進(jìn)程讀文件P179習(xí)題5.2一個并發(fā)程序，它的兩個進(jìn)程p與q，A、B、C、D、E是任意的原子語句。設(shè)主程序執(zhí)行兩個進(jìn)程的parbegin。

voidp(){A;B;C;}voidq(){D;E;}給出這兩個進(jìn)程所有可能的交替執(zhí)行（根據(jù)原子語句給出執(zhí)行軌跡）

ABCDE;ABDCE;ABDEC;ADBCE;ADBEC;ADEBC;DEABC;DAEBC;DABEC;DABCEP179習(xí)題5.3考慮右邊的程序：

a、確定由這個并發(fā)程序輸出的共享變量最后值的上限與下線。設(shè)進(jìn)程可以以任意相對速度執(zhí)行，并當(dāng)一個值由獨(dú)立的機(jī)器指令載入一個寄存器中后，它只能增1.b、在a的假設(shè)下，允許任意多的進(jìn)程并發(fā)執(zhí)行，tally值的范圍？constintn=50;inttally;voidtotal(){ intcount; for(count=1;count<=n;count++){ tally++; }}voidmain(){ tally=0; parbegin(total(),total()); write(tally);}P179習(xí)題5.3a.乍一看,tally的范圍好像是落在[50,100]

這個區(qū)間里,因?yàn)楫?dāng)沒有互斥時可以從0直接增加到50.這一基本論點(diǎn)是當(dāng)并發(fā)的運(yùn)行這兩進(jìn)程時,我們不可能得到一個比連續(xù)執(zhí)行單一某進(jìn)程所得tally值還低的一個最終tally值.但是考慮下面由這兩進(jìn)程按交替順序執(zhí)行載入,增加,存儲的情況下同時變更這個共享變量的取值:1.進(jìn)程A載入tally值,并將tally的值加到1,在此時失去處理器(它已經(jīng)增加寄存器的值到1,但是還沒有存儲這個值).2.進(jìn)程B載入tally值(仍然是0),然后運(yùn)行完成49次增加操作,在它已經(jīng)將49這個值存儲給共享變量tally后,失去處理器控制權(quán).3.進(jìn)程A重新獲得處理器控制權(quán)去完成它的第一次存儲操作(用1去代替先前的49這個tally值),此時被迫立即放棄處理器.4.進(jìn)程B重新開始,將1(當(dāng)前的tally值)載入到它自己的寄存器中,但此時被迫放棄處理器(注意這是B的最后一次載入).5.進(jìn)程A被重新安排開始,但這次沒有被中斷,直到運(yùn)行完成它剩余的49次載入,增加和存儲操作,結(jié)果是此時tally值已經(jīng)是50.6.進(jìn)程B在它終止前完成僅有的最后一次增加和存儲操作.它的寄存器值增至2,同時存儲這個值做為這個共享變量的最終結(jié)果.

一些人認(rèn)為會出現(xiàn)低于2這個值的結(jié)果,這種情況是不會出現(xiàn).所以

tally值的正確范圍是[2,100].P182習(xí)題5.3P182習(xí)題5.3b、在a的假設(shè)下，允許任意多的進(jìn)程并發(fā)執(zhí)行，tally值的范圍？

對一般有N個進(jìn)程的情況,tally值的最終范圍是[2,N*50],因?yàn)閷ζ渌羞M(jìn)程來說,從最初開始運(yùn)行到在第五步完成.但最后都被進(jìn)程B破壞掉它們的最終結(jié)果.P182習(xí)題5.13考慮圖5.10中定義的無限緩沖區(qū)生產(chǎn)者/消費(fèi)者問題的解決方案，設(shè)生產(chǎn)者與消費(fèi)者都以大致相同的速度運(yùn)行，運(yùn)行情況如下：生產(chǎn)者：append;semSignal;produce;...;append;semSignal;produce;...;消費(fèi)者：consume;...;take;semWait;consume;...;take;semWait;...;生產(chǎn)者通常管理給緩沖區(qū)添加一個新元素，并在消費(fèi)者消費(fèi)了前面的元素后發(fā)出信號。生產(chǎn)者通常添加到一個空緩沖區(qū)中，而消費(fèi)者通常取走緩沖區(qū)中的惟一元素。消費(fèi)者從不在信號量上阻塞，但必須進(jìn)行大量的信號量調(diào)用，產(chǎn)生相當(dāng)多的開銷。構(gòu)造新程序，使之更有效。提示：允許n的值為-1，這表示不僅緩沖區(qū)為空，而且消費(fèi)者也檢測到這個事實(shí)并將被阻塞，直到生產(chǎn)者產(chǎn)生新的數(shù)據(jù)。這個方案不要圖5.10中的局部變量m。P182習(xí)題5.13P182習(xí)題5.13program producerconsumer; var n:integer; s:(*binary*)semaphore(:=1); delay:(*binary*)semaphore(:=0); procedureproducer; begin repeat produce; semWaitB(s); append; n:=n+1; ifn=0thensemSignalB(delay); semSignalB(s) forever end;P182習(xí)題5.13procedureconsumer; begin repeat semWaitB(s); take; n:=n-1; ifn=-1then begin semSignalB(s); semWaitB(delay); semWaitB(s) end; consume; semSignalB(s) forever end; begin(*mainprogram*) n:=0; parbegin producer;consumer parendP182習(xí)題5.14考慮圖5.13，若發(fā)生下面的交換，程序的意義是否會改變？a.semWait(e);semWait(s)b.semSignal(s);semSignal(n)c.semWait(n);semWait(s)d.semSignal(s);semSignal(e)P182習(xí)題5.14P182習(xí)題5.14

信號量s控制對臨界區(qū)的訪問，在臨界區(qū)只包含append或take操作。AC會導(dǎo)致死鎖。BD不變，但效率變低（臨界區(qū)變長）。p211復(fù)習(xí)題6.2可能發(fā)生死鎖所必需的三個條件：互斥一次只有一個進(jìn)程可以使用一個資源占有且等待一個進(jìn)程在等待其它資源分配時，繼續(xù)占有已分配的資源非搶占不能強(qiáng)行搶占已分配給其它進(jìn)程的資源除非進(jìn)程主動釋放p211復(fù)習(xí)題6.3產(chǎn)生死鎖的第四個條件：循環(huán)等待資源分配圖中存在一條封閉的進(jìn)程鏈p212習(xí)題6.3證明圖6.3所反映的情況不會發(fā)生死鎖（圖見P186）

資源可重用的，P、Q同時申請B，Q獲得B，P、Q同時申請A，P獲得A，Q釋放B，P得到A，P釋放A，Q得到A，不構(gòu)成死鎖的第四個條件。p212習(xí)題6.5把6.4節(jié)中的死鎖檢測算法應(yīng)用于下面的數(shù)據(jù)，給出結(jié)果。Available=(2100)RequestAllocation200100101010200121000120p212習(xí)題6.51. W=(2100)2. MarkP3; W=(2100)+(0120)=(2220)3. MarkP2; W=(2220)+(2001)=(4221)4. MarkP1;nodeadlockdetected算法步驟見P195p212習(xí)題6.6一個假脫機(jī)系統(tǒng)（如圖示）含一個輸入進(jìn)程I、用戶進(jìn)程P和一個輸出進(jìn)程0，他們之間用兩個緩沖區(qū)連接。進(jìn)程以相等大小塊為單位交換數(shù)據(jù)，這些塊利用輸入緩沖區(qū)和輸出緩沖區(qū)之間的移動邊界緩存在磁盤上，并取決于進(jìn)程的速度，