第1章 概述一、單項(xiàng)選擇題D、A、B、A、C、D、C、A、C、B二、填空題Windows、linux用戶態(tài)、內(nèi)核態(tài)PSW中斷同步中斷系統(tǒng)調(diào)用I/O設(shè)備管理、文件系統(tǒng)實(shí)時(shí)性、可靠性第2章 進(jìn)程管理一、單項(xiàng)選擇題D、D、C、D、B、A、B、D、C、CB、B、B、D、B、A、B、A二、填空題PCB運(yùn)行、就像、阻塞4、5時(shí)間片用完進(jìn)程管理、存儲管理PCB進(jìn)程CPU寄存器的值、棧競爭狀態(tài)運(yùn)行、就緒I/O繁忙SJFFCFS短進(jìn)程、I/O繁忙進(jìn)程三、簡答題1、運(yùn)行狀態(tài)、阻塞狀態(tài)、就緒狀態(tài) 運(yùn)行-阻塞：如進(jìn)行I/O操作、進(jìn)程間同步關(guān)系； 運(yùn)行-就緒：時(shí)間片用完、被高優(yōu)先級進(jìn)程所打斷； 阻塞-就緒：等待的I/O操作、信號量等事件發(fā)生； 就緒-運(yùn)行：調(diào)度程序選中該進(jìn)程運(yùn)行； 2、 (1)進(jìn)程是資源分配單位，擁有一個(gè)完整的資源平臺，而線程只獨(dú)享必不可少的資源，如寄存器和棧； (2)線程能減少并發(fā)執(zhí)行的時(shí)間和空間開銷，包括創(chuàng)建時(shí)間、終止時(shí)間、切換時(shí)間； (3)線程之間可以共享同一個(gè)地址空間，可以進(jìn)行不通過內(nèi)核的通信，而進(jìn)程不行； (4)線程 輕量級進(jìn)程； (5)線程是CPU調(diào)度單位；3、 (1)當(dāng)一個(gè)新的進(jìn)程被創(chuàng)建時(shí)； (2)當(dāng)一個(gè)進(jìn)程運(yùn)行完畢時(shí)； (3)當(dāng)一個(gè)進(jìn)程由于I/O、信號量或其他的某個(gè)原因被阻塞時(shí)； (4)當(dāng)一個(gè)I/O中斷發(fā)生時(shí)，表明某個(gè)I/O操作已經(jīng)完成，而等待該I/O操作的進(jìn)程轉(zhuǎn)入就緒狀態(tài)； (5)在分時(shí)系統(tǒng)中，當(dāng)一個(gè)進(jìn)程的時(shí)間片用完時(shí)；4、 RR算法的基本思路： (1)將所有的就緒進(jìn)程按照FCFS原則，排成一個(gè)隊(duì)列； (2)每次調(diào)度時(shí)將處理器分派給隊(duì)首進(jìn)程，讓其執(zhí)行一小段CPU時(shí)間； (3)在一個(gè)時(shí)間片結(jié)束時(shí)，如果進(jìn)程還沒有執(zhí)行完的話，將發(fā)生時(shí)鐘中斷，在時(shí)鐘中斷中，進(jìn)程調(diào)度程序?qū)和．?dāng)前進(jìn)程的執(zhí)行，并將其送到就緒隊(duì)列的末尾，然后執(zhí)行當(dāng)前的隊(duì)首進(jìn)程； (4)如果進(jìn)程在它的時(shí)間片用完之前就已結(jié)束或被阻塞，那么立即讓出CPU。 RR算法的主要缺點(diǎn)：時(shí)間片q的大小難以確定。5、(1)時(shí)間片用完，高優(yōu)先級進(jìn)程就緒(2)不會發(fā)生切換(3)PCB(4)不需要(5)不能四、應(yīng)用題1、(1)CPU空閑：100ms150ms(2)A無等待，B有等待，180ms200ms2、(1)Job1從投入到運(yùn)行完成需要110ms，Job2從投入到運(yùn)行完成需要90ms，Job3從投入到運(yùn)行完成需要110ms：(2)CPU的利用率：(11030)/110 = 72.7%；(3)設(shè)備I1的利用率：(110-30)/110 = 72.7%，設(shè)備I2的利用率：(110-20)/110 = 81.8%。3、(1)這種機(jī)制不能實(shí)現(xiàn)資源的互斥訪問考慮如下的情形： (a)初始化的時(shí)候，flag數(shù)組的兩個(gè)元素值均為FALSE (b)線程0先執(zhí)行，在執(zhí)行while循環(huán)語句的時(shí)候，由于flag1=FALSE，所以順利結(jié)束，不會被卡住。假設(shè)這個(gè)時(shí)候來了一個(gè)時(shí)鐘中斷，打斷它的運(yùn)行； (c)線程1去執(zhí)行，在執(zhí)行while循環(huán)語句的時(shí)候，由于flag0=FALSE，所以順利結(jié)束，不會被卡住，然后就進(jìn)入了臨界區(qū)； (d)后來當(dāng)線程0再執(zhí)行的時(shí)候，也進(jìn)入了臨界區(qū)，這樣就同時(shí)有兩個(gè)線程在臨界區(qū) (2)可能會出現(xiàn)死鎖考慮如下的情形： (a)初始化的時(shí)候，flag數(shù)組的兩個(gè)元素值均為FALSE (b)線程0先執(zhí)行，flag0=TRUE，假設(shè)這個(gè)時(shí)候來了一個(gè)時(shí)鐘中斷，打斷它的運(yùn)行； (c)線程1去執(zhí)行，flag1=TRUE，在執(zhí)行while循環(huán)語句的時(shí)候，由于flag0=TRUE,所以在這個(gè)地方被卡住了，直到時(shí)間片用完； (d)線程0再執(zhí)行的時(shí)候，由于flag1=TRUE，它也在while循環(huán)語句的地方被卡住了，這樣，這兩個(gè)線程都無法執(zhí)行下去，從而死鎖。4、 (1)最后打印了3個(gè)字符D (2)最少可能打印了0個(gè)字符A，例如，P1連續(xù)執(zhí)行了3次，然后P3連續(xù)執(zhí)行了3次。P2一次也沒有執(zhí)行。 (3)不可能，因?yàn)楫?dāng)打印出前面的“CABAB”的時(shí)候，信號量R的值等于1，此時(shí)，不可能連續(xù)打印兩個(gè)D。 (4)可能。相當(dāng)于進(jìn)程P2在打印完第二個(gè)A的時(shí)候被中斷了。5、(1)信號量的定義：int boys_waiting = 0, girls_waiting = 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_waiting -; 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 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算法： 周轉(zhuǎn)時(shí)間：P1：52，P2：68，P3：136，P4：164 平均周轉(zhuǎn)時(shí)間：105(2)SJF算法： 周轉(zhuǎn)時(shí)間：P1：96，P2：16，P3：164，P4：44 平均周轉(zhuǎn)時(shí)間：80(3)RR算法： 周轉(zhuǎn)時(shí)間：P1：136，P2：36，P3：164，P4：124 平均周轉(zhuǎn)時(shí)間：1157、(1)不可搶占的SJF算法： 執(zhí)行順序：P1(0-14)P4(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 平均周轉(zhuǎn)時(shí)間：(14+41+20+11+13)/5=19.8(2)可搶占的SJF算法： 執(zhí)行順序：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 平均周轉(zhuǎn)時(shí)間：(25+41+11+4+13)/5=18.8(3)時(shí)間片輪轉(zhuǎn)RR算法： 執(zhí)行順序：P1、P2、P1、P3、P4、P2、P1、P3、P5、P2、P1、P5 P1: 41 P2: 39-3=36 P3: 31-5=26; P4：20-7=13; P5=44-19=25 平均周轉(zhuǎn)時(shí)間：(41+36+26+13+25)/5=28.28、(1)不正確，可能導(dǎo)致死鎖 例如，開始時(shí)緩沖區(qū)為空，消費(fèi)者先運(yùn)行，通過了P(S_Mutex)，由于此時(shí)S_ProductNum為0，所以在P(S_ProductNum)處被阻塞，而生產(chǎn)者會在P(S_Mutex)處被阻塞，從而死鎖。 再比如：開始時(shí)緩沖區(qū)滿了，生產(chǎn)者先運(yùn)行，通過了P(S_Mutex)，由于此時(shí)S_BufferNum為0，所以在P(S_BufferNum)處被阻塞，而消費(fèi)者會在P(S_Mutex)處被阻塞，從而死鎖。(2)不正確，可能導(dǎo)致死鎖 例如，假設(shè)現(xiàn)在緩沖區(qū)已經(jīng)滿了，然后生產(chǎn)者先運(yùn)行，通過了P(S_Mutex)，在P(S_BufferNUM)處被阻塞，然后消費(fèi)者執(zhí)行，在P(S_Mutex)處被阻塞，從而死鎖。(3)正確 缺點(diǎn)是降低了并發(fā)性，應(yīng)該在離開臨界區(qū)后立即釋放互斥信號量，這樣才能提高進(jìn)程之間的并發(fā)性。第3章 死鎖一、選擇題D、B、C、D、C二、填空題競爭資源CPU、內(nèi)存不對互斥條件、請求和保持條件環(huán)路2個(gè)死鎖避免剝奪資源、進(jìn)程回退、撤消進(jìn)程三、應(yīng)用題1、令R1+R2+.+Rn n+k 0=km由于C1+C2+.+Cn + R1+R2+.+Rn n+m所以C1+C2+.+Cn k，即 A = k+1而對于每一個(gè)進(jìn)程Pi，Ri Rn1 - Pm2 - Rn2 - Pm3 - Rn3 - . - Pmk - Rnk -如題所述，存在如下的關(guān)系：Rn1 Rn2 Rn3 . Rn1矛盾，因此不可能出現(xiàn)這種環(huán)路，即不可能出現(xiàn)死鎖。第4章 存儲管理一、選擇題C、C、B、B、C、C、B、B、AA、D、A、C二、填空題寄存器、高速緩存內(nèi)存、硬盤外碎片內(nèi)存緊縮MMU邏輯地址、物理地址可變分區(qū)內(nèi)存分區(qū)起始地址、段長可變分區(qū)固定分區(qū)邏輯頁面、物理頁面操作系統(tǒng)TLB2次對數(shù)組（結(jié)構(gòu)體數(shù)組）局部性理論內(nèi)存大小/頁面大小不是FIFO工作集內(nèi)存大小/頁面大小三、簡答題1、 (1)會有外碎片的問題。 用戶給出的請求大小是不同的，在經(jīng)過不斷的申請和釋放以后，有一些小的空閑 塊被夾在其他已分配的數(shù)據(jù)塊之間，無法被利用，成為外碎片。 (2)會有內(nèi)碎片的問題。 由于用戶申請的空間必須是100的整數(shù)倍，即使用戶只需要4個(gè)字節(jié)的內(nèi)存空間， 也必須去申請100個(gè)字節(jié)的內(nèi)存空間，因此剩下的96個(gè)字節(jié)就變成了內(nèi)碎片。2、(1) 在編譯時(shí)確定。(2) 代碼段(3) 全局變量gvCh由于沒有設(shè)置初始值，所以放在bss段當(dāng)中。 全局變量gvInt有初始值，所以放在data段當(dāng)中。 數(shù)組array是main函數(shù)的局部變量，所以存放在棧當(dāng)中。(4) 指針p存放在棧當(dāng)中。*(p+1)所描述的內(nèi)存單元位于堆空間3、 (1)局部性原理：指程序在執(zhí)行過程中的一個(gè)較短時(shí)期，所執(zhí)行的指令地址和指令的操作數(shù)地址，分別局限于一定區(qū)域。 (2)虛擬存儲技術(shù)、LRU頁面置換算法、CPU的cache、TLB、文件系統(tǒng)中的緩沖區(qū)。4、 (1)這兩個(gè)寄存器的內(nèi)容在進(jìn)程切換的時(shí)候需要更新； (2)由操作系統(tǒng)來負(fù)責(zé)更新； (3)它們的內(nèi)容平時(shí)存放在進(jìn)程的PCB當(dāng)中，在進(jìn)程切換的時(shí)候裝入到寄存器當(dāng)中5、 (1)頁表給出了邏輯頁面號和物理頁面號之間的映射關(guān)系。 (2)頁表存放在內(nèi)存中，在OS內(nèi)核的數(shù)據(jù)結(jié)構(gòu)中。 (3)頁表的起始地址存放在進(jìn)程控制塊PCB中。 (4)N張頁表。 (5)對。6、頁表的功能：邏輯頁面號轉(zhuǎn)換為物理頁面號 頁表項(xiàng)的格式：由CPU廠商設(shè)定 頁表項(xiàng)的內(nèi)容：由OS填寫 駐留位的功能：該頁面是否在內(nèi)存 一個(gè)進(jìn)程有多少個(gè)頁表項(xiàng)：邏輯地址空間/頁面大小四、應(yīng)用題1、(1)最先匹配法：無法滿足要求(1分)，在申請96K存儲區(qū)時(shí)，選中的是4號分區(qū)；在申請20K時(shí)，選中1號分區(qū)；在申請200K時(shí)，現(xiàn)有的五個(gè)分區(qū)都無法滿足要求(2)下次匹配法：能夠滿足要求(1分)，在申請96K存儲區(qū)時(shí)，選中的是5號分區(qū)；在申請20K時(shí)，選中1號分區(qū)；在申請200K時(shí)，選中4號分區(qū)(3)最佳匹配法：能夠滿足要求，在申請96K存儲區(qū)時(shí)，選中的是5號分區(qū)；在申請20K時(shí)，選中1號分區(qū)；在申請200K時(shí)，選中4號分區(qū)(4)最壞匹配法：無法滿足要求(1分)，在申請96K存儲區(qū)時(shí)，選中的是4號分區(qū)；在申請20K時(shí)，選中的還是4號分區(qū)；在申請200K時(shí)，無法滿足要求2、（1）CPU必須訪問兩次內(nèi)存才能獲得所需數(shù)據(jù)，因此實(shí)現(xiàn)一次頁面訪問的存取時(shí)間是：1.523微秒；（2）在增加快表后，實(shí)現(xiàn)一次頁面訪問的平均存取時(shí)間為：0.851.5(10.85)21.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時(shí)出錯(cuò)，寫保護(hù)(2.c) 段錯(cuò)誤，段號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優(yōu)于LRU： 3個(gè)頁面：1 2 3 1 4 2 3 (4 : 6) 2個(gè)頁面：1 2 1 3 2 (3 : 4) (2)FIFO等于LRU: 3個(gè)頁面：1 2 3 4 5 6 (6 : 6) 2個(gè)頁面：1 2 3 4 1 2 (6 : 6) (3)LRU優(yōu)于FIFO： 3個(gè)頁面：1 2 3 1 4 1 (4 : 5) 2個(gè)頁面：1 2 1 3 1 (3 : 4)8、每個(gè)進(jìn)程有3個(gè)頁面，其中1個(gè)存放程序，2個(gè)存放數(shù)據(jù)。數(shù)組A有10000個(gè)整數(shù)，每頁存放200個(gè)，數(shù)組占用50頁，順序?yàn)椋篈00, 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, , 因此缺頁次數(shù)為：100505000次。9、(1)略(2)379(0x17B)、缺頁中斷10、(1)頁面大小為4K，每個(gè)頁表項(xiàng)大小為4個(gè)字節(jié)，因此在每個(gè)頁表當(dāng)中，總共有1024個(gè)頁表項(xiàng)，對于每個(gè)層次的頁表來說，都滿足這一點(diǎn)，這樣每級頁表的索引均為10位，由于頁面大小為4K，所以頁內(nèi)偏移地址為12位。邏輯地址被劃分為五個(gè)部分：-| 22位 | 10位 | 10位 | 10位 | 12位 |- 空閑 一級索引 二級索引 三級索引 頁內(nèi)偏移可訪問的虛擬地址空間大小為 242 = 4T (2分)(2) 假定一個(gè)頁面的大小為2Y，即頁內(nèi)偏移地址為Y位，每個(gè)頁表可以包含2Y / 8 = 2 (Y-3)個(gè)頁表項(xiàng)，因此每級頁表的索引位為Y-3位，總共有4級頁表，所以4(Y-3) + Y = 64 Y (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-36 = 10+12+2+12+32+34+30 = 132(2)SSTF: 執(zhí)行順序：(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: 執(zhí)行順序：(20,5,100)-(10,0,10)-(8,5,50)-(6,11,120)-(22,1,20)- (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)柱面定位、設(shè)備驅(qū)動程序6、采用位圖法來管理磁盤空閑空間，每個(gè)磁盤塊的狀態(tài)用0和1表示：2KB = 2*1024*8bit = 16384bit根據(jù)CSCAN算法，被訪問的磁道號順序?yàn)?00 - 120 - 30 - 50 - 90尋道時(shí)間：（20+90+20+40）*1ms = 170ms每分鐘6000轉(zhuǎn)，轉(zhuǎn)一圈時(shí)間10ms，通過一個(gè)扇區(qū)時(shí)間0.1ms，隨機(jī)訪問4個(gè)扇區(qū)，總時(shí)間170 + (0.5*10+0.1)*4 = 190.4ms第6章 文件系統(tǒng)一、選擇題A、D、B、A、D、A、A、C、C、BA、A、C二、填空題文件控制塊FCB文件文件名+FCB塊不對目錄項(xiàng)順序結(jié)構(gòu)可變分區(qū)打開方式、讀寫指針位圖法、鏈表法、索引法三、簡答題1、 (1)普通的子目錄以文件的形式存放。 根目錄單獨(dú)存放在磁盤的固定區(qū)域。 (2)目錄的屬性信息存放在目錄文件的FCB中 (3)直接法：目錄項(xiàng)文件名+FCB。 間接法：目錄項(xiàng)文件名FCB的起始地址。2、 (1)鏈表結(jié)構(gòu)：把文件的各個(gè)邏輯塊依次存放在若干個(gè)（可以）不連續(xù)的物理塊當(dāng)中，各塊之間通過指針連接，前一個(gè)物理塊指向下一個(gè)物理塊。 (2)只能進(jìn)行順序訪問，不能進(jìn)行隨機(jī)訪問。為了訪問一個(gè)文件的第n個(gè)邏輯塊，必須從文件的第一個(gè)物理塊開始，按照指針?biāo)赶虻牡刂罚樞虻卦L問前n個(gè)塊，即為了得到第n個(gè)邏輯塊的物理塊地址，必須先訪問n-1次的磁盤，速度非常慢； (3)每個(gè)物理塊上的數(shù)據(jù)存儲空間不再是2的整數(shù)次冪（指針占用了若干個(gè)字節(jié)），從而使文件的訪問不太方便。3、 (1)移動操作的速度更快； (2)拷貝操作需要把文件的每個(gè)數(shù)據(jù)塊都復(fù)制一份，而且還要?jiǎng)?chuàng)建一個(gè)新的目錄項(xiàng)， 用來指向這些數(shù)據(jù)塊，所以時(shí)間比較長； 而移動操作不需要拷貝數(shù)據(jù)塊，只需要?jiǎng)?chuàng)建一個(gè)新的目錄項(xiàng)，并且刪除舊的目錄 項(xiàng)即可，所以速度很快；4、 (1)文件系統(tǒng)首先就把根目錄讀進(jìn)來； (2)在根目錄中查找temp這個(gè)子目錄的目錄項(xiàng)； (3)根據(jù)這個(gè)目錄項(xiàng)，找到temp目錄文件的FCB，并將其內(nèi)容讀進(jìn)來； (4)在temp目錄文件中去查找old.txt這個(gè)目錄項(xiàng)； (5)在這個(gè)目錄項(xiàng)中，把old.txt修改為new.txt。5、(1)直接重命名方法更快(2)前者只是去修改相應(yīng)的目錄項(xiàng)當(dāng)中的文件名，其他不變(3)后者需要復(fù)制一份文件，增加一