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