1、第1章 概述一、單項選擇題D、A、B、A、C、D、C、A、C、B二、填空題Windows、linux用戶態、內核態PSW中斷同步中斷系統調用I/O設備管理、文件系統實時性、可靠性第2章 進程管理一、單項選擇題D、D、C、D、B、A、B、D、C、CB、B、B、D、B、A、B、A二、填空題PCB運行、就像、阻塞4、5時間片用完進程管理、存儲管理PCB進程CPU寄存器的值、棧競爭狀態運行、就緒I/O繁忙SJFFCFS短進程、I/O繁忙進程三、簡答題1、運行狀態、阻塞狀態、就緒狀態 運行->阻塞：如進行I/O操作、進程間同步關系； 運行->就緒：時間片用完、被高優先級進程所打斷； 阻塞-&

2、gt;就緒：等待的I/O操作、信號量等事件發生； 就緒->運行：調度程序選中該進程運行； 2、 (1)進程是資源分配單位，擁有一個完整的資源平臺，而線程只獨享必不可少的資源，如寄存器和棧； (2)線程能減少并發執行的時間和空間開銷，包括創建時間、終止時間、切換時間； (3)線程之間可以共享同一個地址空間，可以進行不通過內核的通信，而進程不行； (4)線程 輕量級進程； (5)線程是CPU調度單位；3、 (1)當一個新的進程被創建時； (2)當一個進程運行完畢時； (3)當一個進程由于I/O、信號量或其他的某個原因被阻塞時； (4)當一個I/O中斷發生時，表明某個I/O操作已經完成，而等待

3、該I/O操作的進程轉入就緒狀態； (5)在分時系統中，當一個進程的時間片用完時；4、 RR算法的基本思路： (1)將所有的就緒進程按照FCFS原則，排成一個隊列； (2)每次調度時將處理器分派給隊首進程，讓其執行一小段CPU時間； (3)在一個時間片結束時，如果進程還沒有執行完的話，將發生時鐘中斷，在時鐘中斷中，進程調度程序將暫停當前進程的執行，并將其送到就緒隊列的末尾，然后執行當前的隊首進程； (4)如果進程在它的時間片用完之前就已結束或被阻塞，那么立即讓出CPU。 RR算法的主要缺點：時間片q的大小難以確定。5、(1)時間片用完，高優先級進程就緒(2)不會發生切換(3)PCB(4)不需要(

4、5)不能四、應用題1、(1)CPU空閑：100ms150ms(2)A無等待，B有等待，180ms200ms2、(1)Job1從投入到運行完成需要110ms，Job2從投入到運行完成需要90ms，Job3從投入到運行完成需要110ms：(2)CPU的利用率：(11030)/110 = 72.7%；(3)設備I1的利用率：(110-30)/110 = 72.7%，設備I2的利用率：(110-20)/110 = 81.8%。3、(1)這種機制不能實現資源的互斥訪問考慮如下的情形： (a)初始化的時候，flag數組的兩個元素值均為FALSE (b)線程0先執行，在執行while循環語句的時候，由于fl

5、ag1=FALSE，所以順利結束，不會被卡住。假設這個時候來了一個時鐘中斷，打斷它的運行； (c)線程1去執行，在執行while循環語句的時候，由于flag0=FALSE，所以順利結束，不會被卡住，然后就進入了臨界區； (d)后來當線程0再執行的時候，也進入了臨界區，這樣就同時有兩個線程在臨界區 (2)可能會出現死鎖考慮如下的情形： (a)初始化的時候，flag數組的兩個元素值均為FALSE (b)線程0先執行，flag0=TRUE，假設這個時候來了一個時鐘中斷，打斷它的運行； (c)線程1去執行，flag1=TRUE，在執行while循環語句的時候，由于flag0=TRUE,所以在這個地方被

6、卡住了，直到時間片用完； (d)線程0再執行的時候，由于flag1=TRUE，它也在while循環語句的地方被卡住了，這樣，這兩個線程都無法執行下去，從而死鎖。4、 (1)最后打印了3個字符'D' (2)最少可能打印了0個字符'A'，例如，P1連續執行了3次，然后P3連續執行了3次。P2一次也沒有執行。 (3)不可能，因為當打印出前面的“CABAB”的時候，信號量R的值等于1，此時，不可能連續打印兩個D。 (4)可能。相當于進程P2在打印完第二個A的時候被中斷了。5、(1)信號量的定義：int boys_waiting = 0, girls_waiting =

7、0, using = 0;Semaphore S_mutex = 1, S_boys = 0, S_girls = 0;(2) void boy_wants_to_use_bathroom() P(S_mutex); if(using = 0) && (girls_waiting = 0) using = 1; V(S_mutex); else boys_waiting +; V(S_mutex); P(S_boys); (3) void boy_leaves_bathroom() P(S_mutex); if(girls_waiting > 0) girls_waiti

8、ng -; V(S_girls); else if(boys_waiting > 0) boys_waiting -; V(S_boys); else using = 0; V(S_mutex);(4) void girl_wants_to_use_bathroom() P(S_mutex); if(using = 0) using = 1; V(S_mutex); else girls_waiting +; V(S_mutex); P(S_girls); (5) void girl_leaves_bathroom() P(S_mutex); if(girls_waiting >

9、0) girls_waiting -; V(S_girls); else if(boys_waiting > 0) boys_waiting -; V(S_boys); else using = 0; V(S_mutex);6、(1)FCFS算法： 周轉時間：P1：52，P2：68，P3：136，P4：164 平均周轉時間：105(2)SJF算法： 周轉時間：P1：96，P2：16，P3：164，P4：44 平均周轉時間：80(3)RR算法： 周轉時間：P1：136，P2：36，P3：164，P4：124 平均周轉時間：1157、(1)不可搶占的SJF算法： 執行順序：P1(0-14)P

10、4(14-18)P3(18-25)P5(25-32)P2(32-44) P1：14；P2：443=41；P3: 25-5=20; P4: 18-7=11; P5: 32-19=13 平均周轉時間：(14+41+20+11+13)/5=19.8(2)可搶占的SJF算法： 執行順序：P1、P3、P4、P3、P1、P5、P2 P1: 25-0 = 25; P2: 44-3=41; P3= 16-5=11; P4= 11-7=4; P5=32-19=13 平均周轉時間：(25+41+11+4+13)/5=18.8(3)時間片輪轉RR算法： 執行順序：P1、P2、P1、P3、P4、P2、P1、P3、P5

11、、P2、P1、P5 P1: 41 P2: 39-3=36 P3: 31-5=26; P4：20-7=13; P5=44-19=25 平均周轉時間：(41+36+26+13+25)/5=28.28、(1)不正確，可能導致死鎖 例如，開始時緩沖區為空，消費者先運行，通過了P(S_Mutex)，由于此時S_ProductNum為0，所以在P(S_ProductNum)處被阻塞，而生產者會在P(S_Mutex)處被阻塞，從而死鎖。 再比如：開始時緩沖區滿了，生產者先運行，通過了P(S_Mutex)，由于此時S_BufferNum為0，所以在P(S_BufferNum)處被阻塞，而消費者會在P(S_Mu

12、tex)處被阻塞，從而死鎖。(2)不正確，可能導致死鎖 例如，假設現在緩沖區已經滿了，然后生產者先運行，通過了P(S_Mutex)，在P(S_BufferNUM)處被阻塞，然后消費者執行，在P(S_Mutex)處被阻塞，從而死鎖。(3)正確 缺點是降低了并發性，應該在離開臨界區后立即釋放互斥信號量，這樣才能提高進程之間的并發性。第3章 死鎖一、選擇題D、B、C、D、C二、填空題競爭資源CPU、內存不對互斥條件、請求和保持條件環路2個死鎖避免剝奪資源、進程回退、撤消進程三、應用題1、令R1+R2+.+Rn n+k 0<=k<m由于C1+C2+.+Cn + R1+R2+.+Rn <

13、; n+m所以C1+C2+.+Cn < m - k所以剩余的資源個數A = m - (C1+C2+.+Cn) > k，即 A >= k+1而對于每一個進程Pi，Ri <= k+1，所以任何一個進程的資源請求都能夠滿足。2、 當N1、2、3時都不會發生死鎖的危險。 當N3時，在最壞情形下，每個進程都需要4臺磁帶機，且假定每個進程都已經得到了3個資源，那么此時系統中還剩下1個可用資源，可以把該資源分配給任何一個進程，當該進程得到資源后，可以運行完畢，并釋放所占用的所有4個資源，這樣，剩余的2個進程都可以順利地運行完畢。3、(1)系統處于安全狀態 1分當前剩余資源向量A =

14、(2, 1, 1)，調度順序為： P4、*、*、*或者 P3，*, * , *(2)不能，如果分配的話，系統將處于不安全的狀態。如果給它的話，那么當前剩余資源向量A = (0, 1, 1)，無法把它分配給任何一個線程。請求矩陣變為0 2 14 1 01 0 02 0 04、(1)該狀態是一個安全狀態 安全序列：P1、P4、P5、P2、P3(或者P1 P4 P2 P5 P3或P1 P4 P2 P3 P5);(2) 不能把資源分配給它，否則的話會進入不安全的狀態。5、請求矩陣:P13 4 7P2 1 3 4P3 0 0 6P4 2 2 1P5 1 1 0剩余向量(2 3 3)(1)是，P4(4 3

15、 7)P2,P3,P5P1；或者P5(5 4 7)然后任意順序 (2)不能，資源不夠(3)能，順序P4(4 3 7)P2,P3,P5P1 請求矩陣：P1 3 4 7P2 1 3 4P3 0 0 6P4 0 2 0P5 1 1 0剩余向量(0 3 2)(4)不能，找不到安全序列。6、證明：假設出現了死鎖，則必然存在一條環路，如下圖所示：Pm1 -> Rn1 -> Pm2 -> Rn2 -> Pm3 -> Rn3 -> . -> Pmk -> Rnk ->如題所述，存在如下的關系：Rn1 < Rn2 < Rn3 < . <

16、; Rn1矛盾，因此不可能出現這種環路，即不可能出現死鎖。第4章 存儲管理一、選擇題C、C、B、B、C、C、B、B、AA、D、A、C二、填空題寄存器、高速緩存內存、硬盤外碎片內存緊縮MMU邏輯地址、物理地址可變分區內存分區起始地址、段長可變分區固定分區邏輯頁面、物理頁面操作系統TLB2次對數組（結構體數組）局部性理論內存大小/頁面大小不是FIFO工作集內存大小/頁面大小三、簡答題1、 (1)會有外碎片的問題。 用戶給出的請求大小是不同的，在經過不斷的申請和釋放以后，有一些小的空閑 塊被夾在其他已分配的數據塊之間，無法被利用，成為外碎片。 (2)會有內碎片的問題。 由于用戶申請的空間必須是100

17、的整數倍，即使用戶只需要4個字節的內存空間， 也必須去申請100個字節的內存空間，因此剩下的96個字節就變成了內碎片。2、(1) 在編譯時確定。(2) 代碼段(3) 全局變量gvCh由于沒有設置初始值，所以放在bss段當中。 全局變量gvInt有初始值，所以放在data段當中。 數組array是main函數的局部變量，所以存放在棧當中。(4) 指針p存放在棧當中。*(p+1)所描述的內存單元位于堆空間3、 (1)局部性原理：指程序在執行過程中的一個較短時期，所執行的指令地址和指令的操作數地址，分別局限于一定區域。 (2)虛擬存儲技術、LRU頁面置換算法、CPU的cache、TLB、文件系統中的

18、緩沖區。4、 (1)這兩個寄存器的內容在進程切換的時候需要更新； (2)由操作系統來負責更新； (3)它們的內容平時存放在進程的PCB當中，在進程切換的時候裝入到寄存器當中5、 (1)頁表給出了邏輯頁面號和物理頁面號之間的映射關系。 (2)頁表存放在內存中，在OS內核的數據結構中。 (3)頁表的起始地址存放在進程控制塊PCB中。 (4)N張頁表。 (5)對。6、頁表的功能：邏輯頁面號轉換為物理頁面號 頁表項的格式：由CPU廠商設定 頁表項的內容：由OS填寫 駐留位的功能：該頁面是否在內存 一個進程有多少個頁表項：邏輯地址空間/頁面大小四、應用題1、(1)最先匹配法：無法滿足要求(1分)，在申請

19、96K存儲區時，選中的是4號分區；在申請20K時，選中1號分區；在申請200K時，現有的五個分區都無法滿足要求(2)下次匹配法：能夠滿足要求(1分)，在申請96K存儲區時，選中的是5號分區；在申請20K時，選中1號分區；在申請200K時，選中4號分區(3)最佳匹配法：能夠滿足要求，在申請96K存儲區時，選中的是5號分區；在申請20K時，選中1號分區；在申請200K時，選中4號分區(4)最壞匹配法：無法滿足要求(1分)，在申請96K存儲區時，選中的是4號分區；在申請20K時，選中的還是4號分區；在申請200K時，無法滿足要求2、（1）CPU必須訪問兩次內存才能獲得所需數據，因此實現一次頁面訪問的

20、存取時間是：1.5×23微秒；（2）在增加快表后，實現一次頁面訪問的平均存取時間為：0.85×1.5(10.85)×2×1.51.725微秒3、(1)0x0(2)0x20E (3)地址越界 4、邏輯地址物理地址邏輯地址物理地址0x204ABC0x46ABC0x23200D0x7400D0x1020410x100410x1103DBVirt. page too big!0x304F51Invalid segment!0x0103500x163505、(1) 1位、2位、3位(2.a) 34333(2.b) 寫入物理地址67345時出錯，寫保護(2.c) 段

21、錯誤，段號18不合法(2.d) 29806(2.e) 缺頁中斷，物理地址030976、邏輯頁面號：0、0、1、1、0、3、1、2、2、4、4、3(1) OPT: 5次 (2) FIFO: 6次 (3) LRU: 7次(4) Clock: 6次7、 (1)FIFO優于LRU： 3個頁面：1 2 3 1 4 2 3 (4 : 6) 2個頁面：1 2 1 3 2 (3 : 4) (2)FIFO等于LRU: 3個頁面：1 2 3 4 5 6 (6 : 6) 2個頁面：1 2 3 4 1 2 (6 : 6) (3)LRU優于FIFO： 3個頁面：1 2 3 1 4 1 (4 : 5) 2個頁面：1 2

22、1 3 1 (3 : 4)8、每個進程有3個頁面，其中1個存放程序，2個存放數據。數組A有10000個整數，每頁存放200個，數組占用50頁，順序為：A00, A01, A099,A10,A199 1A20, A21, A299,A30,A399 2 A980, , A9899, A990, A9999 50對于程序A：按行訪問矩陣，訪問的頁面號為：1, 2, , 50，因此缺頁50次；對于程序B：按列訪問矩陣，訪問的頁面號為：1, 1, 2, 2, , 50, 50, 1, 1, 2, 2, , 因此缺頁次數為：100×505000次。9、(1)略(2)379(0x17B)、缺頁中

23、斷10、(1)頁面大小為4K，每個頁表項大小為4個字節，因此在每個頁表當中，總共有1024個頁表項，對于每個層次的頁表來說，都滿足這一點，這樣每級頁表的索引均為10位，由于頁面大小為4K，所以頁內偏移地址為12位。邏輯地址被劃分為五個部分：-| 22位 | 10位 | 10位 | 10位 | 12位 |- 空閑 一級索引 二級索引 三級索引 頁內偏移可訪問的虛擬地址空間大小為 242 = 4T (2分)(2) 假定一個頁面的大小為2Y，即頁內偏移地址為Y位，每個頁表可以包含2Y / 8 = 2 (Y-3)個頁表項，因此每級頁表的索引位為Y-3位，總共有4級頁表，所以4(Y-3) + Y <

24、;= 64 Y <= 15.2 因此 Y=15所以最大的頁面大小為32KB。-| 1位 | 12位 | 12位 | 12位 | 12位 | 15位 |- 空閑 一級索引 二級索引 三級索引 三級索引 頁內偏移11、-訪問請求 P1-A P1-B P2-C P2-F P2-E P1-A P2-D P2-E P2-D P1-A P1-B 缺頁次數- A A A F F F D D D D D 全局LRU * B B B E E E E E E B 8次 * * C C C A A A A A A- A A A A A A A A A A A 局部FIFO * B B B B B B B B

25、B B 8次 * * C F E E D E D D D-12、(1) 17CAH：頁面大小1KB，故邏輯頁面號為5。(2)采用FIFO算法，淘汰第0頁，其頁框號為7，因此物理地址為1FCAH(3) 先循環一圈，將所有訪問位都置為0，然后回到2號頁框，將其置換，因此物理地址為0BCAH。第5章 I/O管理一、選擇題A、D、D、A、C、D、D、B、B、BA、A、C、A二、填空題磁盤、鍵盤設備控制器設備獨立性I/O獨立編址、內存映像編址、混合編址程序循環檢測方式、中斷驅動方式、DMA方式不是設備驅動程序Spooling不正確柱面定位、旋轉延遲15.9ms、991.7ms三、簡答題1、 (1)控制寄

26、存器、狀態寄存器、數據寄存器 (2)I/O獨立編址； (3)內存映像編址； (4)混合編址；2、 (1) 是 (2) 控制寄存器、狀態寄存器、數據寄存器 (3) 設備驅動程序 (4) I/O獨立編址、內存映像編址或混合編址3、(1)CPU對DMA控制器進行編程，告訴它應把什么數據傳送到內存的什么地方。并向磁盤控制器發出命令，讓它去磁盤驅動器中讀入所需的數據塊，保存到內部緩沖區中，并驗證數據的正確性； (2)DMA控制器通過總線向磁盤控制器發出一個讀操作的信號，并把將寫入的內存地址打在總線上；(3)磁盤控制器取出一個字節，按該地址寫入內存；(4)磁盤控制器向DMA發一個確認信號，DMA把內存地址

27、加1，把字節計數器減1。若計數器的值大于0轉第2步；(5)DMA控制器向CPU發出一個中斷，告訴它數據傳輸已完成。4、 (1)一般可以分為4層：中斷處理程序、設備驅動程序、設備獨立的 系統軟件、用戶空間的I/O軟件； (2)其中，中斷處理程序和設備驅動程序是與硬件設備有關的； (3)設備獨立的系統軟件和用戶空間的I/O軟件是與硬件設備無關的；5、硬件廠商。 處于系統態（管態） 信號量和PV操作來同步 OS設計人員 OS設計人員6、 (1)扇區 (2)實現過程： (a)讀入包含該字節的扇區； (b)修改該字節； (c)把整個扇區寫回到磁盤；四、應用題1、根據題意：10個盤面，每個盤面有100個磁

28、道，每個磁道有16個扇區，因此總的扇區數為：10×100×1616000每個扇區用一個位來描述，共需要：16000/82000字節。2、磁盤訪問時間柱面定位旋轉延遲數據傳輸；讀一個數據塊的時間為：13×610025203ms讀取一個100塊的文件需要時間：203×10020300ms3、(1) 先來先服務(First-Come First-Served, FCFS) 執行順序：(40)20、44、40、4、80、12、76移動距離：292柱面定位時間：876毫秒(2) 最短定位時間優先(Shortest Seek Time First, SSTF) 執行

29、順序：(40)40、44、20、12、4、76、80移動距離：120柱面定位時間：360毫秒(3) 電梯算法（elevator algorithm），也叫掃描算法（SCAN） 執行順序：(40)40、20、12、4、44、76、80移動距離：112柱面定位時間：336毫秒4、(1)FCFS執行順序：(10,0,10)->(22,1,20)->(20,5,100)->(8,5,50)->(40,10,50)-> (6,11,120)->(36,8,100)移動距離： 20->10->22->20->8->40->6->

30、36 = 10+12+2+12+32+34+30 = 132(2)SSTF: 執行順序：(20,5,100)->(22,1,20)->(10,0,10)->(8,5,50)->(6,11,120)-> (36,8,100)->(40,10,50)移動距離： 20->20->22->10->8->6->36->40 = 0+2+12+2+2+30+4 = 52(3)SCAN: 執行順序：(20,5,100)->(10,0,10)->(8,5,50)->(6,11,120)->(22,1,20)-

31、> (36,8,100)->(40,10,50)移動距離：20->20->10->8->6->22->36->40 = 0+10+2+2+16+14+4 = 485、(1)15.9ms (2)2975.1ms(3)86.4GB(4)柱面定位、設備驅動程序6、采用位圖法來管理磁盤空閑空間，每個磁盤塊的狀態用0和1表示：2KB = 2*1024*8bit = 16384bit根據CSCAN算法，被訪問的磁道號順序為100 -> 120 -> 30 -> 50 -> 90尋道時間：（20+90+20+40）*1ms = 1

32、70ms每分鐘6000轉，轉一圈時間10ms，通過一個扇區時間0.1ms，隨機訪問4個扇區，總時間170 + (0.5*10+0.1)*4 = 190.4ms第6章 文件系統一、選擇題A、D、B、A、D、A、A、C、C、BA、A、C二、填空題文件控制塊FCB文件文件名+FCB塊不對目錄項順序結構可變分區打開方式、讀寫指針位圖法、鏈表法、索引法三、簡答題1、 (1)普通的子目錄以文件的形式存放。 根目錄單獨存放在磁盤的固定區域。 (2)目錄的屬性信息存放在目錄文件的FCB中 (3)直接法：目錄項文件名+FCB。 間接法：目錄項文件名FCB的起始地址。2、 (1)鏈表結構：把文件的各個邏輯塊依次存放在若干個（可以）不連續的物理塊當中，各塊之間通過指針連接，前一個物理塊指向下一個物理塊。 (2)只能進行順序訪問，不能進行隨機訪問。為了訪問一個文件的第n個邏輯塊，必須從文件的第一個物理塊開始，按照指針所指向的地址，順序地訪問前n個塊，即為了得到第n個邏輯塊的物理塊地址，必須先訪問n-1次的磁盤，速度非常慢； (3)每個物理塊上的數據存儲空間不再是2的整數次冪（指針占用了若干個字節），從而使文件的訪問不太方便。3、 (1)移動操作的速度更快； (2)拷貝操作需要把文件的每個數據塊都復制一份，而且還要創建一個新的目錄