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

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

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

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

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

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

{ P（Si）；

Pi從buffer中取出消息；

V（S1）；

Pi消費（使用）該消息；

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

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

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

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

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

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

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

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

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

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

}

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

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

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

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

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

生產一個零件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）；

組裝產品；}

}

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

從取號機獲得

一個號碼;

等待叫號;

獲得服務;}}process營業員 {while(TRUE){

叫號;

為顧客服務;}}2023/2/5操作系統復習40請添加必要的信號量和P、V（或wait()、signal()）操作實現上述過程的互斥和同步。要求寫出完整的過程，說明信號量的含義并賦初值。分析：semaphoremutex=1; //用于顧客取號的互斥信號量semaphoreseat=10; //顧客等待座位的資源信號量，當沒有空座位時顧客在其上阻塞semaphoreS1=0; //營業員與顧客的同步信號量，當沒有顧客時營業員在其上阻塞semaphoreS2=0; //顧客與營業員的同步信號量，等待叫號時顧客在其上阻塞2023/2/5操作系統復習41cobegin{process顧客i{ P(seat); //若沒有空座位，顧客等待 P(mutex); //取號互斥

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

等待叫號;

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

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

叫號;

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

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

222222221是否缺頁√√

√

√

√被淘汰頁號

0

1

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

002104134是否缺頁√√

√

√

√√被淘汰頁號

2

0

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

快表命中：

快表訪問時間+一次內存訪問時間

快表未命中但未缺頁：

快表訪問時間+二次內存訪問時間

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

快表未命中且存在缺頁：

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

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

2的起始物理地址。2023/2/5操作系統復習50物理地址3代碼頁面2代碼頁面1物理地址309000000H

頁表

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

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

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

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

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

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