1、司機和售票員之間的同步關(guān)系司機和售票員之間的同步關(guān)系 司機只有在售票員關(guān)車門后，才能啟動汽車。 售票員只有在司機到站停車后，才能開車門。解： Semaphore close=0，stop=0； driver( ) /*司機*/while(True) P(close);啟動車輛;正常行車;到站停車;V(stop); Conductor( )/*售票員*/while(True)關(guān)車門;V(close);售票;P(stop);開車門;上下乘客;Main( ) parbegin(driver,conductor);()在每個程序中用于實現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對

2、地出現(xiàn)。()對資源信號量empty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的進(jìn)程中，這樣保證生產(chǎn)者進(jìn)程和消費者進(jìn)程的同步及交替執(zhí)行。()在每個進(jìn)程中，多個wait操作順序不能顛倒，而signal操作的次序是無關(guān)緊要的 。例例一臺計算機有10臺磁帶機被n個進(jìn)程競爭，每個進(jìn)程最多需要3臺磁帶機，那么n最多為_時，系統(tǒng)沒有死鎖的危險？解：n最大為4。用整型信號量描述在哲學(xué)家進(jìn)餐問題中，至多允許用整型信號量描述在哲學(xué)家進(jìn)餐問題中，至多允許4個哲學(xué)個哲學(xué)家同時進(jìn)餐的算法。家同時進(jìn)餐的算法。解：解：public class diningphilosophers sem

3、aphore fork 5 = (1,1,1,1,1); semaphore room = 4; int i; void philosopher (int i) /第i個哲學(xué)家進(jìn)餐進(jìn)程 while (true) think(); wait (room); wait (forki); wait (fork (i+1) % 5); eat(); signal (fork (i+1) % 5); signal (forki); signal (room); 例例在銀行家算法中，若出現(xiàn)下述的資源分配情況：ProcessMax AllocationAvailableP00 0 4 40 0 3 21 6

4、 2 2P12 7 5 01 0 0 0P23 6 10 101 3 5 4P30 9 8 40 3 3 2P40 6 6 100 0 1 4試問：1）該狀態(tài)是否安全？ 2）若進(jìn)程P2提出請求Request（1，2，2，2）后，系統(tǒng)能否將資源分配給它？3）如果系統(tǒng)立即滿足P2的上述請求，系統(tǒng)是否立即進(jìn)入死鎖狀態(tài)？解：1）利用安全性算法對上面的狀態(tài)進(jìn)行分析（如下表所示），找到了一個安全序列P0，P3，P4，P1，P2或P0，P3，P1，P4， P2，故系統(tǒng)是安全的。 資源情況資源情況進(jìn)程進(jìn)程WorkNeedAllocationWork+AllocationFinishA B C DA B C D

5、 A B C D A B C DP01 6 2 20 0 1 20 0 3 2 1 6 5 4TrueP31 6 5 40 6 5 20 3 3 2 1 9 8 6TrueP41 9 8 60 6 5 60 0 1 4 1 9 9 10TrueP11 9 9 101 7 5 01 0 0 02 9 9 10TrueP22 9 9 102 3 5 61 3 5 4 3 12 14 14True2) P22) P2發(fā)出請求向量發(fā)出請求向量RequestRequest（1 1，2 2，2 2，2 2）后，系統(tǒng)按照銀行）后，系統(tǒng)按照銀行家算法進(jìn)行檢查：家算法進(jìn)行檢查：Request2Request2（

6、1 1，2 2，2 2，2 2）Need2Need2（2 2，3 3，5 5，6 6）；）；Request2Request2（1 1，2 2，2 2，2 2）AvailableAvailable（1 1，6 6，2 2，2 2）；）；系統(tǒng)先假定可為系統(tǒng)先假定可為P2P2分配資源，并修改分配資源，并修改AvailableAvailable，Allocation2Allocation2和和Need2Need2向量：向量：Availabe=Availabe=（0 0，4 4，0 0，0 0）Allocation2=Allocation2=（2 2，5 5，7 7，6 6）Need2=(1,1,3,4

7、) Need2=(1,1,3,4) 進(jìn)行安全性檢查：此時對所有進(jìn)程，條件進(jìn)行安全性檢查：此時對所有進(jìn)程，條件NeediNeedi Available Available（0 0，4 4，0 0，0 0）都不成立，即）都不成立，即AvailableAvailable不能滿足任何進(jìn)程的不能滿足任何進(jìn)程的請求，故系統(tǒng)進(jìn)入不安全狀態(tài)。因此，當(dāng)進(jìn)程請求，故系統(tǒng)進(jìn)入不安全狀態(tài)。因此，當(dāng)進(jìn)程P2P2提出請求提出請求RequestRequest（1 1，2 2，2 2，2 2）后，系統(tǒng)不能將資源分配給它。）后，系統(tǒng)不能將資源分配給它。3）系統(tǒng)立即滿足進(jìn)程系統(tǒng)立即滿足進(jìn)程P2P2的請求（的請求（1 1，2 2，

8、2 2，2 2）后，并沒有馬上）后，并沒有馬上進(jìn)入死鎖狀態(tài)。因為，此時上述進(jìn)程并沒有申請新的資源，進(jìn)入死鎖狀態(tài)。因為，此時上述進(jìn)程并沒有申請新的資源，并未因得不到資源而進(jìn)入阻塞狀態(tài)。只有當(dāng)上述進(jìn)程提出新并未因得不到資源而進(jìn)入阻塞狀態(tài)。只有當(dāng)上述進(jìn)程提出新的請求，并導(dǎo)致所有沒執(zhí)行完的多個進(jìn)程因得不到資源而阻的請求，并導(dǎo)致所有沒執(zhí)行完的多個進(jìn)程因得不到資源而阻塞時，系統(tǒng)才進(jìn)入死鎖狀態(tài)。塞時，系統(tǒng)才進(jìn)入死鎖狀態(tài)。先進(jìn)先出（先進(jìn)先出（FIFOFIFO）頁面置換算法）頁面置換算法引用率70770170122010323104430230321013201770201頁框23042042302301271

9、2701最近最久未使用最近最久未使用(LRU)(LRU)置換算法置換算法引用率70770170122010320304403230321132201770101頁框402432032102地址結(jié)構(gòu)分頁地址中的地址結(jié)構(gòu)如下：它含有兩部分：前一部分為頁號P，后一部分為位移量W(或稱為頁內(nèi)地址)。圖中的地址長度為32位，其中011位為頁內(nèi)地址，即每頁的大小為4 KB；1231位為頁號，地址空間最多允許有1 M頁。 例：在分頁存儲管理中，假設(shè)程序地址字為32位，頁長為4KB，則頁號占用_位，空間最多有_頁。某分頁存儲器每頁大小為1KB，某進(jìn)程的頁表如下所示：頁號塊號05110 24 37 問：邏輯地址

10、0A5C（H）對應(yīng)的物理地址是什么？0A5C(H)=0000 1010 1001 1100(B) 后10位為頁內(nèi)地址，前6位為頁號，因此頁號為2，對應(yīng)的塊號為4，即000100，加上頁內(nèi)地址，得到物理地址為0001 0010 1001 1100(B)=125C(H)一個磁盤系統(tǒng)，平均尋道時間為一個磁盤系統(tǒng)，平均尋道時間為12ms，轉(zhuǎn)速為，轉(zhuǎn)速為10000轉(zhuǎn)轉(zhuǎn)/分，每個磁道有分，每個磁道有18個扇區(qū)，每個扇區(qū)個扇區(qū)，每個扇區(qū)512個字節(jié)。個字節(jié)。請問要讀取一個扇區(qū)所花的時間是多少？請問要讀取一個扇區(qū)所花的時間是多少？ 解：解： TS = 12msTR = 1/2r = 60000100000.5

11、 = 3ms TA=b/rN = (51260000)(1851210000)= 0.33ms TT = TS + TR + TA =12 + 3 + 0.33 = 15.33ms答：讀取一個扇區(qū)所花的時間是答：讀取一個扇區(qū)所花的時間是15.33ms。 例例5.6.2 5.6.2 磁盤調(diào)度磁盤調(diào)度 目標(biāo)：減少尋道時間目標(biāo)：減少尋道時間1 1、FCFSFCFS（Fisrt Come First ServedFisrt Come First Served）先來先服務(wù)）先來先服務(wù) 特點：公平、簡單，尋道時間長，相當(dāng)于隨機特點：公平、簡單，尋道時間長，相當(dāng)于隨機訪問模式。訪問模式。 僅適用于請求磁盤僅

12、適用于請求磁盤I/OI/O的進(jìn)程數(shù)目較少的場合。的進(jìn)程數(shù)目較少的場合。2 2、SSTFSSTF（最短尋道優(yōu)先）最短尋道時間優(yōu)先（最短尋道優(yōu)先）最短尋道時間優(yōu)先 SSTFSSTF比比FCFSFCFS有更好的尋道性能有更好的尋道性能 貪心的算法貪心的算法 饑餓現(xiàn)象饑餓現(xiàn)象 不能保證平均尋道時間最短不能保證平均尋道時間最短 ？例如，當(dāng)前磁頭在第例如，當(dāng)前磁頭在第1111磁道，申請訪問磁道序列：磁道，申請訪問磁道序列：1 1，9, 129, 12，1616，3232圖 5-25 FCFS調(diào)度算法圖 5-26 SSTF調(diào)度算法 3 3、SCAN SCAN 掃描算法（也稱為電梯算法）。掃描算法（也稱為電梯

13、算法）。 進(jìn)程進(jìn)程“饑餓現(xiàn)象饑餓現(xiàn)象”SSTFSSTF存在。存在。 SCANSCAN算法：算法： 在移動方向固定的情況下采用了在移動方向固定的情況下采用了SSTFSSTF，以避免饑餓，以避免饑餓現(xiàn)象現(xiàn)象 存在請求進(jìn)程等待延遲現(xiàn)象存在請求進(jìn)程等待延遲現(xiàn)象4 4、循環(huán)掃描、循環(huán)掃描CSCANCSCAN 磁頭單向移動磁頭單向移動 一個方向讀完，不是象一個方向讀完，不是象SCANSCAN那樣回頭，而是循環(huán)掃描。那樣回頭，而是循環(huán)掃描。 請求延遲時間：請求延遲時間：2T2TT+SmaxT+Smax圖圖 5-27 SCAN調(diào)度算法示例調(diào)度算法示例 圖圖 5-28 CSCAN調(diào)度算法示例調(diào)度算法示例若干個等

14、待訪問磁盤者依次要訪問的磁道為若干個等待訪問磁盤者依次要訪問的磁道為20，44，40，4，80，12，76，假設(shè)每移動一個磁道需，假設(shè)每移動一個磁道需要要3毫秒時間，移動臂當(dāng)前位于毫秒時間，移動臂當(dāng)前位于40號柱面，請按下列號柱面，請按下列算法分別寫出訪問序列并計算為完成上述各次訪問總算法分別寫出訪問序列并計算為完成上述各次訪問總共花費的尋道時間。共花費的尋道時間。 （1）先來先服務(wù)算法；）先來先服務(wù)算法； （2）最短尋道時間優(yōu)先算法。）最短尋道時間優(yōu)先算法。（3）掃描算法（當(dāng)前磁頭移動的方向為磁道遞增）掃描算法（當(dāng)前磁頭移動的方向為磁道遞增）解：解：（1）磁道訪問順序為：）磁道訪問順序為：2

15、0，44，40，4，80，12，76尋道時間尋道時間=（20+24+4+36+76+68+64）*3=292*3=876（2）磁道訪問順序為：）磁道訪問順序為：40，44，20，12，4，76，80尋道時間尋道時間=（0+4+24+8+8+72+4）*3=120*3=360（3）磁道訪問順序為：）磁道訪問順序為：40，44，76，80，20，12，4尋道時間尋道時間=（0+4+32+4+60+8+8）*3=116*3=348一個進(jìn)程的大小為5個頁面，為它分配了四個物理塊。當(dāng)前每個塊的情況如下表所示（都為十進(jìn)制數(shù)，且從0開始計數(shù)。）。當(dāng)虛頁4發(fā)生缺頁時，使用下列的頁面置換算法，哪一個物理塊將被換出？并解釋原因頁號塊號加載時間訪問時間訪問位R修改位M2 060161001 1130160010 226162103 32016311 FIFO算法（先進(jìn)先出置換算法）LRU算法（最近最久未使用置換算法）CLOCK算法（最近未用置換算法，又稱NRU算法）當(dāng)頁面的訪問串為：“4，0，0，0，2，4，2，1，0，3，2”的OPT算法（最佳置換算法）解：1換出第3號虛頁，因為它加載的時間最早；2換出第1號虛頁，因為它最近最久沒被訪問；3換出第2號虛頁，因為它最近既沒被訪問，又沒被修改；4換出第3號虛頁，因為它離訪問點最遠(yuǎn)