2024年大學(xué)試題(計(jì)算機(jī)科學(xué))-操作系統(tǒng)(CH1)考試近5年真題集錦（頻考類試題）帶答案

（圖片大小可自由調(diào)整）2024年大學(xué)試題(計(jì)算機(jī)科學(xué))-操作系統(tǒng)(CH1)考試近5年真題集錦（頻考類試題）帶答案第I卷一.參考題庫(共100題)1.文件系統(tǒng)的性能取決于高速緩存的命中率，從高速緩存讀取數(shù)據(jù)需要1ms，從磁盤讀取數(shù)據(jù)需要40ms。若命中率為h，給出讀取數(shù)據(jù)所需平均時(shí)間的計(jì)算公式，并畫出h從0到1變化時(shí)的函數(shù)曲線。2.若內(nèi)存中有3道程序A、B、C，它們按A、B、C優(yōu)先次序運(yùn)行。各程序的計(jì)算軌跡為：? A：計(jì)算（20）、I/O（30）、計(jì)算（10）??? B：計(jì)算（40）、I/O（20）、計(jì)算（10）? C://計(jì)算（10）、I/O（30）、計(jì)算（20）? 如果三道程序都使用相同設(shè)備進(jìn)行I/O（即程序用串行方式使用設(shè)備，調(diào)度開銷忽略不計(jì)）。試分別畫出單道和多道運(yùn)行的時(shí)間關(guān)系圖。兩種情況下，CPU的平均利用率各為多少？3.某磁盤共有100個(gè)柱面，每個(gè)柱面有8個(gè)磁頭，每個(gè)盤面分4個(gè)扇區(qū)。若邏輯記錄?與扇區(qū)等長，柱面、磁道、扇區(qū)均從0起編號?，F(xiàn)用16位的200個(gè)字（0-199）來組成位示圖來管理盤空間。問：位示圖第15個(gè)字的第7位為0而準(zhǔn)備分配給某一記錄，該塊的柱面號、磁道號、扇區(qū)號是多少？4.有一個(gè)分頁虛存系統(tǒng)，測得CPU和磁盤的利用率如下，試指出每種情況下的存在問題和可采取的措施： （1）CPU利用率為13%，磁盤利用率為97%?? （2）CPU利用率為87%，磁盤利用率為3%?? （3）CPU利用率為13%，磁盤利用率為3%5.若有如表所示四個(gè)作業(yè)進(jìn)入系統(tǒng)，分別計(jì)算在FCFS、SJF和HRRF算法下的平均周轉(zhuǎn)時(shí)間與帶權(quán)平均周轉(zhuǎn)時(shí)間。（時(shí)間以十進(jìn)制表示） 6.Kleinrock提出一種動(dòng)態(tài)優(yōu)先權(quán)算法：進(jìn)程在就緒隊(duì)列等待時(shí)，其優(yōu)先權(quán)以速率α變化；?當(dāng)進(jìn)程在處理器上運(yùn)行，時(shí)其優(yōu)先權(quán)以速率β變化。給參數(shù)α、β賦以不同值可得到不同算法。若α<β<0是什么算法？7.假設(shè)有一種低級調(diào)度算法是讓“最近使用處理器較少的進(jìn)程”運(yùn)行，試解釋這種算法對“I/O繁重”型作業(yè)有利，但并不是永遠(yuǎn)不受理“處理器繁重”型作業(yè)。8.系統(tǒng)有A、B、C、D共4種資源，在某時(shí)刻進(jìn)程P0、P1、P2、P3和P4對資源的占有和需求情況如表，試解答下列問題： 若此時(shí)P2發(fā)出request1（1、2、2、2），系統(tǒng)能分配資源給它嗎？為什么？9.在按動(dòng)態(tài)優(yōu)先數(shù)調(diào)度進(jìn)程的系統(tǒng)中，每個(gè)進(jìn)程的優(yōu)先數(shù)需定時(shí)重新計(jì)算。在處理器不斷地在進(jìn)程之間交替的情況下，重新計(jì)算進(jìn)程優(yōu)先數(shù)的時(shí)間從何而來？10.假定磁盤有200個(gè)柱面，編號0~199，當(dāng)前存取臂的位置在143號柱面上，并剛剛完成了125號柱面的服務(wù)請求，如果請求隊(duì)列的先后順序是：86，147，91，177，94，150，102，175，130；試問：為完成上述請求，下列算法存取臂移動(dòng)的總量是多少？并算出存取臂移動(dòng)的順序。電梯調(diào)度。11.一個(gè)32位地址的計(jì)算機(jī)系統(tǒng)使用二級頁表，虛地址被分為9位頂級頁表，11位二級頁表和偏移。試問：頁面長度是多少？虛地址空間共有多少個(gè)頁面？12.假定磁盤有200個(gè)柱面，編號0~199，當(dāng)前存取臂的位置在143號柱面上，并剛剛完成了125號柱面的服務(wù)請求，如果請求隊(duì)列的先后順序是：86，147，91，177，94，150，102，175，130；試問：為完成上述請求，下列算法存取臂移動(dòng)的總量是多少？并算出存取臂移動(dòng)的順序。掃描算法SCAN。13.一臺(tái)計(jì)算機(jī)的內(nèi)存空間為1024個(gè)頁面，頁表放在內(nèi)存中，從頁表中讀一個(gè)字的開銷是500ns。為了減少開銷，使用了有32個(gè)字的快表，查找速度為100ns。要把平均開銷降到200ns需要的快表命中率是多少？14.某計(jì)算機(jī)有4個(gè)頁框，每頁的裝入時(shí)間、最后訪問時(shí)間、訪問位R、修改位D如下所示（時(shí)間用時(shí)鐘點(diǎn)數(shù)表示）： 分別用FIFO、LRU、二次機(jī)會(huì)算法分別淘汰哪一頁？15.有一個(gè)磁盤組共有10個(gè)盤面，每個(gè)盤面有100個(gè)磁道，每個(gè)磁道有16個(gè)扇區(qū)。若以扇區(qū)為分配單位，問：若空白文件目錄的每個(gè)目錄項(xiàng)占5個(gè)字節(jié)，則什么時(shí)候空白文件目錄大于位示圖？16.在UNIX/Linux系統(tǒng)中，如果當(dāng)前目錄是/usr/wang，那么，相對路徑為‥/ast/xxx文件的絕對路徑名是什么？17.假設(shè)某虛存的用戶空間為1024KB，頁面大小為4KB，內(nèi)存空間為512KB。已知用戶的虛頁10、11、12、13頁分得內(nèi)存頁框號為62、78、25、36，求出虛地址0BEBC（16進(jìn)制）的實(shí)地址（16進(jìn)制）是多少？18.有5個(gè)批處理作業(yè)A到E均已到達(dá)計(jì)算中心，其運(yùn)行時(shí)間分別10、6、2、4和8分鐘；各自的優(yōu)先級分別被規(guī)定為3、5、2、1和4，這里5為最高級。若不考慮系統(tǒng)切換開銷，計(jì)算出平均作業(yè)周轉(zhuǎn)時(shí)間。 （1）FCFS（按A、B、C、D、E）； （2）優(yōu)先級調(diào)度算法； （3）時(shí)間片輪轉(zhuǎn)法（每個(gè)作業(yè)獲得相同的2分鐘長的時(shí)間片）。19.有一個(gè)分頁系統(tǒng)，其頁表存放在主存里 （1）如果對內(nèi)存的一次存取要1.2微秒，試問實(shí)現(xiàn)一次頁面訪問的存取需花多少時(shí)間？ （2）若系統(tǒng)配置了聯(lián)想存儲(chǔ)器，命中率為80×%，假定頁表表目在聯(lián)想存儲(chǔ)器的查找時(shí)間忽略不計(jì)，試問實(shí)現(xiàn)一次頁面訪問的存取時(shí)間是多少？20.在一個(gè)請求分頁虛擬存儲(chǔ)管理系統(tǒng)中，一個(gè)程序運(yùn)行的頁面走向是：??????? 1、2、3、4、2、1、5、6、2、1、2、3、7、6、3、2、1、2、3、6。? 分別用FIFO、OPT和LRU算法，對分配給程序3個(gè)頁框、4個(gè)頁框、5個(gè)頁框和6個(gè)頁框的情況下，分別求出缺頁中斷次數(shù)和缺頁中斷率。21.有一臺(tái)計(jì)算機(jī)，具有1MB內(nèi)存，操作系統(tǒng)占用200KB，每個(gè)用戶進(jìn)程各占200KB。如果用戶進(jìn)程等待I/O的時(shí)間為80%，若增加1MB內(nèi)存，則CPU的利用率提高多少？22.有一個(gè)具有兩道作業(yè)的批處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先的調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，在下表所示的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。 （1）列出所有作業(yè)進(jìn)入內(nèi)存時(shí)間及結(jié)束時(shí)間。? （2）計(jì)算平均周轉(zhuǎn)時(shí)間。23.設(shè)某文件為連接文件，由5個(gè)邏輯記錄組成，每個(gè)邏輯記錄的大小與磁盤塊大小相等，均為512字節(jié)，并依次存放在50、121、75、80、63號磁盤塊上。若要存取文件的第1569邏輯字節(jié)處的信息，問要訪問哪一個(gè)磁盤塊？?24.一個(gè)頁式存儲(chǔ)管理系統(tǒng)使用FIFO、OPT和LRU頁面替換算法，如果一個(gè)作業(yè)的頁面走向?yàn)椋? （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時(shí)，試計(jì)算訪問過程中發(fā)生的缺頁中斷次數(shù)和缺頁中斷率。25.在信號量S上作P、V操作時(shí)，S的值發(fā)生變化，當(dāng)S＞0、S=0、S<0時(shí)，它們的物理意義是什么？26.考慮下列的段表： 段號????????始址???????????段長? 0???????????200????????????500? 1???????????890????????????30? 2???????????120????????????100? 3??????????1250????????????600? 4??????????1800????????????88?? 對下面的邏輯地址，求物理地址，如越界請指明。1）??2）?3）?4）?5）??6）。27.在一個(gè)盒子里，混裝了數(shù)量相等的黑白圍棋子。現(xiàn)在用自動(dòng)分揀系統(tǒng)把黑子、白子分開，設(shè)分揀系統(tǒng)有二個(gè)進(jìn)程P1和P2，其中P1揀白子；P2揀黑子。規(guī)定每個(gè)進(jìn)程每次揀一子；當(dāng)一個(gè)進(jìn)程在揀時(shí)，不允許另一個(gè)進(jìn)程去揀；當(dāng)一個(gè)進(jìn)程揀了一子時(shí)，必須讓另一個(gè)進(jìn)程去揀。試寫出兩進(jìn)程P1和P2能并發(fā)正確執(zhí)行的程序。28.有5個(gè)待運(yùn)行的作業(yè)，各自預(yù)計(jì)運(yùn)行時(shí)間分別是：9、6、3、5和x，采用哪種運(yùn)行次序使得平均響應(yīng)時(shí)間最短？29.設(shè)當(dāng)前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時(shí)Available=（1，1，2）：P2發(fā)出請求向量request1（1，0，1），系統(tǒng)能把資源分給它嗎？30.設(shè)某個(gè)文件系統(tǒng)的文件目錄中，指示文件數(shù)據(jù)塊的索引表長度為13，其中0到9項(xiàng)為直接尋址方式，后3項(xiàng)為間接尋址方式。試描述出文件數(shù)據(jù)塊的索引方式；給出對文件第n個(gè)字節(jié)（設(shè)塊長512字節(jié)）的尋址算法．31.在UNIX?中，如果一個(gè)盤塊的大小為1KB，每個(gè)盤塊號占4個(gè)字節(jié)，即每塊可放256個(gè)地址。請轉(zhuǎn)換下列文件的字節(jié)偏移量為物理地址：（1）9999；（2）18000；（3）420000。32.某操作系統(tǒng)的磁盤文件空間共有500塊，若用字長為32位的位示圖管理盤空間并給出申請/歸還一塊的工作流程。33.某系統(tǒng)有R1設(shè)備3臺(tái)，R2設(shè)備4臺(tái)，它們被P1、P2、P3和P4進(jìn)程共享，且已知這4個(gè)進(jìn)程均按以下順序使用設(shè)備：→申請R1→申請R2→申請R1→釋放R1→釋放R2→釋放R1若可能的話，請舉出一種情況，并畫出表示該死鎖狀態(tài)的進(jìn)程—資源圖。34.請頁式存儲(chǔ)管理中，進(jìn)程訪問地址序列為：10，11，104，170，73，305，180，240，244，445，467，366。如果頁面大小為100，給出頁面訪問序列。35.給定段表如下： 給定地址為段號和位移：1）[0，430]、2）[3，400]、3）[1，1]、4）[2，500]、5）[4，42]，試求出對應(yīng)的內(nèi)存物理地址。36.設(shè)有三道程序，按A、B、C優(yōu)先次序運(yùn)行，其內(nèi)部計(jì)算和I/O操作時(shí)間由圖給出。 試畫出按多道運(yùn)行的時(shí)間關(guān)系圖（忽略調(diào)度執(zhí)行時(shí)間）。完成三道程序共花多少時(shí)間？比單道運(yùn)行節(jié)省了多少時(shí)間？若處理器調(diào)度程序每次進(jìn)行程序轉(zhuǎn)換化時(shí)1ms，試畫出各程序狀態(tài)轉(zhuǎn)換的時(shí)間關(guān)系圖。37.有一具有40個(gè)磁道的盤面，編號為0~39，當(dāng)磁頭位于第11磁道時(shí)，順序來到如下磁道請求：磁道號：1、36、16、34、9、12； 試用1）先來先服務(wù)算法FCFS 2）最短查找時(shí)間優(yōu)先算法SSTF 3）掃描算法SCAN等三種磁盤驅(qū)動(dòng)調(diào)度算法，計(jì)算出它們各自要來回穿越多少磁道？38.下列指令中哪些只能在核心態(tài)運(yùn)行？? （1）讀時(shí)鐘日期； （2）訪管指令； （3）設(shè)時(shí)鐘日期； （4）加載PSW； （5）置特殊寄存器； （6）改變存儲(chǔ)器映象圖； （7）啟動(dòng)I/O指令。39.設(shè)有一頁式存儲(chǔ)管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁，每頁2048字節(jié)，內(nèi)存總共有8個(gè)存儲(chǔ)塊。試問邏輯地址至少應(yīng)為多少位？內(nèi)存空間有多大？40.（1）兩個(gè)并發(fā)進(jìn)程并發(fā)執(zhí)行，其中，A、B、C、D、E是原語，試給出可能的并發(fā)執(zhí)行路徑。? Process?P?????????????Process?Q? begin?????????????????begin? ?????????????A；??????????????????D； ?????????????B；??????????????????E； ?????????????C；???????????????end； ??????????end；? （2）?兩個(gè)并發(fā)進(jìn)程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í)行兩個(gè)循環(huán)，然后，P1和P2又并發(fā)執(zhí)行了一個(gè)循環(huán)，寫出可能的打印值，指出與時(shí)間有關(guān)的錯(cuò)誤。41.除FCFS外，所有磁盤調(diào)度算法都不公平，如造成有些請求饑餓，試分析為什么公平性在分時(shí)系統(tǒng)中是一個(gè)很重要的指標(biāo)？42.某多道程序設(shè)計(jì)系統(tǒng)采用可變分區(qū)內(nèi)存管理，供用戶使用的主存為200K，磁帶機(jī)5臺(tái)。采用靜態(tài)方式分配外圍設(shè)備，且不能移動(dòng)在主存中的作業(yè)，忽略用戶作業(yè)I/O時(shí)間?，F(xiàn)有作業(yè)序列如下： FIFO算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時(shí)間？43.有5個(gè)批處理作業(yè)A到E均已到達(dá)計(jì)算中心，其運(yùn)行時(shí)間分別2、4、6、8和10分鐘；各自的優(yōu)先級分別被規(guī)定為1、2、3、4和5，這里5為最高級。對于1）時(shí)間片輪轉(zhuǎn)算法、2）優(yōu)先數(shù)法、3）短作業(yè)優(yōu)先算法、4）先來先服務(wù)調(diào)度算法（按到達(dá)次序C、D、B、E、A），在忽略進(jìn)程切換時(shí)間的前提下，計(jì)算出平均作業(yè)周轉(zhuǎn)時(shí)間。（對1）每個(gè)作業(yè)獲得相同的2分鐘長的時(shí)間片；對2）到4）采用單道運(yùn)行，直到結(jié)束。）44.除FCFS外，所有磁盤調(diào)度算法都不公平，如造成有些請求饑餓，試分析為什么不公平？45.（1）假定一個(gè)處理器正在執(zhí)行兩道作業(yè)，一道以計(jì)算為主，另一道以輸入輸出為主，你將怎樣賦予它們占有處理器的優(yōu)先級？為什么？? （2）假定一個(gè)處理器正在執(zhí)行三道作業(yè)，一道以計(jì)算為主，第二道以輸入輸出為主，第三道為計(jì)算與輸入輸出均勻。應(yīng)該如何賦予它們占有處理器的優(yōu)先級使得系統(tǒng)效率較高？46.在單CPU和兩臺(tái)I/O(I1,I2)設(shè)備的多道程序設(shè)計(jì)環(huán)境下，同時(shí)投入三個(gè)作業(yè)運(yùn)行。它們的執(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)每個(gè)作業(yè)從投入到完成分別所需的時(shí)間。 (2)?每個(gè)作業(yè)投入到完成CPU的利用率。 (3)I/O設(shè)備利用率。47.有兩個(gè)優(yōu)先級相同的進(jìn)程P1和P2，各自執(zhí)行的操作如下，信號量S1和S2初值均為0。試問P1、P2并發(fā)執(zhí)行后，x、y、z的值各為多少？ 48.某請求分頁存儲(chǔ)系統(tǒng)使用一級頁表，假設(shè)頁表全部放在主存內(nèi)：若一次訪問主存花120ns，那么，訪問一個(gè)數(shù)據(jù)的時(shí)間是多少？49.若兩個(gè)用戶共享一個(gè)文件系統(tǒng)，用戶甲使用文件A、B、C、D、E；用戶乙要用到文件A、D、E、F。己知用戶甲的文件A與用戶乙的文件A實(shí)際上不是同一文件；甲、乙兩用戶的文件D和E正是同一文件。試設(shè)計(jì)一種文件系統(tǒng)組織方案，使得甲、乙兩用戶能共享該文件系統(tǒng)又不致造成混亂。50.給定內(nèi)存空閑分區(qū)，按地址從小到大為：100K、500K、200K、300K和600K。現(xiàn)有用戶進(jìn)程依次分別為212K、417K、112K和426K，（1）分別用first-fit、best-fit和worst-fit算法將它們裝入到內(nèi)存的哪個(gè)分區(qū)？ （2）哪個(gè)算法能最有效利用內(nèi)存？51.某系統(tǒng)有R1設(shè)備3臺(tái)，R2設(shè)備4臺(tái)，它們被P1、P2、P3和P4進(jìn)程共享，且已知這4個(gè)進(jìn)程均按以下順序使用設(shè)備：→申請R1→申請R2→申請R1→釋放R1→釋放R2→釋放R1系統(tǒng)運(yùn)行中可能產(chǎn)生死鎖嗎？為什么？52.某多道程序設(shè)計(jì)系統(tǒng)供用戶使用的主存為100K，磁帶機(jī)2臺(tái)，打印機(jī)1臺(tái)。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)I/O時(shí)間。現(xiàn)有作業(yè)序列如下： 作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配主存低地址區(qū)且不準(zhǔn)移動(dòng)已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時(shí)間。全部作業(yè)運(yùn)行結(jié)束的時(shí)間？53.設(shè)有n個(gè)進(jìn)程共享一個(gè)互斥段，如果：? （1）每次只允許一個(gè)進(jìn)程進(jìn)入互斥段；? （2）每次最多允許m個(gè)進(jìn)程（m≤n）同時(shí)進(jìn)入互斥段。? 試問：所采用的信號量初值是否相同？信號量值的變化范圍如何？54.有矩陣：VAR??A：ARRAY[1‥100，1‥100]??OF??integer；元素按行存儲(chǔ)。在一虛存系統(tǒng)中，采用LRU淘汰算法，一個(gè)進(jìn)程有3頁內(nèi)存空間，每頁可以存放200個(gè)整數(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í)行進(jìn)程計(jì)算缺頁次數(shù)。55.并發(fā)進(jìn)程之間有什么樣的相互制約關(guān)系？下列日常生活中的活動(dòng)是屬哪種制約關(guān)系： （1）踢足球 （2）吃自助餐 （3）圖書館借書 （4）電視機(jī)生產(chǎn)流水線工序56.某多道程序設(shè)計(jì)系統(tǒng)供用戶使用的主存為100K，磁帶機(jī)2臺(tái)，打印機(jī)1臺(tái)。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)I/O時(shí)間?，F(xiàn)有作業(yè)序列如下： 作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配主存低地址區(qū)且不準(zhǔn)移動(dòng)已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時(shí)間。最大作業(yè)周轉(zhuǎn)時(shí)間為多少？57.Kleinrock提出一種動(dòng)態(tài)優(yōu)先權(quán)算法：進(jìn)程在就緒隊(duì)列等待時(shí)，其優(yōu)先權(quán)以速率α變化；?當(dāng)進(jìn)程在處理器上運(yùn)行，時(shí)其優(yōu)先權(quán)以速率β變化。給參數(shù)α、β賦以不同值可得到不同算法。若α>β>0是什么算法？58.若磁頭的當(dāng)前位置為100柱面，磁頭正向磁道號減小方向移動(dòng)?，F(xiàn)有一磁盤讀寫請求隊(duì)列，柱面號依次為：190，10，160，80，90，125，30，20，29，140，25。若采用最短尋道時(shí)間優(yōu)先和電梯調(diào)度算法，試計(jì)算出各種算法的移臂經(jīng)過的柱面數(shù)？59.對某系統(tǒng)進(jìn)行監(jiān)測后表明平均每個(gè)進(jìn)程在I/O阻塞之前的運(yùn)行時(shí)間為T。一次進(jìn)程切換的系統(tǒng)開銷時(shí)間為S。若采用時(shí)間片長度為Q的時(shí)向片輪轉(zhuǎn)法，對下列各種情況算出CPU利用率。 1）Q＝∞??? 2）Q＞T??? 3）S＜Q＜T???? 4）Q＝S??? 5）Q接近于060.除FCFS外，所有磁盤調(diào)度算法都不公平，如造成有些請求饑餓，試分析提出一種公平性調(diào)度算法。61.另一個(gè)經(jīng)典同步問題：吸煙者問題（patil，1971）。三個(gè)吸煙者在一個(gè)房間內(nèi)，還有一個(gè)香煙供應(yīng)者。為了制造并抽掉香煙，每個(gè)吸煙者需要三樣?xùn)|西：煙草、紙和火柴，供應(yīng)者有豐富貨物提供。三個(gè)吸煙者中，第一個(gè)有自己的煙草，第二個(gè)有自己的紙和第三個(gè)有自己的火柴。供應(yīng)者隨機(jī)地將兩樣?xùn)|西放在桌子上，允許一個(gè)吸煙者進(jìn)行對健康不利的吸煙。當(dāng)吸煙者完成吸煙后喚醒供應(yīng)者，供應(yīng)者再把兩樣?xùn)|西放在桌子上，喚醒另一個(gè)吸煙者。試采用：（1）信號量和P、V操作，（2）管程編寫他們同步工作的程序。62.假定磁盤有200個(gè)柱面，編號0~199，當(dāng)前存取臂的位置在143號柱面上，并剛剛完成了125號柱面的服務(wù)請求，如果請求隊(duì)列的先后順序是：86，147，91，177，94，150，102，175，130；試問：為完成上述請求，下列算法存取臂移動(dòng)的總量是多少？并算出存取臂移動(dòng)的順序。先來先服務(wù)算法FCFS；63.設(shè)當(dāng)前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時(shí)Available=（1，1，2）：計(jì)算各個(gè)進(jìn)程還需要的資源數(shù)Cki-Aki？64.考慮下面的程序： for?（i=0；i<20；i++）? ??????????????for（j=0；j<10；j++） ??????????????a[i]：=a[i]×j 試舉例說明該程序的空間局部性和時(shí)間局部性。65.桌上有一只盤子，最多可以容納兩個(gè)水果，每次僅能放入或取出一個(gè)水果。爸爸向盤子中放蘋果（apple），媽媽向盤子中放桔子（orange），兩個(gè)兒子專等吃盤子中的桔子，兩個(gè)女兒專等吃盤子中的蘋果。試用：（1）信號量和P、V操作，（2）管程，來實(shí)現(xiàn)爸爸、媽媽、兒子、女兒間的同步與互斥關(guān)系。66.把死鎖檢測算法用于下面的數(shù)據(jù)，并請問：此時(shí)系統(tǒng)此時(shí)處于安全狀態(tài)嗎？67.在一個(gè)請求分頁虛擬存儲(chǔ)管理系統(tǒng)中，一個(gè)作業(yè)共有5頁，執(zhí)行時(shí)其訪問頁面次序?yàn)椋?（1）1、4、3、1、2、5、1、4、2、1、4、5。? （2）3、2、1、4、4、5、5、3、4、3、2、1、5。? 若分配給該作業(yè)三個(gè)頁框，分別采用FIFO和LRU面替換算法，求出各自的缺頁中斷次數(shù)和缺頁中斷率。68.設(shè)當(dāng)前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時(shí)Available=（1，1，2）：系統(tǒng)是否處于安全狀態(tài)，為什么？69.一進(jìn)程以下列次序訪問5個(gè)頁：A、B、C、D、A、B、E、A、B、C、D、E；假定使用FIFO替換算法，在內(nèi)存有3個(gè)和4個(gè)空閑頁框的情況下，分別給出頁面替換次數(shù)。70.單道批處理系統(tǒng)中，下列三個(gè)作業(yè)采用先來先服務(wù)調(diào)度算法和最高響應(yīng)比優(yōu)先算法進(jìn)行調(diào)度，哪一種算法性能較好？請完成下表： 71.一個(gè)計(jì)算機(jī)系統(tǒng)有足夠的內(nèi)存空間存放4道程序，這些程序有一半時(shí)間在空閑等待I/O操作。問多大比例的CPU時(shí)間被浪費(fèi)掉了？72.某計(jì)算機(jī)系統(tǒng)提供24位虛存空間，主存為218B，采用分頁式虛擬存儲(chǔ)管理，頁面尺寸為1KB。假定用戶程序產(chǎn)生了虛擬地址11123456（八進(jìn)制），而該頁面分得塊號為100（八進(jìn)制），說明該系統(tǒng)如何產(chǎn)生相應(yīng)的物理地址及寫出物理地址。 虛擬地址11123456（八進(jìn)制）轉(zhuǎn)化為二進(jìn)制為：????????????????? 001?001?001?010?011?100?101?110? 其中前面為頁號，而后10位為位移：001?001?001?010?011?100?101?110。由于主存大小為218B，頁面尺寸為1KB，所以，主存共有256塊。所以，塊號為100（八進(jìn)制）是合法地址，于是，物理地址為100與位移1?100?101?110并接，得到：八進(jìn)制物理地址100?1?100?101?110。 13主存中有兩個(gè)空間區(qū)如圖所示， 現(xiàn)有作業(yè)序列依次為：Job1要求30K；Job2要求70K；Job3要求50K；使用首次適應(yīng)、最壞適應(yīng)和最佳適應(yīng)算法處理這個(gè)作業(yè)序列，試問哪種算法可以滿足分配？為什么？73.某操作系統(tǒng)的磁盤文件空間共有500塊，若用字長為32位的位示圖管理盤空間第i字第j位對應(yīng)的塊號是多少？74.有P1、P2、P3三個(gè)進(jìn)程共享一個(gè)表格F，P1對F只讀不寫，P2對F只寫不讀，P3對F先讀后寫。進(jìn)程可同時(shí)讀F，但有進(jìn)程寫時(shí)，其他進(jìn)程不能讀和寫。用（1）信號量和P、V操作，（2）管程編寫三進(jìn)程能正確工作的程序。75.若后備作業(yè)隊(duì)列中等待運(yùn)行的同時(shí)有三個(gè)作業(yè)J1、J2、J3，已知它們各自的運(yùn)行時(shí)間為a、b、c，且滿足a<b<c，試證明采用短作業(yè)優(yōu)先算法調(diào)度能獲得最小平均作業(yè)周轉(zhuǎn)時(shí)間。76.假定磁盤有200個(gè)柱面，編號0~199，當(dāng)前存取臂的位置在143號柱面上，并剛剛完成了125號柱面的服務(wù)請求，如果請求隊(duì)列的先后順序是：86，147，91，177，94，150，102，175，130；試問：為完成上述請求，下列算法存取臂移動(dòng)的總量是多少？并算出存取臂移動(dòng)的順序。最短查找時(shí)間優(yōu)先算法SSTF；77.若內(nèi)存中有3道程序A、B、C，優(yōu)先級從高到低為A、B和C，它們單獨(dú)運(yùn)行時(shí)的CPU和I/O占用時(shí)間為： 如果三道程序同時(shí)并發(fā)執(zhí)行，調(diào)度開銷忽略不計(jì)，但優(yōu)先級高的程序可中斷優(yōu)先級低的程序，優(yōu)先級與I/O設(shè)備無關(guān)。試畫出多道運(yùn)行的時(shí)間關(guān)系圖，并問最早與最遲結(jié)束的程序是哪個(gè)？每道程序執(zhí)行到結(jié)束分別用了多少時(shí)間？計(jì)算三個(gè)程序全部運(yùn)算結(jié)束時(shí)的CPU利用率？78.在一分頁存儲(chǔ)管理系統(tǒng)中，邏輯地址長度為16位，頁面大小為4096字節(jié)，現(xiàn)有一邏輯地址為2F6AH，且第0、1、2頁依次存在物理塊10、12、14號中，問相應(yīng)的物理地址為多少？79.設(shè)當(dāng)前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時(shí)Available=（1，1，2）：若在P2申請資源后，若P1發(fā)出請求向量request0（1，0，1），系統(tǒng)能把資源分給它嗎？80.假定執(zhí)行表中所列作業(yè)，作業(yè)號即為到達(dá)順序，依次在時(shí)刻0按次序1、2、3、4、5進(jìn)入單處理器系統(tǒng)。? 1）分別用先來先服務(wù)調(diào)度算法、時(shí)間片輪轉(zhuǎn)算法、短作業(yè)優(yōu)先算法及非強(qiáng)占優(yōu)先權(quán)調(diào)度算法算出各作業(yè)的執(zhí)行先后次序（注意優(yōu)先權(quán)高的數(shù)值?。?； 2）計(jì)算每種情況下作業(yè)的平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間。 81.旋轉(zhuǎn)型設(shè)備上信息的優(yōu)化分布能減少為若干個(gè)I/O服務(wù)的總時(shí)間。設(shè)磁鼓上分為20個(gè)區(qū)，每區(qū)存放一個(gè)記錄，磁鼓旋轉(zhuǎn)一周需20毫秒，讀出每個(gè)記錄平均需用1毫秒，讀出后經(jīng)2毫秒處理，再繼續(xù)處理下一個(gè)記錄。在不知當(dāng)前磁鼓位置的情況下：給出優(yōu)先分布20個(gè)記錄的一種方案，使得所花的總處理時(shí)間減少，且計(jì)算出這個(gè)方案所花的總時(shí)間。82.某多道程序設(shè)計(jì)系統(tǒng)供用戶使用的主存為100K，磁帶機(jī)2臺(tái)，打印機(jī)1臺(tái)。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)I/O時(shí)間?，F(xiàn)有作業(yè)序列如下： 作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配主存低地址區(qū)且不準(zhǔn)移動(dòng)已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時(shí)間。作業(yè)平均周轉(zhuǎn)時(shí)間為多少？83.N個(gè)進(jìn)程共享M個(gè)資源，每個(gè)進(jìn)程一次只能申請/釋放一個(gè)資源，每個(gè)進(jìn)程最多需要M個(gè)資源，所有進(jìn)程總共的資源需求少于M+N個(gè)，證明該系統(tǒng)此時(shí)不會(huì)產(chǎn)生死鎖。?84.若某操作系統(tǒng)僅支持單級目錄，但允許該目錄有任意多個(gè)文件，且文件名可任意長，試問能否模擬一個(gè)層次式文件系統(tǒng)？如能的話，如何模擬。85.某多道程序設(shè)計(jì)系統(tǒng)采用可變分區(qū)內(nèi)存管理，供用戶使用的主存為200K，磁帶機(jī)5臺(tái)。采用靜態(tài)方式分配外圍設(shè)備，且不能移動(dòng)在主存中的作業(yè)，忽略用戶作業(yè)I/O時(shí)間?，F(xiàn)有作業(yè)序列如下： SJF算法選中作業(yè)執(zhí)行的次序及作業(yè)平均周轉(zhuǎn)時(shí)間？86.在虛擬頁式存儲(chǔ)管理中，為解決抖動(dòng)問題，可采用工作集模型以決定分給進(jìn)程的物理塊數(shù)，有如下頁面訪問序列： 窗口尺寸△＝9，試求t1、t2時(shí)刻的工作集。87.設(shè)一個(gè)文件由100個(gè)物理塊組成，對于連續(xù)文件、連接文件和索引文件，分別計(jì)算執(zhí)行下列操作時(shí)的啟動(dòng)磁盤I/O次數(shù)（假如頭指針和索引表均在內(nèi)存中）： （1）把一塊加在文件的開頭； （2）把一塊加在文件的中間（第51塊）； （3）把一塊加在文件的末尾； （4）從文件的開頭刪去一塊； （5）從文件的中間（第51塊）刪去一塊； （6）從文件的未尾刪去一塊。88.有一個(gè)磁盤組共有10個(gè)盤面，每個(gè)盤面有100個(gè)磁道，每個(gè)磁道有16個(gè)扇區(qū)。若以扇區(qū)為分配單位，問：用位示圖管理磁盤空間，則位示圖占用多少空間？89.一個(gè)UNIX/Linux文件，如果一個(gè)盤塊的大小為1KB，每個(gè)盤塊占4個(gè)字節(jié)，那么，若進(jìn)程欲訪問偏移為263168字節(jié)處的數(shù)據(jù)，需經(jīng)過幾次間接？90.系統(tǒng)有同類資源m個(gè)，被n個(gè)進(jìn)程共享，問：當(dāng)m＞n和m≤n時(shí)，每個(gè)進(jìn)程最多可以請求多少個(gè)這類資源時(shí)，使系統(tǒng)一定不會(huì)發(fā)生死鎖？91.旋轉(zhuǎn)型設(shè)備上信息的優(yōu)化分布能減少為若干個(gè)I/O服務(wù)的總時(shí)間。設(shè)磁鼓上分為20個(gè)區(qū)，每區(qū)存放一個(gè)記錄，磁鼓旋轉(zhuǎn)一周需20毫秒，讀出每個(gè)記錄平均需用1毫秒，讀出后經(jīng)2毫秒處理，再繼續(xù)處理下一個(gè)記錄。在不知當(dāng)前磁鼓位置的情況下：順序存放記錄1、……，記錄20時(shí)，試計(jì)算讀出并處理20個(gè)記錄的總時(shí)間；92.如果一個(gè)索引節(jié)點(diǎn)為128B，指針長4B，狀態(tài)信息占用68B，而每塊大小為8KB。問在索引節(jié)點(diǎn)中有多大空間給指針？使用直接、一次間接、二次間接和三次間接指針分別可表示多大的文件？93.把死鎖檢測算法用于下面的數(shù)據(jù)，并請問：若第五個(gè)進(jìn)程提出資源請求request5（0，0，1，0），系統(tǒng)能分配資源給它嗎？94.磁帶卷上記錄了若干文件，假定當(dāng)前磁頭停在第j個(gè)文件的文件頭標(biāo)前，現(xiàn)要按名讀出文件i，試給出讀出文件i的步驟。95.假定某計(jì)算機(jī)系統(tǒng)有R1和R2兩類可再使用資源（其中R1有兩個(gè)單位，R2有一個(gè)單位），它們被進(jìn)程P1，P2所共享，且已知兩個(gè)進(jìn)程均以下列順序使用兩類資源。????????????? →申請R1→申請R2→申請R1→釋放R1→釋放R2→釋放R1→? 試求出系統(tǒng)運(yùn)行過程中可能到達(dá)的死鎖點(diǎn)，并畫出死鎖點(diǎn)的資源分配圖（或稱進(jìn)程－資源圖）。96.在可變分區(qū)存儲(chǔ)管理下，按地址排列的內(nèi)存空閑區(qū)為：10K、4K、20K、18K、7K、9K、12K和15K。對于下列的連續(xù)存儲(chǔ)區(qū)的請求：（1）12K、10K、9K，（2）12K、10K、15K、18K試問：使用首次適應(yīng)算法、最佳適應(yīng)算法、最差適應(yīng)算法和下次適應(yīng)算法，哪個(gè)空閑區(qū)被使用？97.有一個(gè)四道作業(yè)的操作系統(tǒng)，若在一段時(shí)間內(nèi)先后到達(dá)6個(gè)作業(yè)，它們的提交和估計(jì)運(yùn)行時(shí)間由下表給出： 系統(tǒng)采用SJF調(diào)度算法，作業(yè)被調(diào)度進(jìn)入系統(tǒng)后中途不會(huì)退出，但作業(yè)運(yùn)行時(shí)可被更短作業(yè)搶占。 （1）分別給出6個(gè)作業(yè)的執(zhí)行時(shí)間序列、即開始執(zhí)行時(shí)間、作業(yè)完成時(shí)間、作業(yè)周轉(zhuǎn)時(shí)間。 （2）計(jì)算平均作業(yè)周轉(zhuǎn)時(shí)間。98.現(xiàn)有如下請求隊(duì)列：8，18，27，129，110，186，78，147，41，10，64，12；試用查找時(shí)間最短優(yōu)先算法計(jì)算處理所有請求移動(dòng)的總柱面數(shù)。假設(shè)磁頭當(dāng)前位置下在磁道100。99.請頁式存儲(chǔ)管理中，進(jìn)程訪問地址序列為：10，11，104，170，73，305，180，240，244，445，467，366。進(jìn)程若分得3個(gè)頁框，采用FIFO和LRU替換算法，求缺頁中斷率？100.請你設(shè)計(jì)一種先進(jìn)的計(jì)算機(jī)體系結(jié)構(gòu)，它使用硬件而不是中斷來完成進(jìn)程切換，則CPU需要哪些信息？?請描述用硬件完成進(jìn)程切換的工作過程。第I卷參考答案一.參考題庫1.參考答案： 讀取數(shù)據(jù)所需平均時(shí)間T=h×1+40×(1-h)=h+40×(1-h)。2.參考答案： 分別畫出單道和多道運(yùn)行的時(shí)間圖? 單道運(yùn)行時(shí)間關(guān)系圖 單道總運(yùn)行時(shí)間為190ms。CPU利用率為（190-80）/190=57.9% 多道運(yùn)行時(shí)間關(guān)系圖 多道總運(yùn)行時(shí)間為140ms。CPU利用率為（140-30）/140=78.6%3.參考答案： 位示圖第15個(gè)字的第7位對應(yīng)的塊號=15×16（字長）+7=247，而塊號247對應(yīng)的： 柱面號=247/（8×4）=7（從0編號，向下取整） 磁頭號=（247?MOD?32）/4=5 扇區(qū)號=247?MOD?32?MOD?4=34.參考答案： （1）系統(tǒng)可能出現(xiàn)抖動(dòng)，可把暫停部分進(jìn)程運(yùn)行。 （2）系統(tǒng)運(yùn)行正常，可增加運(yùn)行進(jìn)程數(shù)以進(jìn)一步提高資源利用率。 （3）處理器和設(shè)備和利用率均很低，可增加并發(fā)運(yùn)行的進(jìn)程數(shù)。5.參考答案： 6.參考答案： 是后進(jìn)先出算法。因?yàn)樵诰途w隊(duì)列中的進(jìn)程比在CPU上運(yùn)行的進(jìn)程的優(yōu)先權(quán)下降得快，故后進(jìn)入就緒隊(duì)列的進(jìn)程此先進(jìn)入的進(jìn)程的優(yōu)先權(quán)高。7.參考答案：因?yàn)镮/O繁忙型作業(yè)忙于I/O，所以它CPU用得少，按調(diào)度策略能優(yōu)先執(zhí)行。同樣原因一個(gè)進(jìn)程等待CPU足夠久時(shí)，由于它是“最近使用處理器較少的進(jìn)程”，就能被優(yōu)先調(diào)度，故不會(huì)饑餓。8.參考答案： 不能分配，否則系統(tǒng)會(huì)處于不安全狀態(tài)。9.參考答案：許多操作系統(tǒng)重新計(jì)算進(jìn)程的優(yōu)先數(shù)在時(shí)鐘中斷處理例程中進(jìn)行，由于中斷是隨機(jī)的，碰到哪個(gè)進(jìn)程，就插入哪個(gè)進(jìn)程中運(yùn)行處理程序，并把處理時(shí)間記在這個(gè)進(jìn)程的賬上。10.參考答案： 電梯調(diào)度為125(先向地址大的方向)，依次為143-147-150-175-177-102-94-91-86。為148(先向地址小的方向)?依次為143-130-102-94-91-86-147-150-175-177。11.參考答案：由于32-9-11=12，所以，頁面大小為4KB，頁面的個(gè)數(shù)為220個(gè)。12.參考答案： 掃描算法SCAN為169，依次為143-147-150-175-177-199-130-102-94-91-86。13.參考答案：設(shè)快表命中率是x，則內(nèi)存命中率為1-x。于是：500(1-x)+100x=200,解方程得x=75%。14.參考答案： （1）FIFO??淘汰page2。 （2）LRU??淘汰page1。 （3）二次機(jī)會(huì)??淘汰page0。15.參考答案： 己知空白文件目錄的每個(gè)目錄項(xiàng)占5個(gè)字節(jié)，而位示圖占用2000字節(jié)，也就是說2000字節(jié)可容納400個(gè)文件目錄項(xiàng)。當(dāng)空白文件目錄>400時(shí)，空白文件目錄大于位示圖。16.參考答案：在UNIX/Linux系統(tǒng)中，“/”表示根目錄，“．”是指當(dāng)前目錄，“‥”?是指父目錄。在本題中當(dāng)前目錄是/usr/wang，故相對路徑為‥/ast/xxx文件實(shí)際上是usr目錄下的文件，故絕對路徑名是/usr/ast/xxx。17.參考答案：虛地址0BEBC(16進(jìn)制)的二進(jìn)制形式為：0000?1011?1110?1011?1100。由于頁面大小為4KB，故其中后12位是位移，所以，虛地址的頁號為：11。查頁表分得內(nèi)存對應(yīng)頁框號為：78。已知內(nèi)存空間為512KB，故內(nèi)存共有128個(gè)頁框，78是合法物理塊。把78化為16進(jìn)制是4E，虛地址0BEBC(16進(jìn)制)的實(shí)地址(16進(jìn)制)是：4EEBC。18.參考答案： 19.參考答案： （1）2.4微秒 （2）0.8×1.2+0.2×2.4=0.76+0.48=1.24微秒20.參考答案： 只要把表中缺頁中斷次數(shù)除以20，便得到缺頁中斷率。21.參考答案： 設(shè)每個(gè)進(jìn)程等待I/O的百分比為P，則n個(gè)進(jìn)程同時(shí)等待I/O的概率是Pn，當(dāng)n個(gè)進(jìn)程同時(shí)等待I/O期間CPU是空閑的，故CPU的利用率為1-Pn。由題意可知，除去操作系統(tǒng)，內(nèi)存還能容納4個(gè)用戶進(jìn)程，由于每個(gè)用戶進(jìn)程等待I/O的時(shí)間為80%，故： CPU利用率=1-（80%）4=0.59 若再增加1MB內(nèi)存，系統(tǒng)中可同時(shí)運(yùn)行9個(gè)用戶進(jìn)程，此時(shí)： CPU利用率=1-（80%）9=0.87 故增加1MB內(nèi)存使CPU的利用率提高了47%： 87%÷59%=147% 147%-100%=47%22.參考答案： 每個(gè)作業(yè)運(yùn)行將經(jīng)過兩個(gè)階段：作業(yè)調(diào)度（SJF算法）和進(jìn)程調(diào)度（優(yōu)先數(shù)搶占式）。另外，批處理最多容納2道作業(yè)，更多的作業(yè)將在后備隊(duì)列等待。 （1）10：00，作業(yè)A到達(dá)并投入運(yùn)行。 （2）10：20，作業(yè)B到達(dá)且優(yōu)先權(quán)高于作業(yè)A，故作業(yè)B投入運(yùn)行而作業(yè)A在就緒隊(duì)列等待。 （3）10：30，作業(yè)C到達(dá)，因內(nèi)存中已有兩道作業(yè)，故作業(yè)C進(jìn)入作業(yè)后備隊(duì)列等待。 （4）10：50，作業(yè)B運(yùn)行結(jié)束，作業(yè)D到達(dá)，按SJF短作業(yè)優(yōu)先算法，作業(yè)D被裝入內(nèi)存進(jìn)入就緒隊(duì)列。而由于作業(yè)A的優(yōu)先級高于作業(yè)D，故作業(yè)A投入運(yùn)行。 （5）11：10，作業(yè)A運(yùn)行結(jié)束，作業(yè)C被調(diào)入內(nèi)存，且作業(yè)C的優(yōu)先級高于作業(yè)D，故作業(yè)C投入運(yùn)行。 （6）12：00，作業(yè)C運(yùn)行結(jié)束，作業(yè)D投入運(yùn)行。 （7）12：20，作業(yè)D運(yùn)行結(jié)束。 各作業(yè)周轉(zhuǎn)時(shí)間為：作業(yè)A??70，作業(yè)B??30，作業(yè)C??90，作業(yè)D??90。平均作業(yè)周轉(zhuǎn)時(shí)間為70分鐘。23.參考答案：1569/512得到商為：3，余數(shù)為：33。所以，訪問的是75磁盤塊的第33個(gè)字節(jié)。24.參考答案： （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ù)，反使缺頁中斷率上升。25.參考答案：S的值表示它代表的物理資源的使用狀態(tài)：S>0表示還有共享資源可供使用。S=0表示共享資源正被進(jìn)程使用但沒有進(jìn)程等待使用資源。S26.參考答案： 1）680 2）915 3）904 4）越界 5）1750 6）越界。27.參考答案： 實(shí)質(zhì)上是兩個(gè)進(jìn)程的同步問題，設(shè)信號量S1和S2分別表示可揀白子和黑子，不失一般性，若令先揀白子。28.參考答案： 按照最短作業(yè)優(yōu)先的算法可以使平均響應(yīng)時(shí)間最短。X取值不定，按照以下情況討論： 1）x≤3????次序?yàn)椋簒，3，5，6，9? 2）329.參考答案： 可以分配，存在安全序列：P2，P1，P3，P4。30.參考答案： 索引表長度為13，其中0到9項(xiàng)為直接尋址方式，后3項(xiàng)為一次、二次和三次間接尋址。 步1?將邏輯文件的字節(jié)偏移量轉(zhuǎn)換為文件的邏輯塊號和塊內(nèi)偏移。方法是：將邏輯文件的字節(jié)偏移量n/盤塊大小（512），商為文件的邏輯塊號，余數(shù)是塊內(nèi)偏移。 步2將文件的邏輯塊號轉(zhuǎn)換為物理塊號。使用多重索引結(jié)構(gòu)，在索引節(jié)點(diǎn)中根據(jù)邏輯塊號通過直接索引或間接索引找到對應(yīng)物理塊號。再判別邏輯塊號在10塊以內(nèi)或以上，分別采用可直接尋址，一次、二次和三次間接尋址。31.參考答案： 步1?將邏輯文件的字節(jié)偏移量轉(zhuǎn)換為文件的邏輯塊號和塊內(nèi)偏移。方法是：將邏輯文件的字節(jié)偏移量/盤塊大小，商為文件的邏輯塊號，余數(shù)是塊內(nèi)偏移。 步2將文件的邏輯塊號轉(zhuǎn)換為物理塊號。使用多重索引結(jié)構(gòu)，在索引節(jié)點(diǎn)中根據(jù)邏輯塊號通過直接索引或間接索引找到對應(yīng)物理塊號。 （1）?9000?????L1=INT（9999，1024）=9??B1=MOD（9999，1024）=783 其邏輯塊號為9，故直接索引addr[8]中可找到物理塊號。 （2）?18000????L2=INT（18000，1024）=17??B1=MOD（18000，1024）=592 其邏輯塊號為17，通過一次間接索引addr[10]中可找到物理塊號。 （3）?420000???L1=INT（420000，1024）=410??B1=MOD（9000，1024）=160 其邏輯塊號為410，通過二次間接索引addr[11]中可找到物理塊號。32.參考答案： 申請時(shí)自上至下、自左至有掃描位示圖跳過為1的位，找到第一個(gè)遷到的0位，根據(jù)它是第i字第j位算出對應(yīng)塊號，并分配出去。歸還時(shí)已知塊號，塊號/32算出第i字第j位并把位示圖相應(yīng)位清0。?33.參考答案： 當(dāng)三個(gè)進(jìn)程執(zhí)行完申請資源R1，開始執(zhí)行申請資源R2時(shí)，第四個(gè)進(jìn)程會(huì)因沒有資源R1而被阻塞。當(dāng)三個(gè)進(jìn)程執(zhí)行完申請資源R2后，系統(tǒng)還剩1個(gè)R2資源。而這三個(gè)進(jìn)程因執(zhí)行申請第二個(gè)資源R1而全部被阻塞，系統(tǒng)進(jìn)入死鎖。34.參考答案： 頁面訪問序列為1，1，2，2，1，4，2，3，3，5，5，4。35.參考答案： 1)449； 2)1727； 3)2301； 4)越界； 5)1994。?36.參考答案： 37.參考答案： 1）FCFS為111。 2）SSTF為61。 3）SCAN為60（先掃地址大的請求），為45（先掃地址小的請求）。38.參考答案：(3)，(4)，(5)，(6)，(7)。39.參考答案：邏輯地址211×24，故為15位。內(nèi)存大小為23×211=214B=16KB。?40.參考答案： （1）?共有10種交錯(cuò)執(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í)行兩個(gè)循環(huán)后，K=23。 2）語句并發(fā)執(zhí)行有以下情況： ①、②、③、④，這時(shí)的打印值為：47 ③、④、①、②，這時(shí)的打印值為：23 ①、③、②、④，這時(shí)的打印值為：46 ①、③、④、②，這時(shí)的打印值為：46 ③、①、②、④，這時(shí)的打印值為：23 ③、①、④、②，這時(shí)的打印值為：23 由于進(jìn)程P1和P2并發(fā)執(zhí)行，共享了變量K，故產(chǎn)生了‘結(jié)果不唯一’。41.參考答案： 可避免分時(shí)進(jìn)程等待時(shí)間過長而拉長響應(yīng)時(shí)間。42.參考答案： FIFO算法選中作業(yè)執(zhí)行的次序?yàn)椋篈、B、D、C和E。作業(yè)平均周轉(zhuǎn)時(shí)間為63分鐘。?43.參考答案： 44.參考答案： 對位于當(dāng)前柱面的新請求，只要一到達(dá)就可得到服務(wù)，但對其他柱面的服務(wù)則不然。如SSTF算法，一個(gè)離當(dāng)前柱面遠(yuǎn)的請求，可能其后不斷有離當(dāng)前柱面近的請求到達(dá)而得不到服務(wù)(饑餓)。45.參考答案：處理器調(diào)度算法會(huì)考慮以下因素：作業(yè)響應(yīng)時(shí)間要求；讓CPU盡量和外圍設(shè)備并行工作；限制一個(gè)計(jì)算進(jìn)程長時(shí)間霸占處理器。因而，(1)I/O為主作業(yè)優(yōu)先級高。(2)?輸入輸出為主作業(yè)優(yōu)先級最高，輸入輸出均勻的作業(yè)其次，而計(jì)算為主作業(yè)的優(yōu)先級最低。46.參考答案： 畫出三個(gè)作業(yè)并行工作圖如下（圖中著色部分為作業(yè)等待時(shí)間）： （1）Job1從投入到運(yùn)行完成需80ms，Job2從投入到運(yùn)行完成需90ms，Job3從投入到運(yùn)行完成需90ms。 （2）CPU空閑時(shí)間段為：60ms至70ms，80ms至90ms。所以CPU利用率為（90-20）/90=77.78%。 （3）設(shè)備I1空閑時(shí)間段為：20ms至40ms，故I1的利用率為（90-20）/90=77.78%。設(shè)備I2空閑時(shí)間段為：30ms至50ms，故I2的利用率為（90-20）/90=77.78%。47.參考答案： ①、②、⑤和⑥是不相交語句，可以任何次序交錯(cuò)執(zhí)行，而結(jié)果是唯一的。接著無論系統(tǒng)如何調(diào)度進(jìn)程并發(fā)執(zhí)行，當(dāng)執(zhí)行到語句⑦時(shí)，可以得到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。48.參考答案：120ns×2=240ns。49.參考答案： 可以采用二級目錄或樹形目錄結(jié)構(gòu)來解決難題。例如，50.參考答案： 按題意地址從小到大進(jìn)行分區(qū)如圖所示。 （1）?1）first-fit???212KB選中分區(qū)2，這時(shí)分區(qū)2還剩288KB。417KB選中分區(qū)5，這時(shí)分區(qū)5還剩183KB。112KB選中分區(qū)2，這時(shí)分區(qū)2還剩176KB。426KB無分區(qū)能滿足，應(yīng)該等待。 2）best-fit????212KB選中分區(qū)4，這時(shí)分區(qū)4還剩88KB。417KB選中分區(qū)2，這時(shí)分區(qū)2還剩83KB。112KB選中分區(qū)3，這時(shí)分區(qū)3還剩88KB。426KB選中分區(qū)5，這時(shí)分區(qū)5還剩174KB。 3）worst-fit???212KB選中分區(qū)5，這時(shí)分區(qū)5還剩388KB。417KB選中分區(qū)2，這時(shí)分區(qū)2還剩83KB。112KB選中分區(qū)5，這時(shí)分區(qū)5還剩176KB。426KB無分區(qū)能滿足，應(yīng)該等待。 （2）?對于該作業(yè)序列，best-fit算法能最有效利用內(nèi)存.51.參考答案： 系統(tǒng)四個(gè)進(jìn)程需要使用的資源數(shù)為R1各2臺(tái)，R2各1臺(tái)?？梢娰Y源數(shù)不足，同時(shí)各進(jìn)程申請資源在先，有可能產(chǎn)生死鎖發(fā)生的四個(gè)條件，故系統(tǒng)可能產(chǎn)生死鎖。52.參考答案： 全部作業(yè)運(yùn)行結(jié)束的時(shí)間9:30。53.參考答案： 所采用的互斥信號量初值不同。 1）互斥信號量初值為1，變化范圍為?[-n+1?，1]。 當(dāng)沒有進(jìn)程進(jìn)入互斥段時(shí)，信號量值為1；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段但沒有進(jìn)程等待進(jìn)入互斥段時(shí)，信號量值為0；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段且有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號量值為-1；最多可能有n-1個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號量的值應(yīng)為-（n-1）也就是-n+1。 2）互斥信號量初值為m，變化范圍為?[-n+m?，m]。 當(dāng)沒有進(jìn)程進(jìn)入互斥段時(shí)，信號量值為m；當(dāng)有1個(gè)進(jìn)程進(jìn)入互斥段但沒有進(jìn)程等待進(jìn)入互斥段時(shí)，信號量值為m-1；當(dāng)有m個(gè)進(jìn)程進(jìn)入互斥段且沒有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號量值為0；當(dāng)有m個(gè)進(jìn)程進(jìn)入互斥段且有一個(gè)進(jìn)程等待進(jìn)入互斥段時(shí)，信號量值為-1；最多可能有n-m個(gè)進(jìn)程等待進(jìn)入互斥段，故此時(shí)信號量的值應(yīng)為-（n-m）也就是-n+m。54.參考答案：題中100×100=10000個(gè)數(shù)據(jù)，每頁可以存放200個(gè)整數(shù)，故一共存放在50個(gè)頁面中。由于元素按行存儲(chǔ)，第1行、第2行放在第1頁，…，第99行、第100行放在第50頁。故對于程序A，缺頁中斷為50次。對于程序B，缺頁中斷為5000次。55.參考答案：并發(fā)進(jìn)程之間的基本相互制約關(guān)系有互斥和同步兩種。其中(1)、(3)為互斥問題。(2)、(4)為同步問題。56.參考答案： 最大作業(yè)周轉(zhuǎn)時(shí)間為55分鐘。57.參考答案： 是先進(jìn)先出算法。因?yàn)樵诰途w隊(duì)列中的進(jìn)程比在CPU上運(yùn)行的進(jìn)程的優(yōu)先數(shù)提高得快，故進(jìn)程切換時(shí)，先進(jìn)入就緒隊(duì)列的進(jìn)程優(yōu)先權(quán)就越高。58.參考答案：采用SSTF處理次序?yàn)椋?00-90-80-125-140-160-190-30-29-25-20-10，總柱面數(shù)為：310。采用電梯調(diào)度處理次序?yàn)椋?00-90-80-30-29-25-20-10-125-140-160-190，總柱面數(shù)為：270。59.參考答案： 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利用率→060.參考答案： 可劃定一個(gè)時(shí)間界限，把這段時(shí)間內(nèi)尚未得到服務(wù)的請求強(qiáng)制移到隊(duì)列首部，并標(biāo)記任何新請求不能插到這些請求前。對于SSTF算法來說，可以重新排列這些老請求，以優(yōu)先處理。61.參考答案： 62.參考答案： 先來先服務(wù)算法FCFS為565，依次為143-86-147-91-177-94-150-102-175-130。?63.參考答案： P1，P2，P3，P4的Cki-Aki分別為：(2，2，2)、(1，0，2)、(1，0，3)、(4，2，0)?64.參考答案：當(dāng)數(shù)組元素a[0]，a[1]，…，a[19]存放在一個(gè)頁面中時(shí)，其空間局部性和時(shí)間局部性較好，也就是說，在很短時(shí)間內(nèi)執(zhí)行都掛行循環(huán)乘法程序，而且數(shù)組元素分布在緊鄰連續(xù)的存儲(chǔ)單元中。當(dāng)數(shù)組元素存放在不同頁面中時(shí)，其時(shí)間局部性雖相同，但空間局部性較差，因?yàn)樘幚淼臄?shù)組元素分布在不連續(xù)的存儲(chǔ)單元中。65.參考答案： （1）用信號量和P、V操作。 類似于課文中的答案，擴(kuò)充如下：1）?同步信號量初值為2； 2）?要引進(jìn)一個(gè)互斥信號量mutex，用于對盤子進(jìn)行互斥； 3）盤子中每一項(xiàng)用橘子、蘋果2個(gè)枚舉值。 66.參考答案： 此時(shí)可以找出進(jìn)程安全序列：P4，P1，P5，P2，P3。故系統(tǒng)處于安全狀態(tài)。67.參考答案： （1）采用FIFO為9次，9/12=75%。采用LRU為8次，8/12=67%。 （2）采用FIFO和LRU均為9次，9/13=69%。68.參考答案： 系統(tǒng)處于安全狀態(tài)，存在安全序：P2，P1，P3，P469.參考答案：內(nèi)存有3個(gè)和4個(gè)空閑頁框的情況下，頁面替換次數(shù)為9次和10次。出現(xiàn)了Belady現(xiàn)象，增加分給作業(yè)的內(nèi)存塊數(shù)，反使缺頁中斷率上升。70.參考答案： 71.參考答案：(50%)4=(1/2)4=1/16。72.參考答案： 首次適應(yīng)、最壞適應(yīng)算法處理這個(gè)作業(yè)序列可以滿足分配，最佳適應(yīng)算法不行。因?yàn)楹笳邥?huì)分割出無法使用的碎片，浪費(fèi)內(nèi)存，從而，不能滿足所有作業(yè)的內(nèi)存需求。73.參考答案： 第i字第j位對應(yīng)的塊號N=32×i+j。74.參考答案： （1）信號量和P、V操作。 這是讀--寫者問題的變種。其中，P3既是讀者又是寫者。讀者與寫者之間需要互斥，寫者與寫者之間需要互斥，為提高進(jìn)程運(yùn)行的并發(fā)性，可讓讀者盡量優(yōu)先。 75.參考答案： 采用短作業(yè)優(yōu)先算法調(diào)度時(shí)，三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為： T1=a+（a+b）+（a+b+c）=3a+2b+c???????????????①? 若不按短作業(yè)優(yōu)先算法調(diào)度，不失一般性，設(shè)調(diào)度次序?yàn)椋篔2、J1、J3。則三個(gè)作業(yè)的總周轉(zhuǎn)時(shí)間為：? T2=b+（b+a）+（b+a+c）=3b+2a+c????????????????②? 令②-①式得到：? T2-T1=b-a>0? 可見，采用短作業(yè)優(yōu)先算法調(diào)度才能獲得最小平均作業(yè)周轉(zhuǎn)時(shí)間。76.參考答案： 最短查找時(shí)間優(yōu)先算法SSTF為162，依次為143-147-150-130-102-94-91-86-175-177。77.參考答案： 畫出三個(gè)作業(yè)并發(fā)執(zhí)行的時(shí)間圖： （1）最早結(jié)束的程序?yàn)锽，最后結(jié)束的程序?yàn)镃。 （2）程序A為250ms。程序B為220ms。程序C為310ms。 （3）CPU利用率為（310-120）/310=61.3%78.參考答案：因?yàn)檫壿嫷刂烽L度為16位，而頁面大小為4096字節(jié)，所以，前面的4位表示頁號。把2F6AH轉(zhuǎn)換成二進(jìn)制為：0010?1111?0110?1010，可知頁號為2。故放在14號物理塊中，寫成十六進(jìn)制為：EF6AH。79.參考答案： 不可以分配。80.參考答案： 81.參考答案： 如果給出優(yōu)先分布20個(gè)記錄的方案為：1，8，15，2，9，16，3，10，17，4，11，18，5，12，19，6，13，20，7，14。當(dāng)讀出第1個(gè)記錄，花2ms處理后，恰好就可以處理記錄2，省去了尋找下一個(gè)記錄的時(shí)間，讀出并處理20個(gè)記錄的總時(shí)間： 10+3+3×19=13+247=260ms82.參考答案： 周轉(zhuǎn)時(shí)間：作業(yè)1為30分鐘、作業(yè)2為55分鐘、作業(yè)3為40分鐘、作業(yè)4為40分鐘和作業(yè)5為55分鐘。 平均作業(yè)周轉(zhuǎn)時(shí)間=44分鐘。83.參考答案： 設(shè)max?（i）表示第i個(gè)進(jìn)程的最大資源需求量，need（i）表示第i個(gè)進(jìn)程還需要的資源量，alloc（i）表示第i個(gè)進(jìn)程已分配的資源量。由題中所給條件可知：? max（1）+┅+max（n）=（need（1）+┅+need（n））+（（alloc（1）+┅+alloc（n））84.參考答案：可以，文件名中可以用插入多個(gè)“/”來模擬文件分層。例如/usu1/datafile/data1和/user1/datafile/data2。但在此操作系統(tǒng)中，這些僅僅是包含“/”的單個(gè)文件名。85.參