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

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

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

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

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

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

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

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

對一般有N個進程的情況,tally值的最終范圍是[2,N*50],因為對其他所有進程來說,從最初開始運行到在第五步完成.但最后都被進程B破壞掉它們的最終結果.P182習題5.13考慮圖5.10中定義的無限緩沖區(qū)生產(chǎn)者/消費者問題的解決方案，設生產(chǎn)者與消費者都以大致相同的速度運行，運行情況如下：生產(chǎn)者：append;semSignal;produce;...;append;semSignal;produce;...;消費者：consume;...;take;semWait;consume;...;take;semWait;...;生產(chǎn)者通常管理給緩沖區(qū)添加一個新元素，并在消費者消費了前面的元素后發(fā)出信號。生產(chǎn)者通常添加到一個空緩沖區(qū)中，而消費者通常取走緩沖區(qū)中的惟一元素。消費者從不在信號量上阻塞，但必須進行大量的信號量調用，產(chǎn)生相當多的開銷。構造新程序，使之更有效。提示：允許n的值為-1，這表示不僅緩沖區(qū)為空，而且消費者也檢測到這個事實并將被阻塞，直到生產(chǎn)者產(chǎn)生新的數(shù)據(jù)。這個方案不要圖5.10中的局部變量m。P182習題5.13P182習題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習題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習題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習題5.14P182習題5.14

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

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