操作系統(tǒng)例題講解1

1、操作系統(tǒng)例題講解、調(diào)度算法對如下表所示的 5個進(jìn)程:進(jìn)程到達(dá)時間(ms)優(yōu)先級CPU陣發(fā)時間(ms)P1233P2012P3443P4024P5552采用可剝奪的靜態(tài)最高優(yōu)先數(shù)算法進(jìn)行調(diào)度(不考慮系統(tǒng)開銷)問題：畫出對上述5個進(jìn)程調(diào)度結(jié)果的 Gantt圖;計算5個進(jìn)程的平均周轉(zhuǎn)時間、平均帶權(quán)周轉(zhuǎn)時間。 解：調(diào)度結(jié)果的Gantt圖如下：P4P1P3P5P3P1P4P2024579101214(2)時間計算:進(jìn)程到達(dá)時間(ms)優(yōu)先級運行時間(ms)開始時間(ms)完成時1可(ms)周轉(zhuǎn)時間(ms)帶權(quán)周轉(zhuǎn) 時間(ms)P123321088/3P20121214147P34434955/3P402

2、4012123P55525721平均周轉(zhuǎn)時間=(8+14+5+12+2)/5=41/5=8.2 (ms)平均帶權(quán)周轉(zhuǎn)時間=(8/3+7+5/3+3+1)/5=46/15 = 3.07(ms)、存儲管理某系統(tǒng)采用虛擬頁式存儲管理方式，頁面大小為2KB ,每個進(jìn)程分配的頁框數(shù)固定為4頁。采用局部置換策略，置換算法采用 改進(jìn)的時鐘算法，當(dāng)有頁面新裝入內(nèi)存時，頁表的時鐘指針指向新裝入頁面的下一個在內(nèi)存的表項。設(shè)當(dāng)前進(jìn)程P的頁表如下(“時鐘”指針指向邏輯頁面3的表項)邏輯頁號012345頁框號訪問位r修改位m內(nèi)外標(biāo)識101H001一0110H101138H001一0100H111問 題： 當(dāng)進(jìn)程P依次對

3、邏輯地址執(zhí)行下述操作： 引用 4c7H ; 修改19B4H ; 修改 0C9AH ;寫出進(jìn)程P的頁表內(nèi)容； 在的基礎(chǔ)上，當(dāng) P對邏輯地址27A8H進(jìn)行訪問，該邏輯地址對應(yīng)的物理地址是多少？解：頁面大小為 2KB , 2KB= 2X 21°=211,即邏輯地址和物理地址的地址編碼的低11位為頁內(nèi)偏移;(1) 邏輯地址4c7H=0 100 1100 0111B,高于11位為0,所以該地址訪問邏輯頁面0;引用4C7H,頁表表項 0: r=1 ; 邏輯地址19B4H=0001 1 0011011 0100B,高于11位為3,所以該地址訪問邏輯頁面3;修改19B4H ,頁表表項 3： r=1,

4、 m=1; 邏輯地址0c9AH=0000 11 00 1001 1010B,高于11位為1,所以該地址訪問邏輯頁面1;邏輯頁1不在內(nèi)存，發(fā)生缺頁中斷;、兩操作后， P的頁表如下：邏輯頁號頁框號訪問位r修改位m內(nèi)外標(biāo)識101H101一0110H101138H111一0100H1110145按改進(jìn)的時鐘算法，且時鐘指針指向表項3,應(yīng)淘汰0頁面,23即把P的邏輯頁面1讀到內(nèi)存頁框101H ,頁表時鐘指針指向表項2并執(zhí)行操作：修改0C9AH 。邏輯頁號01k2345頁框號訪問位r修改位m內(nèi)外標(biāo)識一000101H111110H001138H011一0100H011經(jīng)上述3個操作后，P的頁表如下: 邏輯地

5、址27A8H=0010 0 111 1010 1000 B,高于11位為4,所以該地址訪問邏輯頁面4;頁面4不在內(nèi)存，發(fā)生缺頁中斷；按改進(jìn)的時鐘算法，淘汰頁面2,頁面4讀到110H頁框,所以，邏輯地址 27A8H對應(yīng)的 物理地址為：0001 0001 0000 111 1010 1000B=887A8H 。三、設(shè)備與I/O管理設(shè)系統(tǒng)磁盤只有一個移動磁頭，磁道由外向內(nèi)編號為：0、1、2、199;磁頭移動一個磁道所需時間為1毫秒；每個磁道有32個扇區(qū)；磁盤轉(zhuǎn)速 R=7500r/min.系統(tǒng)對磁盤設(shè)備的I/O請求采用 N-Step Look(即N-Step Scan,但不必移動到磁道盡頭)，N=5。

6、設(shè)當(dāng)前磁頭在 60號磁道，向內(nèi)移動；每個 I/O請求訪問磁道上的1個扇區(qū)?，F(xiàn)系統(tǒng) 依次接收到 對磁道的I/O請求序列如下：50, 20, 60, 30, 75, 30, 10, 65, 20, 80, 15, 70問題：(1)寫出對上述I/O請求序列的調(diào)度序列，并計算磁頭引臂的移動量； 計算：總尋道時間(啟動時間忽略)、總旋轉(zhuǎn)延遲時間、總傳輸時間和總訪問處理時間。解：(1)考慮序列中有重復(fù)磁道的I/O請求，調(diào)度序列 為：60-75503020151065 7080磁頭移動量=(75-60)+(75-50)+(50-30)+(30-20)+(20-15)+(15-10)+(65-10)+(70-

7、65)+(80-70)=15+25+20+10+5+5+55+5+10=155 (磁道) 總尋道時間 =1 X 155=155 (ms)一次訪盤的旋轉(zhuǎn)時間=1/(2R)=1/(2 X 7500/min)=(60 X 1000)/(2 X 7500)ms=4(ms)請求序列共12次訪盤，總旋轉(zhuǎn)延遲時間 =4X 12=48(ms)1 次訪盤的傳輸時間 =1/(R X32)=(60 X 1000)/(7500 X 32)=1/4ms12次訪盤 總傳輸時間=1/4 X 12=3(ms)總訪盤處理時間 =155+48+3=206(ms)四、文件系統(tǒng)(1)給出“用戶打開文件表”和“系統(tǒng)打開文件表”的形式，

8、并圖示二者之間的聯(lián)系;(2)說明"寫文件"系統(tǒng)調(diào)用命令write(fd,buf,count)的實現(xiàn)過程。解：用戶打開文件表和系統(tǒng)打開文件表圖示如下：文件打開讀寫系統(tǒng)打開描述符方式指針文件表入口fd1進(jìn)程P1的用戶打開文件表文件打開讀寫系統(tǒng)打開描述符方式指針文件表入口fd2進(jìn)程P2的用戶打開文件表FCB主部文件號共享計數(shù)修改標(biāo)志1520/1系統(tǒng)打開文件表(2) write(fd,buf,count)的實現(xiàn)過程如下：參數(shù)含義：fd ：文件描述符；count：寫出記錄個數(shù)； buf ：內(nèi)存起始位置；執(zhí)行步驟： 由fd查找用戶打開文件表，找到對應(yīng)的系統(tǒng)打開文件表入口；根據(jù)用戶打開文

9、件表中所記錄的打開方式和存取方式核查訪問的合法性；查系統(tǒng)打開文件表，找到文件的地址；計算欲訪問起始記錄的地址；如果需要，申請存儲塊； 將內(nèi)存中由buf起始的count個記錄寫到文件中由當(dāng)前寫指針?biāo)_定的區(qū)域;調(diào)整用戶打開文件表的讀寫指針。五、死鎖問題某系統(tǒng)采用死鎖檢測發(fā)現(xiàn)死鎖。設(shè)系統(tǒng)有資源類集合為R= A, B, C , 6個進(jìn)程P0、P1、P2、P3、P4、P5并發(fā)運行。當(dāng)前系統(tǒng)狀態(tài)如下：allocationrequestavailableABCABCABCP0100000221P1321000P2012202P3000000P4210031P5001000問題：(1)在上述狀態(tài)下，系統(tǒng)依次

10、接收請求：request0=(1,0,0)、request1=(2,1,0)、request3=(0,0,2),給出系統(tǒng)狀態(tài)變化情況，并說明沒有死鎖 在所確定的狀態(tài)下，系統(tǒng)接收請求：request0=(0,3,1),說明此時已經(jīng)發(fā)生死鎖，并找出參與死鎖的進(jìn)程。解： 在上述情況下，系統(tǒng)依次接收請求： request0=(1,0,0)、request1=(2,1,0)、request3=(0,0,2), 系統(tǒng)狀態(tài)變化如下：allocationrequestavailableABCABCABCP020 :0:00 :0121P1321210P2012202P3000002P4210031P50010

11、00上一狀態(tài)沒有死鎖。因為，用死鎖檢測算法，進(jìn)程P5、P0、P1、P2、P3、P4能依次運行完。 在所確定的狀態(tài)下，系統(tǒng)接收請求：request0=(0,3,1),系統(tǒng)狀態(tài)變化如下:allocationrequestavailableABCABCABCP0200031121P1321210P2012202P3000002P4210031P5001000對上一狀態(tài)用死鎖檢測算法，P5、P3能完成，P0、P1、P2、P4不能完成,發(fā)生死鎖，參與死鎖的進(jìn)程為P0、P1、P2、P4o六、信號量與P/V操作一南北流向的小河上有一座獨木橋，如下圖所示：西y X東該獨木橋?qū)挾戎荒苋菁{一人，且該橋最多只能承重

12、4人；東、西兩方向過橋人只能前進(jìn)、不能后退問題：寫出用信號量和 PV操作實現(xiàn)東、西兩方向行人過橋沒有死鎖、沒有餓死的并發(fā)運行算法。要 求：給出定義的各信號量和變量的含義及其初值；算法用類C偽代碼描述。解：共享變量定義：int west_crossing=0,east_crossing=0,west_wait=0,east_wait=0;semaphore wq , eq; /*初值均為 0*/semaphore mutex; /* 初值均為 1,用于共享變量的互斥*/semaphore num;/*初值為4,用于限制過河人數(shù)*/semaphore w_wait, e_wait; /* 初值均為

13、西面過河者算法：P(w_wait); /*后續(xù)過橋者將在此等待 */ P(mutex);if (east_crossing > 0) west_wait + ;if (west_wait= =1) P(e_wait);西邊有等待，東邊后續(xù)過橋者將等待1,防止對方餓死*/東面過河者算法：P(east_wait);/*后續(xù)過橋者將在此等待 */ P(mutex);if (west_crossing > 0) east_wait + ;if (east_wait= =1) P(w_wait);東邊有等待，西邊后續(xù)過橋者將等待region。和region1 。用軟件方法解決P0和P1互斥進(jìn)

14、入其進(jìn)程P1 ：do flag1=1; turn= ； while ( )do continue; <region1> ；flag1=0； 其余代碼; while(1);七、進(jìn)程互斥并發(fā)進(jìn)程 P0和P1關(guān)于共享變量的臨界區(qū)分別為 臨界區(qū)的不完整.的C偽代碼如下：int flag2=0,0;/* 公共變量 */int turn;/*公共變量*/進(jìn)程P0：do flag0=1;turn=;while ( )do continue;<region0> ；flag0=0;其余代碼; while(1);問題：1 .在、處分別填上正確的數(shù)；在、處分別填上正確的C表達(dá)式，使 P0、P

15、1滿足臨界區(qū)管理的互斥性、進(jìn)展性、有限等待性原則；2 .當(dāng)P0和P1兩進(jìn)程都要進(jìn)入臨界區(qū)，并分別執(zhí)行完各自有關(guān) turn的賦值語句后，哪個進(jìn)程先進(jìn)入臨界區(qū)？說明理由。解：1.完善進(jìn)程：=1、=0;=flag1&&turn=1 、=flag0&&turn=0;2.當(dāng)P0和P1兩進(jìn)程都要進(jìn)入臨界區(qū)，并分別執(zhí)行完、處的有關(guān)turn的賦值語句后，哪個進(jìn)程先執(zhí)行完turn的賦值語句，哪個進(jìn)程就先進(jìn)入臨界區(qū)。理由如下：假設(shè)P0先執(zhí)行turn=1 , P1后執(zhí)行turn=0 ,執(zhí)行各自的 while語句之前，turn=0，使P0的while循 環(huán)條件為假、P1的while循環(huán)

16、條件為真，所以 P0不用while循環(huán)等待，直接跳出循環(huán)先進(jìn)入臨界區(qū)。八、文件系統(tǒng)在UNIX系統(tǒng)中，進(jìn)程P部分程序如下:Int pid1,pid2;Int fd2;Char buf50;/*關(guān)閉寫端*/Pipe(fd); If(Pid1=fork()=0) close(fd1;read(fd0,buf,6); sleep(100);exit(1);/*關(guān)閉讀端*/Hello "，6); If(pid2=fork()=0) close(fd0);write(fd1, " sleep(100);exit(2);close(fd0);close(fd1);畫圖說明上述程序在 ex

17、it執(zhí)行前，系統(tǒng)中u_ofile表、file表、inode表的主要內(nèi)容及表之間的聯(lián)系情況，以及 buf 的內(nèi)容。解：給定程序在執(zhí)行 exit前，各表主要內(nèi)容及各表之間的關(guān)系如下圖所示。進(jìn)程P和寫子進(jìn)程pid2的buf值不確定，pidl讀子進(jìn)程的 buf=H, 'e','l',T,'o','0' ;fd0fd1f_flag = Rpipe f_count=1 finode=kFd0 Fd1-1Pidl 的 U ofileFd0Fd1Pid2 的 U ofilef_o f offset=6f_flag = Wpipe f_count=

18、1 f_inode=k foffset=6icount=2i_addr0=bi_addr1 7=nullHello內(nèi)存file表磁盤塊九、死鎖問題A, B, C , 5 個進(jìn)程 P0、P1、論在P3odP41發(fā)運行。按銀行家算法，當(dāng)前設(shè)系統(tǒng)有資源集合為 系統(tǒng)狀態(tài)如下：ABCABCABC554010211432221652101ClaimAllocationAvailableP0P1P2322211443002P3P4問題：(1)系統(tǒng)中各類資源總量是多少？ 矩陣Need的值是多少？判斷當(dāng)前系統(tǒng)狀態(tài)是否安全？ 在當(dāng)前狀態(tài)下，如果進(jìn)程P0提出資源請求request0=(1,0,0),系統(tǒng)能否實施分配？說明原因解：系統(tǒng)各類資源總量( A, B, C) = (7, 5, 6)