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

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

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

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

a、確定由這個(gè)并發(fā)程序輸出的共享變量最后值的上限與下線。設(shè)進(jìn)程可以以任意相對(duì)速度執(zhí)行，并當(dāng)一個(gè)值由獨(dú)立的機(jī)器指令載入一個(gè)寄存器中后，它只能增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]

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

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

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

對(duì)一般有N個(gè)進(jìn)程的情況,tally值的最終范圍是[2,N*50],因?yàn)閷?duì)其他所有進(jìn)程來(lái)說(shuō),從最初開始運(yùn)行到在第五步完成.但最后都被進(jìn)程B破壞掉它們的最終結(jié)果.P182習(xí)題5.13考慮圖5.10中定義的無(wú)限緩沖區(qū)生產(chǎn)者/消費(fèi)者問(wèn)題的解決方案，設(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ū)添加一個(gè)新元素，并在消費(fèi)者消費(fèi)了前面的元素后發(fā)出信號(hào)。生產(chǎn)者通常添加到一個(gè)空緩沖區(qū)中，而消費(fèi)者通常取走緩沖區(qū)中的惟一元素。消費(fèi)者從不在信號(hào)量上阻塞，但必須進(jìn)行大量的信號(hào)量調(diào)用，產(chǎn)生相當(dāng)多的開銷。構(gòu)造新程序，使之更有效。提示：允許n的值為-1，這表示不僅緩沖區(qū)為空，而且消費(fèi)者也檢測(cè)到這個(gè)事實(shí)并將被阻塞，直到生產(chǎn)者產(chǎn)生新的數(shù)據(jù)。這個(gè)方案不要圖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ā)生下面的交換，程序的意義是否會(huì)改變？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

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

資源可重用的，P、Q同時(shí)申請(qǐng)B，Q獲得B，P、Q同時(shí)申請(qǐng)A，P獲得A，Q釋放B，P得到A，P釋放A，Q得到A，不構(gòu)成死鎖的第四個(gè)條件。p212習(xí)題6.5把6.4節(jié)中的死鎖檢測(cè)算法應(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一個(gè)假脫機(jī)系統(tǒng)（如圖示）含一個(gè)輸入進(jìn)程I、用戶進(jìn)程P和一個(gè)輸出進(jìn)程0，他們之間用兩個(gè)緩沖區(qū)連接。進(jìn)程以相等大小塊為單位交換數(shù)據(jù)，這些塊利用輸入緩沖區(qū)和輸出緩沖區(qū)之間的移動(dòng)邊界緩存在磁盤上，并取決于進(jìn)程的速度，