大學試題(計算機科學)-操作系統(tǒng)(CH1)筆試（2018-2023年）真題摘選含答案

長風破浪會有時，直掛云帆濟滄海。大學試題(計算機科學)-操作系統(tǒng)(CH1)筆試（2018-2023年）真題摘選含答案（圖片大小可自由調整）卷I一.參考題庫(共30題)1.有一個分頁系統(tǒng)，其頁表存放在主存里 （1）如果對內存的一次存取要1.2微秒，試問實現(xiàn)一次頁面訪問的存取需花多少時間？ （2）若系統(tǒng)配置了聯(lián)想存儲器，命中率為80×%，假定頁表表目在聯(lián)想存儲器的查找時間忽略不計，試問實現(xiàn)一次頁面訪問的存取時間是多少？2.某計算機系統(tǒng)提供24位虛存空間，主存為218B，采用分頁式虛擬存儲管理，頁面尺寸為1KB。假定用戶程序產生了虛擬地址11123456（八進制），而該頁面分得塊號為100（八進制），說明該系統(tǒng)如何產生相應的物理地址及寫出物理地址。 虛擬地址11123456（八進制）轉化為二進制為：????????????????? 001?001?001?010?011?100?101?110? 其中前面為頁號，而后10位為位移：001?001?001?010?01--------1?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è)序列，試問哪種算法可以滿足分配？為什么？3.給定內存空閑分區(qū)，按地址從小到大為：100K、500K、200K、300K和600K?，F(xiàn)有用戶進程依次分別為212K、417K、112K和426K，（1）分別用first-fit、best-fit和worst-fit算法將它們裝入到內存的哪個分區(qū)？ （2）哪個算法能最有效利用內存？4.在一分頁存儲管理系統(tǒng)中，邏輯地址長度為16位，頁面大小為4096字節(jié)，現(xiàn)有一邏輯地址為2F6AH，且第0、1、2頁依次存在物理塊10、12、14號中，問相應的物理地址為多少？5.假定令B=物理塊長、R=邏輯記錄長、F=塊因子。對定長記錄（一個塊中有整數(shù)個邏輯記錄），給出計算F的公式。6.在虛擬頁式存儲管理中，為解決抖動問題，可采用工作集模型以決定分給進程的物理塊數(shù)，有如下頁面訪問序列： 窗口尺寸△＝9，試求t1、t2時刻的工作集。7.把死鎖檢測算法用于下面的數(shù)據(jù)，并請問：若第二個進程提出資源請求request2（0，0，1，0），系統(tǒng)能分配資源給它嗎？8.除FCFS外，所有磁盤調度算法都不公平，如造成有些請求饑餓，試分析提出一種公平性調度算法。9.有一閱覽室，讀者進入時必須先在一張登記表上登記，該表為每一座位列出一個表目，包括座號、姓名，讀者離開時要注銷登記信息；假如閱覽室共有100個座位。試用：1）信號量和P、V操作；2）管程，來實現(xiàn)用戶進程的同步算法。10.一個計算機系統(tǒng)，有一臺輸入機和一臺打印機，現(xiàn)有兩道程序投入運行，且程序A先開始做，程序B后開始運行。程序A的運行軌跡為：計算50ms、打印100ms、再計算50ms、打印100ms，結束。程序B的運行軌跡為：計算50ms、輸入80ms、再計算100ms，結束。 試說明（1）兩道程序運行時，CPU有無空閑等待？若有，在哪段時間內等待？為什么會等待？ （2）程序A、B有無等待CPU的情況？若有，指出發(fā)生等待的時刻。11.單道批處理系統(tǒng)中，下列三個作業(yè)采用先來先服務調度算法和最高響應比優(yōu)先算法進行調度，哪一種算法性能較好？請完成下表： 12.某計算機有cache、內存、輔存來實現(xiàn)虛擬存儲器。如果數(shù)據(jù)在cache中，訪問它需要20ns；如果在內存但不在cache，需要60ns將其裝入緩存，然后才能訪問；如果不在內存而在輔存，需要12ms將其讀入內存，然后，用60ns再讀入cache，然后才能訪問。假設cache命中率為0.9，內存命中率為0.6，則數(shù)據(jù)平均訪問時間是多少（ns）？13.假定某計算機系統(tǒng)有R1和R2兩類可再使用資源（其中R1有兩個單位，R2有一個單位），它們被進程P1，P2所共享，且已知兩個進程均以下列順序使用兩類資源。????????????? →申請R1→申請R2→申請R1→釋放R1→釋放R2→釋放R1→? 試求出系統(tǒng)運行過程中可能到達的死鎖點，并畫出死鎖點的資源分配圖（或稱進程－資源圖）。14.某系統(tǒng)有R1設備3臺，R2設備4臺，它們被P1、P2、P3和P4進程共享，且已知這4個進程均按以下順序使用設備：→申請R1→申請R2→申請R1→釋放R1→釋放R2→釋放R1若可能的話，請舉出一種情況，并畫出表示該死鎖狀態(tài)的進程—資源圖。15.在某計算機系統(tǒng)中，時鐘中斷處理程序每次執(zhí)行的時間為2ms（包括進程切換開銷）。若時鐘中斷頻率為60HZ，試問CPU用于時鐘中斷處理的時間比率為多少？16.請頁式存儲管理中，進程訪問地址序列為：10，11，104，170，73，305，180，240，244，445，467，366。如果頁面大小為100，給出頁面訪問序列。17.有兩個優(yōu)先級相同的進程P1和P2，各自執(zhí)行的操作如下，信號量S1和S2初值均為0。試問P1、P2并發(fā)執(zhí)行后，x、y、z的值各為多少？ 18.在一個請求分頁虛擬存儲管理系統(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ù)和缺頁中斷率。19.假定磁盤有200個柱面，編號0~199，當前存取臂的位置在143號柱面上，并剛剛完成了125號柱面的服務請求，如果請求隊列的先后順序是：86，147，91，177，94，150，102，175，130；試問：為完成上述請求，下列算法存取臂移動的總量是多少？并算出存取臂移動的順序。電梯調度。20.某請求分頁存儲系統(tǒng)使用一級頁表，假設頁表全部放在主存內：若增加一個快表，在命中或失誤時需有20ns開銷，如果快表命中率為80%，則訪問一個數(shù)據(jù)的時間為多少？21.有矩陣：VAR??A：ARRAY[1‥100，1‥100]??OF??integer；元素按行存儲。在一虛存系統(tǒng)中，采用LRU淘汰算法，一個進程有3頁內存空間，每頁可以存放200個整數(shù)。其中第1頁存放程序，且假定程序已在內存。? 程序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ù)。22.（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)，寫出可能的打印值，指出與時間有關的錯誤。23.（1）假定一個處理器正在執(zhí)行兩道作業(yè)，一道以計算為主，另一道以輸入輸出為主，你將怎樣賦予它們占有處理器的優(yōu)先級？為什么？? （2）假定一個處理器正在執(zhí)行三道作業(yè)，一道以計算為主，第二道以輸入輸出為主，第三道為計算與輸入輸出均勻。應該如何賦予它們占有處理器的優(yōu)先級使得系統(tǒng)效率較高？24.有一個四道作業(yè)的操作系統(tǒng)，若在一段時間內先后到達6個作業(yè)，它們的提交和估計運行時間由下表給出： 系統(tǒng)采用SJF調度算法，作業(yè)被調度進入系統(tǒng)后中途不會退出，但作業(yè)運行時可被更短作業(yè)搶占。 （1）分別給出6個作業(yè)的執(zhí)行時間序列、即開始執(zhí)行時間、作業(yè)完成時間、作業(yè)周轉時間。 （2）計算平均作業(yè)周轉時間。25.若兩個用戶共享一個文件系統(tǒng)，用戶甲使用文件A、B、C、D、E；用戶乙要用到文件A、D、E、F。己知用戶甲的文件A與用戶乙的文件A實際上不是同一文件；甲、乙兩用戶的文件D和E正是同一文件。試設計一種文件系統(tǒng)組織方案，使得甲、乙兩用戶能共享該文件系統(tǒng)又不致造成混亂。26.文件系統(tǒng)的性能取決于高速緩存的命中率，從高速緩存讀取數(shù)據(jù)需要1ms，從磁盤讀取數(shù)據(jù)需要40ms。若命中率為h，給出讀取數(shù)據(jù)所需平均時間的計算公式，并畫出h從0到1變化時的函數(shù)曲線。27.設當前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時Available=（1，1，2）：若在P1申請資源后，若P3發(fā)出請求向量request0（0，0，1），系統(tǒng)能把資源分給它嗎？28.某多道程序設計系統(tǒng)供用戶使用的主存為100K，磁帶機2臺，打印機1臺。采用可變分區(qū)內存管理，采用靜態(tài)方式分配外圍設備，忽略用戶作業(yè)I/O時間。現(xiàn)有作業(yè)序列如下： 作業(yè)調度采用FCFS策略，優(yōu)先分配主存低地址區(qū)且不準移動已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時間。作業(yè)平均周轉時間為多少？29.磁帶卷上記錄了若干文件，假定當前磁頭停在第j個文件的文件頭標前，現(xiàn)要按名讀出文件i，試給出讀出文件i的步驟。30.除FCFS外，所有磁盤調度算法都不公平，如造成有些請求饑餓，試分析為什么不公平？卷I參考答案一.參考題庫1.參考答案: （1）2.4微秒 （2）0.8×1.2+0.2×2.4=0.76+0.48=1.24微秒2.參考答案: 首次適應、最壞適應算法處理這個作業(yè)序列可以滿足分配，最佳適應算法不行。因為后者會分割出無法使用的碎片，浪費內存，從而，不能滿足所有作業(yè)的內存需求。3.參考答案: 按題意地址從小到大進行分區(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ū)能滿足，應該等待。 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ū)能滿足，應該等待。 （2）?對于該作業(yè)序列，best-fit算法能最有效利用內存.4.參考答案:因為邏輯地址長度為16位，而頁面大小為4096字節(jié)，所以，前面的4位表示頁號。把2F6AH轉換成二進制為：0010?1111?0110?1010，可知頁號為2。故放在14號物理塊中，寫成十六進制為：EF6AH。5.參考答案:F=[B/R]。6.參考答案: t1時刻的工作集為：{1，2，3，6，7，8，9}。t時刻的工作集為：{3，4}。7.參考答案: 可以分配，存在安全序列：P4，P1，P5，P2，P3。8.參考答案: 可劃定一個時間界限，把這段時間內尚未得到服務的請求強制移到隊列首部，并標記任何新請求不能插到這些請求前。對于SSTF算法來說，可以重新排列這些老請求，以優(yōu)先處理。9.參考答案: 10.參考答案: 畫出兩道程序并發(fā)執(zhí)行圖如下： （1）?兩道程序運行期間，CPU存在空閑等待，時間為100至150ms之間（見圖中有色部分）。 （2）?程序A無等待現(xiàn)象，但程序B有等待。程序B有等待時間段為180ms至200ms間（見圖中有色部分）。11.參考答案: 12.參考答案:則數(shù)據(jù)平均訪問時間是506ns。13.參考答案: 當兩個進程都執(zhí)行完第一步(都占用R1)?時，系統(tǒng)進入不安全狀態(tài)。這時無論哪個進程執(zhí)行完第二步，死鎖都會發(fā)生?？赡艿竭_的死鎖點：進程P1占有一個R1和一個R2，而進程P2占有一個R1?；蛘呦喾础＿@時己形成死鎖。進程---資源圖為：14.參考答案: 當三個進程執(zhí)行完申請資源R1，開始執(zhí)行申請資源R2時，第四個進程會因沒有資源R1而被阻塞。當三個進程執(zhí)行完申請資源R2后，系統(tǒng)還剩1個R2資源。而這三個進程因執(zhí)行申請第二個資源R1而全部被阻塞，系統(tǒng)進入死鎖。15.參考答案:因時鐘中斷頻率為60HZ，所以，時鐘周期為：1/60s=50/3ms。在每個時鐘周期中，CPU花2ms執(zhí)行中斷任務。所以，CPU用于時鐘中斷處理的時間比率為：2(50/3)=6/50=12%。16.參考答案: 頁面訪問序列為1，1，2，2，1，4，2，3，3，5，5，4。17.參考答案: ①、②、⑤和⑥是不相交語句，可以任何次序交錯執(zhí)行，而結果是唯一的。接著無論系統(tǒng)如何調度進程并發(fā)執(zhí)行，當執(zhí)行到語句⑦時，可以得到x=10，y=4。按Bernstein條件，語句③的執(zhí)行結果不受語句⑦的影響，故語句③執(zhí)行后得到z=5。最后，語句④和⑧并發(fā)執(zhí)行，最后結果為：? 語句④先執(zhí)行：x=10，y=9，z=15。? 語句⑧先執(zhí)行：x=10，y=19，z=15。18.參考答案: 只要把表中缺頁中斷次數(shù)除以20，便得到缺頁中斷率。19.參考答案: 電梯調度為125(先向地址大的方向)，依次為143-147-150-175-177-102-94-91-86。為148(先向地址小的方向)?依次為143-130-102-94-91-86-147-150-175-177。20.參考答案:(120+20)×80%+(120+120+20)×20%=174ns。21.參考答案:題中100×100=10000個數(shù)據(jù)，每頁可以存放200個整數(shù)，故一共存放在50個頁面中。由于元素按行存儲，第1行、第2行放在第1頁，…，第99行、第100行放在第50頁。故對于程序A，缺頁中斷為50次。對于程序B，缺頁中斷為5000次。22.參考答案: （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，故產生了‘結果不唯一’。23.參考答案:處理器調度算法會考慮以下因素：作業(yè)響應時間要求；讓CPU盡量和外圍設備并行工作；限制一個計算進程長時間霸占處理器。因而，(1)I/O為主作業(yè)優(yōu)先級高。(2)?輸入輸出為主作業(yè)優(yōu)先級最高，輸入輸出均勻的作業(yè)其次，而計算為主作業(yè)的優(yōu)先級最低。24.參考答案: 注意，J1被調度運行后，直到它執(zhí)行結束，才會引出作業(yè)調度程序工作。所以，J2至J6雖在J1執(zhí)行期間進入，但未被調度，均在等待。當J1撤離后，作業(yè)調度程序工作，按SJF算法，顯然有執(zhí)行次序：J5、J6、J3、J4、和J2。25.參考答案: 可以采用二級目錄或樹形目錄結構來解決難題。例如，26.參考答案: 讀取數(shù)據(jù)所需平均時間T=h×1+40×(1-h)=h+40×(1-h)。27.參考答案: 不可以分配。28.參考答案: 周轉時間：作業(yè)1為30分鐘、作業(yè)2為55分鐘、作業(yè)3為40分鐘、作業(yè)4為40分鐘和作業(yè)5為55分鐘。 平均作業(yè)周轉時間=44分鐘。29.參考答案: 由于磁帶卷上的文件用“帶標”隔開，每個文件的文件頭標前后都使用了三個帶標。 正常情況磁頭應停在文件頭標的前面，所以，只要計算帶標的個數(shù)，就可找到所要文件。 1）當i≧j時，要正走磁帶， 步驟1?組織通道程序正走磁帶，走過“帶標”個數(shù)為3×（i-j）個。 步驟2?組織通道程序讀文件i的文件頭標。 步驟3?根據(jù)文件i的文件頭標信息，組織讀文件信息。 2）當i<j時，要反走磁帶，步驟1?組織通道程序反走磁帶，走過“帶標”個數(shù)為3×（j-i）+1個。 步驟2?組織通道程序讀文件i的文件頭標。 步驟3?根據(jù)文件i的文件頭標信息，組織讀文件信息。</j時，要反走磁帶，30.參考答案: 對位于當前柱面的新請求，只要一到達就可得到服務，但對其他柱面的服務則不然。如SSTF算法，一個離當前柱面遠的請求，可能其后不斷有離當前柱面近的請求到達而得不到服務(饑餓)。卷II一.參考題庫(共30題)1.一個有快表的請頁式虛存系統(tǒng)，設內存訪問周期為1微秒，內外存?zhèn)魉鸵粋€頁面的平均時間為5毫秒。如果快表命中率為75%，缺頁中斷率為10%。忽略快表訪問時間，試求內存的有效存取時間。2.旋轉型設備上信息的優(yōu)化分布能減少為若干個I/O服務的總時間。設磁鼓上分為20個區(qū)，每區(qū)存放一個記錄，磁鼓旋轉一周需20毫秒，讀出每個記錄平均需用1毫秒，讀出后經2毫秒處理，再繼續(xù)處理下一個記錄。在不知當前磁鼓位置的情況下：給出優(yōu)先分布20個記錄的一種方案，使得所花的總處理時間減少，且計算出這個方案所花的總時間。3.在UNIX?中，如果一個盤塊的大小為1KB，每個盤塊號占4個字節(jié)，即每塊可放256個地址。請轉換下列文件的字節(jié)偏移量為物理地址：（1）9999；（2）18000；（3）420000。4.在按動態(tài)優(yōu)先數(shù)調度進程的系統(tǒng)中，每個進程的優(yōu)先數(shù)需定時重新計算。在處理器不斷地在進程之間交替的情況下，重新計算進程優(yōu)先數(shù)的時間從何而來？5.有一個分頁虛存系統(tǒng)，測得CPU和磁盤的利用率如下，試指出每種情況下的存在問題和可采取的措施： （1）CPU利用率為13%，磁盤利用率為97%?? （2）CPU利用率為87%，磁盤利用率為3%?? （3）CPU利用率為13%，磁盤利用率為3%6.在一個盒子里，混裝了數(shù)量相等的黑白圍棋子?，F(xiàn)在用自動分揀系統(tǒng)把黑子、白子分開，設分揀系統(tǒng)有二個進程P1和P2，其中P1揀白子；P2揀黑子。規(guī)定每個進程每次揀一子；當一個進程在揀時，不允許另一個進程去揀；當一個進程揀了一子時，必須讓另一個進程去揀。試寫出兩進程P1和P2能并發(fā)正確執(zhí)行的程序。7.若內存中有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）? 如果三道程序都使用相同設備進行I/O（即程序用串行方式使用設備，調度開銷忽略不計）。試分別畫出單道和多道運行的時間關系圖。兩種情況下，CPU的平均利用率各為多少？8.某多道程序設計系統(tǒng)供用戶使用的主存為100K，磁帶機2臺，打印機1臺。采用可變分區(qū)內存管理，采用靜態(tài)方式分配外圍設備，忽略用戶作業(yè)I/O時間?，F(xiàn)有作業(yè)序列如下： 作業(yè)調度采用FCFS策略，優(yōu)先分配主存低地址區(qū)且不準移動已在主存的作業(yè)，在主存中的各作業(yè)平分CPU時間。全部作業(yè)運行結束的時間？9.設有一頁式存儲管理系統(tǒng)，向用戶提供的邏輯地址空間最大為16頁，每頁2048字節(jié)，內存總共有8個存儲塊。試問邏輯地址至少應為多少位？內存空間有多大？10.假定磁盤有200個柱面，編號0~199，當前存取臂的位置在143號柱面上，并剛剛完成了125號柱面的服務請求，如果請求隊列的先后順序是：86，147，91，177，94，150，102，175，130；試問：為完成上述請求，下列算法存取臂移動的總量是多少？并算出存取臂移動的順序。掃描算法SCAN。11.考慮下列的段表： 段號????????始址???????????段長? 0???????????200????????????500? 1???????????890????????????30? 2???????????120????????????100? 3??????????1250????????????600? 4??????????1800????????????88?? 對下面的邏輯地址，求物理地址，如越界請指明。1）??2）?3）?4）?5）??6）。12.對某系統(tǒng)進行監(jiān)測后表明平均每個進程在I/O阻塞之前的運行時間為T。一次進程切換的系統(tǒng)開銷時間為S。若采用時間片長度為Q的時向片輪轉法，對下列各種情況算出CPU利用率。 1）Q＝∞??? 2）Q＞T??? 3）S＜Q＜T???? 4）Q＝S??? 5）Q接近于013.Kleinrock提出一種動態(tài)優(yōu)先權算法：進程在就緒隊列等待時，其優(yōu)先權以速率α變化；?當進程在處理器上運行，時其優(yōu)先權以速率β變化。給參數(shù)α、β賦以不同值可得到不同算法。若α<β<0是什么算法？14.假設某虛存的用戶空間為1024KB，頁面大小為4KB，內存空間為512KB。已知用戶的虛頁10、11、12、13頁分得內存頁框號為62、78、25、36，求出虛地址0BEBC（16進制）的實地址（16進制）是多少？15.設一個文件由100個物理塊組成，對于連續(xù)文件、連接文件和索引文件，分別計算執(zhí)行下列操作時的啟動磁盤I/O次數(shù)（假如頭指針和索引表均在內存中）： （1）把一塊加在文件的開頭； （2）把一塊加在文件的中間（第51塊）； （3）把一塊加在文件的末尾； （4）從文件的開頭刪去一塊； （5）從文件的中間（第51塊）刪去一塊； （6）從文件的未尾刪去一塊。16.假定磁盤有200個柱面，編號0~199，當前存取臂的位置在143號柱面上，并剛剛完成了125號柱面的服務請求，如果請求隊列的先后順序是：86，147，91，177，94，150，102，175，130；試問：為完成上述請求，下列算法存取臂移動的總量是多少？并算出存取臂移動的順序。最短查找時間優(yōu)先算法SSTF；17.某操作系統(tǒng)的磁盤文件空間共有500塊，若用字長為32位的位示圖管理盤空間位示圖需多少個字？18.考慮下面的程序： for?（i=0；i<20；i++）? ??????????????for（j=0；j<10；j++） ??????????????a[i]：=a[i]×j 試舉例說明該程序的空間局部性和時間局部性。19.有一臺計算機，具有1MB內存，操作系統(tǒng)占用200KB，每個用戶進程各占200KB。如果用戶進程等待I/O的時間為80%，若增加1MB內存，則CPU的利用率提高多少？20.某操作系統(tǒng)的磁盤文件空間共有500塊，若用字長為32位的位示圖管理盤空間第i字第j位對應的塊號是多少？21.設有三道程序，按A、B、C優(yōu)先次序運行，其內部計算和I/O操作時間由圖給出。 試畫出按多道運行的時間關系圖（忽略調度執(zhí)行時間）。完成三道程序共花多少時間？比單道運行節(jié)省了多少時間？若處理器調度程序每次進行程序轉換化時1ms，試畫出各程序狀態(tài)轉換的時間關系圖。22.如果一個索引節(jié)點為128B，指針長4B，狀態(tài)信息占用68B，而每塊大小為8KB。問在索引節(jié)點中有多大空間給指針？使用直接、一次間接、二次間接和三次間接指針分別可表示多大的文件？23.下列指令中哪些只能在核心態(tài)運行？? （1）讀時鐘日期； （2）訪管指令； （3）設時鐘日期； （4）加載PSW； （5）置特殊寄存器； （6）改變存儲器映象圖； （7）啟動I/O指令。24.設當前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時Available=（1，1，2）：若在P2申請資源后，若P1發(fā)出請求向量request0（1，0，1），系統(tǒng)能把資源分給它嗎？25.某磁盤共有100個柱面，每個柱面有8個磁頭，每個盤面分4個扇區(qū)。若邏輯記錄?與扇區(qū)等長，柱面、磁道、扇區(qū)均從0起編號?，F(xiàn)用16位的200個字（0-199）來組成位示圖來管理盤空間。問：位示圖第15個字的第7位為0而準備分配給某一記錄，該塊的柱面號、磁道號、扇區(qū)號是多少？26.設當前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時Available=（1，1，2）：P2發(fā)出請求向量request1（1，0，1），系統(tǒng)能把資源分給它嗎？27.系統(tǒng)有同類資源m個，被n個進程共享，問：當m＞n和m≤n時，每個進程最多可以請求多少個這類資源時，使系統(tǒng)一定不會發(fā)生死鎖？28.請頁式存儲管理中，進程訪問地址序列為：10，11，104，170，73，305，180，240，244，445，467，366。進程若分得3個頁框，采用FIFO和LRU替換算法，求缺頁中斷率？29.設有n個進程共享一個互斥段，如果：? （1）每次只允許一個進程進入互斥段；? （2）每次最多允許m個進程（m≤n）同時進入互斥段。? 試問：所采用的信號量初值是否相同？信號量值的變化范圍如何？30.旋轉型設備上信息的優(yōu)化分布能減少為若干個I/O服務的總時間。設磁鼓上分為20個區(qū)，每區(qū)存放一個記錄，磁鼓旋轉一周需20毫秒，讀出每個記錄平均需用1毫秒，讀出后經2毫秒處理，再繼續(xù)處理下一個記錄。在不知當前磁鼓位置的情況下：順序存放記錄1、……，記錄20時，試計算讀出并處理20個記錄的總時間；卷II參考答案一.參考題庫1.參考答案:快表命中率為75%，缺頁中斷率為10%，所以，內存命中率為15%。故內存的有效存取時間=1×75%+2×15%+(5000+2)×10%=501.25微秒。2.參考答案: 如果給出優(yōu)先分布20個記錄的方案為：1，8，15，2，9，16，3，10，17，4，11，18，5，12，19，6，13，20，7，14。當讀出第1個記錄，花2ms處理后，恰好就可以處理記錄2，省去了尋找下一個記錄的時間，讀出并處理20個記錄的總時間： 10+3+3×19=13+247=260ms3.參考答案: 步1?將邏輯文件的字節(jié)偏移量轉換為文件的邏輯塊號和塊內偏移。方法是：將邏輯文件的字節(jié)偏移量/盤塊大小，商為文件的邏輯塊號，余數(shù)是塊內偏移。 步2將文件的邏輯塊號轉換為物理塊號。使用多重索引結構，在索引節(jié)點中根據(jù)邏輯塊號通過直接索引或間接索引找到對應物理塊號。 （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]中可找到物理塊號。4.參考答案:許多操作系統(tǒng)重新計算進程的優(yōu)先數(shù)在時鐘中斷處理例程中進行，由于中斷是隨機的，碰到哪個進程，就插入哪個進程中運行處理程序，并把處理時間記在這個進程的賬上。5.參考答案: （1）系統(tǒng)可能出現(xiàn)抖動，可把暫停部分進程運行。 （2）系統(tǒng)運行正常，可增加運行進程數(shù)以進一步提高資源利用率。 （3）處理器和設備和利用率均很低，可增加并發(fā)運行的進程數(shù)。6.參考答案: 實質上是兩個進程的同步問題，設信號量S1和S2分別表示可揀白子和黑子，不失一般性，若令先揀白子。7.參考答案: 分別畫出單道和多道運行的時間圖? 單道運行時間關系圖 單道總運行時間為190ms。CPU利用率為（190-80）/190=57.9% 多道運行時間關系圖 多道總運行時間為140ms。CPU利用率為（140-30）/140=78.6%8.參考答案: 全部作業(yè)運行結束的時間9:30。9.參考答案:邏輯地址211×24，故為15位。內存大小為23×211=214B=16KB。10.參考答案: 掃描算法SCAN為169，依次為143-147-150-175-177-199-130-102-94-91-86。11.參考答案: 1）680 2）915 3）904 4）越界 5）1750 6）越界。12.參考答案: 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利用率→013.參考答案: 是后進先出算法。因為在就緒隊列中的進程比在CPU上運行的進程的優(yōu)先權下降得快，故后進入就緒隊列的進程此先進入的進程的優(yōu)先權高。14.參考答案:虛地址0BEBC(16進制)的二進制形式為：0000?1011?1110?1011?1100。由于頁面大小為4KB，故其中后12位是位移，所以，虛地址的頁號為：11。查頁表分得內存對應頁框號為：78。已知內存空間為512KB，故內存共有128個頁框，78是合法物理塊。把78化為16進制是4E，虛地址0BEBC(16進制)的實地址(16進制)是：4EEBC。15.參考答案: 16.參考答案: 最短查找時間優(yōu)先算法SSTF為162，依次為143-147-150-130-102-94-91-86-175-177。17.參考答案: 位示圖占用字數(shù)為500/32=16(向上取整)個字。18.參考答案:當數(shù)組元素a[0]，a[1]，…，a[19]存放在一個頁面中時，其空間局部性和時間局部性較好，也就是說，在很短時間內執(zhí)行都掛行循環(huán)乘法程序，而且數(shù)組元素分布在緊鄰連續(xù)的存儲單元中。當數(shù)組元素存放在不同頁面中時，其時間局部性雖相同，但空間局部性較差，因為處理的數(shù)組元素分布在不連續(xù)的存儲單元中。19.參考答案: 設每個進程等待I/O的百分比為P