操系計(jì)網(wǎng)離數(shù)復(fù)試課件操作系統(tǒng)習(xí)題課

1西安電子科技大學(xué)計(jì)算機(jī)學(xué)院2習(xí)題講解第一章～第六章第一章3ch1－3操作系統(tǒng)形成標(biāo)志－多道程序系統(tǒng)的出現(xiàn)ch1－11客戶機(jī)/服務(wù)器模型可以用于單機(jī)系統(tǒng)，同時(shí)它也適用于分布式系統(tǒng)。理解時(shí)注意以下幾點(diǎn)：1）客戶機(jī)、服務(wù)器是一個(gè)抽象的概念，并不一定要和實(shí)際的物理機(jī)器對應(yīng)；2）把握其核心思想第一章下圖展示的是一個(gè)客戶機(jī)/服務(wù)器模型在這里內(nèi)核的全部工作就是處理客戶機(jī)和服務(wù)器間的通信，如果是單機(jī)則消息直接由本機(jī)操作系統(tǒng)內(nèi)核傳遞，如果是分布式系統(tǒng)則消息需要通過網(wǎng)絡(luò)在不同機(jī)器的操作系統(tǒng)內(nèi)核間傳遞，但是無論采用何種方式，都是符合上述客戶機(jī)/服務(wù)器模型的。4第一章下圖是一個(gè)分布式系統(tǒng)中的客戶機(jī)/服務(wù)器模型5第二章作業(yè)的執(zhí)行順序?yàn)?->2->4->3->1作業(yè)提交時(shí)間執(zhí)行時(shí)間（分鐘）開始時(shí)刻完成時(shí)刻周轉(zhuǎn)時(shí)間（分鐘）18：00608：0010：0512528：20358：208：553538：30259：009：255548：3558：559：0025平均周轉(zhuǎn)時(shí)間T＝60分鐘2406第二章7ch2－10本題不嚴(yán)密，兩處有歧義：“作業(yè)在時(shí)刻0以1,2,3,4,5的順序到達(dá)”：時(shí)刻是一個(gè)瞬時(shí)概念，如果作業(yè)都是在這個(gè)時(shí)刻到達(dá)則不應(yīng)當(dāng)有先后順序；優(yōu)先數(shù)代表的優(yōu)先級高低未交代清楚，因?yàn)橛械臋C(jī)器可能是高優(yōu)先數(shù)代表高優(yōu)先級，但有的機(jī)器卻相反。為此對這兩處作如下規(guī)定：改為“作業(yè)從時(shí)刻0開始在很短的時(shí)間（可以忽略）內(nèi)以1,2,3,4,5的順序到達(dá)”；規(guī)定低優(yōu)先數(shù)代表高優(yōu)先級第二章8FCFS：作業(yè)的執(zhí)行順序?yàn)?->2->3->4->5作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)刻完成時(shí)刻周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間1010010101201101111113021113136.5401131414145051419193.8平均周轉(zhuǎn)時(shí)間T＝13.4，平均帶權(quán)周轉(zhuǎn)時(shí)間＝7.266736.3第二章9SJF：作業(yè)的執(zhí)行順序?yàn)?->2->4->3->5作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)刻完成時(shí)刻周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間1010010101201101111113021214147401111212125051419193.8平均周轉(zhuǎn)時(shí)間T＝13.2，平均帶權(quán)周轉(zhuǎn)時(shí)間＝6.966634.8第二章10非剝奪式優(yōu)先級算法：作業(yè)的執(zhí)行順序?yàn)?->2->5->3->4作業(yè)提交時(shí)間執(zhí)行時(shí)間開始時(shí)刻完成時(shí)刻周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間1010010101201101111113021618189401181919195051116163.2平均周轉(zhuǎn)時(shí)間T＝14.8，平均帶權(quán)周轉(zhuǎn)時(shí)間＝8.647443.2第二章11討論作業(yè)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間是衡量作業(yè)調(diào)度算法的兩個(gè)重要指標(biāo)，通常，使用前者來衡量不同調(diào)度算法對同一作業(yè)流的調(diào)度性能；使用后者來衡量同一調(diào)度算法對不同作業(yè)流的調(diào)度性能。作業(yè)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間越短越好。注：帶權(quán)周轉(zhuǎn)時(shí)間＝周轉(zhuǎn)時(shí)間/執(zhí)行時(shí)間；帶權(quán)周轉(zhuǎn)時(shí)間即為周轉(zhuǎn)系數(shù)，平均帶權(quán)周轉(zhuǎn)時(shí)間即為平均周轉(zhuǎn)系數(shù)。第三章12ch3-24(教材73,74,75,77畫線部分）初值為1，范圍1,0,-1,…,-(n-1)初值為m，范圍m,m-1,…,1,0,…,-(n-m)第三章13ch3-26設(shè)置信號量mutex1,mutex2，初值為1，用于counti的互斥；tunnel初值為1；計(jì)數(shù)器count1，count2，初值為0。北方：P(mutex1);count1:=count1+1;if

count1=1

thenP(tunnel);V(mutex1);過隧道；P(mutex1);count1:=count1-1;if

count1=0

then

V(tunnel);V(mutex1);南方：P(mutex2);count2:=count2+1;if

count2=1

thenP(tunnel);V(mutex2);過隧道；P(mutex2);count2:=count2-1;if

count2=0

then

V(tunnel);V(mutex2);第三章14ch3-27（1）設(shè)：私有信號量C表示貨位的容量，初值為1（也可不用，直接用S就可以）；公有信號量S用于貨位的互斥操作，初值為

1；私有信號量Icebox表示冰箱，初值為0；私有信號量Car表示汽車，初值為0A:While(true){B:While(true){甲:While(true){乙While(true){P(C)；P(S)；P(C)；P(S)；P(Car)；P(S)；P(Icebox)；P(S)；放汽車；放冰箱；取汽車；取冰箱；V(S);V(Car);}V(S);V(Icebox);}V(S);V(C);}V(S);V(C);}第三章15ch3-27（2）設(shè)：私有信號量C表示貨位的容量，初值為N，其它同前。第三章16ch3－29可看作四對生產(chǎn)者／消費(fèi)者問題。mutexi(i＝0，1，2，3)控制四個(gè)信箱的互斥使用，初值均為1；emptyi(i＝0，1，2，3)表示各信箱中空單元的個(gè)數(shù)，初值分別為1，3，2，2；fulli(i＝0，1，2，3)表示各箱中信息個(gè)數(shù)，初值分別為2，0，0，0。第三章17P0：BeginL1：P(full0)；P(mutex0)；從M0中取一個(gè)消息;V(mutex0)；V(empty0)；加工消息；P(emptyl);P(mutex1)；送消息進(jìn)入M1；V(mutex1)；V(fulll)；GotoL1;End；P1：BeginL2：P(full1)；P(mutex1)；從M1中取一個(gè)消息;V(mutex1)；V(empty1)；加工消息；P(empty2);P(mutex2)；送消息進(jìn)入M2；V(mutex2)；V(full2)；GotoL2;End；第三章18P2：BeginL3：P(full2)；P(mutex2)；從M2中取一個(gè)消息;V(mutex2)；V(empty2)；加工消息；P(empty3);P(mutex3)；送消息進(jìn)入M3；V(mutex3)；V(full3)；GotoL3;End；P3：BeginL4：P(full3)；P(mutex3)；從M3中取一個(gè)消息;V(mutex3)；V(empty3)；加工消息；P(empty0);P(mutex0)；送消息進(jìn)入M0；V(mutex0)；V(full0)；GotoL4;End；第三章補(bǔ)充19桌上有一空盤，允許放一個(gè)水果。爸爸可向盤中放蘋果和桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。規(guī)定當(dāng)盤中空時(shí)一次只能放一只水果供吃者取用，請用PV原語實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。桌子上有一只盤子，最多可容納兩個(gè)水果，每次只能放人或取出一個(gè)水果。爸爸專向盤子中放蘋果(apple)，媽媽專向盤于中放桔子(orange)，兩個(gè)兒子專等吃盤子中的桔子，兩個(gè)女兒專等吃盤子中的蘋果。請用PV操作來實(shí)現(xiàn)爸爸、媽媽、兒子、女兒之間的同步與互斥關(guān)系。第四章20ch4－9不安全，因?yàn)檎也坏揭粋€(gè)安全序列。不可以，否則會死鎖。ch4－10死鎖。死鎖，因?yàn)閳D中最右邊的資源無進(jìn)程生產(chǎn)。第四章ch4－11T121T2T3T4S1?

R1

?S2R2

?

?第四章ch4－11T1T2T4S1?

R1

?S2R2

?

?22第四章ch4－11T2T4?

R1

?S2R2

?

?23T2T4?

R1

?S2第四章ch4－11死鎖24第四章25ch4－12判斷是否為安全狀態(tài)，關(guān)鍵在于能否找到一個(gè)安全序列。進(jìn)程剩余需求量系統(tǒng)剩余資源P13,4,72,3,3P21,3,4P30,0,6P42,2,1P51,1,0至少可以找到一個(gè)安全序列<P4P2P3P5Pl>，答案不唯一。不能，因?yàn)橄到y(tǒng)剩余資源不夠?？梢苑峙?。因?yàn)橹辽倏梢哉业揭粋€(gè)安全序列<P4P5P1P2P3>。不能分配，因?yàn)檎也坏揭粋€(gè)安全序列。第四章26ch4－13為永久性資源（a）會死鎖（b)不會死鎖第四章27ch4－9不安全，因?yàn)檎也坏揭粋€(gè)安全序列。不可以，否則會死鎖。ch4－10死鎖。死鎖，因?yàn)閳D中最右邊的資源無進(jìn)程生產(chǎn)。第四章ch4－11T128T2T3T4S1?

R1

?S2R2

?

?第四章ch4－11T1T2T4S1?

R1

?S2R2

?

?29第四章ch4－11T2T4?

R1

?S2R2

?

?30T2T4?

R1

?S2第四章ch4－11死鎖31第四章32ch4－12判斷是否為安全狀態(tài)，關(guān)鍵在于能否找到一個(gè)安全序列。進(jìn)程剩余需求量系統(tǒng)剩余資源P13,4,72,3,3P21,3,4P30,0,6P42,2,1P51,1,0至少可以找到一個(gè)安全序列<P4P2P3P5Pl>，答案不唯一。不能，因?yàn)橄到y(tǒng)剩余資源不夠。可以分配。因?yàn)橹辽倏梢哉业揭粋€(gè)安全序列<P4P5P1P2P3>。不能分配，因?yàn)檎也坏揭粋€(gè)安全序列。第四章33ch4－13為永久性資源（a）會死鎖（b)不會死鎖第五章3415（1）當(dāng)M＝3時(shí)，采用LRU替換算法：時(shí)刻123456789101112P432143543215M4+3+2+1+4+3+5+432+1+5+432143543214-3-2-1-4-3-5-4-3-2-F++++++++++算出缺頁中斷次數(shù)F=10，缺頁率f

=10／12=83％。第五章3515（2）當(dāng)M＝4時(shí)，采用LRU替換算法：時(shí)刻123456789101112P432143543215M4+3+2+1+435+432+1+5+4321435432143214354324-3-2-1-1-1-5-4-3-F++++++++由表可以算出缺頁中斷次數(shù)F=8，而缺頁率：8／12=67%。第五章3615（3）如果采用FIFO替換算法，當(dāng)M＝3時(shí)時(shí)刻123456789101112P432143543215M4+3+2+1+4+3+5+552+1+1432143335224-3-2-1-4-4-4-3-5-5-F+++++++++由表可以算出缺頁中斷次數(shù)F=9，而缺頁率：9／12=75%。第五章3715（4）采用FIFO替換算法，當(dāng)M＝4時(shí)時(shí)刻123456789101112P432143543215M4+3+2+1+115+4+3+2+1+5+4322215432143332154324-4-4-3-2-1-5-4-3-F++++++++++由表可以算出缺頁中斷次數(shù)F=10，而缺頁率：10／12=83%。第五章3815（5）采用OPT淘汰算法，當(dāng)M＝3時(shí)時(shí)刻123456789101112P432143543215M4+3+2+-1+-1-1-5+-55555-43333333-2+-1+-1444444-4444F+++++++由表可以算出缺頁中斷次數(shù)F=7，而缺頁率：7／12=58%。第五章3915（6）采用OPT淘汰算法，當(dāng)M＝4時(shí)時(shí)刻123456789101112P432143543215M4+3+2+1+-1-1-5+-55555-432222222-1+-14333333-33344444-4444F++++++由表可以算出缺頁中斷次數(shù)F=6，而缺頁率：6／12=50%。第五章4015通過以上缺頁次數(shù)和缺頁率的分析計(jì)算，可以看

出，對于LRU、OPT算法，增加物理塊數(shù)，不會增加

缺頁次數(shù)。對于FIFO算法，增加物理塊數(shù)，不一定能減少缺頁次數(shù)。但這里，OPT算法僅是一種理論算法，因?yàn)樗鶕?jù)未來頁面走向決定淘汰哪一頁，而在實(shí)際執(zhí)行時(shí)無法準(zhǔn)確的知道未來行為。所以，該算法不作為實(shí)用算法，僅用于算法的比較和評價(jià)。討論：計(jì)算缺頁次數(shù)和缺頁率時(shí)，要注意初始時(shí)刻所有物理塊為空。調(diào)入頁面時(shí)，不需要頁面替換，但是需要引起缺頁中斷。第五章4116(1)為了實(shí)現(xiàn)從邏輯地址到物理地址的變換，在系統(tǒng)中需要設(shè)置段表寄存器，存放段表起始地址和段表長度

STL。在進(jìn)行地址變換時(shí)，系統(tǒng)將邏輯地址中的段號S與段表長度STL進(jìn)行比較。若S≥STL，則表示段號太大，訪問越界(段號越界)，產(chǎn)生越界中斷。若未越界，則根據(jù)段表的起始地址和段號，計(jì)算出該段對應(yīng)段表項(xiàng)的位置，從中讀出該段在內(nèi)存中的起始位置和段長SL，再檢查段內(nèi)地址D是否超過該段的段長SL。若超過，即D≥SL，則同樣發(fā)出越界中斷信號(段內(nèi)地址越界)；若未越界，則將該段的起始地址與段內(nèi)地址D相加，即得要訪問的內(nèi)存物理地址。第五章4216(2)

[0,340]------------------219+340

=

559[1,10]-------------------3300+10

=

3310[2,500]-----------------段內(nèi)地址越界（500>100），不合法[3,400]-----------------1237+400

=

1637第五章4316(3)存取主存中的一條指令或數(shù)據(jù)至少要訪問2次主存。一次是訪問段表，另一次是訪問需要的指令或數(shù)據(jù)。討論

在分段存儲管理的地址變換過程中，要點(diǎn)是由段號查段表得段起始地址。然后與段內(nèi)地址相加得物理地址。但要注意，段地址是二維地址，段號和段內(nèi)地址都有可能越界。如因5＞4，所以[5，l00]越界(段號越界)第五章17(1)(2)操作系統(tǒng)作業(yè)1（60KB）空閑區(qū)A（60KB）作業(yè)2（40KB）空閑區(qū)B（20KB）作業(yè)3（30KB）空閑區(qū)C（26KB）0K20K80K140K180K200K230K255K操作系統(tǒng)空閑區(qū)A（120KB）作業(yè)2（40KB）空閑區(qū)B（76KB）0K20K140K180K255K44第五章17(3)首次適應(yīng)算法操作系統(tǒng)空閑區(qū)A（120KB）作業(yè)2（40KB）空閑區(qū)B（76KB）0K20K140K180K255K0K20K90K140K180K45255K操作系統(tǒng)作業(yè)4（70KB）空閑區(qū)A（50KB）作業(yè)2（40KB）空閑區(qū)B（76KB）第五章17(3)最佳適應(yīng)算法操作系統(tǒng)空閑區(qū)A（120KB）作業(yè)2（40KB）空閑區(qū)B（76KB）0K20K140K180K255K0K20K46140K180K250K255K操作系統(tǒng)空閑區(qū)A（120KB）作業(yè)2（40KB）作業(yè)4（70KB）空閑區(qū)B（6KB）第五章18（1）J2頁面映像表47頁號塊號03142638第五章4818（2）頁面大小為1024字節(jié)，邏輯地址2100頁號為2（2100/1024

＝

2.05），對應(yīng)塊號為6，頁內(nèi)位移為52（1024×2＋52

＝

2100），所以物理地址為1024×6＋52＝6196。邏輯地址3100頁號為3

（

3100/1024

＝

3.02

），對應(yīng)塊號為8，頁內(nèi)位移為28（1024×3＋28

＝

3100），所以物理地址為1024×8＋28＝8220。第五章18（2）2100轉(zhuǎn)換過程如下圖所示：S4頁表控制寄存器頁表起始地址 頁表長度252邏輯地址2100頁號 頁內(nèi)偏移量65203142638+S

虛頁號實(shí)頁號地址寄存器49第五章5019NRU：0號頁（因?yàn)镽＝0）FIFO：2號頁（需回寫，因?yàn)樾薷奈籑＝0）LRU：1號頁第二次機(jī)會算法：0號頁第五章5120（1）每一塊為4k=4*1024=4096，所以9016/4096=2.2，在2號頁中（頁號從0開始），對應(yīng)32號塊。頁內(nèi)偏移量為9016-4096*2=824。根據(jù)頁表映射關(guān)系，其物理地址為：32*4k+824=131896；（2）

12300屬于第12300/4096=3.002,所以其頁號為3，此時(shí)該頁不在內(nèi)存，引起缺頁中斷，待3號頁面裝入內(nèi)存后（假設(shè)3號頁面對應(yīng)的內(nèi)存塊號為x，由內(nèi)存頁表得出塊x

的物理地址為y），則邏輯地址12300

的物理地址為=y+12（12

是頁內(nèi)偏移量=12300-4096*3）第六章1(1)(2)(3)52第六章353第六章546、由于每個(gè)邏輯記錄的大小與磁盤塊大小相等，均為512字節(jié)，所以，從要存取的文件邏輯字節(jié)地址1569＝512x3+33可知，我們要訪問是第四個(gè)磁盤塊(邏輯記錄號為3)的第33字節(jié)相對地址，即要訪問第80號磁盤塊第六章5512在UNIX操作系統(tǒng)中，一個(gè)文件應(yīng)屬于某個(gè)用戶所有，

我們將這個(gè)用戶稱為該文件的文件主。一般情況下，文件主就是建立文件的用戶。在系統(tǒng)中，使用用戶標(biāo)識符(uid)來記錄文件主。UNIX將使用文件的用戶分成三類，即文件主、同組用戶和其他用戶。同組用戶是相互之間有某種關(guān)系的用戶、如同一課題組的人，用戶所在的用戶組用組標(biāo)識符(gid)來表示。其他用戶一般是和文件主無關(guān)的用戶，但他們也是系統(tǒng)中的用戶。第六章5612每一類用戶對文件的操作都有三種不同的存取權(quán)限，即讀、寫和執(zhí)行。由于有三類用戶，每類用戶有三種存取權(quán)限，故每個(gè)文件都有9種存取權(quán)限。在系統(tǒng)內(nèi)部，文件的存取權(quán)限用9位二進(jìn)制數(shù)描述，文件主權(quán)限對應(yīng)最高三位，同組用戶權(quán)限對應(yīng)中間三位，其他用戶權(quán)限對應(yīng)低三位。例如，111101001(也可以用八進(jìn)制數(shù)表示，如0751)，表示文件主可以對該文件進(jìn)行讀、寫、執(zhí)行操作；同組用戶可以對該文件進(jìn)行讀和執(zhí)行操作；其他用戶只能對該文件進(jìn)行執(zhí)行操作。第六章5712當(dāng)系統(tǒng)用ls命令列目錄時(shí)，文件權(quán)限以標(biāo)準(zhǔn)的符號形式表示。這種表示法使用9個(gè)字符，分為3組，每組3個(gè)字符。第一組表示文件主的權(quán)限，第二組表示同組用戶的權(quán)限，第三組表示其他用戶的權(quán)限。在每組的三個(gè)字符中，如果允許這類用戶讀，則第一個(gè)字符置為

“r”，如果允許進(jìn)行寫，則第二個(gè)字符置為“w”，如果允許執(zhí)行，則第三個(gè)字符置為“x”。如果不允許某個(gè)權(quán)限，則相應(yīng)的字符置為“-”。第六章5812由上述介紹可知，文件F的存取權(quán)限r(nóng)wxr-x---表示文件主可以對F進(jìn)行讀、寫及執(zhí)行操作，同組用戶可以對F進(jìn)行讀及執(zhí)行操作，其他用戶不能對F進(jìn)行操作。因?yàn)榱硪挥脩襞c文件主的組標(biāo)識符相同(gid均為1)，由此可知他們是同組用戶，所以允許該用戶執(zhí)行文件F。第六章5916、能。如果允許使用任意長的名字，則可以模擬多級目錄結(jié)構(gòu)。例如，可用符號

“.”指明子目錄的結(jié)束。這樣，名字

h.lisp.F1指明F1是子目錄lisp的文件，而

lisp是根目錄h的文件。第六章6018空白文件目錄是管理磁盤空間的一種方法，該方法將文件存儲設(shè)備上的每個(gè)連續(xù)空閑區(qū)看作一個(gè)空白文件。系統(tǒng)為所有空白文件單獨(dú)建立一個(gè)目錄，每個(gè)空白文件在這個(gè)目錄中占一個(gè)表目。表目的內(nèi)容至少包括第一個(gè)空白塊的地址(物