【文章內(nèi)容簡(jiǎn)介】 別演示用 FCFS、SJF、非搶占優(yōu)先級(jí)（數(shù)字小代表優(yōu)先級(jí)高）和RR（時(shí)間片＝1）算法調(diào)度時(shí)進(jìn)程的執(zhí)行過(guò)程。 a 里每個(gè)進(jìn)程在每種調(diào)度算法下的周轉(zhuǎn)時(shí)間是多少？ a 里每個(gè)進(jìn)程在每種調(diào)度算法下的等待時(shí)間是多少？ a 里哪一種調(diào)度算法的平均等待時(shí)間對(duì)所有進(jìn)程而言最小？答： FCFSRRSJF非搶占優(yōu)先級(jí)P110191916P211211P3137418P4144219P5191496FCFSRRSJF非搶占優(yōu)先級(jí)P10996P210100P3115216P4133118P514942 答：最短工作優(yōu)先調(diào)度和優(yōu)先級(jí)調(diào)度算法會(huì)引起饑餓 RR 調(diào)度算法的一個(gè)變種，在這個(gè)算法里，就緒隊(duì)列里的項(xiàng)是指向 PCB 的指針。，會(huì)有什么效果？？ RR 調(diào)度算法，從而不用兩個(gè)指針達(dá)到同樣的效果？，這個(gè)過(guò)程將會(huì)增加它的優(yōu)先權(quán)，因?yàn)橥ㄟ^(guò)經(jīng)常得到時(shí)間它能夠優(yōu)先得以運(yùn)行。也就是說(shuō)，優(yōu)先級(jí)越高越先運(yùn)行。然而，結(jié)果將由短任務(wù)來(lái)承擔(dān)。換句話說(shuō)，可能有兩個(gè)或多個(gè)時(shí)間片在RR 調(diào)度中。假設(shè)，I/O限制任務(wù)一次分配給一個(gè)I/O操作1毫秒的CPU計(jì)算，但每個(gè)I/O操作的完成需要 10毫秒。同時(shí)，所有的進(jìn)程都是長(zhǎng)進(jìn)程。對(duì)一個(gè)RR調(diào)度來(lái)說(shuō)，以下情況時(shí)CPU 的利用率是多少：：：不論是哪個(gè)進(jìn)程被調(diào)度。CPU的利用率是1/*100=92%。：這I/O限制任務(wù)會(huì)在使用完1毫秒時(shí)間片后進(jìn)行一次上下文切換。這個(gè)時(shí)間片要求在所有的進(jìn)程間都走一遍，因此，10*+(因?yàn)槊總€(gè)I / O限定任務(wù)執(zhí)行為1毫秒，然后承擔(dān)上下文切換的任務(wù)，而CPU限制任務(wù)的執(zhí)行10毫秒在承擔(dān)一個(gè)上下文切換之前) 。因此，CPU的利用率是*100=94%。什么策略能夠使一個(gè)計(jì)算機(jī)用戶使用由用戶進(jìn)程分配的最大的CPU時(shí)間片。答：這個(gè)程序可以使分配給它的沒有被完全利用的CPU時(shí)間最大化。它可以使用分配給它的時(shí)間片中的絕大部分，但在時(shí)間片結(jié)束前放棄CPU，因此提高了與進(jìn)程有關(guān)的優(yōu)先級(jí)。1. 。大的優(yōu)先權(quán)數(shù)代表高優(yōu)先權(quán)。當(dāng)一個(gè)進(jìn)程在等待 CPU 時(shí)（在就緒隊(duì)列中，但未執(zhí)行），優(yōu)先權(quán)以α速率改變；當(dāng)它運(yùn)行時(shí)，優(yōu)先權(quán)以速率β改變。所有的進(jìn)程在進(jìn)入就緒隊(duì)列時(shí)被給定優(yōu)先權(quán)為 0。參數(shù)α 和β可以設(shè)定給許多不同的調(diào)度算法。α0時(shí)所得的是什么算法？ β0時(shí)所得的是什么算法？答： ：c．多級(jí)反饋隊(duì)列答:。b. RR對(duì)所有的任務(wù)都是能夠相同的（給它們相同的CPU時(shí)間區(qū)間），所以，短任務(wù)可以很快的離開系統(tǒng)，只要它們可以先完成。c. 多級(jí)反饋隊(duì)列和RR調(diào)度算法相似——它們不會(huì)先選擇短任務(wù)。 XP的調(diào)度算法，下列什么是數(shù)字優(yōu)先的線程。答：5．12考慮在Solaris操作系統(tǒng)中的為分時(shí)線程的調(diào)度算法：a:一個(gè)優(yōu)先權(quán)是10的線程的時(shí)間片是多少？?jī)?yōu)先權(quán)是55的呢？b:假設(shè)優(yōu)先權(quán)是35的一個(gè)線程用它所有的時(shí)間片在沒有任何阻止的情況下，這調(diào)度算法將會(huì)分配給這個(gè)線程什么樣新的優(yōu)先權(quán)？c:假設(shè)一個(gè)優(yōu)先權(quán)是35的線程在時(shí)間片結(jié)束前阻止I/O操作。這調(diào)度算法將會(huì)分配給這個(gè)線程什么樣新的優(yōu)先權(quán)？答：a:160和40b:35C：54：數(shù)字越高，優(yōu)先權(quán)越低。該調(diào)度進(jìn)程利用下面的方程重新計(jì)算進(jìn)程的優(yōu)先權(quán)一次一秒:優(yōu)先權(quán)= （最近CPU使用率/ 2 ） +基本數(shù)這里的基本數(shù)= 60,最近的 CPU使用率是指一個(gè)表明優(yōu)先權(quán)從上一次重新計(jì)算后開始進(jìn)程被CPU使用的情況。假設(shè)最近進(jìn)程p1的CPU使用率是40個(gè)，p2是18 ，p3是10。當(dāng)優(yōu)先權(quán)重新計(jì)算后這三個(gè)進(jìn)程的新的優(yōu)先權(quán)是什么？在此信息的基礎(chǔ)上，傳統(tǒng)UNIX的調(diào)度會(huì)不會(huì)提高或降低CPU限制的進(jìn)程的相對(duì)優(yōu)先權(quán)？答 ： 分配給這些進(jìn)程的優(yōu)先權(quán)分別是80。第六章 管程。兩個(gè)進(jìn)程P0和P1共享以下變量： boolean flag[2]。 /*initially false*/int turn。進(jìn)程Pi(i==0或1)和另一個(gè)進(jìn)程Pj(j==0或1)。證明這個(gè)算法滿足臨界區(qū)問(wèn)題的所有三個(gè)要求。do{flag[i]=ture。 while(flag[j]){ if(turn==j){ flag[i]=false。 while(turn==j)。 flag[i]=true。}}臨界區(qū)turn=j。flag[i]=false。剩余區(qū)}while(1)。 圖 Dekker 算法中的進(jìn)程 Pi 結(jié)構(gòu)答：該算法滿足三個(gè)相互排斥條件。（1）相互排斥是為了確保使用的變量和標(biāo)志是可變的。如果所有進(jìn)程都把他們的變量設(shè)置為真，只有一個(gè)會(huì)成功，那就是哪個(gè)進(jìn)程輪到的問(wèn)題了。等待中的進(jìn)程只能夠進(jìn)入它的重要部分當(dāng)其他進(jìn)程在更新變量值時(shí)。 這兩個(gè)進(jìn)程的臨界區(qū)域問(wèn)題的最初的正確的軟件解決方案是由 Dekker 提出的。P0、P1 兩個(gè)進(jìn)程，具有以下共同的變量： boolean flag[2]。 /* initially false */ int turn。進(jìn)程 Pi(i==0 or1)的結(jié)構(gòu)在 中已經(jīng)出現(xiàn)過(guò)；其他進(jìn)程為 Pj(j == 1 or 0)。證明這個(gè)算法滿足關(guān)鍵問(wèn)題的三個(gè)要求。答：這個(gè)算法滿足臨界區(qū)域的三個(gè)條件：（1） 在標(biāo)記和返回變量的使用中，互斥條件是保證的。如果兩個(gè)進(jìn)程將它們的標(biāo)識(shí)設(shè)為真，那么只有一個(gè)進(jìn)程會(huì)成功進(jìn)行，即輪到的那個(gè)進(jìn)程。當(dāng)另一個(gè)進(jìn)程更新它的返回變量時(shí)，等待的那個(gè)進(jìn)程只能進(jìn)入它的臨界區(qū)域。（2） 就緒的進(jìn)程，通過(guò)標(biāo)志，返回變量。這個(gè)算法沒有提供嚴(yán)格的交替。如果一個(gè)進(jìn)程想要進(jìn)入它們的臨界區(qū)域，它可以將它的標(biāo)識(shí)設(shè)為真，然后進(jìn)入它們的臨界區(qū)域。當(dāng)退出它的臨界區(qū)域，它可以設(shè)置轉(zhuǎn)向其他進(jìn)程的值。如果這個(gè)進(jìn)程想要在其他進(jìn)程之前再次進(jìn)入它的臨界區(qū)域，它會(huì)重復(fù)這樣的進(jìn)程：進(jìn)入它的臨界區(qū)域，在退出時(shí)轉(zhuǎn)向另一個(gè)進(jìn)程。（3） 在雙 T 返回變量的使用過(guò)程中，界等待受阻。假設(shè)兩個(gè)進(jìn)程想要進(jìn)入它們的責(zé)任所在的臨界區(qū)域。它們都將它們的標(biāo)志的值設(shè)為真；而只有輪到的那個(gè)線程可以執(zhí)行；其他的線程處于等待狀態(tài)。如果界等待沒有受阻，當(dāng)?shù)谝粋€(gè)進(jìn)程重復(fù)“進(jìn)入退出”它的臨界區(qū)域這一過(guò)程。Dekker 算法在一個(gè)進(jìn)程中設(shè)置一個(gè)轉(zhuǎn)向另一個(gè)進(jìn)程的值，從而保證另一個(gè)進(jìn)程接下來(lái)進(jìn)入它的臨界區(qū)域。 針對(duì)有 n 個(gè)進(jìn)程在帶有較低時(shí)間限制的等待 n1 個(gè)的輪次這樣一個(gè)臨界區(qū)域最早的解決該問(wèn)題的正確方法是由艾森伯格和麥圭爾提出的。這些進(jìn)程有以下的共同的變量：枚舉 pstate{idle, want in, in cs}。 pstate flag[n]。int turn。所有的枚舉標(biāo)志被初始為空，輪次的最初值是無(wú)關(guān)緊要的（在 0 和 n1 之間）。進(jìn)程 p 的結(jié)構(gòu)在 中有說(shuō)明。證明這個(gè)算法滿足臨界區(qū)域問(wèn)題的三項(xiàng)要求。答：：注意到一個(gè)進(jìn)程只有在下列條件滿足時(shí)才能進(jìn)入臨界區(qū)域：沒有其他進(jìn)程在 CS 中有設(shè)置的標(biāo)識(shí)變量。這是由于進(jìn)程在 CS 中設(shè)置自身的標(biāo)識(shí)變量之前要先檢查其他進(jìn)程的狀態(tài)。我們保證沒有兩個(gè)進(jìn)程將同時(shí)進(jìn)入臨界區(qū)域。:考慮以下情況，當(dāng)多進(jìn)程同時(shí)在 CS 中設(shè)置它們的標(biāo)識(shí)變量，然后檢查是否有其他進(jìn)程在 cs 中設(shè)置標(biāo)識(shí)變量。當(dāng)這種情況發(fā)生時(shí)，所有的進(jìn)程意識(shí)到這里存在進(jìn)程競(jìng)爭(zhēng)，在外層 while(1)的循環(huán)下進(jìn)入下一次迭代，重置它們的標(biāo)識(shí)變量到 want 中?，F(xiàn)在只有唯一的進(jìn)程將設(shè)置它的輪次變量到 cs 中，這個(gè)唯一的進(jìn)程就是其序號(hào)是最接近輪次的。從這個(gè)角度來(lái)說(shuō)，對(duì)于哪些序號(hào)次接近輪次的新的進(jìn)程就能決定進(jìn)入臨界區(qū)域，而且能同時(shí)在 CS 中設(shè)置它們的標(biāo)識(shí)。隨后這些進(jìn)程意識(shí)到這里存在競(jìng)爭(zhēng)的進(jìn)程，于是重新啟動(dòng)進(jìn)入臨界區(qū)域的進(jìn)程。在每次迭代中，進(jìn)程在 cs 中設(shè)置的序號(hào)值將變得更加接近輪次，最后我們得出以下結(jié)論：只有進(jìn)程 k 在 cs 中設(shè)置它的標(biāo)識(shí)，而其他哪些序號(hào)在輪次和 k 之間不能在 cs 中設(shè)置它們的標(biāo)識(shí)。這個(gè)進(jìn)程僅能進(jìn)入臨界區(qū)域。：有限等待需要滿足以下事實(shí)：當(dāng)進(jìn)程 k 在打算進(jìn)入臨界區(qū)域時(shí)，它的標(biāo)識(shí)不再置為空閑。任何序號(hào)不在輪次和 k 之間的進(jìn)程不能進(jìn)入臨界區(qū)域。與此同時(shí)，所有序號(hào)落在輪次和 k 之間且又想要進(jìn)入臨界區(qū)域的進(jìn)程能夠進(jìn)入臨界區(qū)域（這是基于系統(tǒng)一直在進(jìn)步的事實(shí)），這個(gè)輪次值變得越來(lái)越接近 k。最后，要么輪次變?yōu)?k，要么沒有哪些序號(hào)在輪次和 k 之間的進(jìn)程，這樣進(jìn)程 k 就進(jìn)入臨界區(qū)域了。 忙等待的含義是什么？在操作系統(tǒng)中還有哪些其他形式的等待？忙等待能完全避免嗎？給出你的答案。答：忙等待意味著一個(gè)進(jìn)程正在等待滿足一個(gè)沒有閑置處理器的嚴(yán)格循環(huán)的條件?；蛘?，一個(gè)進(jìn)程通過(guò)放棄處理器來(lái)等待，在這種情況下的塊等待在將來(lái)某個(gè)適當(dāng)?shù)臅r(shí)間被喚醒。忙等待能夠避免，但是承擔(dān)這種開銷與讓一個(gè)進(jìn)程處于沉睡狀態(tài)，當(dāng)相應(yīng)程序的狀態(tài)達(dá)到的時(shí)候進(jìn)程又被喚醒有關(guān)。 解釋為什么自旋鎖不適合在單處理器系統(tǒng)，而經(jīng)常在多處理器系統(tǒng)下使用？答：自旋鎖不適合在單處理器系統(tǒng)是因?yàn)閺淖孕i中打破一個(gè)進(jìn)程的條件只有在執(zhí)行一個(gè)不同的進(jìn)程時(shí)才能獲得。如果這個(gè)進(jìn)程沒有閑置處理器，其他進(jìn)程不能夠得到這個(gè)機(jī)會(huì)去設(shè)定一個(gè)第一個(gè)進(jìn)程進(jìn)展需要的程序條件。在一個(gè)多處理器系統(tǒng)中，其他進(jìn)程在其他處理器上執(zhí)行，從而為了讓第一個(gè)進(jìn)程從自旋鎖中釋放修改程序狀態(tài)。 如果一個(gè)同步元是在一個(gè)用戶級(jí)程序中使用的，解釋在一個(gè)單處理器系統(tǒng)中為什么通過(guò)停止中斷去實(shí)現(xiàn)這個(gè)同步元是不適合的？答：如果一個(gè)用戶級(jí)程序具有停止中斷的能力，那么它能夠停止計(jì)時(shí)器中斷，防止上下文切換的發(fā)生，從而允許它使用處理器而不讓其他進(jìn)程執(zhí)行。 解釋為什么在一個(gè)多處理器系統(tǒng)中中斷不適合同步元？答：由于只有在防止其他進(jìn)程在一個(gè)中斷不能實(shí)現(xiàn)的處理器上執(zhí)行來(lái)停止中斷，中斷在多處理器系統(tǒng)中是不夠的。在對(duì)于進(jìn)程能在其他處理器上執(zhí)行是沒有心智的，所以進(jìn)程停止中斷不能保證互斥進(jìn)入程序狀態(tài)。 服務(wù)器能夠設(shè)計(jì)成限制打開連接的數(shù)量。比如，一臺(tái)服務(wù)器可以在任何時(shí)候有 n 個(gè)插座連接。這 n 個(gè)連接一形成，服務(wù)器就不能接收再有進(jìn)來(lái)的連接直到一個(gè)現(xiàn)有的連線釋放。解釋為什么信號(hào)量能夠通過(guò)服務(wù)器限制當(dāng)前連線的數(shù)量而被使用。答：信號(hào)量初始化為允許開放式的插座連接的數(shù)量。當(dāng)一個(gè)連接被接受，收購(gòu)方法調(diào)用。當(dāng)連接釋放時(shí)，釋放方法調(diào)用。如果系統(tǒng)道道了允許開放式的插座連接的數(shù)量，相繼調(diào)用收購(gòu)方法將受阻直到一個(gè)現(xiàn)有的連線終止，釋放方法調(diào)用。 證明如果獲得和釋放的信號(hào)量操作沒有動(dòng)態(tài)地執(zhí)行，那么互斥會(huì)受干擾。答：收購(gòu)操作自動(dòng)遞減和信號(hào)量有關(guān)的值。如果兩個(gè)收購(gòu)操作在信號(hào)量的值為 1 的信號(hào)量上執(zhí)行，而且這兩種操作不是自動(dòng)執(zhí)行的，那么這兩個(gè)操作在進(jìn)展中會(huì)遞減信號(hào)量的值，從而干擾互斥。6. 10(程序，不用翻)（） 證明管程和信號(hào)量是相當(dāng)于它們能在執(zhí)行相同類型的同步問(wèn)題時(shí)使用答：在用下列方法使用信號(hào)量時(shí)，管程可以實(shí)施。每個(gè)條件變量是由一個(gè)隊(duì)列中的線程等待條件組成的。每個(gè)線程有一個(gè)和它的隊(duì)列進(jìn)入有關(guān)的信號(hào)量。當(dāng)線程表現(xiàn)出等待操作時(shí)，它創(chuàng)造一個(gè)心得信號(hào)量（初始化為 0），附加信號(hào)量到和條件變量有關(guān)的隊(duì)列中，在新創(chuàng)造的信號(hào)量上執(zhí)行阻塞信號(hào)遞減操作。 討論在讀者作者問(wèn)題中的公平和吞吐量的權(quán)衡問(wèn)題。提出一種解決讀者作者問(wèn)題而不引起饑餓的方法答：在讀者作者問(wèn)題中吞吐量是由利益多的讀者增加的，而不是讓一個(gè)作家獨(dú)占式地獲得共同的價(jià)值觀。另一個(gè)方面，有利于讀者可能會(huì)導(dǎo)致饑餓的作者。在讀者作者問(wèn)題中的借能夠通過(guò)保持和等待進(jìn)程有關(guān)的時(shí)間戳來(lái)避免。當(dāng)作者完成他的任務(wù)，那么喚醒那些已經(jīng)等了最長(zhǎng)期限的進(jìn)程。當(dāng)讀者到達(dá)和注意到另一個(gè)讀者正在訪問(wèn)數(shù)據(jù)庫(kù)，那么它只有在沒有等待的作者時(shí)才能進(jìn)入臨界區(qū)域。這些限制保證公平。管程的signal操作和信號(hào)量的signal操作有什么不同？管程的signal操作在以下情況下是不能繼續(xù)進(jìn)行的：當(dāng)執(zhí)行signal操作并且無(wú)等待線程時(shí)，那么系統(tǒng)會(huì)忽略signal操作，認(rèn)為signal操作沒有發(fā)生過(guò)。如果隨后執(zhí)行wait操作，那么相關(guān)的線程就會(huì)被阻塞。然后在信號(hào)量中，即使沒有等待線程，每個(gè)signal操作都會(huì)是相應(yīng)的信號(hào)量值增加。接下來(lái)的等待操作因?yàn)橹暗男盘?hào)量值的增加而馬上成功進(jìn)行。假設(shè)signal語(yǔ)句只能作為一個(gè)管程中的最后一條語(yǔ)句出現(xiàn)， 節(jié)所描述的實(shí)現(xiàn)？如果signal語(yǔ)句作為最后一條語(yǔ)句出現(xiàn)，那么鎖會(huì)使發(fā)出信號(hào)的進(jìn)程轉(zhuǎn)化成接受信號(hào)的進(jìn)程。否則，發(fā)出信號(hào)的進(jìn)程將解鎖，并且接受信號(hào)的進(jìn)程則需要和其他進(jìn)程共同操作獲得鎖從而使操作繼續(xù)下去。假設(shè)將管程中的wait和signal操作替換成一個(gè)單一的構(gòu)件await（B），這里B 是一個(gè)普通的布爾表達(dá)式，進(jìn)程執(zhí)行直到B變成真a. 用這種方法寫一個(gè)管程實(shí)現(xiàn)讀者—作者問(wèn)題。b. 解釋為什么一般來(lái)說(shuō)這種結(jié)構(gòu)實(shí)現(xiàn)的效率不高。c. 要使這種實(shí)現(xiàn)達(dá)到高效率需要對(duì)await語(yǔ)句加上哪些限制？（提示，限制B 的一般性，參見Kessels[1977].）a. 讀者—作者問(wèn)題可以進(jìn)行以下修改，修改中產(chǎn)生了 await 聲明：讀者可以執(zhí)行“await(active writers == 0 amp。amp。 waiting writers == 0)”來(lái)確保在進(jìn)入臨界區(qū)域時(shí)沒有就緒的作者和等待的作者。作者可以執(zhí)行“await(active writers == 0 amp。amp。 active readers == 0)”來(lái)確?；コ?。b. 在signal操作后，系統(tǒng)檢查滿足等待條件滿足的等待線程，檢查其中被喚醒的等待線程。這個(gè)要求相當(dāng)復(fù)雜，并且可能需要用到交互的編譯器來(lái)評(píng)估在不同時(shí)間點(diǎn)下的條件?？梢酝ㄟ^(guò)限制布爾條件，使布爾變量和其他部分分開作為獨(dú)立的程序變量（僅僅用來(lái)檢查是否相等的一個(gè)靜態(tài)值）。在這種情況下，布爾條件可以傳達(dá)給運(yùn)行時(shí)系統(tǒng)，該系統(tǒng)可以執(zhí)行檢查每一個(gè)它所需要的時(shí)間，以確定哪些線程被喚醒。為什么Solaris、Linux和Windows2000都使用