1、操作系統原理復習南京工業大學信息學院計算機系1.第1頁，共68頁。注意要點考核形式試卷，閉卷考試，120分鐘可以帶計算器，但不得使用手機中的計算器功能試卷占總評成績的80%考察范圍第一章第九章部分章節除外2022/7/222.第2頁，共68頁。題型分布單選題15題，共30分填空題10題，共10分綜合應用題6題，共60分2022/7/223.第3頁，共68頁。主要知識點第一章操作系統的目標操作系統的作用三種經典的操作系統類型分時系統的特征實時系統的特征操作系統的基本特征用戶接口的種類2022/7/224.第4頁，共68頁。主要知識點第二章順序執行程序的主要特征并發執行程序的主要特征進程的特征進程

2、的各個狀態，及各狀態之間的轉換條件導致進程創建、終止、阻塞的條件同步機制的4條設計原則進程同步：只需要掌握用信號量解決P-C問題進程通信的方法2022/7/225.第5頁，共68頁。主要知識點第三章處理機的調度層次調度算法：FIFO，SJF，高相應比優先，時間片輪轉產生死鎖的4個必要條件銀行家算法資源分配圖的簡化2022/7/226.第6頁，共68頁。主要知識點第四章動態分區分配中分配和回收內存的方法動態分區分配算法：FF，NF，BF，WF邏輯地址到物理地址的轉換及訪問時間的計算多級頁表段頁式存儲管理的地址轉換（虛地址到實地址的轉換）2022/7/227.第7頁，共68頁。主要知識點第五章虛擬

3、存儲器的特征頁面置換算法及缺頁率的計算最佳，FIFO，LRU，時鐘置換抖動的概念2022/7/228.第8頁，共68頁。主要知識點第六章I/O系統的基本功能I/O系統的層次結構I/O設備的類型設備控制器的基本功能單緩沖和雙緩沖傳輸時間的計算磁盤訪問時間的計算磁盤調度算法：FCFS，SSTF，SCAN，CSCAN2022/7/229.第9頁，共68頁。主要知識點第七章文件的組織分類及其特征目錄管理的要求目錄結構的組織形式目錄檢索的方法文件共享的方法（文件）2022/7/2210.第10頁，共68頁。主要知識點第八章連續組織方式的優缺點隱式連接、顯示鏈接組織方式的優缺點索引組織方式的優缺點混合索引

4、文件最大容量的計算方法位示圖法存儲空間管理（位圖計算）2022/7/2211.第11頁，共68頁。主要知識點第九章用戶接口的類型主要聯機命令Shell命令語言的主要簡單命令系統調用的實現方法2022/7/2212.第12頁，共68頁。1. 假設有一磁盤含有64000塊，塊號記為164000，現用2000個32位(Bit)的字作該盤的位示圖，試問第59999塊對應于位示圖中第幾字的第幾位(字、位均從0開始)；而第1599字的第17位對應于磁盤的第幾塊?解：由塊號b，求字號i和位號j的公式為：i=(b-1) div 32(div表示整數除法，32是字長)j=(b-1) mod 32(mod表示整數

5、相除取余數)(59999-1) div 32=1874 (59999-1) mod 32=30故59999塊對應于位示圖中第1874字的第30位。由位示圖的字號i和位號j，求對應的磁盤塊號b的公式為：b=i32+j+1=159932+17+1=51186即第1599字的第17位對應于磁盤的第51186塊。2022/7/2213.第13頁，共68頁。2. 頁式存儲管理中，主存空間按頁分配，可用一張“位示圖”構成主存分配表。假設主存容量為2M字節，頁面長度為512字節，若用字長為32位的字作主存分配的“位示圖”需要多少個字？如頁號從1開始，字號和字內位號（從高位到低位）均從1開始，試問：第2999

6、頁對應于何字何位；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頁2022/7/2214.第14頁，共68頁。3某多道程序設計系統供用戶使用的主存為100KB，磁帶機2臺，打印機1臺。采用可變分區內存管理，采用靜態方式分配外圍設備，忽略用戶作業的I/O時間。現有如下作業序列： 作業名提交時間需運行時間主存需求量磁帶

7、機需求打印機需求J18:0025分鐘15KB11J28:2010分鐘30KB01J38:2020分鐘60KB10J48:3020分鐘20KB10J58:3515分鐘10KB11作業調度采用FCFS策略，優先分配主存低地址區域且不準移動已在主存中的作業，進程調度采用時間片輪轉算法(即在主存中的作業均分CPU時間)?，F求： 2022/7/2215.第15頁，共68頁。(1) 作業被調度的先后次序；(2) 全部作業運行結束的時間；(3) 作業的平均周轉時間；(4) 最大作業周轉時間。作業達到及結束順序分析：8:00J1到達，分配它所需資源(15KB內存、 1臺磁帶機、1臺打印機后，調入內存運行。余內

8、存85KB、磁帶機1臺。8:20J2到達，因無打印機，不調入。同時J3到達，分配它內存60KB，磁帶機1臺，調入內存，與J1均分CPU時間運行。余內存25KB、磁帶機和打印機都已分完(余0臺)。8:30J1結束，釋放內存15KB、磁帶機1臺、打印機1臺。雖有打印機但內存不夠，J2仍不能調入；J4到達，因低端內存15KB不夠，分配高端內存20KB和磁帶機1臺，調入內存與J3一起運行。剩下內存空閑塊是15KB、5KB，打印機1臺8:35J5到達，因無磁帶機，不能調入。2022/7/2216.第16頁，共68頁。9:00J3結束。釋放資源后，系統有內存75KB，5KB、打印機和磁帶機個1臺。J2調入

9、，內存余45KB，5KB、磁帶機剩1臺、打印機0臺。J5仍不能進入(無打印機)。將J2、J4運行。J4還需運行5分鐘。9:10J4結束，釋放資源后，內存空余70KB、磁帶機空2臺、打印機0臺。J5仍不能進入。J2單獨運行(還需5分鐘)。9:15J2結束，釋放資源后，內存有100KB、磁帶機有2臺、打印機有1臺。J5調入運行。9:30J5結束。解：(1) 作業被調度的先后次序為J1, J3, J4, J2, J5(2) 全部作業運行結束的時間為9:30(3) 作業的平均周轉時間為(30+55+40+40+55)5=44 (分鐘)(4) 最大作業周轉時間為55分鐘。2022/7/2217.第17頁

10、，共68頁。CPU磁帶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進入以下是畫圖分析法：2022/7/2218.第18頁，共68頁。4多道批處理系統中配有一個處理器和2臺外設(D1和D2)，用戶存儲空間為100MB。已知系統采用可搶占式的高

11、優先數調度算法和不允許移動的可變分區分配策略，設備分配按照動態分配原則。今有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分鐘分析見后頁2022/7/2219.第19頁，共68頁。CCDDDCCADBBBCCCAADDBAA1

12、2345678910111213CPUD1D2時間A的周轉時間為12分鐘B的周轉時間為13分鐘C的周轉時間為7分鐘D的周轉時間為12分鐘所以平均周轉時間為(12+13+7+12)/4=11(分鐘)2022/7/2220.第20頁，共68頁。5. 有一個具有兩道作業的批處理系統（最多可有兩道作業同時裝入內存執行），作業調度采用計算時間短的作業優先調度算法，進程調度采用以優先數為基礎的搶占式調度算法，今有如下作業序列，作業優先數即為進程優先數，優先數越小優先級越高：(1) 列出所有作業進入內存時間及結束時間。(2) 計算平均周轉時間。作業名到達時間估計運行時間優先數J110 : 1020分鐘5J2

13、10 : 2030分鐘3J310 : 3025分鐘4J410 : 5020分鐘62022/7/2221.第21頁，共68頁。分析：10：10 J1到達，進入系統，運行10分鐘10：20 J2到達，進入系統，因優先級高于J1搶奪CPU開始運行10：30 J3到達后備隊列，因為系統已經載入2個作業，無法進入系統10：50 J2運行結束退出，J4到達，根據短作業優先，調入J4，由于 J1的優先級高于J4，J1開始運行11：00 J1運行結束退出，J3進入系統，由于J3優先級較高，開始運行11：25 J3運行結束退出，J4開始運行11：45 J4運行結束2022/7/2222.第22頁，共68頁。答：

14、（1）各個作業進入主存時間、結束時間和周轉時間如下表所示：（2）平均周轉時間：（50+30+55+55）/4=47.5（min）作業名提交時間進入時間結束時間周轉時間J110：1010：1011：0050J210：2010：2010：5030J310：3011：0011：2555J410：5010：5011：45552022/7/2223.第23頁，共68頁。6有一個多道程序設計系統，采用不可移動的可變分區方式管理主存空間，設主存空間為100K，采用最先適應分配算法分配主存，作業調度采用響應比高者優先算法，進程調度采用時間片輪轉算法（即內存中的作業均分CPU時間），今有如下作業序列：假定所有作

15、業都是計算型作業且忽略系統調度時間?；卮鹣铝袉栴}：(1)列表說明各個作業被裝入主存的時間、完成時間和周轉時間；(2)寫出各作業被調入主存的順序；(3)計算5個作業的平均周轉時間。作業名提交時間需要執行時間要求主存量J110 : 0040分鐘25KJ210 : 1530分鐘60KJ310 : 3020分鐘50KJ410 : 3525分鐘18KJ510 : 4015分鐘20K2022/7/2224.第24頁，共68頁。答：（1）各個作業被裝入主存的時間、完成時間和周轉時間如下表所示：（2）作業被調入主存的順序為J1，J2，J5，J3，J4。（3）平均周轉時間=（65+60+85+95+55）/5=

16、72（分鐘）。作業名裝入主存時間作業完成時間周轉時間J110：0011：0565J210：1511：1560J311：1511：5585J411：3512：1095J511：0511：35552022/7/2225.第25頁，共68頁。信號量機制解決進程同步問題的一般方法：為同步雙方設置各自的信號量，初值為其初始狀態可用的資源數(故該信號量稱為資源信號量或私有信號量)；同步雙方任一進程在進入臨界區之前，應先對自己的信號量執行wait()操作，以測試是否有自己可用的資源。若有資源可用，則進入臨界區，否則阻塞；同步雙方任一進程離開臨界區后，應對合作方 (對方)的信號量執行signal()操作，以通

17、知(若對方處于阻塞狀態，則喚醒它)對方已有資源可用(對方已可進入臨界區)。26.第26頁，共68頁。用信號量機制解決P-C問題的基本方法：為生產者設置1個私有信號量empty，其初值為1，表示有1個空緩沖區；為消費者設置1個私有信號量full，其初值為0，表示開始時沒有滿緩沖區；（信號量初值由物理意義確定）生產者將產品存入緩沖區之前，應先測試緩沖區是否空：執行wait(empty)操作；離開臨界區(存入產品)后，應通知(可能會喚醒)消費者：執行signal(full)操作；消費者從緩沖區取產品之前，應先測試緩沖區是否滿：執行wait(full)操作；離開臨界區(取走產品)后，應通知(可能會喚醒

18、)生產者：執行signal(empty)操作27.第27頁，共68頁。7. 進程P1使用緩沖區buffer向進程P2，P3，P4發送消息，要求每當P1向buffer中發消息時，只有當P2，P3，P4進程都讀取這條消息后才可向buffer中發送新的消息。利用P、V原語描述如下圖所示進程的動作序列。 P1bufferP2P3P42022/7/2228.第28頁，共68頁。設P1、P2、P3、P4的資源信號量分別為S1、S2、S3、S4semaphore S1,S2,S3,S4;S1.value=3;S2.vale=S3.vale=S4.value=0; parbeginprocess P1 whi

19、le (condition) P1生成一個消息；P（S1）；P（S1）；P（S1）；P1將消息存入緩沖區buffer；V（S2）；V（S3）；V（S4）； 解:2022/7/2229.第29頁，共68頁。process Pi(i=2,3,4) while （condition） P（Si）；Pi從buffer中取出消息；V（S1）；Pi消費（使用）該消息； parend2022/7/2230.第30頁，共68頁。8. 有如下圖所示的工作模型：三個進程P0、P1、P2和三個緩沖區B0、B1、B2，進程間借助相鄰緩沖區傳遞消息：P0每次從B0中取出一條消息經加工后送入B1中，P1每次從B1中取出一

20、條消息經加工后送入B2中，P2每次從B2中取出一條消息經加工后送入B0中。B0，B1，B2分別可存放3，2，2個消息。初始時B0中有2個消息，B1 ，B2中各有1個消息。用P、V操作寫出P0，P1，P2的同步及互斥流程。 2022/7/2231.第31頁，共68頁。分析：三個進程形成一個環，兩兩互為P-C因此設置6個資源信號量，另外需要再設置一個互斥信號量保證緩沖區的互斥訪問；此外，本題請注意緩沖去開始是為非空狀態，因此需要正確設置各個信號量的初始值解：semaphore empty0,full0,empty1,full1,empty2,full2,mutex;empty0=1;full0=2

21、; /沖區B0有2個消息，還可放1個消息empty1=1; full1=1; /沖區B1有1個消息，還可放1個消息empty2=1; full2=1; /沖區B2有1個消息，還可放1個消息mutex=1;/互斥信號量2022/7/2232.第32頁，共68頁。parbeginProcess P0 while (1) P(full0);/看看B0中是否有消息 P(mutex);/互斥訪問B0 從緩沖區B0中取一個消息x; V(mutex); V(empty0);/B0中空出一個存放消息的位置 加工消息x; P(empty1);/看看B1中是否可放一個消息 P(mutex); /互斥訪問B1 將加

22、工后的x存入緩沖區B1; V(mutex); V(full1);/B1中增加一個消息 2022/7/2233.第33頁，共68頁。Process P1 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中增加一個消息 2022/7/2234.第34頁，共68頁。Pro

23、cess P2 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中增加一個消息 parend2022/7/2235.第35頁，共68頁。9. 在一個生產車間中，有3個工人共同協作生產某種產品，工人1負責生產零件A并放入車間的貨架，工人2負責生產零件B并放入車間的貨架，工人3從

24、貨架上獲取零件，并將1個零件A和一個零件B組裝成成品運出車間，車間的貨架上最多共可以存放1000個零件，為了保證合理的庫存和零件配比，當某種零件數量比另一種零件數量多出100個時，相應的工人暫時停止該種零件的生產。試用PV操作描述上述生產過程。2022/7/2236.第36頁，共68頁。分析：這是2個生產者、1個消費者的問題；2個生產者公用一個緩沖區，因此Worker1和Worker2的資源信號量為空閑緩沖區empty；Worker3需要2種資源，因此設置資源信號量full1和full2；兩種零件存在配比問題，可以使用2個資源信號量來控制，設為sa和sb；最后，需設置用于互斥訪問的互斥信號量m

25、utex解：semaphore mutex，empty，full1，full2，sa，sb；mutex.vale = 1 ；/互斥信號量empty.value = 1000；/ 空閑貨架位數，假設初始時貨架全空fulla.value = fullb.value = 0；/ 零件A和零件B的數量，sa.value = 100；/ sb.value = 100；2022/7/2237.第37頁，共68頁。Process Worker2 while(1) 生產一個零件B； P（empty）； P（sb）； P（mutex）； 將零件B放入貨架； V（fullb）； V（sa）； V（mutex）；

26、Process Worker3 while(1) P（fulla）； P（fullb）； P（mutex）； 拿去零件A和B； V（empty）； V（empty）； V（mutex）； 組裝產品； PARENDProcess Worker1 while(1) 生產一個零件B； P（empty）； P（sa）； P（mutex）： 將零件A放入貨架； V（fulla）； V（sb）； V（mutex）； 2022/7/2238.第38頁，共68頁。10. 某銀行提供1個服務窗口和10個顧客等待座位。顧客到達銀行時，若有空座位，則到取號機領取一個號，等待叫號。取號機每次僅允許一位顧客使用。當營業

27、員空閑時，通過叫號選取一位顧客，并為其服務。顧客和營業員的活動過程描述如下：cobegin process 顧客i 從取號機獲得 一個號碼; 等待叫號; 獲得服務; process 營業員 while (TRUE) 叫號; 為顧客服務; 2022/7/2239.第39頁，共68頁。請添加必要的信號量和P、V（或wait( )、signal( )）操作實現上述過程的互斥和同步。要求寫出完整的過程，說明信號量的含義并賦初值。分析：semaphore mutex=1;/用于顧客取號的互斥信號量semaphore seat=10;/顧客等待座位的資源信號量，當沒有空座位時顧客在其上阻塞semaphor

28、e S1=0;/營業員與顧客的同步信號量，當沒有顧客時營業員在其上阻塞semaphore S2=0;/顧客與營業員的同步信號量，等待叫號時顧客在其上阻塞2022/7/2240.第40頁，共68頁。cobegin process 顧客i P(seat);/若沒有空座位，顧客等待P(mutex);/取號互斥從取號機獲得一個號碼;V(mutex);V(S1); /通知營業員，已有顧客P(S2);等待叫號;V(seat); / 空出一個座位獲得服務; 2022/7/2241.第41頁，共68頁。 process 營業員while (TRUE)P(S1);/若無顧客則等待V(S2);/喚醒等待叫號的顧客

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

30、0, 4, 1, 3, 4, 2, 1 (1) FIFO的頁面置換圖如下：按FIFO調度算法將產生5次缺頁中斷，依次淘汰的頁號為0,1,2，缺頁中斷率為5/10=50%。頁面走向1210413421頁幀00004444441111113333222222221是否缺頁被淘汰頁號0122022/7/2244.第44頁，共68頁。(2) LRU算法的頁面置換圖如下：按LRU調度算法將產生6次缺頁中斷，依次淘汰的頁號為2,0,1,3，缺頁中斷率為6/10=60%。頁面走向1210413421頁幀12104134210121041342002104134是否缺頁被淘汰頁號20132022/7/2245

31、.第45頁，共68頁。12請求分頁管理系統中，假設某進程的頁表內容如下表所示。頁表內容 頁號頁框(Page frame)號有效位（存在位）0101H1102254H1頁面大小為4KB，一次內存的訪問時間是100ns，一次快表(TLB)的訪問時間是10ns，處理一次缺頁的平均時間為108ns(已含更新TLB和頁表的時間)，進程的駐留集大小固定為2，采用最近最少使用置換算法(LRU)和局部淘汰策略。假設TLB初始為空；地址轉換時先訪問TLB，若TLB未命中，在訪問頁表(忽略訪問頁表之后的TLB更新時間)；有效位為0表示頁面不再內存，產生缺頁中斷，缺頁中斷后，返回到產生缺頁中斷的指令處重新執行。設有

32、虛地址訪問序列2362H、1565H、25A5H，請問：2022/7/2246.第46頁，共68頁。(1) 依次訪問上述三個虛地址，各需多少時間？給出計算過程。(2) 基于上述訪問序列，虛地址1565H的物理地址是多少？請說明理由。分析：考察點地址轉換的過程 快表命中：快表訪問時間 + 一次內存訪問時間 快表未命中但未缺頁：快表訪問時間+二次內存訪問時間（一次頁表訪問，一次實際地址訪問） 快表未命中且存在缺頁：快表訪問時間+二次內存訪問時間+缺頁處理時間2022/7/2247.第47頁，共68頁。(1) 因頁的大小為4KB，即212，故十六進制地址的低3位是頁內偏移，高位是頁號。2362H：頁

33、號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和頁內偏移

34、565H合成得到虛地址1565H對應的物理地址為101565H。2022/7/2248.第48頁，共68頁。13. 某計算機主存按字節編址，邏輯地址和物理地址都是 32 位，頁表項大小為 4 字節。請回答下列問題。1）若使用一級頁表的分頁存儲管理方式，邏輯地址結構為： 則頁的大小是多少字節？頁表最大占用多少字節？2）若使用二級頁表的分頁存儲管理方式，邏輯地址結構為： 設邏輯地址為 LA，請分別給出其對應的頁目錄號和頁表索引的表達式。頁號（20 位）頁內偏移量（12 位）頁目錄號（10 位）頁表索引（10 位）頁內偏移量（12 位）代碼頁面2代碼頁面1物理地址3物理地址30900 0000H20

35、22/7/2249.第49頁，共68頁。3）采用（1）中的分頁存儲管理方式，一個代碼段起始邏輯地址為 0000 8000H，其長度為 8 KB，被裝載到從物理地址 0090 0000H 開始的連續主存空間中。頁表從主存0020 0000H 開始的物理地址處連續存放，如下圖所示（地址大小自下向上遞增） 。請計算出該代碼段對應的兩個頁表項的物理地址（假設每個頁表項的長度為4字節）、這兩個頁表項中的頁框號以及代碼頁面 2 的起始物理地址。物理地址3代碼頁面2代碼頁面1物理地址30900 0000H頁表物理地址2頁框號2物理地址1頁框號10200 0000H2022/7/2250.第50頁，共68頁。

36、（1）因為頁內偏移量是 12 位，所以頁大小為 4 KB，頁表項數為 232/4K=220，該一級頁表最大為 2204 B=4 MB。（2）頁目錄號可表示為：( ( ( unsigned int ) ( LA ) ) 22 ) & 0 x3FF。 或INT(LA / pow(2, 22)頁表索引可表示為：( ( ( unsigned int ) ( LA ) ) 12 ) & 0 x3FF?；?LA / pow(2,12) )%pow(2,10)（3）代碼頁面 1 的邏輯地址為 0000 8000H，表明其位于第 8 個頁處，對應頁表中的第 8 個頁表項，所以第 8 個頁表項的物理地址 = 頁

37、表起始地址+8頁表項的字節數 = 0020 0000H+84 = 0020 0020H。由此可得如下的答案：物理地址1： 0020 0020H物理地址2： 0020 0024H物理地址3： 0900 1000H頁框號1： 0900 0000H頁框號2： 0900 0001H2022/7/2251.第51頁，共68頁。14設某計算機的邏輯地址空間和物理地址空間均為64KB，按字節編址。若某進程最多需要6頁(Page)數據存儲空間，頁的大小為1KB，操作系統采用固定分配局部置換策略為此進程分配4個頁框(Page Frame)。在時刻260前的該進程訪問情況如下表所示(訪問位即使用位)。 頁號頁框號

38、裝入時間訪問位071301142301222001391601當進程執行到時刻260時，要訪問邏輯地址為17CAH的數據。請回答下列問題：（1）該邏輯地址的對應的頁號是多少？（2）若采用先進先出(FIFO)置換算法，該邏輯地址對應的物理地址是多少？要求給出計算過程。2022/7/2252.第52頁，共68頁。（3）若采用時鐘(CLOCK)置換算法，該邏輯地址對應的物理地址是多少？要求給出計算過程(設搜索下一頁的指針沿順時針方向移動，且當前指向2號頁框，示意圖如下)。 0號頁1號頁2號頁3號頁2號頁框4號頁框7號頁框9號頁框2022/7/2253.第53頁，共68頁。(1) 17CAH=0001

39、 0111 1100 1010B，表示頁號的位是左邊6位，即00101B，所以頁號為5。根據FIFO算法，需要替換裝入時間最早的頁，故需要置換裝入時間最早的0號頁，即將5頁裝入7號頁框中，所以物理地址為0001 1111 1100 1010B，換算成十六進制，為1FCAH。根據CLOCK算法，如果當前指針所指頁框的使用位為0，則替換該頁；否則將其使用位清零，并將指針指向下一個頁框，繼續查找。根據題設和示意圖，將從2號頁框開始，前4次查找頁框順序為2479，并將對應頁框的使用位清零。在第5次查找中，指針指向2號頁框，因2號頁框的使用位為0，故淘汰2號頁框對應的2號頁，把5號頁裝入2號頁框中，并將

40、對應的使用位置為1，所以對應的物理地址為0000 1011 1100 1010B，換算成十六進制，為0BCAH。2022/7/2254.第54頁，共68頁。15. 若遞交給磁盤驅動程序的磁盤柱面請求按到達時間順序分別是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、2

41、2、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.57ms2022/7/2255.第55頁，共68頁。16. 設文件索引節點中有7個地址項，其中4個地址項是直接地址索引，2個地址項是一級間接地址索引，1個地址項是二級間接地址索引，每個地址項大小為4字節。若磁盤索引塊和磁盤數據塊大小均為256字節，則可表示的單個文件最大長度是多少？解：每個盤塊存放的索引項=256/4=64（項） 直接地址存儲容量=4256=1KB 一級間址存

42、儲容量=264256=32KB 二級間址存儲容量=16464256=1024KB 最大文件長度=1+32+1024=1057KB2022/7/2256.第56頁，共68頁。17假設計算機系統采用CSCAN(循環掃描)磁盤調度策略，使用2KB的內存空間記錄16384個磁盤塊的空閑狀態。（1）請說明在上述條件下如何進行磁盤塊空閑狀態的管理。（2）設某單面磁盤旋轉速度為每分鐘6000轉，每個磁道有100個扇區，相鄰磁道間的平均移動時間為1ms。若在某時刻，磁頭位于100號磁道處，并沿著磁道號增大的方向移動(如下圖所示)，磁道號請求隊列為50,90,30,120，對請求隊列中的每一個磁道需讀取1個隨機

43、分布的扇區，則讀完這4個扇區總共需要多少時間？給出計算過程。 2022/7/2257.第57頁，共68頁。磁頭當前運動方向0號磁道隨機分布的某扇區100號磁道2022/7/2258.第58頁，共68頁。解：(1) 用位圖表示磁盤的空閑塊狀態。每一位表示一個磁盤塊的空閑狀態，共需16384/32= 512個字=5124個字節=2KB，正好可放在系統提供的內存中。(2) 采用CSCAN調度算法，訪問磁道的順序為120,30,50,90，則移動磁道長度為20+90+20+40= 170，總的移動時間為1701ms=170ms。由于轉速為6000r/m，則平均旋轉延遲時間為60/(60002)1000

44、ms=5ms，總的旋轉時間為5ms4=20ms。由于轉速為6000r/m，則讀取一個磁道上的一個扇區的平均讀取時間為10ms/100=0.1ms，總的讀取扇區的時間=0.1ms4=0.4ms。讀取上述磁道上的所有4個扇區所花費的總時間=170ms+20ms+0.4ms=190.4ms。2022/7/2259.第59頁，共68頁。18. 考慮一個存在于磁盤上的文件系統，其中的文件由大小為512B的邏輯塊組成。假定每一個文件有一個文件目錄項，該目錄項包含該文件的文件名、文件長度以及第一塊（或第一索引塊）和最后一塊的位置，而且該目錄項位于內存。對于索引結構文件，該目錄項指明第一索引塊，該索引塊又一次

45、指向511個文件塊（每個索引值占4B），且有一指向下一索引塊的指針(指針占4B)。針對連續、鏈接、索引結構的每一種，如果當前位于邏輯塊30（即之前最后一次訪問的塊是邏輯塊30）且希望訪問邏輯塊20(假設邏輯塊號從0開始編號)，那么，必須分別從磁盤上讀多少個物理塊？2022/7/2260.第60頁，共68頁。解：(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個磁盤塊即可(因目錄項已在內存)。2022/7/2261.第61頁，共68頁。 (2) 對于磁盤上的鏈接結構文件，當前讀寫了邏輯塊30，要訪問邏輯塊20，需要從文件開頭開始。由前面分析知，磁盤塊大小2048B，故每個盤塊可存放4個邏輯塊。邏輯塊20在文件的第6個物理塊中，因此需依次讀出第1、2、3、4、5等盤塊，從第5個物理塊獲得第6個物理塊的塊號，在讀出第6物理塊，其開頭的512B即是20號