操作系統(tǒng)習(xí)題+答案

1、第一章1. 操作系統(tǒng)的主要作用是（D ）A 管理設(shè)備 B 提供操作命令 C 管理文件 D 為用戶提供使用計算機的接口，管理計算機的資源2. 對外部輸入的信息能在規(guī)定時限內(nèi)處理完畢并作出迅速反應(yīng)的操作系統(tǒng)稱為（C ）A 分時操作系統(tǒng)B 批處理操作系統(tǒng)C 實時操作系統(tǒng)D 多處理機操作系統(tǒng)3. 操作系統(tǒng)的基本特征是 并發(fā)性 、 共享性 、 虛擬性 、 異步性 。4. 什么是操作系統(tǒng)？操作系統(tǒng)是一組控制和管理計算機硬件和軟件資源，合理的對各類作業(yè)進(jìn)行調(diào)度，以及方便用戶使用的程序集合。第二章1 . 蘋果桔子問題 桌上有一只盤子，每次只能存放一個水果。一家四口人各行其職，爸爸專向盤子中放蘋果(apple)

2、，媽媽專向盤子中放桔子(orange)，兒子專等吃盤子中的桔子，女兒專等吃盤子里的蘋果。請用PV操作來實現(xiàn)四人之間的同步算法。答：記錄型信號量解決蘋果桔子問題，plate:semaphore； /* 盤子是否為空*/orange:semaphore; /* 盤子里有桔子 */apple:semaphore; /* 盤子里有蘋果 */plate := 1; orange:= 0; /* 盤子里沒有桔子 */apple:= 0; /* 盤子里沒有蘋果*/parbegin process father begin L1:P(plate);放蘋果；V(apple);goto L1; end; proc

3、ess mother begin L2:P(plate);放桔子；V(orange);goto L2;end;process son begin L3:P(orange);取桔子；V(plate);吃桔子；goto L3; end;process daughter begin L4:P(apple);取蘋果；V(plate);吃蘋果；goto L4; end;parend2. 和尚取水問題寺廟里有老小和尚若干和一水缸，小和尚打水，老和尚飲水。水缸容積為10桶水，水取自同一水井，每次只容一個桶打水，桶的總數(shù)為3個，每次往水缸倒水和從水缸取水僅為一桶。答：Var mutex1, mutex2, e

4、mpty, full, count: semaphore;mutex1:=1; 代表可以用水井mutex2:=1;代表可以用水缸empty:=10; 水缸的容量full:=0; 水缸中的水量count:=3;水桶的個數(shù)process 小和尚: beginrepeatwait(empty);wait(count);wait(mutex1);從井中打水；signal(mutex1);wait(mutex2);送水入水缸；signal(mutex2);signal(count);signal(full);until false; endprocess 老和尚: begi

5、nrepeatwait(full);wait(count);wait(mutex2);從缸中取水；signal(mutex2);signal(empty);signal(count);until false; end3. 有一座東西方向的獨木橋，用P,V操作實現(xiàn)：（1）每次只允許一個人過橋；（2）當(dāng)獨木橋上有行人時，同方向的行人可以連續(xù)過橋，相反方向的人必須等待。（3）當(dāng)某一方向無人過橋時，另一方向的行人可以過橋。答：（1）設(shè)信號量 MUTEX=1 P (MUTEX)   過橋 V (MUTEX)

6、0;(2)設(shè)信號量： MUTEX=1 (東西方互斥)       MD=1    (東向西使用計數(shù)變量互斥)    MX=1    (西向東使用計數(shù)變量互斥)設(shè)整型變量： CD=0  (東向西的已上橋人數(shù))         CX=0  (西向東的已上

7、橋人數(shù))  從東向西： P (MD) IF (CD=0) P (MUTEX)   CD=CD+1 V (MD) 過橋 P (MD) CD=CD-1 IF (CD=0) V (MUTEX)   V (MD) 從西向東： P (MX) IF (CX=0) P (MUTEX) 

8、;  CX=CX+1 V (MX) 過橋 P (MX) CX=CX-1 IF (CX=0) V (MUTEX)   V (MX)  (3) ：從東向西的，和（2）相同；從西向東的和（1）相同。 4. 上圖描述的生產(chǎn)者消費者問題中，如果其緩沖區(qū)部分為n個長度相等的有界緩沖區(qū)組成，且每次傳輸數(shù)據(jù)長度等于有界緩沖區(qū)長度以及生產(chǎn)者和消費者可對緩沖區(qū)同時操作。試重新描述生產(chǎn)過程和消費過程。答：設(shè)第i塊緩沖區(qū)

9、的公用信號量為bufi，初值為1； 生產(chǎn)者進(jìn)程的私用信號量為produce，初值為n； 消費者進(jìn)程的私用信號量為consume，初值為0。 生產(chǎn)過程和消費過程描述如下： 生產(chǎn)過程： Begin  P(produce)  選擇一個空緩沖區(qū)i  P(bufi)  送數(shù)據(jù)入緩沖區(qū)i  V(consume)  V(bufi) End 消費過程： Begin  P(consume)

10、60; 選擇一個滿緩沖區(qū)i  P(bufi)  取緩沖區(qū)i中的數(shù)據(jù)  V(produce)  V(bufi)  End 5. 若信號量的初值為2，當(dāng)前值為-3，則表示有（ ）等待進(jìn)程。 A 1個 B 2個 C 3個 D 5個6. 在操作系統(tǒng)中，（B ）是競爭和分配計算機系統(tǒng)資源的基本單位。 A 程序 B 進(jìn)程 C 作業(yè) D 用戶7. 下面哪一個不會引起進(jìn)程創(chuàng)建（C ） A 用戶登錄 B 作業(yè)調(diào)度 C 設(shè)備分配 D 應(yīng)用請求8. 進(jìn)程和程序的本質(zhì)區(qū)別是（B ） A 內(nèi)存和外存

11、B 動態(tài)和靜態(tài)特征 C共享和獨占使用計算機資源 D順序和非順序執(zhí)行機器指令 9. 在多進(jìn)程的系統(tǒng)中，為了保證公共變量的完整性，各進(jìn)程應(yīng)互斥進(jìn)入臨界區(qū)。所謂臨界區(qū)是（B ） A 一個緩沖區(qū) B 一個數(shù)據(jù)區(qū) C 一種同步機構(gòu) D 一段程序10. 在一輛公共汽車上，司機和售票員各行其職，司機負(fù)責(zé)開車和到站停車，售票員負(fù)責(zé)售票和開、關(guān)門，當(dāng)售票員關(guān)好車門后，駕駛員才能繼續(xù)開車行駛。用P、V操作實現(xiàn)司機與售票員之間的同步。答：    問題分析：    是一個進(jìn)程同步互斥問題，兩個主要點是   &

12、#160;1） 司機開車的時候，售票員不能開門，（這里體現(xiàn)的是進(jìn)程的互斥問題）車停之后，由司機通知售票員開門（這里體現(xiàn)的是進(jìn)程的同步問題）；  2）車門開著的時候，司機不能開車，等售票員把車門關(guān)上之后，由售票員通知司機開車。同步信號量：    driver：司機私有信號量，初為1；conductor：售票員私有信號量，初值為0;    初值的含義是售票員具有優(yōu)先車門控制權(quán)。        semaphore 

13、;   sem_driver=0,    sem_conductor=1;    void    driver()                     while    (true) &

14、#160;                        p(sem_driver);                   start_bus();  

15、;                                  normal_driving();              

16、;                     station_stop();                          &#

17、160;         v(sem_conductor)         void    conductor()                    while &#

18、160;  (true)                                             p(sem_conduct

19、or);                                    open_door();           &#

20、160;                         shut_door();                       &

21、#160;            sell_ticket();                                   

22、; v(sem_driver)                            void    main()        parbegin   

23、0;(driver,    conductor);       第三章1. 在一個有N個進(jìn)程的單處理機系統(tǒng)中，有可能出現(xiàn)N個進(jìn)程都被阻塞的情況。 （ ）2. 系統(tǒng)處于不安全狀態(tài)必然導(dǎo)致系統(tǒng)死鎖。 （ × ）3. 當(dāng)一進(jìn)程運行時，系統(tǒng)可基于某種原則，強行將其撇下，把處理機分配給其他進(jìn)程，這種調(diào)度方式是（B ）A非剝奪方式 B剝奪方式 C中斷方式 D查詢方式4. 在為多道程序所提供的可共享的系統(tǒng)資源不足時可能出現(xiàn)死鎖。但是，不適當(dāng)?shù)模– ）也可能產(chǎn)生死鎖。A進(jìn)程優(yōu)先權(quán) B資源的線

24、性分配 C進(jìn)程推進(jìn)順序 D分配隊列優(yōu)先權(quán)5. 發(fā)生死鎖的必要條件有四個，要防止死鎖的發(fā)生，可以破壞這四個必要條件，但破壞（A ）條件是不太實際的。A互斥 B不可搶占 C部分分配 D循環(huán)等待6. 在分時操作系統(tǒng)中，進(jìn)程調(diào)度經(jīng)常采用（C ）算法。A先來先服務(wù) B最高優(yōu)先權(quán) C時間片輪轉(zhuǎn) D隨機7. （B ）優(yōu)先權(quán)是在創(chuàng)建進(jìn)程時確定的，確定之后在整個進(jìn)程運行期間不再改變。A先來先服務(wù) B靜態(tài) C動態(tài) D短作業(yè)8. 某系統(tǒng)中有3個并發(fā)進(jìn)程，都需要同類資源4個，試問該系統(tǒng)不會發(fā)生死鎖的最少資源數(shù)是（B ）選臨界值，即發(fā)生死鎖時刻，m個進(jìn)程，每個進(jìn)程需要n臺機器，（n-1,n-1,n-1n-1）先給m個進(jìn)

25、程依次分配 n-1臺機器，之后這m臺機器都去搶奪最后一臺機器，進(jìn)入死鎖狀態(tài)，則總得機器資源數(shù)目為：(n-1)*m+1  上面m=3, n=4代入得 10 A9 B10 C11 D129. 在下列解決死鎖的方法中，屬于死鎖預(yù)防策略的是：（B ）A銀行家算法 B資源有序分配法 C死鎖檢測法 D資源分配圖化簡法10. 資源的按序分配策略可以破壞（D ）條件。這樣的話，所有進(jìn)程資源的請求必須嚴(yán)格按照資源序號遞增的次序提出，在所形成的資源分配圖中不可能再出現(xiàn)環(huán)路，因而破壞了循環(huán)等待條件。A互斥使用資源 B占有且等待資源 C非搶占資源 D循環(huán)等待資源11. 進(jìn)程的調(diào)度方式有兩種，一種是

26、 剝奪方式 ，另一種是 非剝奪方式 在 先來先服務(wù) 調(diào)度算法中，按照進(jìn)程進(jìn)入就緒隊列的先后次序來分配處理機。12. 死鎖產(chǎn)生的必要條件有四個，即 互斥條件、請求和保持條件、不可剝奪條件、環(huán)路等待條件 。13. 銀行家算法中，當(dāng)一個進(jìn)程提出的資源請求將導(dǎo)致系統(tǒng)從 安全狀態(tài) 進(jìn)入 不安全狀態(tài)時，系統(tǒng)就拒絕它的資源請求。 14. 對待死鎖，一般應(yīng)考慮死鎖的預(yù)防、避免、檢測和解除四個問題。典型的銀行家算法是屬于 避免死鎖 ，破壞環(huán)路等待條件是屬于 預(yù)防死鎖 ，而剝奪資源是 解除死鎖 的基本方法。15. 為什么說多級反饋隊列能較好的滿足各類用戶的需要？答：(1) 所有類型的作業(yè)都會在很短的時間

27、內(nèi)啟動，用戶會獲得響應(yīng)； (2) 終端型用戶作業(yè)、短批處理作業(yè)用戶，能在較短的時間內(nèi)完成； (3) 系統(tǒng)吞吐率高； (4) 長批處理作業(yè)，能夠最終得到處理。16. 為什么說采用有序資源分配法不會產(chǎn)生死鎖？答：為了便于說明，不妨設(shè)系統(tǒng)中有m類資源，n個進(jìn)程，分別用R1，R2，Rm（1，2，m可看作資源編號）和P1，P2， Pn表示。根據(jù)有序資源分配法可知，進(jìn)程申請資源時必須按照資源編號的升序進(jìn)行，即任何進(jìn)程在占有了Ri類資源后，再申請的資源Rj的編號j一定大于i。因此在任一時刻，系統(tǒng)中至少存在一個進(jìn)程Pk，它占有了較高編號的資

28、源Rh，且它繼續(xù)請求的資源必然是空閑的，因而Pk可以一直向前推進(jìn)直至完成，當(dāng)Pk運行完成后即會釋放它占有的所有資源；在Pk完成之后，剩下的進(jìn)程集合中同樣會存在一個進(jìn)程，它占有了較高編號的資源，且它繼續(xù)請求的資源必然是空閑的，因而它可以一直向前推進(jìn)直至完成；以此類推，所有進(jìn)程均可運行完成，故不會發(fā)生死鎖。 17. 某分時系統(tǒng)中的進(jìn)程可能出現(xiàn)如下圖所示的狀態(tài)變化，回答下列問題：（1）根據(jù)圖示，該系統(tǒng)采用的是什么進(jìn)程調(diào)度策略？（2）指出圖示中的每一個狀態(tài)變化的原因。18. 在銀行家算法中，若出現(xiàn)下述資源分配情況，試問：ProcessAllocationNeedAvailableP00032

29、00121622P110001750P213542356P303320652P400140656(1) 該狀態(tài)是否安全？(2) 若進(jìn)程P2提出請求Request（1，2，2，2）后，系統(tǒng)能否將資源分配給他？答：(1) 該狀態(tài)是安全的，這時可以找到一個安全序列：P0、P3、P4、P1、P2 設(shè)置兩個向量工作向量work，它表示系統(tǒng)可提供給進(jìn)程繼續(xù)運行所需的各類資源數(shù)目，在執(zhí)行算法開始時，work：= Available，finish，它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使其運行完成。 所以對上述分配資源情況進(jìn)行分析如下： ProcessAllo

30、cationNeed   work  work+Allocation finish P00032001216221654true  P30332065216541986true  P4001406561986199(10)true  P110001750199(10)299(10)true  P213542356299(10)3(12)(14)(14)true  (2) 若進(jìn)程P2提出上述請求，系統(tǒng)不能將資源分配給它，因為分配之后系統(tǒng)將

31、進(jìn)入不安全狀態(tài)。 P2請求資源：P2發(fā)出請求向量Request2（1，2，2，2），系統(tǒng)按銀行家算法進(jìn)行檢查： Request2（1，2，2，2）Need2（2，3，5，6）； Request2（1，2，2，2）Available（1，6，2，2）； 系統(tǒng)暫時先假定可為P2分配資源，并修改P2的有關(guān)數(shù)據(jù)，如下表：Process AllocationNeedAvailableP0003200120400P110001750P225761134P303320652P400140656再進(jìn)行安全性檢查：可用資源Available（0，4，0，0）已不能滿足任何

32、進(jìn)程的需要。系統(tǒng)進(jìn)入不安全狀態(tài)，此時系統(tǒng)不分配資源。19. 個進(jìn)程共享某種資源R，該資源共有個可分配單位，每個進(jìn)程一次一個的申請或釋放資源單位。假設(shè)每個進(jìn)程對該資源的最大需求量均小于，且各進(jìn)程最大需求量之和小于，試證明在這個系統(tǒng)中不可能發(fā)生死鎖。答：設(shè)max（i）表示第i個進(jìn)程的最大資源需求量，need（i）表示第i個進(jìn)程還需要的資源量，alloc（i）表示第i個進(jìn)程已分配的資源量。由題中所給條件可知： max（1）max（n）=（need（1）need（n）（alloc（1）+alloc（n）<mn 如果在這個系統(tǒng)中發(fā)生了死鎖，那么一方面m個資源應(yīng)該全部分配出去，即

33、 alloc（1）alloc（n）= m 另一方面所有進(jìn)程將陷入無限等待狀態(tài)。 由上述兩式可得： need（1）need（n）<n 上式表示死鎖發(fā)生后，n個進(jìn)程還需要的資源量之和小于n，這意味著此刻至少存在一個進(jìn)程i，need（i）=0，即它已獲得了所需要的全部資源。既然該進(jìn)程已獲得了它所需要的全部資源，那么它就能執(zhí)行完成并釋放它占有的資源，這與前面的假設(shè)矛盾，從而證明在這個系統(tǒng)中不可能發(fā)生死鎖。20. 有一個內(nèi)存中只能裝入兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法。有如下

34、表所示的作業(yè)序列，表中所列的優(yōu)先數(shù)是指進(jìn)程調(diào)度的優(yōu)先數(shù)，且優(yōu)先數(shù)越小優(yōu)先級越高。（1）列出所有作業(yè)進(jìn)入內(nèi)存的時刻以及結(jié)束的時刻。（2）計算作業(yè)的平均周轉(zhuǎn)時間。答：分析 v 10:00，A進(jìn)入內(nèi)存，并開始執(zhí)行； v 10:20，B進(jìn)入內(nèi)存，搶占A，B開始執(zhí)行； v 10:50，B完成，調(diào)D進(jìn)內(nèi)存，A再次執(zhí)行； v  11:10，A完成，調(diào)C進(jìn)內(nèi)存，C開始執(zhí)行；   12:00，C完成，D開始執(zhí)行；   12:20，D完成。 兩道批處理作業(yè)，作業(yè)調(diào)度采用最短作業(yè)優(yōu)先，進(jìn)

35、程調(diào)度采用基于優(yōu)先級的搶占式調(diào)度同時允許兩個程序存在于主存中 進(jìn)入內(nèi)存運行時間段周轉(zhuǎn)時間A10:0010：00-10：2010：50-11：1070B10:2010：20-10:5030C11:1011:10-12:0090D10:5012:00-12:2090  平均周轉(zhuǎn)時間： (70+30+90+90)/4=70 帶權(quán)平均周轉(zhuǎn)時間： (70/40+30/30+90/50+90/20)/4=2.26 第四章1. 采用（B ）不會產(chǎn)生內(nèi)部碎片A、 分頁式 B、分段式 C、固定分區(qū)式 D、段頁式2. 在可變式分區(qū)分配方案中，某

36、一作業(yè)完成后，系統(tǒng)收回其主存空間，并于相鄰空閑區(qū)合并，為此需修改空閑區(qū)表，造成空閑區(qū)表數(shù)減1的情況是（D ）A 無上鄰空閑區(qū)，也無下鄰空閑區(qū)；B 有上鄰空閑區(qū)，但無下鄰空閑區(qū)；C 有下鄰空閑區(qū)，但無上鄰空閑區(qū)；D 有上鄰空閑區(qū)，也有下鄰空閑區(qū)；3. 段頁式存儲管理中，地址映像表是（C ）A 每個作業(yè)或進(jìn)程的一張段表，兩張頁表B 每個作業(yè)或進(jìn)程的每個段一張段表，一張頁表C 每個作業(yè)或進(jìn)程一張段表，每個段一張頁表D 每個作業(yè)或進(jìn)程的一張頁表，每個段一張段表4. 在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小為4096字節(jié)，現(xiàn)有一邏輯地址為2F6AH，且第0，1，2頁依次存放在物理塊5，10

37、，11中，問相應(yīng)的物理地址為多少？答：第一種解法：第2種解法4096B=212B16位尋址一共216B分頁存儲.共分的頁：216/212=24=16 共分16頁.第0頁的地址范圍 0 - FFFH第1頁的地址范圍 1000H - 1FFFH第2頁得地址范圍 2000H - 2FFFH.第11頁 B000H - BFFFH第15頁 F000H - FFFFH2F6AH=10 1111 0110 1010 在2頁的范圍對應(yīng)物理塊11所以物理地址為：2F6AH - 2000H + B000H = F6AH + B000H= BF6AH5. 設(shè)有一頁式存儲管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁

38、，每頁2048字節(jié)，內(nèi)存總共有8個存儲塊，試問邏輯地址至少應(yīng)為多少位？內(nèi)存空間有多大？答：每頁2048字節(jié)，所以頁內(nèi)位移部分地址需要占據(jù)11個二進(jìn)制位； 邏輯地址空間最大為16頁，所以頁號部分地址需要占據(jù)4個二進(jìn)制位。 故邏輯地址至少應(yīng)為15位。 由于內(nèi)存共有8個存儲塊，在頁式存儲管理系統(tǒng)中，存儲塊大小與頁面的大小相等，因此內(nèi)存空間為16K(2048×8/1024=16K）6. 已知某分頁系統(tǒng)，主存容量為64KB，頁面大小為1KB。對于一個4頁大的作業(yè)，其0、1、2、3頁分別被分配到主存的2、4、6、7塊中。（1）將十進(jìn)制的邏輯地址1023、2500、3

39、500、4500轉(zhuǎn)換成物理地址；（2）以十進(jìn)制的邏輯地址1023為例畫出地址變換過程圖。答：（1）對于上述邏輯地址，可先計算出它們的頁號和頁內(nèi)地址（邏輯地址除以頁面大小得到的商為頁號，余數(shù)為頁內(nèi)地址），然后通過頁表轉(zhuǎn)換成對應(yīng)的物理地址： 邏輯地址1023。1023/1K，得到頁號為0，頁內(nèi)地址為1023，查頁表找到對應(yīng)的物理塊號為2。故物理地址為2*1K+1023=3071。 邏輯地址2500。2500/1K，得到頁號為2，頁內(nèi)地址為452，查頁表找到對應(yīng)的物理塊號為6。故物理地址為6*1K+452=6596。 邏輯地址3500。3500/1K，得到頁號為3，頁內(nèi)

40、地址為428，查頁表找到對應(yīng)的物理塊號為7。故物理地址為7*1K+428=7596。 邏輯地址4500。4500/1K，得到頁號為4，頁內(nèi)地址為404，因頁號大于頁表長度，故產(chǎn)生越界中斷。 (2)邏輯地址1023的地址變換過程如下圖所示，其中的頁表項中沒考慮每頁的訪問 權(quán)限。7. 對于下表所示的段表，請將邏輯地址（0，137），（1，4000），（5，230）轉(zhuǎn)換成物理地址。 答：(1)段號0小于段表長5，故段號合法；由段表的第0項可獲得段的內(nèi)存始址為 50K，段長為10K；由于段內(nèi)地址137，小于段長10K，故段內(nèi)地址也是合法的，因此可得&#

41、160;出對應(yīng)的物理地址為50K+137=5l337。 (2)段號l小于段表長，故段號合法；由段表的第l項可獲得段的內(nèi)存始址為60K，段長為3K：經(jīng)檢查，段內(nèi)地址4000超過段長3K，因此產(chǎn)生越界中斷(3)段號5等于段表長，故段號不合法，產(chǎn)生越界中斷。第五章1. 在一個采用頁式虛擬存儲管理的系統(tǒng)中，某進(jìn)程依次要訪問的字地址序列是：115，228，120，88，446，102，321，432，260，167，若作業(yè)的第0頁已經(jīng)裝入內(nèi)存，現(xiàn)分配給該作業(yè)的主存共300字，頁的大小為100字，則： （1）按FIFO算法將產(chǎn)生 5 次缺頁中斷，依次淘汰頁號為 0，1，2 （2）按LRU算法將產(chǎn)

42、生 6 次缺頁中斷，依次淘汰頁號為 2，0，1，3 2. 有一矩陣“int a100100”以行為先進(jìn)行存儲。有一個虛擬存儲系統(tǒng)，物理內(nèi)存共有3頁，其中1頁用來存放程序，其余2頁用于存放數(shù)據(jù)。假設(shè)程序已在內(nèi)存中占1頁，其余2頁空閑。 程序A：for (i=0; i<=99; i+) for (j=0; j<=99; j+) aij=0; 程序B：for (j=0; j<=99; j+) for (i=0; i<=99; i+) aij=0; 若每頁可存放200個整數(shù)，程序A和程序B的執(zhí)行過程各會發(fā)生多少次缺頁？若每頁只能存放100個整數(shù)呢？答：程序A由于是外層是行索引，

43、內(nèi)層是列索引，因此在執(zhí)行2次外層循環(huán)（也就是200次內(nèi)層循環(huán)）后才會產(chǎn)生一次缺頁，那么100次外層循環(huán)也就是50次缺頁。而程序B和A恰恰相反，外層是列索引，內(nèi)層是行索引，這意味著每執(zhí)行兩次內(nèi)層循環(huán)就得進(jìn)行一次缺頁置換，那么總共要執(zhí)行100*100次內(nèi)層循環(huán)，因此需要5000次缺頁置換。3. （8分）請求分頁管理系統(tǒng)中，假設(shè)某進(jìn)程的頁表內(nèi)容如下表所示。 頁面大小為4KB，一次內(nèi)存的訪問時間是100ns，一次快表（TLB）的訪問時間是10ns，處理一次缺頁的平均時間為108ns（已含更新TLB和頁表的時間），進(jìn)程的駐留集大小固定為2，采用最近最少使用置換算法（LRU）和局部淘汰策略。假設(shè)

44、TLB初始為空；地址轉(zhuǎn)換時先訪問TLB，若TLB未命中，再訪問頁表（忽略訪問頁表之后的TLB更新時間）；有效位為0表示頁面不在內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷處理后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H，請問：  （1） 依次訪問上述三個虛地址，各需多少時間？（2） 基于上述訪問序列，虛地址1565H的 物理地址是多少？請說明理由。答：（1）根據(jù)頁式管理的工作原理，應(yīng)先考慮頁面大小，以便將頁號和頁內(nèi)位移分解出來。頁面大小為4KB，即212，則得到頁內(nèi)位移占虛地址的低12位，頁號占剩余高位。可得三個

45、虛地址的頁號P如下（十六進(jìn)制的一位數(shù)字轉(zhuǎn)換成4位二進(jìn)制，因此，十六進(jìn)制的低三位正好為頁內(nèi)位移，最高位為頁號）： 2362H：P=2，訪問快表10ns，因初始為空，訪問頁表100ns得到頁框號，合成物理地址后訪問主存100ns，共計10ns+100ns+100ns=210ns。 1565H：P=1，訪問快表10ns，落空，訪問頁表100ns落空，進(jìn)行缺頁中斷處理108ns，訪問快表10ns，合成物理地址后訪問主存100ns，共計10ns+100ns+108ns+10ns+100ns=100 000 220ns。 25A5H：P=2，訪問快表，因第

46、一次訪問已將該頁號放入快表，因此花費10ns便可合成物理地址，訪問主存100ns，共計10ns+100ns=110ns。 （2）當(dāng)訪問虛地址1565H時，產(chǎn)生缺頁中斷，合法駐留集為2，必須從頁表中淘汰一個頁面，根據(jù)題目的置換算法，應(yīng)淘汰0號頁面，因此1565H的對應(yīng)頁框號為101H。由此可得1565H的物理地址為101565H。4.設(shè)某計算機的邏輯地址空間和物理地址空間均為64KB，按字節(jié)編址。某進(jìn)程最多需要6頁數(shù)據(jù)存儲空間，頁的大小為1KB，操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配4個頁框。當(dāng)該進(jìn)程執(zhí)行到時刻260時，要訪問邏輯地址為17CAH的數(shù)據(jù)。請回答下列問題：(1)該邏

47、輯地址對應(yīng)的頁號是多少？(2)若采用先進(jìn)先出置換算法，該邏輯地址對應(yīng)的物理地址？要求給出計算過程。(3)采用時鐘置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。（設(shè)搜索下一頁的指針按順時針方向移動，且指向當(dāng)前2號頁框，示意圖如下）答：5. 在一個請求分頁系統(tǒng)中，假如一個作業(yè)的頁面走向為4，3，2，1，4，3，5，4，3，2，1，5，目前它還沒有任何頁裝入內(nèi)存，當(dāng)分配給該作業(yè)的物理塊數(shù)目分別為3和4時，請分別計算采用OPT、LRU和 FIFO頁面淘汰算法時，訪問過程中所發(fā)生的缺頁次數(shù)和缺頁率，并比較所得結(jié)果。第六章1. 通道是一種特殊的（ C ），具有（ A ）能力。主機的CPU與通

48、道可以并行工作，并通過（ C ）實現(xiàn)彼此之間的通信和同步。A I/O設(shè)備 B設(shè)備控制器 C處理機 D I/O控制器A執(zhí)行I/O指令集 B執(zhí)行CPU指令集 C傳輸I/O命令 D運行I/O進(jìn)程A I/O指令 B I/O中斷 C I/O指令和I/O中斷 D操作員2. 磁盤屬于（ C ），其信息的存取是以（ D ）為單位的；磁盤的I/O控制主要采取（ C ）方式A字符設(shè)備 B獨占設(shè)備 C塊設(shè)備 D虛擬設(shè)備A位 B字節(jié) C幀 D固定長數(shù)據(jù)塊A程序I/O方式 B程序中斷 C DMA D SPOOLing3. 假定把磁盤上一個數(shù)據(jù)塊中的信息輸入到一單緩沖區(qū)的時間T為100us，將緩沖區(qū)中的數(shù)據(jù)傳送到用戶區(qū)的

49、時間M為50us，而CPU對這一塊數(shù)據(jù)進(jìn)行計算的時間C為50us，這樣，系統(tǒng)對每一塊數(shù)據(jù)的處理時間為（C ），如果將單緩沖改為雙緩沖，則系統(tǒng)對每一塊數(shù)據(jù)的處理時間為（ B ） A 50us B 100us C 150us D 200us E 250us4. 下列關(guān)于驅(qū)動程序的論述正確的是（D ） A驅(qū)動程序與I/O設(shè)備的特性緊密相關(guān)，因此應(yīng)為每一個I/O設(shè)備配備一個專門的驅(qū)動程序 B驅(qū)動程序與I/O控制方式緊密相關(guān)，因此對DMA方式應(yīng)該以字節(jié)為單位去啟動設(shè)備進(jìn)行中斷處理 C由于驅(qū)動程序與I/O設(shè)備緊密相關(guān)，故必須用匯編語言書寫 D對于一臺多用戶機，配置了相同的8個終端，此時可只配置一個由多個終

50、端共享的驅(qū)動程序5. 下列磁盤調(diào)度算法中，平均尋道時間較短，但容易產(chǎn)生饑餓現(xiàn)象的是（ ），電梯調(diào)度算法是指（ ），能避免磁臂粘著現(xiàn)象的算法是（ ）SSTFFCFSSCANCSCANFSCAN6. I/O軟件通常被組織成 用戶層、與設(shè)備無關(guān)軟件層、設(shè)備驅(qū)動程序、中斷處理程序 四個層次。7. SPOOLing系統(tǒng)是由磁盤中的 輸入井_和_ 輸出井 ，內(nèi)存中的_ 輸入緩沖區(qū) 和_ 輸出緩沖區(qū) 以及_ 輸入進(jìn)程 和_輸出進(jìn)程 構(gòu)成的。8. 磁盤的訪問時間由_ 尋道時間 、 旋轉(zhuǎn)延遲時間_和 數(shù)據(jù)傳輸時間 三部分組成，其中所占比重比較大的是 尋道時間_，故磁盤調(diào)度的目標(biāo)為 使磁盤的平均尋道時間最短 _。

51、9. 為什么引入設(shè)備獨立性？如何實現(xiàn)設(shè)備獨立性？答：引入設(shè)備獨立性，可使應(yīng)用程序獨立于具體的物理設(shè)備，是設(shè)備分配具有靈活性。另外容易實現(xiàn)I/O重定向。 為了實現(xiàn)設(shè)備獨立性，必須在設(shè)備驅(qū)動程序之上設(shè)置一層設(shè)備獨立性軟件，用來執(zhí)行所有I/O設(shè)備的公用操作，并向用戶層軟件提供統(tǒng)一接口。關(guān)鍵是系統(tǒng)中必須設(shè)置一張邏輯設(shè)備表LUT用來進(jìn)行邏輯設(shè)備到物理設(shè)備的映射，其中每個表目中包含了邏輯設(shè)備名、物理設(shè)備名和設(shè)備驅(qū)動程序入口地址三項；當(dāng)應(yīng)用程序用邏輯設(shè)備名請求分配I/O設(shè)備時，系統(tǒng)必須為它分配相應(yīng)的物理設(shè)備，并在LUT中建立一個表目，以后進(jìn)程利用該邏輯設(shè)備名請求I/O操作時，便可從LUT中得到物理

52、設(shè)備名和驅(qū)動程序入口地址。 10. 假設(shè)計算機系統(tǒng)采用CSCAN（循環(huán)掃描）磁盤調(diào)試策略。設(shè)某單面磁盤旋轉(zhuǎn)速度為每分鐘6000轉(zhuǎn)，每個磁道有100個扇區(qū)，相臨磁道間的平均移動時間為1ms。若在某時刻，磁頭位于100號磁道處，并沿著磁道號增大的方向移動（如下圖所示），磁道號請求隊列為50，90，30，120，對請求隊列中的每個磁道需讀取1個隨機分布的扇區(qū)，則讀完這個扇區(qū)點共需要多少時間？要求給出計算過程。 答：每分鐘6000轉(zhuǎn)，轉(zhuǎn)一圈的時間為0.01s，通過一個扇區(qū)的時間為0.0001s。 根據(jù)CSCAN算法，被訪問的磁道號順序為100 ，120 ，

53、60;30， 50 ， 90,因此，尋道用去的總時間為：（20 + 90 + 20 + 40）* 1ms = 170ms 總共要隨機讀取四個扇區(qū)，用去的時間為：（0.01*0.5 + 0.0001）*4 = 0.0204s = 20.4ms 所以，讀完這個扇區(qū)點共需要 170ms + 20.4ms = 190.4ms。 11. 當(dāng)前磁盤讀

54、寫位于柱面號20，此時有多個磁盤請求，以下列柱面號順序送至磁盤驅(qū)動器：10、22、20、2、40、6、38。尋道（Track）時，移動一個柱面需6ms，按下列算法計算所需尋道時間（柱面移動順序及所需時間，總尋道時間；忽略到達(dá)指定柱面后所需尋道時間）。(上海交通大學(xué)1999年試題) 先來先服務(wù)。 下一個最鄰近柱面。 電梯算法（當(dāng)前狀態(tài)為向上）?！窘獯稹?).先來先服務(wù) 在這種順序下面，尋道的次序為20，10，22，20，2，40，6，38 總的尋道時間為：（10+12+2+18+38+34+32）×6876ms 2).下一個最鄰近 在這種順序下面

55、，尋道的次序為20，22，38，40，10，6，2 總的尋道時間為：（12+4+2+30+4+4）×6336ms 3).電梯算法（當(dāng)前狀態(tài)向上） 在這種順序下面，尋道的次序為20，22，38，40，10，6，2 總的尋道時間為：（12+4+2+30+4+4）×6648ms   12. 假定磁盤轉(zhuǎn)速為20ms/圈，磁盤格式化時每個磁道被劃分成10個扇區(qū)，今有10個邏輯記錄（每個記錄的大小剛好與扇區(qū)大小相同）存放在同一磁道上，處理程序每次從磁盤讀出一個記錄后要花4ms進(jìn)行處理，現(xiàn)在要求順序處理這10個記錄，若

56、磁頭現(xiàn)在正處于首個邏輯記錄的始點位置。問：按逆時針方向安排10個邏輯記錄（磁盤順時針方向轉(zhuǎn)），處理程序處理完這10個記錄所花費的時間是多少？答：分析：數(shù)據(jù)處理的時間=磁盤訪問時間+數(shù)據(jù)實際處理的時間，而磁盤訪問時間=尋道時間+旋轉(zhuǎn)延遲+數(shù)據(jù)傳輸時間。本題通過對旋轉(zhuǎn)延遲時間的優(yōu)化來提高訪問磁盤數(shù)據(jù)的速度。 由題意知，20ms/圈，可知：讀取一條記錄需要2ms ，讀出記錄后還需要4ms時間進(jìn)行處理，故當(dāng)磁頭處于記錄的始點時，處理它共需6ms。當(dāng)R1處理完時，磁頭已經(jīng)轉(zhuǎn)到了R4的位置，此時要將其調(diào)整到R2的位置，需要經(jīng)過R4，R5，R6，R7，R8，R9，R10，R1，這樣要耗1

57、6ms的時間，再加上讀取R2需要2ms以及處理數(shù)據(jù)的4ms，R2的總處理時間應(yīng)為22ms。所以2+4+(16+2+4)*9=204ms。 第七章1. 在某個文件系統(tǒng)中，每個盤塊為512字節(jié)，文件控制塊占64個字節(jié)，其中文件名占8個字節(jié)。如果索引結(jié)點編號占2個字節(jié)，對一個存放在磁盤上的256個目錄項的目錄，試比較引入索引結(jié)點前后，為找到其中一個文件的FCB，平均啟動磁盤的次數(shù)。答：在引入索引結(jié)點前，每個目錄項中存放的是對應(yīng)文件的FCB，故128個目錄項的目錄總共需要占用128X64256=32個盤塊。因此，在該目錄中檢索到一個文件，平均啟動磁盤的次數(shù)為(1+32)/2=16.5次。 引

58、入索引結(jié)點后，每個目錄項中只需存放文件名和索引結(jié)點的編號，因此256個目錄項的目錄總共需要占用256X(8+2)512=5個盤塊。因此，找到匹配的目錄項平均需要啟動(1+5)2，即3次磁盤；而得到索引結(jié)點編號后，還需啟動磁盤將對應(yīng)文件的索引結(jié)點讀入內(nèi)存，故平均需要啟動磁盤4次。可見，引入索引結(jié)點后，可大大減少啟動磁盤的次數(shù)，從而有效地提高檢索文件的速度。第八章1. 請分別解釋在連續(xù)分配方式、隱式鏈接分配方式、顯式鏈接分配方式和索引分配方式中如何將文件的字節(jié)偏移量3500轉(zhuǎn)換為物理塊號和塊內(nèi)位移量（設(shè)盤塊大小為1KB，盤塊號需占4個字節(jié)）答：(1) 連續(xù)分配方式：字節(jié)偏移量3500轉(zhuǎn)換

59、成邏輯塊號和塊內(nèi)位移量為3500/1024=3428 可從相應(yīng)文件的FCB中得到分配給該文件的起始物理盤塊號，假設(shè)為a0，字節(jié)偏移量3500相應(yīng)的物理塊號為a0+3，塊內(nèi)位移量為428。 (2) 隱式鏈接分配方式：由于每個盤塊中需要留出4個字節(jié)來存放分配給文件的下一個盤塊的塊號，因此字節(jié)偏移量3500的邏輯塊號為3500/1020=3440 從相應(yīng)文件的FCB中可獲得分配給該文件的首個（即第0個）盤塊的塊號，如b0，然后可通過讀第b0塊獲得分配給文件的第1個盤塊的塊號，如b1；在從b1塊中得到第2塊的塊號，如b2；從b2塊中得到第3塊的塊號，如b3。因此

60、可得到字節(jié)偏移量3500對應(yīng)的物理塊號b3，而塊內(nèi)偏移量為440。 (3) 顯式鏈接分配方式：字節(jié)偏移量3500轉(zhuǎn)換成邏輯塊號和塊內(nèi)位移量為3500/1024=3428 可從相應(yīng)文件的FCB中得到分配給該文件的首個物理盤塊的塊號，如c0，然后從FAT表的第c0項中得到分配給文件的第一個盤塊的塊號，如c1；再在FAT表的第c1項中得到分配給文件的第2個盤塊的塊號c2；在FAT表的第c2項中得到分配給文件的第3個盤塊的塊號c3。如此，即可獲得字節(jié)偏移量3500對應(yīng)的物理塊號c3，而塊內(nèi)偏移量為428。 (4) 索引分配方式：字節(jié)偏移量3500轉(zhuǎn)換成

61、邏輯塊號和塊內(nèi)位移量為3500/1024=3428 從文件的FCB中得到索引表的地址（盤塊號），從索引表的第3項（距離索引表首字節(jié)12字節(jié)的位置）可獲得字節(jié)偏移量3500對應(yīng)的物理塊號，而塊內(nèi)偏移量為428。2. 在Unix system V中，如果一個盤塊的大小為1KB，每個塊號占4個字節(jié)，那么，一個進(jìn)程要訪問偏移量為263168字節(jié)處的數(shù)據(jù)時，需要經(jīng)過幾次間接？答： UNIX/Linux文件系統(tǒng)中，一個盤塊的大小為1KB，每個盤塊號占4個字節(jié)，即每塊可放256個地址。直接尋址為10塊，一次間接尋址為256塊，二次間接尋址為2562塊，三次間接尋址為2563塊。 

62、;首先將邏輯文件的字節(jié)偏移量轉(zhuǎn)換為文件的邏輯塊號和塊內(nèi)偏移。方法是：將邏輯文件的字節(jié)偏移量/盤塊大小，商為文件的邏輯塊號，余數(shù)是塊內(nèi)偏移；再將文件的邏輯塊號轉(zhuǎn)換為物理塊號，使用多重索引結(jié)構(gòu)，在索引節(jié)點中根據(jù)邏輯塊號通過直接索引或間接索引找到對應(yīng)物理塊號。 偏移為263168字節(jié)的邏輯塊號是：263168/1024=257。塊內(nèi)偏移量=263168-257×1024=0。由于10<257<256+10，故263168字節(jié)在一次間接尋址內(nèi)。 3.假定盤塊的大小為1KB，每個盤塊占4個字節(jié)，文件索引節(jié)點中的磁盤地址明細(xì)表如下圖所示，字節(jié)偏移量為9000，14000和3

63、50000的物理地址為？答：首先將邏輯文件的字節(jié)偏移量轉(zhuǎn)換為邏輯塊號和塊內(nèi)偏移量,就是將字節(jié)偏移量/盤塊大小，商為邏輯塊號，余數(shù)是塊內(nèi)偏移量。在FCB中，第0-9個地址為直接地址，第10個為一次間接地址，第11個地址為二次間接地址，第12個地址為三次間接地址。再將文件的邏輯塊號轉(zhuǎn)換為物理塊號。使用多重索引結(jié)構(gòu)，在索引節(jié)點中根據(jù)邏輯塊號 通過直接索引或間接索引找到對應(yīng)的物理塊號。（1）9000/1024=8 余808，則邏輯塊號為8，直接索引第8個地址得到物理塊號，塊內(nèi)偏移地址為808。（2）14000/1024=13余688，則邏輯塊號為10<13<10+256，通過一次間接索引在第10個地址可得到物理塊號，塊內(nèi)偏移地址為688。（3）350000/1024=341 余816，則邏輯塊號為10+256<341，通過二次間接索引在第11個地址可得到一次間址，再由此得到二次間址，再找到物理塊號，其塊內(nèi)偏移地址816。4. 假定一個索引節(jié)點為128字節(jié)，指針為