《操作系統(tǒng)》期末考及答案一、單項選擇題（每題2分，共20分）1.在進程狀態(tài)轉(zhuǎn)換中，不可能發(fā)生的轉(zhuǎn)換是（）A.運行態(tài)→就緒態(tài)B.就緒態(tài)→運行態(tài)C.阻塞態(tài)→運行態(tài)D.阻塞態(tài)→就緒態(tài)2.某系統(tǒng)采用可變分區(qū)存儲管理，當前內(nèi)存分配表中記錄的空閑分區(qū)為（100KB,200KB）、（300KB,150KB）、（500KB,100KB），若要為一個180KB的進程分配內(nèi)存，采用最佳適應算法會選擇的分區(qū)是（）A.100KB起始的200KB分區(qū)B.300KB起始的150KB分區(qū)C.500KB起始的100KB分區(qū)D.無法分配3.以下關于線程的描述中，錯誤的是（）A.同一進程的線程共享進程的地址空間B.線程是CPU調(diào)度的基本單位C.引入線程會增加進程切換的開銷D.線程可分為用戶級線程和內(nèi)核級線程4.某頁式虛擬存儲系統(tǒng)中，頁大小為4KB，邏輯地址空間為32位，則頁號占（）位A.10B.12C.20D.225.下列磁盤調(diào)度算法中，可能導致“饑餓”現(xiàn)象的是（）A.先來先服務（FCFS）B.最短尋道時間優(yōu)先（SSTF）C.掃描算法（SCAN）D.循環(huán)掃描算法（CSCAN）6.文件系統(tǒng)中，文件的邏輯結(jié)構(gòu)若采用記錄式結(jié)構(gòu)，其基本單位是（）A.字節(jié)B.塊C.記錄D.扇區(qū)7.信號量機制中，P操作（wait操作）的本質(zhì)是（）A.釋放資源B.申請資源C.更新信號量值D.喚醒阻塞進程8.死鎖的四個必要條件中，通過“資源有序分配法”可以破壞的是（）A.互斥條件B.請求和保持條件C.不可搶占條件D.循環(huán)等待條件9.在I/O控制方式中，CPU利用率最高的是（）A.程序直接控制方式B.中斷驅(qū)動方式C.DMA方式D.通道控制方式10.以下關于虛擬內(nèi)存的描述，錯誤的是（）A.虛擬內(nèi)存擴大了物理內(nèi)存的容量B.虛擬內(nèi)存通過離散分配方式實現(xiàn)C.需要頁表或段表支持地址轉(zhuǎn)換D.可能導致“抖動”現(xiàn)象二、填空題（每空1分，共15分）1.操作系統(tǒng)的主要功能包括處理機管理、（）、文件管理、設備管理和用戶接口。2.進程的三種基本狀態(tài)是運行態(tài)、（）和阻塞態(tài)。3.時間片輪轉(zhuǎn)調(diào)度算法中，時間片的長度應略大于（）的時間，否則會增加進程切換開銷。4.內(nèi)存分配的連續(xù)分配方式包括單一連續(xù)分配、固定分區(qū)分配和（）。5.頁表的作用是實現(xiàn)（）到物理地址的映射。6.虛擬內(nèi)存的理論基礎是（）原理，包括時間局部性和空間局部性。7.文件的物理結(jié)構(gòu)主要有順序結(jié)構(gòu)、（）和索引結(jié)構(gòu)三種。8.設備管理中的SPOOLing技術(shù)通過（）實現(xiàn)了虛擬設備功能。9.死鎖預防的策略包括破壞互斥條件、破壞請求和保持條件、破壞不可搶占條件和（）。10.某系統(tǒng)有3個同類資源，被2個進程共享，每個進程最多需要2個資源，則系統(tǒng)（）（填“會”或“不會”）發(fā)生死鎖。11.在磁盤訪問時間中，（）是指磁頭移動到指定磁道所需的時間。12.信號量S的初值為2，執(zhí)行兩次P操作后，S的值為（）；若此時有3個進程申請該資源，其中（）個進程會進入阻塞隊列。13.目錄管理的關鍵是實現(xiàn)（），即通過路徑名快速找到文件的索引節(jié)點。三、簡答題（每題6分，共30分）1.簡述進程與線程的主要區(qū)別。2.說明請求分頁存儲管理中缺頁中斷的處理流程。3.比較FCFS和SSTF磁盤調(diào)度算法的優(yōu)缺點。4.解釋文件系統(tǒng)中“文件控制塊（FCB）”的作用及主要包含的信息。5.舉例說明如何利用信號量機制解決兩個進程的互斥問題。四、綜合題（共35分）1.（10分）某系統(tǒng)采用優(yōu)先級調(diào)度算法（優(yōu)先級數(shù)值越小優(yōu)先級越高），忽略進程調(diào)度開銷，現(xiàn)有4個進程P1-P4，到達時間和服務時間如下表所示：|進程|到達時間（ms）|服務時間（ms）|優(yōu)先級||------|----------------|----------------|--------||P1|0|8|3||P2|1|4|1||P3|2|5|4||P4|3|3|2|（1）畫出進程調(diào)度的甘特圖；（2）計算平均周轉(zhuǎn)時間（周轉(zhuǎn)時間=完成時間-到達時間）。2.（10分）某虛擬存儲系統(tǒng)的邏輯地址為16位，頁大小為1KB，頁表如下所示（頁表項中“存在位”為1表示頁面在內(nèi)存中，“物理塊號”單位為KB）：|頁號|存在位|物理塊號||------|--------|----------||0|1|5||1|0|8||2|1|3||3|1|7|（1）邏輯地址0x3A5（十六進制）對應的頁號和頁內(nèi)偏移量是多少？（2）該地址是否會產(chǎn)生缺頁中斷？說明理由；（3）若產(chǎn)生缺頁中斷，簡述處理流程；若不產(chǎn)生，計算對應的物理地址（十六進制）。3.（15分）某銀行自動取款機（ATM）有2臺，同時最多允許2個用戶使用。用戶需要先在取號機取號（取號操作互斥），然后等待叫號。當ATM空閑時，叫號系統(tǒng)從等待隊列中選擇一個用戶使用ATM。請：（1）定義實現(xiàn)該場景所需的信號量（包括名稱、初值及含義）；（2）用偽代碼描述用戶進程的執(zhí)行流程（包含取號、等待叫號、使用ATM、釋放ATM的過程）；（3）說明如何避免用戶取號后長時間無法被叫號的問題。---答案及解析一、單項選擇題1.C解析：阻塞態(tài)的進程需要等待事件完成（如I/O結(jié)束）后才能轉(zhuǎn)換為就緒態(tài)，無法直接轉(zhuǎn)換為運行態(tài)。2.A解析：最佳適應算法選擇滿足需求且最小的空閑分區(qū)。180KB需要分區(qū)大小≥180KB，可用分區(qū)中200KB是最小的滿足條件的分區(qū)（100KB起始的200KB分區(qū)）。3.C解析：線程共享進程資源，進程切換需要切換地址空間，而線程切換只需切換線程上下文，因此線程切換開銷更小。4.C解析：頁大小4KB=212B，邏輯地址32位，頁號占32-12=20位。5.B解析：SSTF優(yōu)先處理最近磁道的請求，可能導致某些遠磁道請求長期得不到服務（饑餓）。6.C解析：記錄式文件的邏輯結(jié)構(gòu)以記錄為基本單位，如數(shù)據(jù)庫中的一條記錄。7.B解析：P操作通過減少信號量值申請資源，若信號量≤0則阻塞進程。8.D解析：資源有序分配法要求進程按固定順序申請資源，破壞循環(huán)等待條件。9.D解析：通道控制方式由通道獨立處理I/O操作，CPU僅需啟動和結(jié)束時干預，利用率最高。10.A解析：虛擬內(nèi)存并未擴大物理內(nèi)存容量，而是通過邏輯地址空間擴展了程序可用的內(nèi)存范圍。二、填空題1.內(nèi)存管理2.就緒態(tài)3.一次中斷處理4.動態(tài)分區(qū)分配5.邏輯地址（頁號）6.局部性7.鏈式結(jié)構(gòu)（鏈接結(jié)構(gòu)）8.磁盤緩存（輸入井/輸出井）9.破壞循環(huán)等待條件10.不會解析：最大需求總和=2+2=4≤3+1（系統(tǒng)資源+1），根據(jù)銀行家算法，存在安全序列。11.尋道時間12.0；1解析：初始S=2，兩次P操作后S=0；第三個進程執(zhí)行P操作時S=-1，進入阻塞隊列。13.按名存取三、簡答題1.進程與線程的主要區(qū)別：（1）資源分配：進程是資源分配的基本單位，線程共享進程資源；（2）調(diào)度：線程是CPU調(diào)度的基本單位；（3）并發(fā)性：同一進程的線程間并發(fā)開銷更小；（4）獨立性：進程間獨立性強，線程間共享地址空間；（5）開銷：線程創(chuàng)建/切換開銷小于進程。2.請求分頁缺頁中斷處理流程：（1）CPU訪問邏輯地址，查頁表發(fā)現(xiàn)存在位為0，觸發(fā)缺頁中斷；（2）保存當前進程現(xiàn)場；（3）檢查頁表項的外存地址，確定缺失頁面位置；（4）若內(nèi)存有空閑塊，直接分配；否則選擇淘汰頁面（需換出修改過的頁面到外存）；（5）將缺失頁面從外存調(diào)入內(nèi)存，更新頁表存在位和物理塊號；（6）恢復進程現(xiàn)場，重新執(zhí)行引發(fā)中斷的指令。3.FCFS與SSTF比較：FCFS：按請求順序調(diào)度，公平無饑餓，但尋道時間長（尤其當請求分散時）；SSTF：優(yōu)先處理最近磁道請求，平均尋道時間短，但可能導致遠磁道請求饑餓（某些請求長期等待）。4.文件控制塊（FCB）的作用及信息：作用：是文件存在的標志，包含文件的基本信息，用于文件系統(tǒng)管理文件。主要信息：（1）基本信息（文件名、文件類型、文件物理位置）；（2）存取控制信息（文件主權(quán)限、用戶權(quán)限）；（3）使用信息（創(chuàng)建時間、修改時間、訪問次數(shù)）。5.信號量解決兩進程互斥示例：定義互斥信號量mutex，初值為1。進程A：while(1){P(mutex);//申請臨界區(qū)臨界區(qū)操作;V(mutex);//釋放臨界區(qū)}進程B：while(1){P(mutex);臨界區(qū)操作;V(mutex);}當一個進程進入臨界區(qū)時，mutex減為0，另一進程執(zhí)行P操作會阻塞，直到前一進程釋放mutex（V操作），確?；コ庠L問。四、綜合題1.（1）甘特圖：0-1ms：P1運行（唯一到達進程）；1ms：P2到達（優(yōu)先級1最高），搶占P1；1-5ms：P2運行（服務4ms，完成時間5ms）；5ms：就緒隊列有P1（剩余7ms）、P3（到達2ms，服務5ms）、P4（到達3ms，服務3ms），優(yōu)先級P4（2）>P1（3）>P3（4）；5-8ms：P4運行（服務3ms，完成時間8ms）；8ms：就緒隊列有P1（剩余7ms）、P3（剩余5ms），P1優(yōu)先級3高于P3的4；8-15ms：P1運行（剩余7ms，完成時間15ms）；15ms：P3運行（服務5ms，完成時間20ms）。甘特圖時間線：0-1(P1),1-5(P2),5-8(P4),8-15(P1),15-20(P3)（2）周轉(zhuǎn)時間計算：P1：15-0=15ms；P2：5-1=4ms；P3：20-2=18ms；P4：8-3=5ms；平均周轉(zhuǎn)時間=(15+4+18+5)/4=42/4=10.5ms2.（1）邏輯地址0x3A5=二進制1110100101（16位），頁大小1KB=21?B，頁號占高位6位（16-10=6），頁內(nèi)偏移占10位。0x3A5的二進制為001110100101，前6位（001110）=14（頁號），后10位（10100101）=0xA5（偏移量）。（2）頁號14是否在頁表中？題目頁表頁號0-3，說明邏輯地址空間頁號范圍0-3（因為16位地址，頁大小1KB，總頁數(shù)=21?/21?=64頁，頁號0-63），但題目頁表僅給出0-3頁的信息，假設頁號14對應的頁表項存在位為0（題目未明確，需按常規(guī)判斷）?；蚩赡茴}目頁表為部分頁表，實際邏輯地址0x3A5=933（十進制），頁號=933/1024=0（整數(shù)除法），頁內(nèi)偏移=933%1024=933。此時頁號0的存在位為1，不會缺頁。（注：原題可能存在頁號計算歧義，正確計算應為頁號=邏輯地址/頁大小=0x3A5/0x400=0（十六進制0x3A5=933，0x400=1024，933<1024，頁號0）。（3）頁號0存在位為1，物理塊號5（單位KB），物理地址=51024+933=50x400+0x3A5=0x1400+0x3A5=0x17A5（十六進制）。3.（1）信號量定義：-mutex：初值1，用于取號機的互斥訪問；-atm：初值2，表示可用ATM數(shù)量；-wait_queue：初值0，用于用戶等待叫號（或直接用atm的P/V操作管理