2024年大學(xué)試題(計算機科學(xué))-操作系統(tǒng)(CH1)筆試歷年真題薈萃含答案

2024年大學(xué)試題(計算機科學(xué))-操作系統(tǒng)(CH1)筆試歷年真題薈萃含答案（圖片大小可自由調(diào)整）答案解析附后卷I一.參考題庫(共25題)1.有矩陣：VAR??A：ARRAY[1‥100，1‥100]??OF??integer；元素按行存儲。在一虛存系統(tǒng)中，采用LRU淘汰算法，一個進程有3頁內(nèi)存空間，每頁可以存放200個整數(shù)。其中第1頁存放程序，且假定程序已在內(nèi)存。? 程序A：? FOR?i：＝1?TO?100?DO? ?????FOR?j：＝1?TO?100?DO ????????A[i，j]：＝0；?程序B：?? FOR?j：＝1?TO?100?DO? ??????FOR?i：＝1?TO?100?DO ?????????A[i，j]：＝0；? 分別就程序A和B的執(zhí)行進程計算缺頁次數(shù)。2.把死鎖檢測算法用于下面的數(shù)據(jù)，并請問：此時系統(tǒng)此時處于安全狀態(tài)嗎？3.某操作系統(tǒng)的磁盤文件空間共有500塊，若用字長為32位的位示圖管理盤空間并給出申請/歸還一塊的工作流程。4.設(shè)某系統(tǒng)中作業(yè)J1，J2，J3占用主存的情況如圖。今有一個長度為20k的作業(yè)J4要裝入主存，當(dāng)采用可變分區(qū)分配方式時，請回答： （1）J4裝入前的主存已分配表和未分配表的內(nèi)容。? （2）寫出裝入J4時的工作流程，并說明你采用什么分配算法。 5.設(shè)公共汽車上，司機和售票員的活動分別如下：? 司機的活動：啟動車輛：正常行車；到站停車。?售票員的活動：關(guān)車門；售票；開車門。? 在汽車不斷地到站、停車、行駛過程中，這兩個活動有什么同步關(guān)系？用信號量和P、V操作實現(xiàn)它們的同步。6.有一具有40個磁道的盤面，編號為0~39，當(dāng)磁頭位于第11磁道時，順序來到如下磁道請求：磁道號：1、36、16、34、9、12； 試用1）先來先服務(wù)算法FCFS 2）最短查找時間優(yōu)先算法SSTF 3）掃描算法SCAN等三種磁盤驅(qū)動調(diào)度算法，計算出它們各自要來回穿越多少磁道？7.把死鎖檢測算法用于下面的數(shù)據(jù)，并請問：若第二個進程提出資源請求request2（0，0，1，0），系統(tǒng)能分配資源給它嗎？8.（1）假定一個處理器正在執(zhí)行兩道作業(yè)，一道以計算為主，另一道以輸入輸出為主，你將怎樣賦予它們占有處理器的優(yōu)先級？為什么？? （2）假定一個處理器正在執(zhí)行三道作業(yè)，一道以計算為主，第二道以輸入輸出為主，第三道為計算與輸入輸出均勻。應(yīng)該如何賦予它們占有處理器的優(yōu)先級使得系統(tǒng)效率較高？9.現(xiàn)有如下請求隊列：8，18，27，129，110，186，78，147，41，10，64，12；試用查找時間最短優(yōu)先算法計算處理所有請求移動的總柱面數(shù)。假設(shè)磁頭當(dāng)前位置下在磁道100。10.某文件為連接文件，由5個邏輯記錄組成，每個邏輯記錄的大小與磁盤塊大小相等，均為512字節(jié)，并依次存放在50、121、75、80、63號磁盤塊上?，F(xiàn)要讀出文件的1569字節(jié)，問訪問哪一個磁盤塊？11.一臺機器有48位虛地址和32位物理地址，若頁長為8KB，問頁表共有多少個頁表項？如果設(shè)計一個反置頁表，則有多少個頁表項？12.假定磁盤有200個柱面，編號0~199，當(dāng)前存取臂的位置在143號柱面上，并剛剛完成了125號柱面的服務(wù)請求，如果請求隊列的先后順序是：86，147，91，177，94，150，102，175，130；試問：為完成上述請求，下列算法存取臂移動的總量是多少？并算出存取臂移動的順序。掃描算法SCAN。13.一進程以下列次序訪問5個頁：A、B、C、D、A、B、E、A、B、C、D、E；假定使用FIFO替換算法，在內(nèi)存有3個和4個空閑頁框的情況下，分別給出頁面替換次數(shù)。14.有P1、P2、P3三個進程共享一個表格F，P1對F只讀不寫，P2對F只寫不讀，P3對F先讀后寫。進程可同時讀F，但有進程寫時，其他進程不能讀和寫。用（1）信號量和P、V操作，（2）管程編寫三進程能正確工作的程序。15.在某計算機系統(tǒng)中，時鐘中斷處理程序每次執(zhí)行的時間為2ms（包括進程切換開銷）。若時鐘中斷頻率為60HZ，試問CPU用于時鐘中斷處理的時間比率為多少？16.除FCFS外，所有磁盤調(diào)度算法都不公平，如造成有些請求饑餓，試分析提出一種公平性調(diào)度算法。17.假定磁盤有200個柱面，編號0~199，當(dāng)前存取臂的位置在143號柱面上，并剛剛完成了125號柱面的服務(wù)請求，如果請求隊列的先后順序是：86，147，91，177，94，150，102，175，130；試問：為完成上述請求，下列算法存取臂移動的總量是多少？并算出存取臂移動的順序。電梯調(diào)度。18.某多道程序設(shè)計系統(tǒng)供用戶使用的主存為100K，磁帶機2臺，打印機1臺。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)I/O時間?，F(xiàn)有作業(yè)序列如下： 作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配主存低地址區(qū)且不準(zhǔn)移動已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時間。作業(yè)被調(diào)度的先后次序？19.Kleinrock提出一種動態(tài)優(yōu)先權(quán)算法：進程在就緒隊列等待時，其優(yōu)先權(quán)以速率α變化；?當(dāng)進程在處理器上運行，時其優(yōu)先權(quán)以速率β變化。給參數(shù)α、β賦以不同值可得到不同算法。若α<β<0是什么算法？20.有5個批處理作業(yè)A到E均已到達計算中心，其運行時間分別2、4、6、8和10分鐘；各自的優(yōu)先級分別被規(guī)定為1、2、3、4和5，這里5為最高級。對于1）時間片輪轉(zhuǎn)算法、2）優(yōu)先數(shù)法、3）短作業(yè)優(yōu)先算法、4）先來先服務(wù)調(diào)度算法（按到達次序C、D、B、E、A），在忽略進程切換時間的前提下，計算出平均作業(yè)周轉(zhuǎn)時間。（對1）每個作業(yè)獲得相同的2分鐘長的時間片；對2）到4）采用單道運行，直到結(jié)束。）21.設(shè)當(dāng)前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時Available=（1，1，2）：系統(tǒng)是否處于安全狀態(tài)，為什么？22.有一個具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。 （1）列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。? （2）計算平均周轉(zhuǎn)時間。23.給定內(nèi)存空閑分區(qū)，按地址從小到大為：100K、500K、200K、300K和600K。現(xiàn)有用戶進程依次分別為212K、417K、112K和426K，（1）分別用first-fit、best-fit和worst-fit算法將它們裝入到內(nèi)存的哪個分區(qū)？ （2）哪個算法能最有效利用內(nèi)存？24.有兩個程序，A程序按順序使用：（CPU）10秒、（設(shè)備甲）5秒、（CPU）5秒、（設(shè)備乙）10秒、（CPU）10秒。B程序按順序使用：（設(shè)備甲）10秒、（CPU）10秒、（設(shè)備乙）5秒、（CPU）5秒、（設(shè)備乙）10秒。在順序環(huán)境下先執(zhí)行A，再執(zhí)行B，求出總的CPU利用率為多少？25.考慮下列的段表： 段號????????始址???????????段長? 0???????????200????????????500? 1???????????890????????????30? 2???????????120????????????100? 3??????????1250????????????600? 4??????????1800????????????88?? 對下面的邏輯地址，求物理地址，如越界請指明。1）??2）?3）?4）?5）??6）。卷II一.參考題庫(共25題)1.若有如表所示四個作業(yè)進入系統(tǒng)，分別計算在FCFS、SJF和HRRF算法下的平均周轉(zhuǎn)時間與帶權(quán)平均周轉(zhuǎn)時間。（時間以十進制表示） 2.Kleinrock提出一種動態(tài)優(yōu)先權(quán)算法：進程在就緒隊列等待時，其優(yōu)先權(quán)以速率α變化；?當(dāng)進程在處理器上運行，時其優(yōu)先權(quán)以速率β變化。給參數(shù)α、β賦以不同值可得到不同算法。若α>β>0是什么算法？3.若兩個用戶共享一個文件系統(tǒng)，用戶甲使用文件A、B、C、D、E；用戶乙要用到文件A、D、E、F。己知用戶甲的文件A與用戶乙的文件A實際上不是同一文件；甲、乙兩用戶的文件D和E正是同一文件。試設(shè)計一種文件系統(tǒng)組織方案，使得甲、乙兩用戶能共享該文件系統(tǒng)又不致造成混亂。4.某計算機有4個頁框，每頁的裝入時間、最后訪問時間、訪問位R、修改位D如下所示（時間用時鐘點數(shù)表示）： 分別用FIFO、LRU、二次機會算法分別淘汰哪一頁？5.在一個請求分頁虛擬存儲管理系統(tǒng)中，一個程序運行的頁面走向是：??????? 1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6。? 分別用FIFO、OPT和LRU算法，對分配給程序3個頁框、4個頁框、5個頁框和6個頁框的情況下，分別求出缺頁中斷次數(shù)和缺頁中斷率。6.請你設(shè)計一種先進的計算機體系結(jié)構(gòu)，它使用硬件而不是中斷來完成進程切換，則CPU需要哪些信息？?請描述用硬件完成進程切換的工作過程。7.（1）兩個并發(fā)進程并發(fā)執(zhí)行，其中，A、B、C、D、E是原語，試給出可能的并發(fā)執(zhí)行路徑。? Process?P?????????????Process?Q? begin?????????????????begin? ?????????????A；??????????????????D； ?????????????B；??????????????????E； ?????????????C；???????????????end； ??????????end；? （2）?兩個并發(fā)進程P1和P2并發(fā)執(zhí)行，它們的程序分別如下： ???????P1?????????????P2 ????????repeat????????????repeat ?????????k：=k×2；????????print?k； ?????????k：=k+1；?????????k：=0； ??????until?false；???????until?false；? 若令k的初值為5，讓P1先執(zhí)行兩個循環(huán)，然后，P1和P2又并發(fā)執(zhí)行了一個循環(huán)，寫出可能的打印值，指出與時間有關(guān)的錯誤。8.若內(nèi)存中有3道程序A、B、C，它們按A、B、C優(yōu)先次序運行。各程序的計算軌跡為：? A：計算（20）、I/O（30）、計算（10）??? B：計算（40）、I/O（20）、計算（10）? C://計算（10）、I/O（30）、計算（20）? 如果三道程序都使用相同設(shè)備進行I/O（即程序用串行方式使用設(shè)備，調(diào)度開銷忽略不計）。試分別畫出單道和多道運行的時間關(guān)系圖。兩種情況下，CPU的平均利用率各為多少？9.某多道程序設(shè)計系統(tǒng)采用可變分區(qū)內(nèi)存管理，供用戶使用的主存為200K，磁帶機5臺。采用靜態(tài)方式分配外圍設(shè)備，且不能移動在主存中的作業(yè)，忽略用戶作業(yè)I/O時間?，F(xiàn)有作業(yè)序列如下： FIFO算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時間？10.一個有快表的請頁式虛存系統(tǒng)，設(shè)內(nèi)存訪問周期為1微秒，內(nèi)外存?zhèn)魉鸵粋€頁面的平均時間為5毫秒。如果快表命中率為75%，缺頁中斷率為10%。忽略快表訪問時間，試求內(nèi)存的有效存取時間。11.有一個磁盤組共有10個盤面，每個盤面有100個磁道，每個磁道有16個扇區(qū)。若以扇區(qū)為分配單位，問：若空白文件目錄的每個目錄項占5個字節(jié)，則什么時候空白文件目錄大于位示圖？12.設(shè)有一頁式存儲管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁，每頁2048字節(jié)，內(nèi)存總共有8個存儲塊。試問邏輯地址至少應(yīng)為多少位？內(nèi)存空間有多大？13.在單CPU和兩臺I/O(I1,I2)設(shè)備的多道程序設(shè)計環(huán)境下，同時投入三個作業(yè)運行。它們的執(zhí)行軌跡如下： Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)、I2(20ms)? Job2：I1(20ms)、CPU(20ms)、I2(40ms)? Job3：CPU(30ms)、I1(20ms)、CPU(10ms)、I1(10ms)? 如果CPU、I1和I2都能并行工作，優(yōu)先級從高到低為Job1、Job2和Job3，優(yōu)先級高的作業(yè)可以搶占優(yōu)先級低的作業(yè)的CPU，但不搶占I1和I2。 試求：(1)每個作業(yè)從投入到完成分別所需的時間。 (2)?從投入到完成CPU的利用率。 (3)I/O設(shè)備利用率。14.若某操作系統(tǒng)僅支持單級目錄，但允許該目錄有任意多個文件，且文件名可任意長，試問能否模擬一個層次式文件系統(tǒng)？如能的話，如何模擬。15.單道批處理系統(tǒng)中，下列三個作業(yè)采用先來先服務(wù)調(diào)度算法和最高響應(yīng)比優(yōu)先算法進行調(diào)度，哪一種算法性能較好？請完成下表： 16.一個頁式存儲管理系統(tǒng)使用FIFO、OPT和LRU頁面替換算法，如果一個作業(yè)的頁面走向為：? （1）2、3、2、1、5、2、4、5、3、2、5、2。? （2）4、3、2、1、4、3、5、4、3、2、1、5。? （3）1、2、3、4、1、2、5、1、2、3、4、5。? 當(dāng)分配給該作業(yè)的物理塊數(shù)分別為3和4時，試計算訪問過程中發(fā)生的缺頁中斷次數(shù)和缺頁中斷率。17.下列指令中哪些只能在核心態(tài)運行？? （1）讀時鐘日期； （2）訪管指令； （3）設(shè)時鐘日期； （4）加載PSW； （5）置特殊寄存器； （6）改變存儲器映象圖； （7）啟動I/O指令。18.系統(tǒng)有A、B、C、D共4種資源，在某時刻進程P0、P1、P2、P3和P4對資源的占有和需求情況如表，試解答下列問題： 系統(tǒng)此時處于安全狀態(tài)嗎？19.假定某計算機系統(tǒng)有R1和R2兩類可再使用資源（其中R1有兩個單位，R2有一個單位），它們被進程P1，P2所共享，且已知兩個進程均以下列順序使用兩類資源。????????????? →申請R1→申請R2→申請R1→釋放R1→釋放R2→釋放R1→? 試求出系統(tǒng)運行過程中可能到達的死鎖點，并畫出死鎖點的資源分配圖（或稱進程－資源圖）。20.假定執(zhí)行表中所列作業(yè)，作業(yè)號即為到達順序，依次在時刻0按次序1、2、3、4、5進入單處理器系統(tǒng)。? 1）分別用先來先服務(wù)調(diào)度算法、時間片輪轉(zhuǎn)算法、短作業(yè)優(yōu)先算法及非強占優(yōu)先權(quán)調(diào)度算法算出各作業(yè)的執(zhí)行先后次序（注意優(yōu)先權(quán)高的數(shù)值小）； 2）計算每種情況下作業(yè)的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。 21.某操作系統(tǒng)的磁盤文件空間共有500塊，若用字長為32位的位示圖管理盤空間位示圖需多少個字？22.有5個待運行的作業(yè)，各自預(yù)計運行時間分別是：9、6、3、5和x，采用哪種運行次序使得平均響應(yīng)時間最短？23.設(shè)一個文件由100個物理塊組成，對于連續(xù)文件、連接文件和索引文件，分別計算執(zhí)行下列操作時的啟動磁盤I/O次數(shù)（假如頭指針和索引表均在內(nèi)存中）： （1）把一塊加在文件的開頭； （2）把一塊加在文件的中間（第51塊）； （3）把一塊加在文件的末尾； （4）從文件的開頭刪去一塊； （5）從文件的中間（第51塊）刪去一塊； （6）從文件的未尾刪去一塊。24.對某系統(tǒng)進行監(jiān)測后表明平均每個進程在I/O阻塞之前的運行時間為T。一次進程切換的系統(tǒng)開銷時間為S。若采用時間片長度為Q的時向片輪轉(zhuǎn)法，對下列各種情況算出CPU利用率。 1）Q＝∞??? 2）Q＞T??? 3）S＜Q＜T???? 4）Q＝S??? 5）Q接近于025.某多道程序設(shè)計系統(tǒng)采用可變分區(qū)內(nèi)存管理，供用戶使用的主存為200K，磁帶機5臺。采用靜態(tài)方式分配外圍設(shè)備，且不能移動在主存中的作業(yè)，忽略用戶作業(yè)I/O時間。現(xiàn)有作業(yè)序列如下： SJF算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時間？卷III一.參考題庫(共25題)1.有兩個優(yōu)先級相同的進程P1和P2，各自執(zhí)行的操作如下，信號量S1和S2初值均為0。試問P1、P2并發(fā)執(zhí)行后，x、y、z的值各為多少？ 2.某多道程序設(shè)計系統(tǒng)供用戶使用的主存為100K，磁帶機2臺，打印機1臺。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)I/O時間?，F(xiàn)有作業(yè)序列如下： 作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配主存低地址區(qū)且不準(zhǔn)移動已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時間。作業(yè)平均周轉(zhuǎn)時間為多少？3.某系統(tǒng)有R1設(shè)備3臺，R2設(shè)備4臺，它們被P1、P2、P3和P4進程共享，且已知這4個進程均按以下順序使用設(shè)備：→申請R1→申請R2→申請R1→釋放R1→釋放R2→釋放R1系統(tǒng)運行中可能產(chǎn)生死鎖嗎？為什么？4.有一閱覽室，讀者進入時必須先在一張登記表上登記，該表為每一座位列出一個表目，包括座號、姓名，讀者離開時要注銷登記信息；假如閱覽室共有100個座位。試用：1）信號量和P、V操作；2）管程，來實現(xiàn)用戶進程的同步算法。5.旋轉(zhuǎn)型設(shè)備上信息的優(yōu)化分布能減少為若干個I/O服務(wù)的總時間。設(shè)磁鼓上分為20個區(qū)，每區(qū)存放一個記錄，磁鼓旋轉(zhuǎn)一周需20毫秒，讀出每個記錄平均需用1毫秒，讀出后經(jīng)2毫秒處理，再繼續(xù)處理下一個記錄。在不知當(dāng)前磁鼓位置的情況下：順序存放記錄1、……，記錄20時，試計算讀出并處理20個記錄的總時間；6.設(shè)文件ABCD為定長記錄的連續(xù)文件，共有18個邏輯記錄。如果記錄長為512B，物理塊長為1024B，采用成組方式存放，起始塊號為12，敘述第15號邏輯記錄讀入內(nèi)存緩沖區(qū)的過程。7.某多道程序設(shè)計系統(tǒng)供用戶使用的主存為100K，磁帶機2臺，打印機1臺。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)I/O時間?，F(xiàn)有作業(yè)序列如下： 作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配主存低地址區(qū)且不準(zhǔn)移動已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時間。最大作業(yè)周轉(zhuǎn)時間為多少？8.設(shè)當(dāng)前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時Available=（1，1，2）：P2發(fā)出請求向量request1（1，0，1），系統(tǒng)能把資源分給它嗎？9.在單CPU和兩臺I/O(I1,I2)設(shè)備的多道程序設(shè)計環(huán)境下，同時投入三個作業(yè)運行。它們的執(zhí)行軌跡如下：? Job1：I2(30ms)、CPU(10ms)、I1(30ms)、CPU(10ms)? Job2：I1(20ms)、CPU(20ms)、I2(40ms)? Job3：CPU(30ms)、I1(20ms)? 如果CPU、I1和I2都能并行工作，優(yōu)先級從高到低為Job1、Job2和Job3，優(yōu)先級高的作業(yè)可以搶占優(yōu)先級低的作業(yè)的CPU。 試求：(1)每個作業(yè)從投入到完成分別所需的時間。 (2)?每個作業(yè)投入到完成CPU的利用率。 (3)I/O設(shè)備利用率。10.桌上有一只盤子，最多可以容納兩個水果，每次僅能放入或取出一個水果。爸爸向盤子中放蘋果（apple），媽媽向盤子中放桔子（orange），兩個兒子專等吃盤子中的桔子，兩個女兒專等吃盤子中的蘋果。試用：（1）信號量和P、V操作，（2）管程，來實現(xiàn)爸爸、媽媽、兒子、女兒間的同步與互斥關(guān)系。11.系統(tǒng)有同類資源m個，被n個進程共享，問：當(dāng)m＞n和m≤n時，每個進程最多可以請求多少個這類資源時，使系統(tǒng)一定不會發(fā)生死鎖？12.假設(shè)計算機有2M內(nèi)存，其中，操作系統(tǒng)占用512K，每個用戶程序也使用512K內(nèi)存。如果所有程序都有70%的I/O等待時間，那么，再增加1M內(nèi)存，吞吐率增加多少？13.系統(tǒng)有A、B、C、D共4種資源，在某時刻進程P0、P1、P2、P3和P4對資源的占有和需求情況如表，試解答下列問題： 若此時P2發(fā)出request1（1、2、2、2），系統(tǒng)能分配資源給它嗎？為什么？14.設(shè)有三道程序，按A、B、C優(yōu)先次序運行，其內(nèi)部計算和I/O操作時間由圖給出。 試畫出按多道運行的時間關(guān)系圖（忽略調(diào)度執(zhí)行時間）。完成三道程序共花多少時間？比單道運行節(jié)省了多少時間？若處理器調(diào)度程序每次進行程序轉(zhuǎn)換化時1ms，試畫出各程序狀態(tài)轉(zhuǎn)換的時間關(guān)系圖。15.另一個經(jīng)典同步問題：吸煙者問題（patil，1971）。三個吸煙者在一個房間內(nèi)，還有一個香煙供應(yīng)者。為了制造并抽掉香煙，每個吸煙者需要三樣?xùn)|西：煙草、紙和火柴，供應(yīng)者有豐富貨物提供。三個吸煙者中，第一個有自己的煙草，第二個有自己的紙和第三個有自己的火柴。供應(yīng)者隨機地將兩樣?xùn)|西放在桌子上，允許一個吸煙者進行對健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再把兩樣?xùn)|西放在桌子上，喚醒另一個吸煙者。試采用：（1）信號量和P、V操作，（2）管程編寫他們同步工作的程序。16.在按動態(tài)優(yōu)先數(shù)調(diào)度進程的系統(tǒng)中，每個進程的優(yōu)先數(shù)需定時重新計算。在處理器不斷地在進程之間交替的情況下，重新計算進程優(yōu)先數(shù)的時間從何而來？17.在虛擬頁式存儲管理中，為解決抖動問題，可采用工作集模型以決定分給進程的物理塊數(shù)，有如下頁面訪問序列： 窗口尺寸△＝9，試求t1、t2時刻的工作集。18.在UNIX?中，如果一個盤塊的大小為1KB，每個盤塊號占4個字節(jié)，即每塊可放256個地址。請轉(zhuǎn)換下列文件的字節(jié)偏移量為物理地址：（1）9999；（2）18000；（3）420000。19.如果一個索引節(jié)點為128B，指針長4B，狀態(tài)信息占用68B，而每塊大小為8KB。問在索引節(jié)點中有多大空間給指針？使用直接、一次間接、二次間接和三次間接指針分別可表示多大的文件？20.一臺計算機的內(nèi)存空間為1024個頁面，頁表放在內(nèi)存中，從頁表中讀一個字的開銷是500ns。為了減少開銷，使用了有32個字的快表，查找速度為100ns。要把平均開銷降到200ns需要的快表命中率是多少？21.某計算機系統(tǒng)提供24位虛存空間，主存為218B，采用分頁式虛擬存儲管理，頁面尺寸為1KB。假定用戶程序產(chǎn)生了虛擬地址11123456（八進制），而該頁面分得塊號為100（八進制），說明該系統(tǒng)如何產(chǎn)生相應(yīng)的物理地址及寫出物理地址。 虛擬地址11123456（八進制）轉(zhuǎn)化為二進制為：????????????????? 001?001?001?010?011?100?101?110? 其中前面為頁號，而后10位為位移：001?001?001?010?011?100?101?110。由于主存大小為218B，頁面尺寸為1KB，所以，主存共有256塊。所以，塊號為100（八進制）是合法地址，于是，物理地址為100與位移1?100?101?110并接，得到：八進制物理地址100?1?100?101?110。 13主存中有兩個空間區(qū)如圖所示， 現(xiàn)有作業(yè)序列依次為：Job1要求30K；Job2要求70K；Job3要求50K；使用首次適應(yīng)、最壞適應(yīng)和最佳適應(yīng)算法處理這個作業(yè)序列，試問哪種算法可以滿足分配？為什么？22.有一臺計算機，具有1MB內(nèi)存，操作系統(tǒng)占用200KB，每個用戶進程各占200KB。如果用戶進程等待I/O的時間為80%，若增加1MB內(nèi)存，則CPU的利用率提高多少？23.在一個分頁虛存系統(tǒng)中，用戶編程空間32個頁，頁長1KB，主存為16KB。如果用戶程序有10頁長，若己知虛頁0、1、2、3，已分到頁框8、7、4、10?，試把虛地址0AC5H和1AC5H轉(zhuǎn)換成對應(yīng)的物理地址。24.設(shè)有n個進程共享一個互斥段，如果：? （1）每次只允許一個進程進入互斥段；? （2）每次最多允許m個進程（m≤n）同時進入互斥段。? 試問：所采用的信號量初值是否相同？信號量值的變化范圍如何？25.對磁盤存在下面五個請求： 假如當(dāng)前磁頭位于1號柱面。試分析對這五個請求如何調(diào)度，可使磁盤的旋轉(zhuǎn)圈數(shù)為最少？卷I參考答案一.參考題庫1.參考答案:題中100×100=10000個數(shù)據(jù)，每頁可以存放200個整數(shù)，故一共存放在50個頁面中。由于元素按行存儲，第1行、第2行放在第1頁，…，第99行、第100行放在第50頁。故對于程序A，缺頁中斷為50次。對于程序B，缺頁中斷為5000次。2.參考答案: 此時可以找出進程安全序列：P4，P1，P5，P2，P3。故系統(tǒng)處于安全狀態(tài)。3.參考答案: 申請時自上至下、自左至有掃描位示圖跳過為1的位，找到第一個遷到的0位，根據(jù)它是第i字第j位算出對應(yīng)塊號，并分配出去。歸還時已知塊號，塊號/32算出第i字第j位并把位示圖相應(yīng)位清0。4.參考答案: （1）主存已分配表共有三項，由作業(yè)J1、J2、J3占用，長度依次為：10k、30k和54k。未分配表共有三項：空閑區(qū)1、空閑區(qū)2和空閑區(qū)3，長度依次為18k、40k和70k。 （2）作業(yè)J4裝入時，采用直接分配，搜索未分配表，空閑區(qū)1不能滿足。所以，要繼續(xù)搜索未分配表，空閑區(qū)2可以滿足J4的裝入要求。5.參考答案: 在汽車行駛過程中，司機活動與售票員活動之間的同步關(guān)系為：售票員關(guān)車門后，向司機發(fā)開車信號，司機接到開車信號后啟動車輛，在汽車正常行駛過程中售票員售票，到站時司機停車，售票員在車停后開門讓乘客上下車。因此，司機啟動車輛的動作必須與售票員關(guān)車門的動作取得同步；售票員開車門的動作也必須與司機停車取得同步。 應(yīng)設(shè)置兩個信號量：s1、s2；s1表示是否允許司機啟動汽車（其初值為0）；s2表示是否允許售票員開門（其初值為0）。用P、V原語描述如下： 6.參考答案: 1）FCFS為111。 2）SSTF為61。 3）SCAN為60（先掃地址大的請求），為45（先掃地址小的請求）。7.參考答案: 可以分配，存在安全序列：P4，P1，P5，P2，P3。8.參考答案:處理器調(diào)度算法會考慮以下因素：作業(yè)響應(yīng)時間要求；讓CPU盡量和外圍設(shè)備并行工作；限制一個計算進程長時間霸占處理器。因而，(1)I/O為主作業(yè)優(yōu)先級高。(2)?輸入輸出為主作業(yè)優(yōu)先級最高，輸入輸出均勻的作業(yè)其次，而計算為主作業(yè)的優(yōu)先級最低。9.參考答案:處理次序為：100-110-129-147-186-78-64-41-27-18-12-10-8。移動的總柱面數(shù)：264。10.參考答案:80號磁盤塊。11.參考答案:因為頁長8KB占用13住，所以，頁表項有235個。反置頁表項有219個。12.參考答案: 掃描算法SCAN為169，依次為143-147-150-175-177-199-130-102-94-91-86。13.參考答案:內(nèi)存有3個和4個空閑頁框的情況下，頁面替換次數(shù)為9次和10次。出現(xiàn)了Belady現(xiàn)象，增加分給作業(yè)的內(nèi)存塊數(shù)，反使缺頁中斷率上升。14.參考答案: （1）信號量和P、V操作。 這是讀--寫者問題的變種。其中，P3既是讀者又是寫者。讀者與寫者之間需要互斥，寫者與寫者之間需要互斥，為提高進程運行的并發(fā)性，可讓讀者盡量優(yōu)先。 15.參考答案:因時鐘中斷頻率為60HZ，所以，時鐘周期為：1/60s=50/3ms。在每個時鐘周期中，CPU花2ms執(zhí)行中斷任務(wù)。所以，CPU用于時鐘中斷處理的時間比率為：2(50/3)=6/50=12%。16.參考答案: 可劃定一個時間界限，把這段時間內(nèi)尚未得到服務(wù)的請求強制移到隊列首部，并標(biāo)記任何新請求不能插到這些請求前。對于SSTF算法來說，可以重新排列這些老請求，以優(yōu)先處理。17.參考答案: 電梯調(diào)度為125(先向地址大的方向)，依次為143-147-150-175-177-102-94-91-86。為148(先向地址小的方向)?依次為143-130-102-94-91-86-147-150-175-177。18.參考答案: 作業(yè)調(diào)度選擇的作業(yè)次序為：作業(yè)1、作業(yè)3、作業(yè)4、作業(yè)2和作業(yè)5。19.參考答案: 是后進先出算法。因為在就緒隊列中的進程比在CPU上運行的進程的優(yōu)先權(quán)下降得快，故后進入就緒隊列的進程此先進入的進程的優(yōu)先權(quán)高。20.參考答案: 21.參考答案: 系統(tǒng)處于安全狀態(tài)，存在安全序：P2，P1，P3，P422.參考答案: 每個作業(yè)運行將經(jīng)過兩個階段：作業(yè)調(diào)度（SJF算法）和進程調(diào)度（優(yōu)先數(shù)搶占式）。另外，批處理最多容納2道作業(yè)，更多的作業(yè)將在后備隊列等待。 （1）10：00，作業(yè)A到達并投入運行。 （2）10：20，作業(yè)B到達且優(yōu)先權(quán)高于作業(yè)A，故作業(yè)B投入運行而作業(yè)A在就緒隊列等待。 （3）10：30，作業(yè)C到達，因內(nèi)存中已有兩道作業(yè)，故作業(yè)C進入作業(yè)后備隊列等待。 （4）10：50，作業(yè)B運行結(jié)束，作業(yè)D到達，按SJF短作業(yè)優(yōu)先算法，作業(yè)D被裝入內(nèi)存進入就緒隊列。而由于作業(yè)A的優(yōu)先級高于作業(yè)D，故作業(yè)A投入運行。 （5）11：10，作業(yè)A運行結(jié)束，作業(yè)C被調(diào)入內(nèi)存，且作業(yè)C的優(yōu)先級高于作業(yè)D，故作業(yè)C投入運行。 （6）12：00，作業(yè)C運行結(jié)束，作業(yè)D投入運行。 （7）12：20，作業(yè)D運行結(jié)束。 各作業(yè)周轉(zhuǎn)時間為：作業(yè)A??70，作業(yè)B??30，作業(yè)C??90，作業(yè)D??90。平均作業(yè)周轉(zhuǎn)時間為70分鐘。23.參考答案: 按題意地址從小到大進行分區(qū)如圖所示。 （1）?1）first-fit???212KB選中分區(qū)2，這時分區(qū)2還剩288KB。417KB選中分區(qū)5，這時分區(qū)5還剩183KB。112KB選中分區(qū)2，這時分區(qū)2還剩176KB。426KB無分區(qū)能滿足，應(yīng)該等待。 2）best-fit????212KB選中分區(qū)4，這時分區(qū)4還剩88KB。417KB選中分區(qū)2，這時分區(qū)2還剩83KB。112KB選中分區(qū)3，這時分區(qū)3還剩88KB。426KB選中分區(qū)5，這時分區(qū)5還剩174KB。 3）worst-fit???212KB選中分區(qū)5，這時分區(qū)5還剩388KB。417KB選中分區(qū)2，這時分區(qū)2還剩83KB。112KB選中分區(qū)5，這時分區(qū)5還剩176KB。426KB無分區(qū)能滿足，應(yīng)該等待。 （2）?對于該作業(yè)序列，best-fit算法能最有效利用內(nèi)存.24.參考答案:程序A執(zhí)行了40秒，其中CPU用了25秒。程序B執(zhí)行了40秒，其中CPU用了15秒。兩個程序共用了80秒，CPU化了40秒。故CPU利用率為40/80=50%。25.參考答案: 1）680 2）915 3）904 4）越界 5）1750 6）越界。卷II參考答案一.參考題庫1.參考答案: 2.參考答案: 是先進先出算法。因為在就緒隊列中的進程比在CPU上運行的進程的優(yōu)先數(shù)提高得快，故進程切換時，先進入就緒隊列的進程優(yōu)先權(quán)就越高。3.參考答案: 可以采用二級目錄或樹形目錄結(jié)構(gòu)來解決難題。例如，4.參考答案: （1）FIFO??淘汰page2。 （2）LRU??淘汰page1。 （3）二次機會??淘汰page0。5.參考答案: 只要把表中缺頁中斷次數(shù)除以20，便得到缺頁中斷率。6.參考答案:該計算機有一個專用硬件寄存器，它始終存放指向當(dāng)前運行進程的PCB的指針。當(dāng)系統(tǒng)中發(fā)生了一個事件，如I/O結(jié)束事件，CPU便可把運行進程的上下文保存到專用硬件寄存器指針指向的PCB中保護起來，然后，CPU轉(zhuǎn)向中斷向量表，找到設(shè)備中斷處理程序入口，讓專用硬件寄存器指針指向(設(shè)備)中斷服務(wù)例程，于是，便可啟動中斷服務(wù)例程工作。7.參考答案: （1）?共有10種交錯執(zhí)行的路徑： A、B、C、D、E；A、B、D、E、C；A、B、D、C、E； A、D、B、E、C；A、D、B、C、E；A、D、E、B、C； D、A、B、E、C；D、A、B、C、E；D、A、E、B、C；D、E、A、B、C。 （2）?把語句編號，以便于描述： P1?????????????P2 repeat????????????repeat K:=k×2；???①?????print?k；??③ K:=k+1；????②?????k：=0；???④ until?false；????????until?false； 1）K的初值為5，故P1執(zhí)行兩個循環(huán)后，K=23。 2）語句并發(fā)執(zhí)行有以下情況： ①、②、③、④，這時的打印值為：47 ③、④、①、②，這時的打印值為：23 ①、③、②、④，這時的打印值為：46 ①、③、④、②，這時的打印值為：46 ③、①、②、④，這時的打印值為：23 ③、①、④、②，這時的打印值為：23 由于進程P1和P2并發(fā)執(zhí)行，共享了變量K，故產(chǎn)生了‘結(jié)果不唯一’。8.參考答案: 分別畫出單道和多道運行的時間圖? 單道運行時間關(guān)系圖 單道總運行時間為190ms。CPU利用率為（190-80）/190=57.9% 多道運行時間關(guān)系圖 多道總運行時間為140ms。CPU利用率為（140-30）/140=78.6%9.參考答案: FIFO算法選中作業(yè)執(zhí)行的次序為：A、B、D、C和E。作業(yè)平均周轉(zhuǎn)時間為63分鐘。10.參考答案:快表命中率為75%，缺頁中斷率為10%，所以，內(nèi)存命中率為15%。故內(nèi)存的有效存取時間=1×75%+2×15%+(5000+2)×10%=501.25微秒。11.參考答案: 己知空白文件目錄的每個目錄項占5個字節(jié)，而位示圖占用2000字節(jié)，也就是說2000字節(jié)可容納400個文件目錄項。當(dāng)空白文件目錄>400時，空白文件目錄大于位示圖。12.參考答案:邏輯地址211×24，故為15位。內(nèi)存大小為23×211=214B=16KB。13.參考答案: （1）Job1從投入到運行完成需110ms，Job2從投入到運行完成需90ms，Job3從投入到運行完成需110ms。 （2）CPU空閑時間段為：60ms至70ms，80ms至90ms，100ms至110ms。所以CPU利用率為（110-30）/110=72.7%。 （3）設(shè)備I1空閑時間段為：20ms至40ms，90ms至100ms，故I1的利用率為（110-30）/110=72.7%。設(shè)備I2空閑時間段為：30ms至50ms，故I2的利用率為（110-20）/110=81.8%。14.參考答案:可以，文件名中可以用插入多個“/”來模擬文件分層。例如/usu1/datafile/data1和/user1/datafile/data2。但在此操作系統(tǒng)中，這些僅僅是包含“/”的單個文件名。15.參考答案: 16.參考答案: （1）作業(yè)的物理塊數(shù)為3塊，使用FIFO為9次，9/12=75%。使用LRU為7次，7/12=58%。使用OPT為6次，6/12=50%。 作業(yè)的物理塊數(shù)為4塊，使用FIFO為6次，6/12=50%。使用LRU為6次，6/12=50%。使用OPT為5次，5/12=42%。 （2）作業(yè)的物理塊數(shù)為3塊，使用FIFO為9次，9/12=75%。使用LRU為10次，10/12=83%。使用OPT為7次，7/12=58%。 作業(yè)的物理塊數(shù)為4塊，使用FIFO為10次，10/12=83%。使用LRU為8次，8/12=66%。使用OPT為6次，6/12=50%。 其中，出現(xiàn)了Belady現(xiàn)象，增加分給作業(yè)的內(nèi)存塊數(shù)，反使缺頁中斷率上升。17.參考答案:(3)，(4)，(5)，(6)，(7)。18.參考答案: 系統(tǒng)處于安全狀態(tài)，存在安全序列：P0，P3，P4，P1，P2。19.參考答案: 當(dāng)兩個進程都執(zhí)行完第一步(都占用R1)?時，系統(tǒng)進入不安全狀態(tài)。這時無論哪個進程執(zhí)行完第二步，死鎖都會發(fā)生。可能到達的死鎖點：進程P1占有一個R1和一個R2，而進程P2占有一個R1?；蛘呦喾础＿@時己形成死鎖。進程資源圖為：20.參考答案: 21.參考答案: 位示圖占用字?jǐn)?shù)為500/32=16(向上取整)個字。22.參考答案: 按照最短作業(yè)優(yōu)先的算法可以使平均響應(yīng)時間最短。X取值不定，按照以下情況討論： 1）x≤3????次序為：x，3，5，6，9? 2）3<x≤5??次序為：3，x，5，6，9? 3）5<x≤6????次序為：3，5，x，6，9? 4）6<x≤9????次序為：3，5，6，x，9? 5）9<x???????次序為：3，5，6，9，x23.參考答案: 24.參考答案: 1）Q=∞???CPU利用率=T/（T+S 2）Q>T????CPU利用率=T/（T+S） 3）T>Q>S??CPU利用率=Q/（Q+S）? 4)?Q=S????CPU利用率=50%?5)?Q→0???CPU利用率→025.參考答案: SJF算法選中作業(yè)執(zhí)行的次序為：A、B、D、E和C。作業(yè)平均周轉(zhuǎn)時間為58分鐘。卷III參考答案一.參考題庫1.參考答案: ①、②、⑤和⑥是不相交語句，可以任何次序交錯執(zhí)行，而結(jié)果是唯一的。接著無論系統(tǒng)如何調(diào)度進程并發(fā)執(zhí)行，當(dāng)執(zhí)行到語句⑦時，可以得到x=10，y=4。按Bernstein條件，語句③的執(zhí)行結(jié)果不受語句⑦的影響，故語句③執(zhí)行后得到z=5。最后，語句④和⑧并發(fā)執(zhí)行，最后結(jié)果為：? 語句④先執(zhí)行：x=10，y=9，z=15。? 語句⑧先執(zhí)行：x=10，y=19，z=15。2.參考答案: 周轉(zhuǎn)時間：作業(yè)1為30分鐘、作業(yè)2為55分鐘、作業(yè)3為40分鐘、作業(yè)4為40分鐘和作業(yè)5為55分鐘。 平均作業(yè)周轉(zhuǎn)時間=44分鐘。3.參考答案: 系統(tǒng)四個進程需要使用的資源數(shù)為R1各2臺，R2各1臺?？梢娰Y源數(shù)不足，同時各進程申請資源在先，有可能產(chǎn)生死鎖發(fā)生的四個條件，故系統(tǒng)可能產(chǎn)生死鎖。4.參考答案: 5.參考答案: 定位第1個記錄需10ms。讀出第1個記錄，處理花2ms，這時已到了第4個記錄，再轉(zhuǎn)過18個記錄（花18ms）才能找到記錄2，所以，讀出并處理20個記錄的總時間： 10+3+（1+2+18）×19=13+21×19=412ms6.參考答案:采用成組方式存放，塊因子為2。由于共有18個邏輯記錄，故占用了9個物理塊，而第15號邏輯記錄占用的是第15/2=8(向上取整)物理塊。因為，是連續(xù)文件物理塊也是連續(xù)的，所以，該邏輯記錄占用的是12+8-1=19塊。所以，第15號邏輯記錄讀入內(nèi)存緩沖區(qū)的過程如下：根據(jù)塊因子，計算占用的相對物理塊號8；根據(jù)起始塊號為12，計算出絕對物理塊號19；把物理塊號19讀入內(nèi)存緩沖區(qū)；把所要的邏輯記錄分解出來。7.參考答案: 最大作業(yè)周轉(zhuǎn)時間為55分鐘。8.參考答案: 可以分配，存在安全序列：P2，P1，P3，P4。9.參考答案: 畫出三個作業(yè)并行工作圖如下（圖中著色部分為作業(yè)等待時間）： （1）Job1從投入到運行完成需80ms，Job2從投入到運行完成需90ms，Job3從投入到運行完成需90ms。 （2）CPU空閑時間段為：60ms至70ms，80ms至90ms。所以CPU利用率為（90-20）/90=77.78%。 （3）設(shè)備I1空閑時間段為：20ms至40ms，故I1的利用率為（90-20）/90=77.78%。設(shè)備I2空閑時間段為：30ms至50ms，故I2的利用率為（90-20）/90=77.78%。10.參考答案: （1）用信號量和P、V操作。 類似于課文中的答案，擴充如下：1）?同步信號量初值為2； 2）?要引進一個互斥信號量mutex，用于對盤子進行互斥； 3）盤子中每一項用橘子、蘋果2個枚舉值。 11.參考答案:當(dāng)m≤n時，每個進程最多請求1個這類資源時，系統(tǒng)一定不會發(fā)生死鎖。當(dāng)m>n時，如果m/n不整除，每個進程最多可以請求”商+1”個這類資源，否則為”商”個資源，使系統(tǒng)一定不會發(fā)生死鎖12.參考答案:由題意可知，內(nèi)存中可以存放3個用戶進程，而CPU的利用率為：1-(70%)3=1-(0.7)3=65.7%。再增加1M內(nèi)存，可增加2個用戶進程，這時CPU的利用率為：1-(70%)5=1-(0.7)5=83.2%。故再增加1M內(nèi)存，吞吐率增加了：83.2%÷65.7%-1