計(jì)算機(jī)操作系統(tǒng)習(xí)題課.ppt

操作系統(tǒng)習(xí)題課,王培崇,一、判斷題 1. 操作系統(tǒng)的所有程序都必須常駐內(nèi)存. 2. 進(jìn)程獲得處理機(jī)而運(yùn)行是通過申請(qǐng)而得到的. 3. 通過任何手段都無法實(shí)現(xiàn)計(jì)算機(jī)系統(tǒng)資源之間的互換. （中斷等都可以） 4. 進(jìn)程控制塊中的所有信息必須常駐內(nèi)存. 5. 一旦出現(xiàn)死鎖, 所有進(jìn)程都不能運(yùn)行. (運(yùn)行不能結(jié)束) 6. 所有進(jìn)程都掛起時(shí), 系統(tǒng)陷入死鎖. （掛起的意思是什么？） 7. 優(yōu)先數(shù)是進(jìn)程調(diào)度的重要依據(jù), 一旦確定不能改變. 8. 同一文件系統(tǒng)中不允許文件同名, 否則會(huì)引起混亂. 9. 用戶程序有時(shí)也可以在核心態(tài)下運(yùn)行. （只能在用戶態(tài)下） 10. 虛擬存儲(chǔ)系統(tǒng)可以在每一臺(tái)計(jì)算機(jī)上實(shí)現(xiàn). 11. 進(jìn)程在運(yùn)行中, 可以自行修改自己的進(jìn)程控制塊. 12. 進(jìn)程申請(qǐng)CPU得不到滿足時(shí), 其狀態(tài)變?yōu)榈却龖B(tài). ,13. 在虛存系統(tǒng)中, 只要磁盤空間無限大, 作業(yè)就能擁有任意大的編址空間. 17. 大多數(shù)虛擬系統(tǒng)采用OPT(優(yōu)化)淘汰算法是因?yàn)樗_實(shí)可以得到最小的缺頁(yè)率. 19. 文件的索引表全部存放在文件控制塊中. 20. 打印機(jī)是一類典型的塊設(shè)備. 21. 當(dāng)一個(gè)進(jìn)程從等待態(tài)變成就緒態(tài), 則一定有一個(gè)進(jìn)程從就緒態(tài)變成運(yùn)行態(tài). 22. 執(zhí)行系統(tǒng)調(diào)用時(shí)可以被中斷. 23. 在作業(yè)調(diào)度時(shí), 采用最高響應(yīng)比優(yōu)先的作業(yè)調(diào)度算法可以得到最短的作業(yè)平均周轉(zhuǎn)時(shí)間. 24. 在請(qǐng)求頁(yè)式存儲(chǔ)管理中, 頁(yè)面淘汰所花費(fèi)的時(shí)間不屬于系統(tǒng)開銷. 25. 進(jìn)程優(yōu)先數(shù)是進(jìn)程調(diào)度的重要依據(jù), 必須根據(jù)進(jìn)程運(yùn)行情況動(dòng)態(tài)改變. 26. 流式文件是指無結(jié)構(gòu)的文件. 27. 參與死鎖的所有進(jìn)程都占有資源. (死鎖的某個(gè)進(jìn)程可能沒有拿到任何資源) 28. 頁(yè)式存儲(chǔ)管理中, 用戶應(yīng)將自己的程序劃分成若干相等的頁(yè). （頁(yè)式由系統(tǒng)決定）,29. 引入當(dāng)前目錄是為了減少啟動(dòng)磁盤的次數(shù). （當(dāng)前目錄可以放入內(nèi)存） 30. 文件目錄必須常駐內(nèi)存. （肯定不一定） 32. 在文件系統(tǒng)中, 打開文件是指創(chuàng)建一個(gè)文件控制塊. 33. 存儲(chǔ)保護(hù)的目的是限制內(nèi)存的分配. （是為了保護(hù)數(shù)據(jù)錯(cuò)誤） 34. 原語和系統(tǒng)調(diào)用的主要區(qū)別在于兩者的實(shí)現(xiàn)方法不同. （系統(tǒng)調(diào)用能夠被中斷） 37. 在頁(yè)式虛擬存儲(chǔ)系統(tǒng)中, 頁(yè)面長(zhǎng)度是根據(jù)程序長(zhǎng)度動(dòng)態(tài)地分配的. （固定的） 38. 如果信號(hào)量S的當(dāng)前值為-5, 則表示系統(tǒng)中共有5個(gè)等待進(jìn)程. （信號(hào)上的） 39. 磁盤上物理結(jié)構(gòu)為鏈接結(jié)構(gòu)的文件只能順序存取. 40. 系統(tǒng)處于不安全狀態(tài)不一定是死鎖狀態(tài). （不安全意味著不能再分配資源） 41. 有m個(gè)進(jìn)程的操作系統(tǒng)出現(xiàn)死鎖時(shí), 死鎖進(jìn)程的個(gè)數(shù)為1km. 42. 進(jìn)程狀態(tài)的轉(zhuǎn)換是由操作系統(tǒng)完成的, 對(duì)用戶是透明的. ,43. 優(yōu)先數(shù)是進(jìn)程調(diào)度的重要依據(jù), 優(yōu)先數(shù)大的進(jìn)程首先被調(diào)度運(yùn)行. （不一定） 44. 文件系統(tǒng)的主要目的是存儲(chǔ)系統(tǒng)文檔. 45. 對(duì)文件進(jìn)行讀寫前，要先打開文件. 46. 所謂最近最少使用（LRU）頁(yè)面調(diào)度算法是指將駐留在內(nèi)存中使用次數(shù)最少的頁(yè)面淘汰掉. 48. 參與死鎖的進(jìn)程至少有兩個(gè)已經(jīng)占有資源. （兩個(gè)占資源形成循環(huán)申請(qǐng)） 49. 在頁(yè)式虛擬存儲(chǔ)系統(tǒng)中，頁(yè)面長(zhǎng)度固定并且是硬件的設(shè)計(jì)特性. 50. 不可搶占式動(dòng)態(tài)優(yōu)先數(shù)法一定會(huì)引起進(jìn)程長(zhǎng)時(shí)間得不到運(yùn)行. 52. 選擇通道主要用于連接低速設(shè)備. 55. 進(jìn)程間的互斥是一種特殊的同步關(guān)系. （互斥就是為了同步） 56. 所有進(jìn)程都進(jìn)入等待狀態(tài)時(shí)，系統(tǒng)陷入死鎖. （等待是因?yàn)橘Y源，不一定是死鎖） 57. 引入緩沖的主要目的是提高I/O設(shè)備的利用率. 59. 文件目錄一般存放在外存. (當(dāng)前目錄一般駐留內(nèi)存),二、計(jì)算題 1. 假設(shè)一個(gè)活動(dòng)頭磁盤有200道, 編號(hào)從0-199. 當(dāng)前磁頭正在143道上服務(wù), 并且剛剛完成了125道的請(qǐng)求. 現(xiàn)有如下訪盤請(qǐng)求序列 (磁道號(hào)): 86, 147, 91, 177, 94, 150, 102, 175, 130 試給出采用下列算法后磁頭移動(dòng)的順序和移動(dòng)總量(總磁道數(shù)). (1). 先來先服務(wù)(FCFS)磁盤調(diào)度算法. (2). 最短尋道時(shí)間優(yōu)先(SSTF)磁盤調(diào)度算法. (3). 掃描法(SCAN)磁盤調(diào)度算法.(假設(shè)沿磁頭移動(dòng)方向不再有訪問請(qǐng)求時(shí), 磁頭沿相反方向移動(dòng).) 答案： （1）86，147，91，177，94，150，102，175，130 （2）當(dāng)前磁頭在143道上： 147，150，130，102，94，91，86，175，177 （3）當(dāng)前磁頭在143道上，并且剛剛完成125道的請(qǐng)求 147，150，175，177，130，102，94，91，86 計(jì)算移動(dòng)總量略,2. 設(shè)系統(tǒng)中有三類資源A、B和C，又設(shè)系統(tǒng)中有5個(gè)進(jìn)程P1，P2，P3，P4和P5.在T0時(shí)刻系統(tǒng)狀態(tài)如下： 最大需求量 已分配資源量 剩余資源量 A B C A B C A B C P1 8 6 4 1 2 1 2 1 1 P2 4 3 3 3 1 1 P3 10 1 3 4 1 3 P4 3 3 3 3 2 2 P5 5 4 6 1 1 3 (1) 系統(tǒng)是否處于安全狀態(tài)？如是，則給出進(jìn)程安全序列. (2) 如果進(jìn)程P5申請(qǐng)1個(gè)資源類A、1個(gè)資源類B和1個(gè)資源類C，能否實(shí)施分配？為什么？,答案：（1） 最大需求量 已分配資源量 剩余資源量 尚需要量 A B C A B C A B C A B C P1 8 6 4 1 2 1 2 1 1 7 4 3 P2 4 3 3 3 1 1 1 2 2 P3 10 1 3 4 1 3 6 0 0 P4 3 3 3 3 2 2 0 1 1 P5 5 4 6 1 1 3 4 3 3 系統(tǒng)是處于安全狀態(tài)，安全序列為：P4，P2，P1，P3，P5,（2）P5申請(qǐng)（1，1，1） 最大需求量 已分配資源量 剩余資源量 尚需要量 A B C A B C A B C A B C P1 8 6 4 1 2 1 1 0 0 7 4 3 P2 4 3 3 3 1 1 1 2 2 P3 10 1 3 4 1 3 6 0 0 P4 3 3 3 3 2 2 0 1 1 P5 5 4 6 2 2 4 3 2 2 不能實(shí)施分配，因?yàn)榉峙浜笳也坏桨踩蛄?，系統(tǒng)將處于不安全狀態(tài).,3、在一個(gè)兩道的批處理操作系統(tǒng)中，有6個(gè)作業(yè)進(jìn)入系統(tǒng)，它們的進(jìn)入時(shí)刻、估計(jì)運(yùn)行時(shí)間和優(yōu)先級(jí)如下表所示. 作業(yè)號(hào) 進(jìn)入時(shí)刻 估計(jì)運(yùn)行時(shí)間 優(yōu)先級(jí) JOB1 8：00 90分鐘 5 JOB2 8：10 30分鐘 6 JOB3 8：30 20分鐘 3 JOB4 8：50 15分鐘 8 JOB5 9：20 10分鐘 2 JOB6 9：40 5分鐘 4 （1）系統(tǒng)采用短作業(yè)優(yōu)先作業(yè)調(diào)度算法，作業(yè)一旦被調(diào)度運(yùn)行就不再退出.但當(dāng)有新的作業(yè)投入運(yùn)行時(shí)，可以按照優(yōu)先級(jí)進(jìn)行進(jìn)程調(diào)度. 試給出各個(gè)作業(yè)的運(yùn)行時(shí)間序列.（例如：JOB1：8：00-8：30，9：10-9：20，） （2）試計(jì)算出作業(yè)的平均周轉(zhuǎn)時(shí)間。,（1）各個(gè)作業(yè)的運(yùn)行時(shí)間序列為： JOB1 8：00-8：10， 8：40-10：00 JOB2 8：10-8：40 JOB3 10：05-10：25 JOB4 10：25-10：50 JOB5 10：50-11：00 JOB6 10：00-10：05 （2）根據(jù)公式計(jì)算（略）.,5 有四個(gè)進(jìn)程A、B、C、D 進(jìn)程A通過一個(gè)緩沖區(qū)不斷地向進(jìn)程B、C、D發(fā)送信息, A 每向緩沖區(qū)送入一個(gè)信息后, 必須等進(jìn)程B、C、D都取走后才可以發(fā)送下一個(gè)信息, B、C、D對(duì)A 送入的每一信息各取一次, 試用P、V操作實(shí)現(xiàn)它們之間的正確通訊. 答案： 初始值：Sab=Sac=Sad =0 /互斥讀寫； Sb=Sc=Sd=0;/讀取緩沖區(qū) A: Repeat /生產(chǎn)者 生產(chǎn)消息； P(Sab); P(Sac);,P(Sad); /在b,c,d各自的信號(hào)上進(jìn)行鎖定，避免b,c,d同時(shí)讀 向緩沖區(qū)送消息； V(Sb); V(Sc); V(Sd) /釋放b,c,d的通訊信號(hào)，允許他們讀取 Until False B: Repeat P(Sb); 從緩沖區(qū)取消息； V(Sab) Until False 其它可以參考B類似,6、有n+1個(gè)進(jìn)程p1, p2, .pn 和 Q: (1) p1,.pn通過同一個(gè)緩沖區(qū)各自不斷地向Q發(fā)送消息, Q不斷地取消息, 它必 須取走發(fā)來的每一個(gè)消息. 剛開始時(shí)緩沖區(qū)為空. 試用P、V操作正確實(shí)現(xiàn)之. (2) 若緩沖區(qū)個(gè)數(shù)增至k個(gè), 試用P、V操作實(shí)現(xiàn)正確的通訊. 答：(1) n+1個(gè)進(jìn)程P1, P2, .,Pn 和 Q ，一個(gè)緩沖區(qū)。 Pi ( i=1,n): Repeat 生產(chǎn)消息； P(S1); 向緩沖區(qū)送消息； V(S2) Until False,Q: Repeat P(S2); 從緩沖區(qū)取消息； V(S1)； 處理消息； Until False 初始化： S1=1, S2=0,(2) k個(gè)緩沖區(qū)； 初始化： S1=k;S2=0;mutex=1; l=0;ll=0 Pi ( i=1,n): Repeat 生產(chǎn)消息； P(S1); P(mutex); 向BUFFERl中送消息； l:=(l+1) mod k; V(mutex); V(S2) Until False,Q: Repeat P(S2); P(mutex); 從BUFFERll取消息； ll:=(ll+1) mod k; V(mutex); V(S1) Until False 7. 為什么說P、V操作必須設(shè)計(jì)成原語(即同一信號(hào)量上的P、V操作必須互斥)? 答：略,8.一個(gè)并發(fā)系統(tǒng)中存在4個(gè)進(jìn)程，都需要5個(gè)資源，該系統(tǒng)不發(fā)生死鎖的最少資源數(shù)是多少個(gè)？ 解答： 保證其中1個(gè)進(jìn)程能夠順利執(zhí)行完，則應(yīng)該是5個(gè)資源； 其它剩余3個(gè)進(jìn)程能夠在第1個(gè)進(jìn)程執(zhí)行完畢，釋放資源之后運(yùn)行完畢，則他們應(yīng)該各自保持4個(gè)資源，即3*4=12個(gè)資源。 所以最少資源是5+12=17. 如果是16個(gè)，則可能會(huì)出現(xiàn)造成4個(gè)進(jìn)程都各自保持4個(gè)資源，成為死鎖狀況。,9.假定有一個(gè)分頁(yè)虛擬存儲(chǔ)系統(tǒng)，測(cè)得各相關(guān)成分的利用率是：cpu為20%，磁盤交換區(qū)為99.7%，其它I/O設(shè)備是5%,試問，如下那種措施可以改進(jìn)cpu的利用率，簡(jiǎn)要說明理由。 （1）增加一個(gè)更快的cpu；（2）增加磁盤交換區(qū)的容量； （3）增加多道程序的度數(shù)；（4）減少多道程序的度數(shù)； （5）增加其它更快速度的I/O設(shè)備。 解答：在存儲(chǔ)分配的過程中，該系統(tǒng)顯然在分頁(yè)方面花費(fèi)了大量的時(shí)間，若減少多道程序的度數(shù)，則駐留進(jìn)程的缺頁(yè)中斷率會(huì)降低，且改進(jìn)了cpu的利用率。改進(jìn)性能的另外一個(gè)方法是獲得更多的物理存儲(chǔ)器或使用更加快速的磁盤交換區(qū)。所以，只有措施（4）可以提高cpu的利用率。,10、假設(shè)一個(gè)電影院最多可以容納100人看電影，觀眾進(jìn)入和離開電影院時(shí)，都必須在影院門口的一個(gè)刷卡機(jī)上刷卡登記（進(jìn)入或離開都需要）。假設(shè)每次只允許一個(gè)人刷卡進(jìn)行登記，請(qǐng)使用p、v原語寫出觀眾進(jìn)程的同步算法。 解答： 設(shè)讀者有任意個(gè)，但可以并行看電影的只能是100人，設(shè)信號(hào)量S可以代表空座位數(shù)，其值為100； 另設(shè)信號(hào)量mutex，代表刷卡登記這一共享臨界資源，初始值為1。,.觀眾進(jìn)程如下： Process Ri Begin L: P(S); P(mutex); 刷卡登記進(jìn)入，并置某座位為占用狀態(tài)； V(mutex); 在座位上坐下看電影； P(mutex); 刷卡登記離開，并置某座位空空閑狀態(tài)； V(mutex); V(S)； Goto L End.,11、有一個(gè)程序要將128*128的數(shù)組A置為初值“0”，假定頁(yè)面大小128個(gè)字，數(shù)組A中的元素每一行放在一個(gè)頁(yè)中，假定系統(tǒng)分給此進(jìn)程的物理塊只有1塊（m=1），開始第一頁(yè)在內(nèi)存，若程序如下編制： Var a:array 1128,1128 of integer For j:=1 to 128 do For i:=1 to 128 do Ai,j:=0; 請(qǐng)問，系統(tǒng)會(huì)產(chǎn)生多少次缺頁(yè)中斷，請(qǐng)改寫次程序，讓其缺頁(yè)中斷大大減少。 解： （1） 從程序可以看出，該程序是按照列的順序來存放數(shù)據(jù)的。由于只給一個(gè)頁(yè)面，而且每一行要放在一個(gè)頁(yè)面中，所以每次放一個(gè)數(shù)據(jù)，就會(huì)導(dǎo)致其頁(yè)面不在內(nèi)存，引起缺頁(yè)中斷。 所以會(huì)產(chǎn)生128*128-1次缺頁(yè)中斷。,2既然要減少缺頁(yè)中斷次數(shù)，考慮到存放數(shù)據(jù)的特點(diǎn)，一行數(shù)據(jù)放在一個(gè)頁(yè)面里面，所以應(yīng)該按照行來存放數(shù)據(jù)。故程序應(yīng)該按照如下方式編寫： Var a:array 1128,1128 of integer For i:=1 to 128 do For j:=1 to 128 do Ai,j:=0; 總共產(chǎn)生128-1=127次缺頁(yè)中斷。,14、比較內(nèi)存分配機(jī)制和外存分配機(jī)制的異同。 答： （1）基本功能方面：內(nèi)存管理是內(nèi)存空間的分配、回收、內(nèi)存保護(hù)、對(duì)換、內(nèi)存擴(kuò)充等功能；外存分配基本功能是對(duì)外存空間的分配和回收。 （2）主要任務(wù)方面：內(nèi)存管理主要是為多道程序提供良好的運(yùn)行環(huán)境；外存主要是提供存儲(chǔ)空間； （3）分配方式：內(nèi)存分配主要是連續(xù)分配和離散分配；后者主要是離散方式分配； （4）分配算法：內(nèi)存分配主要是首次適應(yīng)、循環(huán)首次適應(yīng)等；或者使用段式、頁(yè)式等處理方法。外存分分配主要是利用文件分配表。 （5）分配單位不同。前者字節(jié)；后者是塊。,15、假定有如下四道作業(yè)，提交時(shí)間與運(yùn)行時(shí)間如下所示： 作業(yè)號(hào) 提交時(shí)間 運(yùn)行時(shí)間(小時(shí)) 1 8:00 2.0 2 8:50 0.5 3 9:00 0.1 4 9:50 0.2 假定采用單道程序設(shè)計(jì)技術(shù)，請(qǐng)給出系統(tǒng)分別采用FCFS，S