操作系統(tǒng)原理復(fù)習(xí)-課件

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

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

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

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

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

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

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

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

{ P（Si）；

Pi從buffer中取出消息；

V（S1）；

Pi消費(fèi)（使用）該消息；

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

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

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

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

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

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

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

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

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

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

}

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

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

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

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

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

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

從取號(hào)機(jī)獲得

一個(gè)號(hào)碼;

等待叫號(hào);

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

叫號(hào);

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

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

等待叫號(hào);

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

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

叫號(hào);

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

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

222222221是否缺頁√√

√

√

√被淘汰頁號(hào)

0

1

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

002104134是否缺頁√√

√

√

√√被淘汰頁號(hào)

2

0

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

快表命中：

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

快表未命中但未缺頁：

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

（一次頁表訪問，一次實(shí)際地址訪問）

快表未命中且存在缺頁：

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

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

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

頁表

物理地址2頁框號(hào)2物理地址1頁框號(hào)102000000H

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

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

或 (LA/pow(2,12)

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

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

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

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

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