操作系統(tǒng)復(fù)習(xí)2016實用教案

1、注意(zh y)要點 考核形式 試卷，閉卷考試，120分鐘 可以帶計算器，但不得使用手機(jī)中的計算器功能 試卷占總評成績的80% 考察范圍 第一章第九章 部分章節(jié)(zhngji)除外2021-12-151第1頁/共68頁第一頁，共69頁。題型分布(fnb) 單選題15題，共30分 填空題10題，共10分 綜合(zngh)應(yīng)用題6題，共60分2021-12-152第2頁/共68頁第二頁，共69頁。主要(zhyo)知識點 第一章 操作系統(tǒng)的目標(biāo) 操作系統(tǒng)的作用 三種經(jīng)典的操作系統(tǒng)類型 分時系統(tǒng)的特征 實時系統(tǒng)的特征 操作系統(tǒng)的基本特征 用戶(yngh)接口的種類2021-12-153第3頁/共68頁

2、第三頁，共69頁。主要(zhyo)知識點 第二章 順序執(zhí)行程序的主要特征 并發(fā)執(zhí)行程序的主要特征 進(jìn)程的特征 進(jìn)程的各個狀態(tài)，及各狀態(tài)之間的轉(zhuǎn)換條件 導(dǎo)致進(jìn)程創(chuàng)建(chungjin)、終止、阻塞的條件 同步機(jī)制的4條設(shè)計原則 進(jìn)程同步：只需要掌握用信號量解決P-C問題 進(jìn)程通信的方法2021-12-154第4頁/共68頁第四頁，共69頁。主要(zhyo)知識點 第三章 處理機(jī)的調(diào)度層次 調(diào)度算法(sun f)：FIFO，SJF，高相應(yīng)比優(yōu)先，時間片輪轉(zhuǎn) 產(chǎn)生死鎖的4個必要條件 銀行家算法(sun f) 資源分配圖的簡化2021-12-155第5頁/共68頁第五頁，共69頁。主要(zhyo)知識

3、點 第四章 動態(tài)分區(qū)分配中分配和回收內(nèi)存的方法 動態(tài)分區(qū)分配算法(sun f)：FF，NF，BF，WF 邏輯地址到物理地址的轉(zhuǎn)換及訪問時間的計算 多級頁表 段頁式存儲管理的地址轉(zhuǎn)換 （虛地址到實地址的轉(zhuǎn)換）2021-12-156第6頁/共68頁第六頁，共69頁。主要(zhyo)知識點 第五章 虛擬存儲器的特征 頁面置換算法(sun f)及缺頁率的計算 最佳， FIFO， LRU， 時鐘置換 抖動的概念2021-12-157第7頁/共68頁第七頁，共69頁。主要(zhyo)知識點 第六章 I/O系統(tǒng)的基本功能 I/O系統(tǒng)的層次結(jié)構(gòu) I/O設(shè)備的類型 設(shè)備控制器的基本功能 單緩沖和雙緩沖傳輸時間(

4、shjin)的計算 磁盤訪問時間(shjin)的計算 磁盤調(diào)度算法：FCFS，SSTF，SCAN，CSCAN2021-12-158第8頁/共68頁第八頁，共69頁。主要(zhyo)知識點 第七章 文件的組織(zzh)分類及其特征 目錄管理的要求 目錄結(jié)構(gòu)的組織(zzh)形式 目錄檢索的方法 文件共享的方法 （文件）2021-12-159第9頁/共68頁第九頁，共69頁。主要(zhyo)知識點 第八章 連續(xù)組織方式的優(yōu)缺點 隱式連接、顯示鏈接組織方式的優(yōu)缺點 索引組織方式的優(yōu)缺點 混合索引文件最大容量的計算方法 位示圖法(t f)存儲空間管理（位圖計算）2021-12-1510第10頁/共68頁

5、第十頁，共69頁。主要(zhyo)知識點 第九章 用戶(yngh)接口的類型 主要聯(lián)機(jī)命令 Shell命令語言的主要簡單命令 系統(tǒng)調(diào)用的實現(xiàn)方法2021-12-1511第11頁/共68頁第十一頁，共69頁。1. 假設(shè)有一磁盤含有64000塊，塊號記為164000，現(xiàn)用2000個32位(Bit)的字作該盤的位示圖，試問第59999塊對應(yīng)于位示圖中第幾字的第幾位(字、位均從0開始)；而第1599字的第17位對應(yīng)于磁盤的第幾塊?解：由塊號b，求字號(z hao)i和位號j的公式為：i=(b-1) div 32(div表示整數(shù)除法，32是字長)j=(b-1) mod 32(mod表示整數(shù)相除取余數(shù))(

6、59999-1) div 32=1874 (59999-1) mod 32=30故59999塊對應(yīng)于位示圖中第1874字的第30位。由位示圖的字號(z hao)i和位號j，求對應(yīng)的磁盤塊號b的公式為：b=i32+j+1=159932+17+1=51186即第1599字的第17位對應(yīng)于磁盤的第51186塊。2021-12-1512第12頁/共68頁第十二頁，共69頁。2. 頁式存儲管理中，主存空間按頁分配，可用一張“位示圖”構(gòu)成主存分配表。假設(shè)主存容量為2M字節(jié)，頁面長度為512字節(jié)，若用字長為32位的字作主存分配的“位示圖”需要多少個字？如頁號從1開始，字號和字內(nèi)位號（從高位(o wi)到低位

7、）均從1開始，試問：第2999頁對應(yīng)于何字何位；99字19位又對應(yīng)于第幾頁？解：(1) 內(nèi)存總塊數(shù)=2MB/512B=4096位示圖需要字?jǐn)?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頁2021-12-1513第13頁/共68頁第十三頁，共69頁。2021-12-15143某多道程序設(shè)計系統(tǒng)供用戶使用的主存為某多道程序設(shè)計系統(tǒng)供用戶使用的主存為100KB，磁帶，磁帶機(jī)機(jī)2臺，打印機(jī)臺，打印機(jī)1臺。采用可

8、變分區(qū)內(nèi)存管理，采用靜態(tài)臺。采用可變分區(qū)內(nèi)存管理，采用靜態(tài)(jngti)方式分配外圍設(shè)備，忽略用戶作業(yè)的方式分配外圍設(shè)備，忽略用戶作業(yè)的I/O時間?，F(xiàn)有時間。現(xiàn)有如下作業(yè)序列：如下作業(yè)序列： 作業(yè)名作業(yè)名提交時間提交時間需運行時間需運行時間主存需求量主存需求量磁帶機(jī)需求磁帶機(jī)需求打印機(jī)需求打印機(jī)需求J18:0025分鐘分鐘15KB11J28:2010分鐘分鐘30KB01J38:2020分鐘分鐘60KB10J48:3020分鐘分鐘20KB10J58:3515分鐘分鐘10KB11作業(yè)調(diào)度采用作業(yè)調(diào)度采用FCFS策略，優(yōu)先分配策略，優(yōu)先分配(fnpi)主存低地址區(qū)域且不主存低地址區(qū)域且不準(zhǔn)移動已在主

9、存中的作業(yè)，進(jìn)程調(diào)度采用時間片輪轉(zhuǎn)算法準(zhǔn)移動已在主存中的作業(yè)，進(jìn)程調(diào)度采用時間片輪轉(zhuǎn)算法(即在主即在主存中的作業(yè)均分存中的作業(yè)均分CPU時間時間)。現(xiàn)求：?，F(xiàn)求： 第14頁/共68頁第十四頁，共69頁。2021-12-1515(1) 作業(yè)被調(diào)度作業(yè)被調(diào)度(diod)的先后次序；的先后次序；(2) 全部作業(yè)運行結(jié)束的時間；全部作業(yè)運行結(jié)束的時間；(3) 作業(yè)的平均周轉(zhuǎn)時間；作業(yè)的平均周轉(zhuǎn)時間；(4) 最大作業(yè)周轉(zhuǎn)時間。最大作業(yè)周轉(zhuǎn)時間。作業(yè)達(dá)到及結(jié)束順序分析作業(yè)達(dá)到及結(jié)束順序分析(fnx)：8:00J1到達(dá)，分配它所需資源到達(dá)，分配它所需資源(15KB內(nèi)存、內(nèi)存、 1臺磁帶機(jī)、臺磁帶機(jī)、1臺打印

10、機(jī)后，調(diào)入內(nèi)存運行。余內(nèi)存臺打印機(jī)后，調(diào)入內(nèi)存運行。余內(nèi)存85KB、磁帶機(jī)、磁帶機(jī)1臺。臺。8:20J2到達(dá)，因無打印機(jī)，不調(diào)入。同時到達(dá)，因無打印機(jī)，不調(diào)入。同時J3到達(dá)，分配它到達(dá)，分配它內(nèi)存內(nèi)存60KB，磁帶機(jī)，磁帶機(jī)1臺，調(diào)入內(nèi)存，與臺，調(diào)入內(nèi)存，與J1均分均分CPU時間運行。時間運行。余內(nèi)存余內(nèi)存25KB、磁帶機(jī)和打印機(jī)都已分完、磁帶機(jī)和打印機(jī)都已分完(余余0臺臺)。8:30J1結(jié)束，釋放內(nèi)存結(jié)束，釋放內(nèi)存15KB、磁帶機(jī)、磁帶機(jī)1臺、打印機(jī)臺、打印機(jī)1臺。臺。雖有打印機(jī)但內(nèi)存不夠，雖有打印機(jī)但內(nèi)存不夠，J2仍不能調(diào)入；仍不能調(diào)入；J4到達(dá)，因低端內(nèi)到達(dá)，因低端內(nèi)存存15KB不夠，分

11、配高端內(nèi)存不夠，分配高端內(nèi)存20KB和磁帶機(jī)和磁帶機(jī)1臺，調(diào)入內(nèi)存臺，調(diào)入內(nèi)存與與J3一起運行。剩下內(nèi)存空閑塊是一起運行。剩下內(nèi)存空閑塊是15KB、5KB，打印機(jī)，打印機(jī)1臺臺8:35J5到達(dá)，因無磁帶機(jī)，不能調(diào)入。到達(dá)，因無磁帶機(jī)，不能調(diào)入。第15頁/共68頁第十五頁，共69頁。2021-12-15169:00J3結(jié)束。釋放資源后，系統(tǒng)有內(nèi)存結(jié)束。釋放資源后，系統(tǒng)有內(nèi)存(ni cn)75KB，5KB、打印機(jī)和磁帶機(jī)個打印機(jī)和磁帶機(jī)個1臺。臺。J2調(diào)入，內(nèi)存調(diào)入，內(nèi)存(ni cn)余余45KB，5KB、磁帶機(jī)剩磁帶機(jī)剩1臺、打印機(jī)臺、打印機(jī)0臺。臺。J5仍不能進(jìn)入仍不能進(jìn)入(無打印機(jī)無打印機(jī))

12、。將。將J2、J4運行。運行。J4還需運行還需運行5分鐘。分鐘。9:10J4結(jié)束，釋放資源后，內(nèi)存結(jié)束，釋放資源后，內(nèi)存(ni cn)空余空余70KB、磁帶機(jī)、磁帶機(jī)空空2臺、打印機(jī)臺、打印機(jī)0臺。臺。J5仍不能進(jìn)入。仍不能進(jìn)入。J2單獨運行單獨運行(還需還需5分鐘分鐘)。9:15J2結(jié)束，釋放資源后，內(nèi)存結(jié)束，釋放資源后，內(nèi)存(ni cn)有有100KB、磁帶機(jī)有、磁帶機(jī)有2臺、打印機(jī)有臺、打印機(jī)有1臺。臺。J5調(diào)入運行。調(diào)入運行。9:30J5結(jié)束。結(jié)束。解：解：(1) 作業(yè)被調(diào)度的先后次序作業(yè)被調(diào)度的先后次序(cx)為為J1, J3, J4, J2, J5(2) 全部作業(yè)運行結(jié)束的時間為全

13、部作業(yè)運行結(jié)束的時間為9:30(3) 作業(yè)的平均周轉(zhuǎn)時間為作業(yè)的平均周轉(zhuǎn)時間為(30+55+40+40+55)5=44 (分鐘分鐘)(4) 最大作業(yè)周轉(zhuǎn)時間為最大作業(yè)周轉(zhuǎn)時間為55分鐘。分鐘。第16頁/共68頁第十六頁，共69頁。2021-12-1517CPU磁帶磁帶(cdi)1磁帶磁帶(cdi)2打印機(jī)打印機(jī)8:008:20J1J1J1J1, J3J38:30J1J1J1結(jié)束結(jié)束(jish)J4J3J2,J3到到J2不入不入J3進(jìn)入進(jìn)入J3, J48:35J3, J4J5到達(dá)到達(dá)J5不入不入9:00J4J3J3結(jié)束結(jié)束9:10J4結(jié)束結(jié)束內(nèi)存余內(nèi)存余85K25K15, 515, 5J2, J

14、445, 5J4J29:15J2J270KJ2結(jié)束結(jié)束9:3090KJ5J5J5J5結(jié)束結(jié)束J1到達(dá)到達(dá)J1進(jìn)入進(jìn)入J4到達(dá)到達(dá)J2不入不入J4進(jìn)入進(jìn)入J2進(jìn)入進(jìn)入J5仍不仍不能進(jìn)入能進(jìn)入J5進(jìn)入進(jìn)入以下是畫圖分析法：以下是畫圖分析法：第17頁/共68頁第十七頁，共69頁。2021-12-15184多道批處理系統(tǒng)中配有一個處理器和多道批處理系統(tǒng)中配有一個處理器和2臺外設(shè)臺外設(shè)(D1和和D2)，用戶存，用戶存儲空間為儲空間為100MB。已知系統(tǒng)采用可搶占式的高優(yōu)先數(shù)調(diào)度算法和不。已知系統(tǒng)采用可搶占式的高優(yōu)先數(shù)調(diào)度算法和不允許移動的可變分區(qū)允許移動的可變分區(qū)(fn q)分配策略，設(shè)備分配按照動態(tài)分

15、配原則。分配策略，設(shè)備分配按照動態(tài)分配原則。今有今有4個作業(yè)同時提交給系統(tǒng)，如下表所示。個作業(yè)同時提交給系統(tǒng)，如下表所示。作業(yè)名作業(yè)名優(yōu)先數(shù)優(yōu)先數(shù)運行時間運行時間內(nèi)存需求內(nèi)存需求A65分鐘分鐘50MB34分鐘分鐘10MC87分鐘分鐘60MD46分鐘分鐘20M作業(yè)運行時間和作業(yè)運行時間和I/O時間按下述順序進(jìn)行：時間按下述順序進(jìn)行：A. CPU (1分鐘分鐘)，D1(2分鐘分鐘)，D2(2分鐘分鐘)B. CPU (3分鐘分鐘)，D1(1分鐘分鐘)C. CPU (2分鐘分鐘)，D1(3分鐘分鐘)，CPU(2分鐘分鐘)D. CPU (4分鐘分鐘)，D1(2分鐘分鐘)忽略其他輔助操作忽略其他輔助操作(

16、cozu)，求，求4個作業(yè)的平均周轉(zhuǎn)時間是多個作業(yè)的平均周轉(zhuǎn)時間是多少分鐘。少分鐘。11分鐘分鐘分析分析(fnx)見后頁見后頁第18頁/共68頁第十八頁，共69頁。2021-12-1519C C D D D C C A D BBBC C CA A D D BA A12345678910 11 12 13CPUD1D2時間時間(shjin)A的周轉(zhuǎn)時間為的周轉(zhuǎn)時間為12分鐘分鐘B的周轉(zhuǎn)時間為的周轉(zhuǎn)時間為13分鐘分鐘C的周轉(zhuǎn)時間為的周轉(zhuǎn)時間為7分鐘分鐘D的周轉(zhuǎn)時間為的周轉(zhuǎn)時間為12分鐘分鐘所以所以(suy)平均周轉(zhuǎn)時間為平均周轉(zhuǎn)時間為(12+13+7+12)/4=11(分分鐘鐘)第19頁/共68頁

17、第十九頁，共69頁。5. 有一個具有兩道作業(yè)的批處理系統(tǒng)（最多可有兩道作業(yè)同時裝入內(nèi)存執(zhí)行），作業(yè)調(diào)度采用計算時間短的作業(yè)優(yōu)先調(diào)度算法，進(jìn)程調(diào)度采用以優(yōu)先數(shù)為基礎(chǔ)的搶占式調(diào)度算法，今有如下(rxi)作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進(jìn)程優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高：(1) 列出所有作業(yè)進(jìn)入內(nèi)存時間及結(jié)束時間。(2) 計算平均周轉(zhuǎn)時間。2021-12-1520作業(yè)名到達(dá)時間估計運行時間優(yōu)先數(shù)J110 : 1020分鐘5J210 : 2030分鐘3J310 : 3025分鐘4J410 : 5020分鐘6第20頁/共68頁第二十頁，共69頁。分析：10：10 J1到達(dá)，進(jìn)入系統(tǒng)，運行10分鐘10：20 J2到

18、達(dá)，進(jìn)入系統(tǒng)，因優(yōu)先級高于J1搶奪CPU開始運行10：30 J3到達(dá)后備隊列，因為系統(tǒng)已經(jīng)載入2個作業(yè)，無法進(jìn)入系統(tǒng)10：50 J2運行結(jié)束(jish)退出，J4到達(dá)，根據(jù)短作業(yè)優(yōu)先，調(diào)入J4，由于 J1的優(yōu)先級高于J4，J1開始運行11：00 J1運行結(jié)束(jish)退出，J3進(jìn)入系統(tǒng)，由于J3優(yōu)先級較高，開始運行11：25 J3運行結(jié)束(jish)退出，J4開始運行11：45 J4運行結(jié)束(jish)2021-12-1521第21頁/共68頁第二十一頁，共69頁。答：（1）各個作業(yè)進(jìn)入主存時間、結(jié)束時間和周轉(zhuǎn)(zhuzhun)時間如下表所示：（2）平均周轉(zhuǎn)(zhuzhun)時間：（50+3

19、0+55+55）/4=47.5（min）2021-12-1522作業(yè)名提交時間進(jìn)入時間結(jié)束時間周轉(zhuǎn)時間J110：1010：1011：0050J210：2010：2010：5030J310：3011：0011：2555J410：5010：5011：4555第22頁/共68頁第二十二頁，共69頁。6有一個多道程序設(shè)計系統(tǒng)，采用不可移動的可變分區(qū)方式有一個多道程序設(shè)計系統(tǒng)，采用不可移動的可變分區(qū)方式管理主存空間，設(shè)主存空間為管理主存空間，設(shè)主存空間為100K，采用最先適應(yīng)分配算法分，采用最先適應(yīng)分配算法分配主存，作業(yè)調(diào)度采用響應(yīng)比高者優(yōu)先算法，進(jìn)程調(diào)度采用時配主存，作業(yè)調(diào)度采用響應(yīng)比高者優(yōu)先算法，進(jìn)

20、程調(diào)度采用時間片輪轉(zhuǎn)算法（即內(nèi)存中的作業(yè)均分間片輪轉(zhuǎn)算法（即內(nèi)存中的作業(yè)均分CPU時間），今有如下作時間），今有如下作業(yè)序列：業(yè)序列：假定所有作業(yè)都是計算型作業(yè)且忽略系統(tǒng)調(diào)度時間。回答假定所有作業(yè)都是計算型作業(yè)且忽略系統(tǒng)調(diào)度時間?；卮?hud)下列問題：下列問題：(1)列表說明各個作業(yè)被裝入主存的時間、完成時間和周轉(zhuǎn)時間；列表說明各個作業(yè)被裝入主存的時間、完成時間和周轉(zhuǎn)時間；(2)寫出各作業(yè)被調(diào)入主存的順序；寫出各作業(yè)被調(diào)入主存的順序；(3)計算計算5個作業(yè)的平均周轉(zhuǎn)時間。個作業(yè)的平均周轉(zhuǎn)時間。2021-12-1523作業(yè)名提交時間需要執(zhí)行時間要求主存量J110 : 0040分鐘25KJ210

21、 : 1530分鐘60KJ310 : 3020分鐘50KJ410 : 3525分鐘18KJ510 : 4015分鐘20K第23頁/共68頁第二十三頁，共69頁。答：（答：（1）各個作業(yè)）各個作業(yè)(zuy)被裝入主存的時間、完成時間和周轉(zhuǎn)時間如被裝入主存的時間、完成時間和周轉(zhuǎn)時間如下表所示：下表所示：（2）作業(yè)）作業(yè)(zuy)被調(diào)入主存的順序為被調(diào)入主存的順序為J1，J2，J5，J3，J4。（3）平均周轉(zhuǎn)時間）平均周轉(zhuǎn)時間=（65+60+85+95+55）/5=72（分鐘）。（分鐘）。2021-12-1524作業(yè)名裝入主存時間 作業(yè)完成時間 周轉(zhuǎn)時間J110：0011：0565J210：1511

22、：1560J311：1511：5585J411：3512：1095J511：0511：3555第24頁/共68頁第二十四頁，共69頁。25信號量機(jī)制解決進(jìn)程同步問題的一般(ybn)方法：1. 為同步雙方設(shè)置各自的信號量，初值為其初始狀態(tài)可為同步雙方設(shè)置各自的信號量，初值為其初始狀態(tài)可用的資源數(shù)用的資源數(shù)(故該信號量稱為資源信號量或私有信號故該信號量稱為資源信號量或私有信號量量)；2. 同步雙方任一進(jìn)程在進(jìn)入臨界區(qū)之前，應(yīng)先對自己的同步雙方任一進(jìn)程在進(jìn)入臨界區(qū)之前，應(yīng)先對自己的信號量執(zhí)行信號量執(zhí)行wait()操作，以測試操作，以測試(csh)是是否有自己可用的資源。若有資源可用，則進(jìn)入臨界區(qū)，否

23、有自己可用的資源。若有資源可用，則進(jìn)入臨界區(qū)，否則阻塞；否則阻塞；3. 同步雙方任一進(jìn)程離開臨界區(qū)后，應(yīng)對合作方同步雙方任一進(jìn)程離開臨界區(qū)后，應(yīng)對合作方 (對方對方)的信號量執(zhí)行的信號量執(zhí)行signal()操作，以通知操作，以通知(若若對方處于阻塞狀態(tài)，則喚醒它對方處于阻塞狀態(tài)，則喚醒它)對方已有資源可用對方已有資源可用(對對方已可進(jìn)入臨界區(qū)方已可進(jìn)入臨界區(qū))。第25頁/共68頁第二十五頁，共69頁。26用信號量機(jī)制用信號量機(jī)制(jzh)解決解決P-C問題的基本方法：問題的基本方法：1. 為生產(chǎn)者設(shè)置為生產(chǎn)者設(shè)置1個私有信號量個私有信號量empty，其初值為，其初值為1，表示有表示有1個空緩沖

24、區(qū)；為消費者設(shè)置個空緩沖區(qū)；為消費者設(shè)置1個私有信號量個私有信號量full，其初值為，其初值為0，表示開始時沒有滿緩沖區(qū)；（信，表示開始時沒有滿緩沖區(qū)；（信號量初值由物理意義確定）號量初值由物理意義確定）2. 生產(chǎn)者將產(chǎn)品存入緩沖區(qū)之前，應(yīng)先測試緩沖區(qū)是生產(chǎn)者將產(chǎn)品存入緩沖區(qū)之前，應(yīng)先測試緩沖區(qū)是否空：執(zhí)行否空：執(zhí)行wait(empty)操作；離開臨界操作；離開臨界(ln ji)區(qū)區(qū)(存入產(chǎn)品存入產(chǎn)品)后，應(yīng)通知后，應(yīng)通知(可能會喚醒可能會喚醒)消費者：執(zhí)行消費者：執(zhí)行signal(full)操作；操作；3. 消費者從緩沖區(qū)取產(chǎn)品之前，應(yīng)先測試緩沖區(qū)是否消費者從緩沖區(qū)取產(chǎn)品之前，應(yīng)先測試緩沖區(qū)

25、是否滿：執(zhí)行滿：執(zhí)行wait(full)操作；離開臨界操作；離開臨界(ln ji)區(qū)區(qū)(取走產(chǎn)取走產(chǎn)品品 ) 后 ， 應(yīng) 通 知后 ， 應(yīng) 通 知 ( 可 能 會 喚 醒可 能 會 喚 醒 ) 生 產(chǎn) 者 ： 執(zhí) 行生 產(chǎn) 者 ： 執(zhí) 行signal(empty)操作操作第26頁/共68頁第二十六頁，共69頁。2021-12-15277. 進(jìn)程進(jìn)程P1使用緩沖區(qū)使用緩沖區(qū)buffer向進(jìn)程向進(jìn)程P2，P3，P4發(fā)送消息，要求發(fā)送消息，要求(yoqi)每當(dāng)每當(dāng)P1向向buffer中發(fā)消息時，只有當(dāng)中發(fā)消息時，只有當(dāng)P2，P3，P4進(jìn)程都讀取進(jìn)程都讀取這條消息后才可向這條消息后才可向buffer中

26、發(fā)送新的消息。利中發(fā)送新的消息。利用用P、V原語描述如下圖所示進(jìn)程的動作序列。原語描述如下圖所示進(jìn)程的動作序列。 P1bufferP2P3P4第27頁/共68頁第二十七頁，共69頁。2021-12-1528設(shè)設(shè)P1、P2、P3、P4的資源信號量分別為的資源信號量分別為S1、S2、S3、S4semaphore S1,S2,S3,S4;S1.value=3;S2.vale=S3.vale=S4.value=0; parbeginprocess P1 while (condition) P1生成一個生成一個(y )消息；消息；P（S1）；）；P（S1）；）；P（S1）；）；P1將消息存入緩沖區(qū)將消息

27、存入緩沖區(qū)buffer；V（S2）；）；V（S3）；）；V（S4）；）； 解解:第28頁/共68頁第二十八頁，共69頁。2021-12-1529process Pi(i=2,3,4) while （condition） P（Si）；）；Pi從從buffer中取出消息中取出消息(xio xi)；V（S1）；）；Pi消費（使用）該消息消費（使用）該消息(xio xi)； parend第29頁/共68頁第二十九頁，共69頁。2021-12-15308. 有如下圖所示的工作模型有如下圖所示的工作模型(mxng)：三個進(jìn)程三個進(jìn)程P0、P1、P2和三個緩沖區(qū)和三個緩沖區(qū)B0、B1、B2，進(jìn)程間借助相鄰緩

28、沖區(qū)傳遞消息：進(jìn)程間借助相鄰緩沖區(qū)傳遞消息：P0每次從每次從B0中中取出一條消息經(jīng)加工后送入取出一條消息經(jīng)加工后送入B1中，中，P1每次從每次從B1中取出一條消息經(jīng)加工后送入中取出一條消息經(jīng)加工后送入B2中，中，P2每次從每次從B2中取出一條消息經(jīng)加工后送入中取出一條消息經(jīng)加工后送入B0中。中。B0，B1，B2分別可存放分別可存放3，2，2個消息。初始時個消息。初始時B0中有中有2個消息，個消息，B1 ，B2中各有中各有1個消息。用個消息。用P、V操作操作寫出寫出P0，P1，P2的同步及互斥流程。的同步及互斥流程。 第30頁/共68頁第三十頁，共69頁。2021-12-1531分析：三個進(jìn)程形

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

30、消息empty1=1; full1=1; /沖區(qū)沖區(qū)B1有有1個消息，還可放個消息，還可放1個消息個消息empty2=1; full2=1; /沖區(qū)沖區(qū)B2有有1個消息，還可放個消息，還可放1個消息個消息mutex=1;/互斥信號量互斥信號量第31頁/共68頁第三十一頁，共69頁。2021-12-1532parbeginProcess P0 while (1) P(full0);/看看看看B0中是否有消息中是否有消息 P(mutex);/互斥訪問互斥訪問B0 從緩沖區(qū)從緩沖區(qū)B0中取一個消息中取一個消息x; V(mutex); V(empty0);/B0中空出一個存放消息的位置中空出一個存放消

31、息的位置 加工加工(ji gng)消息消息x; P(empty1);/看看看看B1中是否可放一個消息中是否可放一個消息 P(mutex); /互斥訪問互斥訪問B1 將加工將加工(ji gng)后的后的x存入緩沖區(qū)存入緩沖區(qū)B1; V(mutex); V(full1); /B1中增加一個消息中增加一個消息 第32頁/共68頁第三十二頁，共69頁。2021-12-1533Process P1 while (1) P(full1); /看看看看(kn kn)B1中是否有消息中是否有消息 P(mutex); /互斥訪問互斥訪問B1 從緩沖區(qū)從緩沖區(qū)B1中取一個消息中取一個消息y; V(mutex);

32、V(empty1); /B1中空出一個存放消息的位置中空出一個存放消息的位置 加工消息加工消息y; P(empty2); /看看看看(kn kn)B2中是否可放一個消息中是否可放一個消息 P(mutex); /互斥訪問互斥訪問B2 將加工后的將加工后的x存入緩沖區(qū)存入緩沖區(qū)B2; V(mutex); V(full2); /B2中增加一個消息中增加一個消息 第33頁/共68頁第三十三頁，共69頁。2021-12-1534Process P2 while (1) P(full2);/看看看看B2中是否有消息中是否有消息 P(mutex);/互斥訪問互斥訪問(fngwn)B2 從緩沖區(qū)從緩沖區(qū)B2中

33、取一個消息中取一個消息z; V(mutex); V(empty2);/B2中空出一個存放消息的中空出一個存放消息的位置位置 加工消息加工消息z; P(empty0);/看看看看B0中是否可放一個消息中是否可放一個消息 P(mutex); /互斥訪問互斥訪問(fngwn)B0 將加工后的將加工后的z存入緩沖區(qū)存入緩沖區(qū)B0; V(mutex); V(full0);/B0中增加一個消息中增加一個消息 parend第34頁/共68頁第三十四頁，共69頁。2021-12-15359. 在一個生產(chǎn)車間中，有在一個生產(chǎn)車間中，有3個工人共同協(xié)作生個工人共同協(xié)作生產(chǎn)某種產(chǎn)品，工人產(chǎn)某種產(chǎn)品，工人1負(fù)責(zé)生產(chǎn)零

34、件負(fù)責(zé)生產(chǎn)零件A并放入車并放入車間的貨架，工人間的貨架，工人2負(fù)責(zé)生產(chǎn)零件負(fù)責(zé)生產(chǎn)零件B并放入車間并放入車間的貨架，工人的貨架，工人3從貨架上獲取零件，并將從貨架上獲取零件，并將1個個零件零件A和一個零件和一個零件B組裝成成品運出車間，車組裝成成品運出車間，車間的貨架上最多共可以存放間的貨架上最多共可以存放1000個零件，為個零件，為了保證合理的庫存了保證合理的庫存(kcn)和零件配比，當(dāng)某和零件配比，當(dāng)某種零件數(shù)量比另一種零件數(shù)量多出種零件數(shù)量比另一種零件數(shù)量多出100個時，個時，相應(yīng)的工人暫時停止該種零件的生產(chǎn)。試用相應(yīng)的工人暫時停止該種零件的生產(chǎn)。試用PV操作描述上述生產(chǎn)過程。操作描述上

35、述生產(chǎn)過程。第35頁/共68頁第三十五頁，共69頁。2021-12-1536分析：分析：這是這是2個生產(chǎn)者、個生產(chǎn)者、1個消費者的問題；個消費者的問題；2個生產(chǎn)者公用一個緩沖區(qū)，因此個生產(chǎn)者公用一個緩沖區(qū)，因此Worker1和和Worker2的資源信的資源信號量為空閑緩沖區(qū)號量為空閑緩沖區(qū)empty；Worker3需要需要(xyo)2種資源，因此設(shè)置資源信號量種資源，因此設(shè)置資源信號量full1和和full2；兩種零件存在配比問題，可以使用兩種零件存在配比問題，可以使用2個資源信號量來控制，設(shè)個資源信號量來控制，設(shè)為為sa和和sb；最后，需設(shè)置用于互斥訪問的互斥信號量最后，需設(shè)置用于互斥訪問的

36、互斥信號量mutex解：解：semaphore mutex，empty，full1，full2，sa，sb；mutex.vale = 1 ；/互斥信號量互斥信號量empty.value = 1000；/ 空閑貨架位數(shù)，假設(shè)初始時貨架全空空閑貨架位數(shù)，假設(shè)初始時貨架全空fulla.value = fullb.value = 0；/ 零件零件A和零件和零件B的數(shù)量，的數(shù)量，sa.value = 100；/ sb.value = 100；第36頁/共68頁第三十六頁，共69頁。2021-12-1537Process Worker2 while(1) 生產(chǎn)一個零件生產(chǎn)一個零件(ln jin)B； P（

37、empty）；）； P（sb）；）； P（mutex）；）； 將零件將零件(ln jin)B放入貨架；放入貨架； V（fullb）；）； V（sa）；）； V（mutex）；）； Process Worker3 while(1) P（fulla）；）； P（fullb）；）； P（mutex）；）； 拿去零件拿去零件A和和B； V（empty）；）； V（empty）；）； V（mutex）；）； 組裝組裝(z zhun)產(chǎn)產(chǎn)品；品； PARENDProcess Worker1 while(1) 生產(chǎn)一個零件生產(chǎn)一個零件(ln jin)B； P（empty）；）； P（sa）；）； P（mut

38、ex）：）： 將零件將零件(ln jin)A放入放入貨架；貨架； V（fulla）；）； V（sb）；）； V（mutex）；）； 第37頁/共68頁第三十七頁，共69頁。2021-12-153810. 某銀行提供某銀行提供1個服務(wù)窗口和個服務(wù)窗口和10個顧客等待座位。顧個顧客等待座位。顧客到達(dá)銀行時，若有空座位，則到取號機(jī)領(lǐng)取一個號，客到達(dá)銀行時，若有空座位，則到取號機(jī)領(lǐng)取一個號，等待叫號。取號機(jī)每次僅允許一位顧客使用。當(dāng)營業(yè)等待叫號。取號機(jī)每次僅允許一位顧客使用。當(dāng)營業(yè)員空閑員空閑(kngxin)時，通過叫號選取一位顧客，并為時，通過叫號選取一位顧客，并為其服務(wù)。顧客和營業(yè)員的活動過程描述

39、如下：其服務(wù)。顧客和營業(yè)員的活動過程描述如下：cobegin process 顧客顧客(gk)i 從取號機(jī)獲得從取號機(jī)獲得 一個號碼一個號碼; 等待叫號等待叫號; 獲得服務(wù)獲得服務(wù); process 營業(yè)員營業(yè)員 while (TRUE) 叫號叫號; 為顧客為顧客(gk)服務(wù)服務(wù); 第38頁/共68頁第三十八頁，共69頁。2021-12-1539請?zhí)砑颖匾男盘柫亢驼執(zhí)砑颖匾男盘柫亢蚉、V（或（或wait( )、signal( )）操作）操作(cozu)實現(xiàn)上述過程的互斥和同實現(xiàn)上述過程的互斥和同步。要求寫出完整的過程，說明信號量的含義并賦步。要求寫出完整的過程，說明信號量的含義并賦初值。初

40、值。分析：分析：semaphore mutex=1;/用于顧客取號的互斥用于顧客取號的互斥信號量信號量semaphore seat=10;/顧客等待顧客等待(dngdi)座位的資源信號量，當(dāng)沒有空座位時顧客在其上阻座位的資源信號量，當(dāng)沒有空座位時顧客在其上阻塞塞semaphore S1=0;/營業(yè)員與顧客的同步營業(yè)員與顧客的同步信號量，當(dāng)沒有顧客時營業(yè)員在其上阻塞信號量，當(dāng)沒有顧客時營業(yè)員在其上阻塞semaphore S2=0;/顧客與營業(yè)員的同步顧客與營業(yè)員的同步信號量，等待信號量，等待(dngdi)叫號時顧客在其上阻塞叫號時顧客在其上阻塞第39頁/共68頁第三十九頁，共69頁。2021-1

41、2-1540cobegin process 顧客顧客i P(seat);/若沒有空座位若沒有空座位(zu wi)，顧客等待，顧客等待P(mutex);/取號互斥取號互斥從取號機(jī)獲得一個號碼從取號機(jī)獲得一個號碼;V(mutex);V(S1); /通知營業(yè)員，已有顧客通知營業(yè)員，已有顧客P(S2);等待叫號等待叫號;V(seat); / 空出一個座位空出一個座位(zu wi)獲得服務(wù)獲得服務(wù); 第40頁/共68頁第四十頁，共69頁。2021-12-1541 process 營業(yè)員營業(yè)員while (TRUE)P(S1);/若無顧客則等待若無顧客則等待V(S2);/喚醒喚醒(hunxng)等待叫號的

42、顧客等待叫號的顧客叫號叫號;為顧客服務(wù)為顧客服務(wù); 第41頁/共68頁第四十一頁，共69頁。2021-12-154211. 在一個采用頁式虛擬存儲管理的系統(tǒng)中，有一用戶在一個采用頁式虛擬存儲管理的系統(tǒng)中，有一用戶作業(yè)，它依次要訪問的字地址序列是：作業(yè)，它依次要訪問的字地址序列是：115，228，120，88，446，102，321，432，260，167，若該作業(yè)的第，若該作業(yè)的第0頁已經(jīng)裝入主存，現(xiàn)分配給該作業(yè)的主存共頁已經(jīng)裝入主存，現(xiàn)分配給該作業(yè)的主存共300字，頁字，頁的大小為的大小為100字，請回答下列問題：字，請回答下列問題：(1)按按FIFO調(diào)度算法，將產(chǎn)生多少次缺頁中斷？依次淘調(diào)

43、度算法，將產(chǎn)生多少次缺頁中斷？依次淘汰汰(toti)的頁號是什么？缺頁中斷率為多少？的頁號是什么？缺頁中斷率為多少？(2)按按LRU調(diào)度算法，將產(chǎn)生多少次缺頁中斷？依次淘汰調(diào)度算法，將產(chǎn)生多少次缺頁中斷？依次淘汰(toti)的頁號是什么？缺頁中斷率為多少？的頁號是什么？缺頁中斷率為多少？第42頁/共68頁第四十二頁，共69頁。答：由題目的已知條件，可得頁面走向為：答：由題目的已知條件，可得頁面走向為：1, 2, 1, 0, 4, 1, 3, 4, 2, 1 (1) FIFO的頁面置換圖如下：的頁面置換圖如下：按按FIFO調(diào)度算法調(diào)度算法(sun f)將產(chǎn)生將產(chǎn)生5次缺頁中斷，依次淘汰次缺頁中斷

44、，依次淘汰的頁號為的頁號為0,1,2，缺頁中斷率為，缺頁中斷率為5/10=50%。2021-12-1543頁面走向1210413421頁幀00004444441111113333 222222221是否缺頁 被淘汰頁號 0 1 2第43頁/共68頁第四十三頁，共69頁。(2) LRU算法(sun f)的頁面置換圖如下：按LRU調(diào)度算法(sun f)將產(chǎn)生6次缺頁中斷，依次淘汰的頁號為2,0,1,3，缺頁中斷率為6/10=60%。2021-12-1544頁面走向1210413421頁幀12104134210121041342 002104134是否缺頁 被淘汰頁號 2 0 13第44頁/共68頁

45、第四十四頁，共69頁。2021-12-154512請求分頁管理系統(tǒng)中，假設(shè)某進(jìn)程請求分頁管理系統(tǒng)中，假設(shè)某進(jìn)程(jnchng)的頁表內(nèi)容如下的頁表內(nèi)容如下表所示。表所示。頁表內(nèi)容頁表內(nèi)容 頁號頁號頁框頁框(Page frame)號號有效位（存在位）有效位（存在位）0101H1102254H1頁面大小為頁面大小為4KB，一次內(nèi)存的訪問時間是，一次內(nèi)存的訪問時間是100ns，一次快表，一次快表(TLB)的訪問時間是的訪問時間是10ns，處理一次缺頁的平均時間為，處理一次缺頁的平均時間為108ns(已含更新已含更新TLB和頁表的時間和頁表的時間)，進(jìn)程的駐留集大小固定為，進(jìn)程的駐留集大小固定為2，采

46、用最近最少，采用最近最少使用置換算法使用置換算法(sun f)(LRU)和局部淘汰策略。假設(shè)和局部淘汰策略。假設(shè)TLB初始初始為空；地址轉(zhuǎn)換時先訪問為空；地址轉(zhuǎn)換時先訪問TLB，若，若TLB未命中，在訪問頁表未命中，在訪問頁表(忽略訪問頁表之后的忽略訪問頁表之后的TLB更新時間更新時間)；有效位為；有效位為0表示頁面不表示頁面不再內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷后，返回到產(chǎn)生缺頁中斷的指再內(nèi)存，產(chǎn)生缺頁中斷，缺頁中斷后，返回到產(chǎn)生缺頁中斷的指令處重新執(zhí)行。設(shè)有虛地址訪問序列令處重新執(zhí)行。設(shè)有虛地址訪問序列2362H、1565H、25A5H，請問：請問：第45頁/共68頁第四十五頁，共69頁。202

47、1-12-1546(1) 依次訪問上述三個虛地址，各需多少依次訪問上述三個虛地址，各需多少(dusho)時間？給出計時間？給出計算過程。算過程。(2) 基于上述訪問序列，虛地址基于上述訪問序列，虛地址1565H的物理地址是多少的物理地址是多少(dusho)？請說明理由。？請說明理由。分析：考察點地址轉(zhuǎn)換分析：考察點地址轉(zhuǎn)換(zhunhun)的過程的過程 快表命中：快表命中：快表訪問時間快表訪問時間 + 一次內(nèi)存訪問時間一次內(nèi)存訪問時間 快表未命中但未缺頁：快表未命中但未缺頁：快表訪問時間快表訪問時間+二次內(nèi)存訪問時間二次內(nèi)存訪問時間（一次頁表訪問，一次實際地址訪問）（一次頁表訪問，一次實際地址

48、訪問） 快表未命中且存在缺頁：快表未命中且存在缺頁：快表訪問時間快表訪問時間+二次內(nèi)存訪問時間二次內(nèi)存訪問時間+缺頁處理時間缺頁處理時間第46頁/共68頁第四十六頁，共69頁。2021-12-1547(1) 因頁的大小為因頁的大小為4KB，即，即212，故十六進(jìn)制，故十六進(jìn)制(sh li jn zh)地地址的低址的低3位是頁內(nèi)偏移，高位是頁號。位是頁內(nèi)偏移，高位是頁號。2362H：頁號：頁號P=2，訪問快表，訪問快表10ns，因初始為空，訪問頁表，因初始為空，訪問頁表100ns得到頁框號，與頁內(nèi)偏移合成物理地址后訪問內(nèi)存得到頁框號，與頁內(nèi)偏移合成物理地址后訪問內(nèi)存100ns，共花時間，共花時間

49、10+100+100=210ns。1565H：P=1，訪問快表，訪問快表10ns，落空，訪問頁表，落空，訪問頁表100ns缺頁，缺頁，進(jìn)行缺頁中斷處理進(jìn)行缺頁中斷處理108ns，合成物理地址后訪問內(nèi)存，合成物理地址后訪問內(nèi)存100ns，共計共計10+100+108+100=318ns。25A5H：P=2，訪問快表，訪問快表10ns命中，合成物理地址后訪問內(nèi)命中，合成物理地址后訪問內(nèi)存存100ns，共計，共計110ns。(2)故訪問故訪問1565H時，因在此之前剛剛訪問時，因在此之前剛剛訪問2362H所在的所在的2號頁，號頁，按按LRU算法，應(yīng)淘汰算法，應(yīng)淘汰0號頁，空出號頁，空出101H號頁框

50、存放邏輯地址號頁框存放邏輯地址1565H所在的所在的1號頁。由頁框號號頁。由頁框號101H和頁內(nèi)偏移和頁內(nèi)偏移565H合成得合成得到虛地址到虛地址1565H對應(yīng)的物理地址為對應(yīng)的物理地址為101565H。第47頁/共68頁第四十七頁，共69頁。13. 某計算機(jī)主存按字節(jié)編址，邏輯地址和物理地址都是 32 位，頁表項大小為 4 字節(jié)。請回答下列問題。1）若使用一級頁表的分頁存儲管理方式，邏輯地址結(jié)構(gòu)為： 則頁的大小是多少字節(jié)？頁表最大占用多少字節(jié)？2）若使用二級頁表的分頁存儲管理方式，邏輯地址結(jié)構(gòu)為： 設(shè)邏輯地址為 LA，請分別給出其對應(yīng)的頁目錄(ml)號和頁表索引的表達(dá)式。2021-12-15

51、48頁號（20 位）頁內(nèi)偏移量（12 位）頁目錄號（10 位）頁表索引（10 位）頁內(nèi)偏移量（12 位）第48頁/共68頁第四十八頁，共69頁。3）采用（1）中的分頁存儲管理方式，一個代碼段起始邏輯地址為 0000 8000H，其長度為 8 KB，被裝載到從物理地址 0090 0000H 開始的連續(xù)主存空間中。頁表從主存0020 0000H 開始的物理地址處連續(xù)存放，如下圖所示（地址大小自下向上遞增） 。請計算出該代碼段對應(yīng)的兩個頁表項的物理地址（假設(shè)每個頁表項的長度為4字節(jié)(z ji)）、這兩個頁表項中的頁框號以及代碼頁面 2 的起始物理地址。2021-12-1549代碼頁面2代碼頁面1物理

52、地址30900 0000H 頁表 物理地址2頁框號2物理地址1頁框號10200 0000H 第49頁/共68頁第四十九頁，共69頁。2021-12-1550（1）因為頁內(nèi)偏移量是 12 位，所以頁大小為 4 KB，頁表項數(shù)為 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)

53、)%pow(2,10)（3）代碼頁面 1 的邏輯地址為 0000 8000H，表明其位于第 8 個頁處，對應(yīng)(duyng)頁表中的第 8 個頁表項，所以第 8 個頁表項的物理地址 = 頁表起始地址+8頁表項的字節(jié)數(shù) = 0020 0000H+84 = 0020 0020H。由此可得如下的答案：物理地址1： 0020 0020H物理地址2： 0020 0024H物理地址3： 0900 1000H頁框號1： 0900 0000H頁框號2： 0900 0001H第50頁/共68頁第五十頁，共69頁。2021-12-155114設(shè)某計算機(jī)的邏輯地址空間設(shè)某計算機(jī)的邏輯地址空間(kngjin)和物理地址

54、空間和物理地址空間(kngjin)均為均為64KB，按字節(jié)編址。若某進(jìn)程最多需要，按字節(jié)編址。若某進(jìn)程最多需要6頁頁(Page)數(shù)據(jù)存儲空間數(shù)據(jù)存儲空間(kngjin)，頁的大小為，頁的大小為1KB，操作系統(tǒng)采，操作系統(tǒng)采用固定分配局部置換策略為此進(jìn)程分配用固定分配局部置換策略為此進(jìn)程分配4個頁框個頁框(Page Frame)。在時刻在時刻260前的該進(jìn)程訪問情況如下表所示前的該進(jìn)程訪問情況如下表所示(訪問位即使用位訪問位即使用位)。 頁號頁號頁框號頁框號裝入時間裝入時間訪問位訪問位071301142301222001391601當(dāng)進(jìn)程執(zhí)行到時刻當(dāng)進(jìn)程執(zhí)行到時刻260時，要訪問邏輯地址時，要訪

55、問邏輯地址(dzh)為為17CAH的數(shù)據(jù)。的數(shù)據(jù)。請回答下列問題：請回答下列問題：（1）該邏輯地址）該邏輯地址(dzh)的對應(yīng)的頁號是多少？的對應(yīng)的頁號是多少？（2）若采用先進(jìn)先出）若采用先進(jìn)先出(FIFO)置換算法，該邏輯地址置換算法，該邏輯地址(dzh)對應(yīng)的對應(yīng)的物理地址物理地址(dzh)是多少？要求給出計算過程。是多少？要求給出計算過程。第51頁/共68頁第五十一頁，共69頁。2021-12-1552（3）若采用時鐘）若采用時鐘(CLOCK)置換算法，該邏輯地址對應(yīng)的物置換算法，該邏輯地址對應(yīng)的物理地址是多少？要求給出計算理地址是多少？要求給出計算(j sun)過程過程(設(shè)搜索下一頁的

56、設(shè)搜索下一頁的指針沿順時針方向移動，且當(dāng)前指向指針沿順時針方向移動，且當(dāng)前指向2號頁框，示意圖如下號頁框，示意圖如下)。 0號頁號頁1號頁號頁2號頁號頁3號頁號頁2號頁框號頁框4號頁框號頁框7號頁框號頁框9號頁框號頁框第52頁/共68頁第五十二頁，共69頁。2021-12-1553(1) 17CAH=0001 0111 1100 1010B，表示頁號的位是左邊，表示頁號的位是左邊6位，位，即即00101B，所以頁號為，所以頁號為5。根據(jù)根據(jù)FIFO算法，需要替換裝入時間最早的頁，故需要置換算法，需要替換裝入時間最早的頁，故需要置換裝入時間最早的裝入時間最早的0號頁，即將號頁，即將5頁裝入頁裝入

57、7號頁框中，所以物號頁框中，所以物理地址為理地址為0001 1111 1100 1010B，換算成十六進(jìn)制，為，換算成十六進(jìn)制，為1FCAH。根據(jù)根據(jù)CLOCK算法，如果當(dāng)前指針?biāo)疙摽虻氖褂梦粸樗惴?，如果?dāng)前指針?biāo)疙摽虻氖褂梦粸?，則，則替換該頁；否則將其使用位清零替換該頁；否則將其使用位清零(qn ln)，并將指針指，并將指針指向下一個頁框，繼續(xù)查找。根據(jù)題設(shè)和示意圖，將從向下一個頁框，繼續(xù)查找。根據(jù)題設(shè)和示意圖，將從2號號頁框開始，前頁框開始，前4次查找頁框順序為次查找頁框順序為2479，并將對應(yīng)，并將對應(yīng)頁框的使用位清零頁框的使用位清零(qn ln)。在第。在第5次查找中，指針指次查

58、找中，指針指向向2號頁框，因號頁框，因2號頁框的使用位為號頁框的使用位為0，故淘汰，故淘汰2號頁框?qū)μ栱摽驅(qū)?yīng)的應(yīng)的2號頁，把號頁，把5號頁裝入號頁裝入2號頁框中，并將對應(yīng)的使用位號頁框中，并將對應(yīng)的使用位置為置為1，所以對應(yīng)的物理地址為，所以對應(yīng)的物理地址為0000 1011 1100 1010B，換算成十六進(jìn)制，為換算成十六進(jìn)制，為0BCAH。第53頁/共68頁第五十三頁，共69頁。2021-12-155415. 若遞交給磁盤驅(qū)動程序的磁盤柱面請求按到達(dá)時若遞交給磁盤驅(qū)動程序的磁盤柱面請求按到達(dá)時間順序分別是間順序分別是10、22、20、2、40、6和和38，設(shè)磁頭初，設(shè)磁頭初始始(ch

59、sh)處于處于20柱面，磁頭從一柱面移到另一相鄰柱面，磁頭從一柱面移到另一相鄰柱面的時間是柱面的時間是2ms，則對于，則對于FCFS、最短尋道時間優(yōu)先、最短尋道時間優(yōu)先、電梯算法（初始電梯算法（初始(ch sh)磁頭向高柱面移動），平均磁頭向高柱面移動），平均尋道時間各為多少？尋道時間各為多少？ 解：對于解：對于FCFS，服務(wù)順序為，服務(wù)順序為10、22、20、2、40、6、38 平均尋道時間平均尋道時間(shjin)=(10+12+2+18+38+34+32)*2/7=41.71ms最短尋道時間最短尋道時間(shjin)優(yōu)先，服務(wù)順序為：優(yōu)先，服務(wù)順序為：20、22、10、6、2、38、40

60、平均尋道時間平均尋道時間(shjin)=(0+2+12+4+4+36+2)*2/7=17.14ms電梯算法，服務(wù)順序為：電梯算法，服務(wù)順序為：20、22、38、40、10、6、2平均尋道時間平均尋道時間(shjin)=(0+2+16+2+30+4+4)*2/8=16.57ms第54頁/共68頁第五十四頁，共69頁。2021-12-155516. 設(shè)文件索引節(jié)點中有設(shè)文件索引節(jié)點中有7個地址個地址(dzh)項，其中項，其中4個地址個地址(dzh)項是直接地址項是直接地址(dzh)索引，索引，2個地址個地址(dzh)項是一項是一級間接地址級間接地址(dzh)索引，索引，1個地址個地址(dzh)項是二級間接地項是二