操作系統(tǒng)復(fù)習2016

操作系統(tǒng)原理復(fù)習南京工業(yè)大學信息學院計算機系注意要點考核形式試卷，閉卷考試，120分鐘可以帶計算器，但不得使用手機中的計算器功能試卷占總評成績的80%考察范圍第一章～第九章部分章節(jié)除外2023/2/5操作系統(tǒng)復(fù)習2題型分布單選題15題，共30分填空題10題，共10分綜合應(yīng)用題6題，共60分2023/2/5操作系統(tǒng)復(fù)習3主要知識點第一章操作系統(tǒng)的目標操作系統(tǒng)的作用三種經(jīng)典的操作系統(tǒng)類型分時系統(tǒng)的特征實時系統(tǒng)的特征操作系統(tǒng)的基本特征用戶接口的種類2023/2/5操作系統(tǒng)復(fù)習4主要知識點第二章順序執(zhí)行程序的主要特征并發(fā)執(zhí)行程序的主要特征進程的特征進程的各個狀態(tài)，及各狀態(tài)之間的轉(zhuǎn)換條件導(dǎo)致進程創(chuàng)建、終止、阻塞的條件同步機制的4條設(shè)計原則進程同步：只需要掌握用信號量解決P-C問題進程通信的方法2023/2/5操作系統(tǒng)復(fù)習5主要知識點第三章處理機的調(diào)度層次調(diào)度算法：FIFO，SJF，高相應(yīng)比優(yōu)先，時間片輪轉(zhuǎn)產(chǎn)生死鎖的4個必要條件銀行家算法資源分配圖的簡化2023/2/5操作系統(tǒng)復(fù)習6主要知識點第四章動態(tài)分區(qū)分配中分配和回收內(nèi)存的方法動態(tài)分區(qū)分配算法：FF，NF，BF，WF邏輯地址到物理地址的轉(zhuǎn)換及訪問時間的計算多級頁表段頁式存儲管理的地址轉(zhuǎn)換（虛地址到實地址的轉(zhuǎn)換）2023/2/5操作系統(tǒng)復(fù)習7主要知識點第五章虛擬存儲器的特征頁面置換算法及缺頁率的計算最佳，F(xiàn)IFO，LRU，時鐘置換抖動的概念2023/2/5操作系統(tǒng)復(fù)習8主要知識點第六章I/O系統(tǒng)的基本功能I/O系統(tǒng)的層次結(jié)構(gòu)I/O設(shè)備的類型設(shè)備控制器的基本功能單緩沖和雙緩沖傳輸時間的計算磁盤訪問時間的計算磁盤調(diào)度算法：FCFS，SSTF，SCAN，CSCAN2023/2/5操作系統(tǒng)復(fù)習9主要知識點第七章文件的組織分類及其特征目錄管理的要求目錄結(jié)構(gòu)的組織形式目錄檢索的方法文件共享的方法（文件）2023/2/5操作系統(tǒng)復(fù)習10主要知識點第八章連續(xù)組織方式的優(yōu)缺點隱式連接、顯示鏈接組織方式的優(yōu)缺點索引組織方式的優(yōu)缺點混合索引文件最大容量的計算方法位示圖法存儲空間管理（位圖計算）2023/2/5操作系統(tǒng)復(fù)習11主要知識點第九章用戶接口的類型主要聯(lián)機命令Shell命令語言的主要簡單命令系統(tǒng)調(diào)用的實現(xiàn)方法2023/2/5操作系統(tǒng)復(fù)習121.假設(shè)有一磁盤含有64000塊，塊號記為1～64000，現(xiàn)用2000個32位(Bit)的字作該盤的位示圖，試問第59999塊對應(yīng)于位示圖中第幾字的第幾位(字、位均從0開始)；而第1599字的第17位對應(yīng)于磁盤的第幾塊?解：由塊號b，求字號i和位號j的公式為：i=(b-1)div32 (div表示整數(shù)除法，32是字長)j=(b-1)mod32 (mod表示整數(shù)相除取余數(shù))(59999-1)div32=1874 (59999-1)mod32=30故59999塊對應(yīng)于位示圖中第1874字的第30位。 由位示圖的字號i和位號j，求對應(yīng)的磁盤塊號b的公式為：b=i×32+j+1=1599×32+17+1=51186即第1599字的第17位對應(yīng)于磁盤的第51186塊。

2023/2/5操作系統(tǒng)復(fù)習132.頁式存儲管理中，主存空間按頁分配，可用一張“位示圖”構(gòu)成主存分配表。假設(shè)主存容量為2M字節(jié)，頁面長度為512字節(jié)，若用字長為32位的字作主存分配的“位示圖”需要多少個字？如頁號從1開始，字號和字內(nèi)位號（從高位到低位）均從1開始，試問：第2999頁對應(yīng)于何字何位；99字19位又對應(yīng)于第幾頁？解：(1)內(nèi)存總塊數(shù)=2MB/512B=4096 位示圖需要字數(shù)=4096/32=128 (2)字號=(2999-1)/32+1=94 位號=(2999-1)%32+1=23 即第2999內(nèi)存頁對應(yīng)于位示圖中94字的23位。(3)99*（32-1）+19=3088即位示圖99字19位對應(yīng)于內(nèi)存的3088頁2023/2/5操作系統(tǒng)復(fù)習142023/2/5操作系統(tǒng)復(fù)習153．某多道程序設(shè)計系統(tǒng)供用戶使用的主存為100KB，磁帶機2臺，打印機1臺。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)方式分配外圍設(shè)備，忽略用戶作業(yè)的I/O時間。現(xiàn)有如下作業(yè)序列：作業(yè)名提交時間需運行時間主存需求量磁帶機需求打印機需求J18:0025分鐘15KB11J28:2010分鐘30KB01J38:2020分鐘60KB10J48:3020分鐘20KB10J58:3515分鐘10KB11作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配主存低地址區(qū)域且不準移動已在主存中的作業(yè)，進程調(diào)度采用時間片輪轉(zhuǎn)算法(即在主存中的作業(yè)均分CPU時間)?，F(xiàn)求：2023/2/5操作系統(tǒng)復(fù)習16(1)作業(yè)被調(diào)度的先后次序；(2)全部作業(yè)運行結(jié)束的時間；(3)作業(yè)的平均周轉(zhuǎn)時間；(4)最大作業(yè)周轉(zhuǎn)時間。作業(yè)達到及結(jié)束順序分析：8:00 J1到達，分配它所需資源(15KB內(nèi)存、1臺磁帶機、1臺打印機后，調(diào)入內(nèi)存運行。余內(nèi)存85KB、磁帶機1臺。8:20 J2到達，因無打印機，不調(diào)入。同時J3到達，分配它內(nèi)存60KB，磁帶機1臺，調(diào)入內(nèi)存，與J1均分CPU時間運行。余內(nèi)存25KB、磁帶機和打印機都已分完(余0臺)。8:30 J1結(jié)束，釋放內(nèi)存15KB、磁帶機1臺、打印機1臺。雖有打印機但內(nèi)存不夠，J2仍不能調(diào)入；J4到達，因低端內(nèi)存15KB不夠，分配高端內(nèi)存20KB和磁帶機1臺，調(diào)入內(nèi)存與J3一起運行。剩下內(nèi)存空閑塊是15KB、5KB，打印機1臺8:35 J5到達，因無磁帶機，不能調(diào)入。2023/2/5操作系統(tǒng)復(fù)習179:00 J3結(jié)束。釋放資源后，系統(tǒng)有內(nèi)存75KB，5KB、打印機和磁帶機個1臺。J2調(diào)入，內(nèi)存余45KB，5KB、磁帶機剩1臺、打印機0臺。J5仍不能進入(無打印機)。將J2、J4運行。J4還需運行5分鐘。9:10 J4結(jié)束，釋放資源后，內(nèi)存空余70KB、磁帶機空2臺、打印機0臺。J5仍不能進入。J2單獨運行(還需5分鐘)。9:15 J2結(jié)束，釋放資源后，內(nèi)存有100KB、磁帶機有2臺、打印機有1臺。J5調(diào)入運行。9:30 J5結(jié)束。解：(1)作業(yè)被調(diào)度的先后次序為J1,J3,J4,J2,J5(2)全部作業(yè)運行結(jié)束的時間為9:30(3)作業(yè)的平均周轉(zhuǎn)時間為(30+55+40+40+55)÷5=44(分鐘)(4)最大作業(yè)周轉(zhuǎn)時間為55分鐘。2023/2/5操作系統(tǒng)復(fù)習18CPU磁帶1磁帶2打印機8:008:20J1J1J1J1,J3J38:30J1J1J1結(jié)束J4J3J2,J3到J2不入J3進入J3,J48:35J3,J4J5到達J5不入9:00J4J3J3結(jié)束9:10J4結(jié)束內(nèi)存余85K25K15,515,5J2,J445,5J4J29:15J2J270KJ2結(jié)束9:3090KJ5J5J5J5結(jié)束J1到達J1進入J4到達J2不入J4進入J2進入J5仍不能進入J5進入以下是畫圖分析法：2023/2/5操作系統(tǒng)復(fù)習194．多道批處理系統(tǒng)中配有一個處理器和2臺外設(shè)(D1和D2)，用戶存儲空間為100MB。已知系統(tǒng)采用可搶占式的高優(yōu)先數(shù)調(diào)度算法和不允許移動的可變分區(qū)分配策略，設(shè)備分配按照動態(tài)分配原則。今有4個作業(yè)同時提交給系統(tǒng)，如下表所示。作業(yè)名優(yōu)先數(shù)運行時間內(nèi)存需求A65分鐘50MB34分鐘10MC87分鐘60MD46分鐘20M作業(yè)運行時間和I/O時間按下述順序進行：A.CPU(1分鐘)，D1(2分鐘)，D2(2分鐘)B.CPU(3分鐘)，D1(1分鐘)C.CPU(2分鐘)，D1(3分鐘)，CPU(2分鐘)D.CPU(4分鐘)，D1(2分鐘)忽略其他輔助操作，求4個作業(yè)的平均周轉(zhuǎn)時間是多少分鐘。11分鐘分析見后頁2023/2/5操作系統(tǒng)復(fù)習20CCDDDCCADBBBCCCAADDBAA12345678910111213CPUD1D2時間A的周轉(zhuǎn)時間為12分鐘B的周轉(zhuǎn)時間為13分鐘C的周轉(zhuǎn)時間為7分鐘D的周轉(zhuǎn)時間為12分鐘所以平均周轉(zhuǎn)時間為(12+13+7+12)/4=11(分鐘)5.有一個具有兩道作業(yè)的批處理系統(tǒng)（最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行），作業(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)時間。2023/2/5操作系統(tǒng)復(fù)習21作業(yè)名到達時間估計運行時間優(yōu)先數(shù)J110:1020分鐘5J210:2030分鐘3J310:3025分鐘4J410:5020分鐘6分析：10：10J1到達，進入系統(tǒng)，運行10分鐘10：20J2到達，進入系統(tǒng)，因優(yōu)先級高于J1搶奪CPU開始運行10：30J3到達后備隊列，因為系統(tǒng)已經(jīng)載入2個作業(yè)，無法進入系統(tǒng)10：50J2運行結(jié)束退出，J4到達，根據(jù)短作業(yè)優(yōu)先，調(diào)入J4，由于J1的優(yōu)先級高于J4，J1開始運行11：00J1運行結(jié)束退出，J3進入系統(tǒng)，由于J3優(yōu)先級較高，開始運行11：25J3運行結(jié)束退出，J4開始運行11：45J4運行結(jié)束2023/2/5操作系統(tǒng)復(fù)習22答：（1）各個作業(yè)進入主存時間、結(jié)束時間和周轉(zhuǎn)時間如下表所示：

（2）平均周轉(zhuǎn)時間：（50+30+55+55）/4=47.5（min）2023/2/5操作系統(tǒng)復(fù)習23作業(yè)名提交時間進入時間結(jié)束時間周轉(zhuǎn)時間J110：1010：1011：0050J210：2010：2010：5030J310：3011：0011：2555J410：5010：5011：45556．有一個多道程序設(shè)計系統(tǒng)，采用不可移動的可變分區(qū)方式管理主存空間，設(shè)主存空間為100K，采用最先適應(yīng)分配算法分配主存，作業(yè)調(diào)度采用響應(yīng)比高者優(yōu)先算法，進程調(diào)度采用時間片輪轉(zhuǎn)算法（即內(nèi)存中的作業(yè)均分CPU時間），今有如下作業(yè)序列：假定所有作業(yè)都是計算型作業(yè)且忽略系統(tǒng)調(diào)度時間。回答下列問題：(1)列表說明各個作業(yè)被裝入主存的時間、完成時間和周轉(zhuǎn)時間；(2)寫出各作業(yè)被調(diào)入主存的順序；(3)計算5個作業(yè)的平均周轉(zhuǎn)時間。

2023/2/5操作系統(tǒng)復(fù)習24作業(yè)名提交時間需要執(zhí)行時間要求主存量J110:0040分鐘25KJ210:1530分鐘60KJ310:3020分鐘50KJ410:3525分鐘18KJ510:4015分鐘20K答：（1）各個作業(yè)被裝入主存的時間、完成時間和周轉(zhuǎn)時間如下表所示： （2）作業(yè)被調(diào)入主存的順序為J1，J2，J5，J3，J4。 （3）平均周轉(zhuǎn)時間=（65+60+85+95+55）/5=72（分鐘）。 2023/2/5操作系統(tǒng)復(fù)習25作業(yè)名裝入主存時間作業(yè)完成時間周轉(zhuǎn)時間J110：0011：0565J210：1511：1560J311：1511：5585J411：3512：1095J511：0511：355526信號量機制解決進程同步問題的一般方法：為同步雙方設(shè)置各自的信號量，初值為其初始狀態(tài)可用的資源數(shù)(故該信號量稱為資源信號量或私有信號量)；同步雙方任一進程在進入臨界區(qū)之前，應(yīng)先對自己的信號量執(zhí)行wait(<己方信號量>)操作，以測試是否有自己可用的資源。若有資源可用，則進入臨界區(qū)，否則阻塞；同步雙方任一進程離開臨界區(qū)后，應(yīng)對合作方(對方)的信號量執(zhí)行signal(<對方信號量>)操作，以通知(若對方處于阻塞狀態(tài)，則喚醒它)對方已有資源可用(對方已可進入臨界區(qū))。27用信號量機制解決P-C問題的基本方法：為生產(chǎn)者設(shè)置1個私有信號量empty，其初值為1，表示有1個空緩沖區(qū)；為消費者設(shè)置1個私有信號量full，其初值為0，表示開始時沒有滿緩沖區(qū)；（信號量初值由物理意義確定）生產(chǎn)者將產(chǎn)品存入緩沖區(qū)之前，應(yīng)先測試緩沖區(qū)是否空：執(zhí)行wait(empty)操作；離開臨界區(qū)(存入產(chǎn)品)后，應(yīng)通知(可能會喚醒)消費者：執(zhí)行signal(full)操作；消費者從緩沖區(qū)取產(chǎn)品之前，應(yīng)先測試緩沖區(qū)是否滿：執(zhí)行wait(full)操作；離開臨界區(qū)(取走產(chǎn)品)后，應(yīng)通知(可能會喚醒)生產(chǎn)者：執(zhí)行signal(empty)操作2023/2/5操作系統(tǒng)復(fù)習287.進程P1使用緩沖區(qū)buffer向進程P2，P3，P4發(fā)送消息，要求每當P1向buffer中發(fā)消息時，只有當P2，P3，P4進程都讀取這條消息后才可向buffer中發(fā)送新的消息。利用P、V原語描述如下圖所示進程的動作序列。P1bufferP2P3P42023/2/5操作系統(tǒng)復(fù)習29設(shè)P1、P2、P3、P4的資源信號量分別為S1、S2、S3、S4semaphoreS1,S2,S3,S4;S1.value=3;S2.vale=S3.vale=S4.value=0;parbeginprocessP1{while(condition){ P1生成一個消息；

P（S1）；P（S1）；P（S1）；

P1將消息存入緩沖區(qū)buffer；

V（S2）；V（S3）；V（S4）；

}}解:2023/2/5操作系統(tǒng)復(fù)習30processPi(i=2,3,4){while（condition）

{ P（Si）；

Pi從buffer中取出消息；

V（S1）；

Pi消費（使用）該消息；

}}parend2023/2/5操作系統(tǒng)復(fù)習318.有如下圖所示的工作模型：三個進程P0、P1、P2和三個緩沖區(qū)B0、B1、B2，進程間借助相鄰緩沖區(qū)傳遞消息：P0每次從B0中取出一條消息經(jīng)加工后送入B1中，P1每次從B1中取出一條消息經(jīng)加工后送入B2中，P2每次從B2中取出一條消息經(jīng)加工后送入B0中。B0，B1，B2分別可存放3，2，2個消息。初始時B0中有2個消息，B1，B2中各有1個消息。用P、V操作寫出P0，P1，P2的同步及互斥流程。

2023/2/5操作系統(tǒng)復(fù)習32分析：三個進程形成一個環(huán)，兩兩互為P-C因此設(shè)置6個資源信號量，另外需要再設(shè)置一個互斥信號量保證緩沖區(qū)的互斥訪問；此外，本題請注意緩沖去開始是為非空狀態(tài)，因此需要正確設(shè)置各個信號量的初始值解：semaphoreempty0,full0,empty1,full1,empty2,full2,mutex;empty0=1;full0=2;//沖區(qū)B0有2個消息，還可放1個消息empty1=1;full1=1;//沖區(qū)B1有1個消息，還可放1個消息empty2=1;full2=1;//沖區(qū)B2有1個消息，還可放1個消息mutex=1; //互斥信號量

2023/2/5操作系統(tǒng)復(fù)習33parbeginProcessP0{while(1){P(full0); //看看B0中是否有消息P(mutex); //互斥訪問B0

從緩沖區(qū)B0中取一個消息x;V(mutex);V(empty0); //B0中空出一個存放消息的位置

加工消息x;P(empty1); //看看B1中是否可放一個消息P(mutex); //互斥訪問B1

將加工后的x存入緩沖區(qū)B1;V(mutex);V(full1); //B1中增加一個消息

}}2023/2/5操作系統(tǒng)復(fù)習34ProcessP1{while(1){P(full1); //看看B1中是否有消息P(mutex); //互斥訪問B1

從緩沖區(qū)B1中取一個消息y;V(mutex);V(empty1); //B1中空出一個存放消息的位置

加工消息y;P(empty2); //看看B2中是否可放一個消息P(mutex); //互斥訪問B2

將加工后的x存入緩沖區(qū)B2;V(mutex);V(full2); //B2中增加一個消息

}

}2023/2/5操作系統(tǒng)復(fù)習35ProcessP2{while(1){P(full2); //看看B2中是否有消息P(mutex); //互斥訪問B2

從緩沖區(qū)B2中取一個消息z;V(mutex);V(empty2); //B2中空出一個存放消息的位置

加工消息z;P(empty0); //看看B0中是否可放一個消息P(mutex); //互斥訪問B0

將加工后的z存入緩沖區(qū)B0;V(mutex);V(full0); //B0中增加一個消息

}}parend2023/2/5操作系統(tǒng)復(fù)習369.在一個生產(chǎn)車間中，有3個工人共同協(xié)作生產(chǎn)某種產(chǎn)品，工人1負責生產(chǎn)零件A并放入車間的貨架，工人2負責生產(chǎn)零件B并放入車間的貨架，工人3從貨架上獲取零件，并將1個零件A和一個零件B組裝成成品運出車間，車間的貨架上最多共可以存放1000個零件，為了保證合理的庫存和零件配比，當某種零件數(shù)量比另一種零件數(shù)量多出100個時，相應(yīng)的工人暫時停止該種零件的生產(chǎn)。試用PV操作描述上述生產(chǎn)過程。2023/2/5操作系統(tǒng)復(fù)習37分析：這是2個生產(chǎn)者、1個消費者的問題；2個生產(chǎn)者公用一個緩沖區(qū)，因此Worker1和Worker2的資源信號量為空閑緩沖區(qū)empty；Worker3需要2種資源，因此設(shè)置資源信號量full1和full2；兩種零件存在配比問題，可以使用2個資源信號量來控制，設(shè)為sa和sb；最后，需設(shè)置用于互斥訪問的互斥信號量mutex解：semaphoremutex，empty，full1，full2，sa，sb；mutex.vale=1； //互斥信號量empty.value=1000；//空閑貨架位數(shù)，假設(shè)初始時貨架全空fulla.value=fullb.value=0；//零件A和零件B的數(shù)量，sa.value=100；//sb.value=100； 2023/2/5操作系統(tǒng)復(fù)習38ProcessWorker2{while(1){

生產(chǎn)一個零件B；P（empty）；P（sb）；P（mutex）；將零件B放入貨架；V（fullb）；V（sa）；V（mutex）；}}ProcessWorker3{while(1){P（fulla）；P（fullb）；P（mutex）；

拿去零件A和B；V（empty）；V（empty）；V（mutex）；

組裝產(chǎn)品；}

}

PARENDProcessWorker1{while(1){生產(chǎn)一個零件B；P（empty）；P（sa）；P（mutex）：將零件A放入貨架；V（fulla）；V（sb）；V（mutex）；}}2023/2/5操作系統(tǒng)復(fù)習3910.某銀行提供1個服務(wù)窗口和10個顧客等待座位。顧客到達銀行時，若有空座位，則到取號機領(lǐng)取一個號，等待叫號。取號機每次僅允許一位顧客使用。當營業(yè)員空閑時，通過叫號選取一位顧客，并為其服務(wù)。顧客和營業(yè)員的活動過程描述如下：cobegin{process顧客i {

從取號機獲得

一個號碼;

等待叫號;

獲得服務(wù);}}process營業(yè)員 {while(TRUE){

叫號;

為顧客服務(wù);}}2023/2/5操作系統(tǒng)復(fù)習40請?zhí)砑颖匾男盘柫亢蚉、V（或wait()、signal()）操作實現(xiàn)上述過程的互斥和同步。要求寫出完整的過程，說明信號量的含義并賦初值。分析：semaphoremutex=1; //用于顧客取號的互斥信號量semaphoreseat=10; //顧客等待座位的資源信號量，當沒有空座位時顧客在其上阻塞semaphoreS1=0; //營業(yè)員與顧客的同步信號量，當沒有顧客時營業(yè)員在其上阻塞semaphoreS2=0; //顧客與營業(yè)員的同步信號量，等待叫號時顧客在其上阻塞2023/2/5操作系統(tǒng)復(fù)習41cobegin{process顧客i{ P(seat); //若沒有空座位，顧客等待 P(mutex); //取號互斥

從取號機獲得一個號碼; V(mutex); V(S1);//通知營業(yè)員，已有顧客 P(S2);

等待叫號;

V(seat);//空出一個座位

獲得服務(wù); }2023/2/5操作系統(tǒng)復(fù)習42process營業(yè)員{ while(TRUE) { P(S1); //若無顧客則等待 V(S2); //喚醒等待叫號的顧客

叫號;

為顧客服務(wù); }}}2023/2/5操作系統(tǒng)復(fù)習4311.在一個采用頁式虛擬存儲管理的系統(tǒng)中，有一用戶作業(yè)，它依次要訪問的字地址序列是：115，228，120，88，446，102，321，432，260，167，若該作業(yè)的第0頁已經(jīng)裝入主存，現(xiàn)分配給該作業(yè)的主存共300字，頁的大小為100字，請回答下列問題：(1)按FIFO調(diào)度算法，將產(chǎn)生多少次缺頁中斷？依次淘汰的頁號是什么？缺頁中斷率為多少？(2)按LRU調(diào)度算法，將產(chǎn)生多少次缺頁中斷？依次淘汰的頁號是什么？缺頁中斷率為多少？答：由題目的已知條件，可得頁面走向為：

1,2,1,0,4,1,3,4,2,1 (1)FIFO的頁面置換圖如下：按FIFO調(diào)度算法將產(chǎn)生5次缺頁中斷，依次淘汰的頁號為0,1,2，缺頁中斷率為5/10=50%。2023/2/5操作系統(tǒng)復(fù)習44頁面走向1210413421頁幀00004444441111113333

222222221是否缺頁√√

√

√

√被淘汰頁號

0

1

2(2)LRU算法的頁面置換圖如下：按LRU調(diào)度算法將產(chǎn)生6次缺頁中斷，依次淘汰的頁號為2,0,1,3，缺頁中斷率為6/10=60%。2023/2/5操作系統(tǒng)復(fù)習45頁面走向1210413421頁幀12104134210121041342

002104134是否缺頁√√

√

√

√√被淘汰頁號

2

0

132023/2/5操作系統(tǒng)復(fù)習4612．請求分頁管理系統(tǒng)中，假設(shè)某進程的頁表內(nèi)容如下表所示。頁表內(nèi)容頁號頁框(Pageframe)號有效位（存在位）0101H11—02254H1頁面大小為4KB，一次內(nèi)存的訪問時間是100ns，一次快表(TLB)的訪問時間是10ns，處理一次缺頁的平均時間為108ns(已含更新TLB和頁表的時間)，進程的駐留集大小固定為2，采用最近最少使用置換算法(LRU)和局部淘汰策略。假設(shè)①TLB初始為空；②地址轉(zhuǎn)換時先訪問TLB，若TLB未命中，在訪問頁表(忽略訪問頁表之后的TLB更新時間)；③有效位為0表示頁面不再內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H，請問：2023/2/5操作系統(tǒng)復(fù)習47(1)依次訪問上述三個虛地址，各需多少時間？給出計算過程。(2)基于上述訪問序列，虛地址1565H的物理地址是多少？請說明理由。分析：考察點地址轉(zhuǎn)換的過程

快表命中：

快表訪問時間+一次內(nèi)存訪問時間

快表未命中但未缺頁：

快表訪問時間+二次內(nèi)存訪問時間

（一次頁表訪問，一次實際地址訪問）

快表未命中且存在缺頁：

快表訪問時間+二次內(nèi)存訪問時間+缺頁處理時間2023/2/5操作系統(tǒng)復(fù)習48(1)因頁的大小為4KB，即212，故十六進制地址的低3位是頁內(nèi)偏移，高位是頁號。2362H：頁號P=2，訪問快表10ns，因初始為空，訪問頁表100ns得到頁框號，與頁內(nèi)偏移合成物理地址后訪問內(nèi)存100ns，共花時間10+100+100=210ns。 1565H：P=1，訪問快表10ns，落空，訪問頁表100ns缺頁，進行缺頁中斷處理108ns，合成物理地址后訪問內(nèi)存100ns，共計10+100+108+100=318ns。 25A5H：P=2，訪問快表10ns命中，合成物理地址后訪問內(nèi)存100ns，共計110ns。(2)故訪問1565H時，因在此之前剛剛訪問2362H所在的2號頁，按LRU算法，應(yīng)淘汰0號頁，空出101H號頁框存放邏輯地址1565H所在的1號頁。由頁框號101H和頁內(nèi)偏移565H合成得到虛地址1565H對應(yīng)的物理地址為101565H。 13.某計算機主存按字節(jié)編址，邏輯地址和物理地址都是

32位，頁表項大小為4字節(jié)。請回答下列問題。1）若使用一級頁表的分頁存儲管理方式，邏輯地址結(jié)構(gòu)為：則頁的大小是多少字節(jié)？頁表最大占用多少字節(jié)？2）若使用二級頁表的分頁存儲管理方式，邏輯地址結(jié)構(gòu)為：設(shè)邏輯地址為LA，請分別給出其對應(yīng)的頁目錄號和頁表索引的表達式。2023/2/5操作系統(tǒng)復(fù)習49頁號（20位）頁內(nèi)偏移量（12位）頁目錄號（10位）頁表索引（10位）頁內(nèi)偏移量（12位）代碼頁面2代碼頁面1物理地址3物理地址309000000H3）采用（1）中的分頁存儲管理方式，一個代碼段起始邏輯地址為00008000H，其長度為8KB，被裝載到從物理地址00900000H開始的連續(xù)主存空間中。頁表從主存00200000H開始的物理地址處連續(xù)存放，如下圖所示（地址大小自下向上遞增）。請計算出該代碼段對應(yīng)的兩個頁表項的物理地址（假設(shè)每個頁表項的長度為4字節(jié)）、這兩個頁表項中的頁框號以及代碼頁面

2的起始物理地址。2023/2/5操作系統(tǒng)復(fù)習50物理地址3代碼頁面2代碼頁面1物理地址309000000H

頁表

物理地址2頁框號2物理地址1頁框號102000000H

2023/2/5操作系統(tǒng)復(fù)習51（1）因為頁內(nèi)偏移量是12位，所以頁大小為4KB，頁表項數(shù)為232/4K=220，該一級頁表最大為220×4B=4MB。（2）頁目錄號可表示為： (((unsignedint)(LA))>>22)&0x3FF。

或 INT(LA/pow(2,22))頁表索引可表示為：(((unsignedint)(LA))>>12)&0x3FF。

或 (LA/pow(2,12)

)%pow(2,10)（3）代碼頁面1的邏輯地址為00008000H，表明其位于第8個頁處，對應(yīng)頁表中的第8個頁表項，所以第8個頁表項的物理地址=頁表起始地址+8×頁表項的字節(jié)數(shù)=00200000H+8×4=00200020H。由此可得如下的答案：物理地址1：00200020H 物理地址2：00200024H物理地址3：09001000H 頁框號1：09000000H頁框號2：09000001H2023/2/5操作系統(tǒng)復(fù)習5214．設(shè)某計算機的邏輯地址空間和物理地址空間均為64KB，按字節(jié)編址。若某進程最多需要6頁(Page)數(shù)據(jù)存儲空間，頁的大小為1KB，操作系統(tǒng)采用固定分配局部置換策略為此進程分配4個頁框(PageFrame)。在時刻260前的該進程訪問情況如下表所示(訪問位即使用位)。頁號頁框號裝入時間訪問位071301142301222001391601當進程執(zhí)行到時刻260時，要訪問邏輯地址為17CAH的數(shù)據(jù)。請回答下列問題：（1）該邏輯地址的對應(yīng)的頁號是多少？（2）若采用先進先出(FIFO)置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程。2023/2/5操作系統(tǒng)復(fù)習53（3）若采用時鐘(CLOCK)置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算過程(設(shè)搜索下一頁的指針沿順時針方向移動，且當前指向2號頁框，示意圖如下)。0號頁1號頁2號頁3號頁2號頁框4號頁框7號頁框9號頁框2023/2/5操作系統(tǒng)復(fù)習54(1)17CAH=0001011111001010B，表示頁號的位是左邊6位，即00101B，所以頁號為5。根據(jù)FIFO算法，需要替換裝入時間最早的頁，故需要置換裝入時間最早的0號頁，即將5頁裝入7號頁框中，所以物理地址為0001111111001010B，換算成十六進制，為1FCAH。根據(jù)CLOCK算法，如果當前指針所指頁框的使用位為0，則替換該頁；否則將其使用位清零，并將指針指向下一個頁框，繼續(xù)查找。根據(jù)題設(shè)和示意圖，將從2號頁框開始，前4次查找頁框順序為2→4→7→9，并將對應(yīng)頁框的使用位清零。在第5次查找中，指針指向2號頁框，因2號頁框的使用位為0，故淘汰2號頁框?qū)?yīng)的2號頁，把5號頁裝入2號頁框中，并將對應(yīng)的使用位置為1，所以對應(yīng)的物理地址為0000101111001010B，換算成十六進制，為0BCAH。 2023/2/5操作系統(tǒng)復(fù)習5515.若遞交給磁盤驅(qū)動程序的磁盤柱面請求按到達時間順序分別是10、22、20、2、40、6和38，設(shè)磁頭初始處于20柱面，磁頭從一柱面移到另一相鄰柱面的時間是2ms，則對于FCFS、最短尋道時間優(yōu)先、電梯算法（初始磁頭向高柱面移動），平均尋道時間各為多少？解：對于FCFS，服務(wù)順序為10、22、20、2、40、6、38

平均尋道時間=(10+12+2+18+38+34+32)*2/7=41.71ms最短尋道時間優(yōu)先，服務(wù)順序為：20、22、10、6、2、38、40

平均尋道時間=(0+2+12+4+4+36+2)*2/7=17.14ms電梯算法，服務(wù)順序為： 20、22、38、40、10、6、2

平均尋道時間=(0+2+16+2+30+4+4)*2/8=16.57ms2023/2/5操作系統(tǒng)復(fù)習5616.設(shè)文件索引節(jié)點中有7個地址項，其中4個地址項是直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4字節(jié)。若磁盤索引塊和磁盤數(shù)據(jù)塊大小均為256字節(jié)，則可表示的單個文件最大長度是多少？解：每個盤塊存放的索引項=256/4=64（項）直接地址存儲容量=4×256=1KB一級間址存儲容量=2×64×256=32KB二級間址存儲容量=1×64×64×256=1024KB最大文件長度=1+32+1024=1057KB2023/2/5操作系統(tǒng)復(fù)習5717．假設(shè)計算機系統(tǒng)采用CSCAN(循環(huán)掃描)磁盤調(diào)度策略，使用2KB的內(nèi)存空間記錄16384個磁盤塊的空閑狀態(tài)。（1）請說明在上述條件下如何進行磁盤塊空閑狀態(tài)的管理。（2）設(shè)某單面磁盤旋轉(zhuǎn)速度為每分鐘6000轉(zhuǎn)，每個磁道有100個扇區(qū)，相鄰磁道間的平均移動時間為1ms。若在某時刻，磁頭位于100號磁道處，并沿著磁道號增大的方向移動(如下圖所示)，磁道號請求隊列為50,90,30,120，對請求隊列中的每一個磁道需讀取1個隨機分布的扇區(qū)，則讀完這4個扇區(qū)總共需要多少時間？給出計算過程。2023/2/5操作系統(tǒng)復(fù)習58磁頭當前運動方向0號磁道隨機分布的某扇區(qū)100號磁道2023/2/5操作系統(tǒng)復(fù)習59解：(1)用位圖表示磁盤的空閑塊狀態(tài)。每一位表示一個磁盤塊的空閑狀態(tài)，共需16384/32=512個字=512×4個字節(jié)=2KB，正好可放在系統(tǒng)提供的內(nèi)存中。(2)采用CSCAN調(diào)度算法，訪問磁道的順序為120,30,50,90，則移動磁道長度為20+90+20+40=170，總的移動時間為170×1ms=170ms。由于轉(zhuǎn)速為6000r/m，則平均旋轉(zhuǎn)延遲時間為60/(6000×2)×1000ms=5ms，總的旋轉(zhuǎn)時間為5ms×4=20ms。由于轉(zhuǎn)速為6000r/m，則讀取一個磁道上的一個扇區(qū)的平均讀取時間為10ms/100=0.1ms，總的讀取扇區(qū)的時間=0.1ms×4=0.4ms。讀取上述磁道上的所有4個扇區(qū)所花費的總時間=170ms+20ms+0.4ms=190.4ms。2023/2/5操作系統(tǒng)復(fù)習6018.考慮一個存在于磁盤上的文件系統(tǒng)，其中的文件由大小為512B的邏輯塊組成。假定每一個文件有一個文件目錄項，該目錄項包含該文件的文件名、文件長度以及第一塊（或第一索引塊）和最后一塊的位置，而且該目錄項位于內(nèi)存。對于索引結(jié)構(gòu)文件，該目錄項指明第一索引塊，該索引塊又一次指向511個文件塊（每個索引值占4B），且有一指向下一索引塊的指針(指針占4B)。針對連續(xù)、鏈接、索引結(jié)構(gòu)的每一種，如果當前位于邏輯塊30（即之前最后一次訪問的塊是邏輯塊30）且希望訪問邏輯塊20(假設(shè)邏輯塊號從0開始編號)，那么，必須分別從磁盤上讀多少個物理塊？2023/2/5操作系統(tǒng)復(fù)習61解：(1)對于磁盤上的連續(xù)結(jié)構(gòu)文件，由文件的邏輯塊號、文件塊大小、磁盤物理塊大小以及文件的首塊位置，可以計算該邏輯塊所在的物理塊號（地址）A：A=A0+(N*L)/S=A0+20*512/2048=A0+5其中：A0為文件第0塊位置，N為邏輯塊號(N=20)，L為邏輯塊長度(L=512)，S為磁盤塊長度(由已知條件得S=511*4+1*4=2048)。因此，無論當前讀寫位置如何，要訪問第20個邏輯塊，只要直接讀出文件的第6個物理塊，即只需讀1個磁盤塊即可(因目錄項已在內(nèi)存)。 2023/2/5操作系統(tǒng)復(fù)習62

(2)對于磁盤上的鏈接結(jié)構(gòu)文件，當前讀寫了邏輯塊30，要訪問邏輯塊20，需要從文件開頭開始。由前面分析知，磁盤塊大小2048B，故每個盤塊可存放4個邏輯塊。邏輯塊20在文件的第6個物理塊