桂林電子科技大學(xué)信息科技學(xué)院操作系統(tǒng)習(xí)題復(fù)習(xí)課課件

1習(xí)題復(fù)習(xí)課1習(xí)題復(fù)習(xí)課2第一部分

同步和互斥問題2第一部分31.有三個(gè)進(jìn)程，進(jìn)程get從輸入設(shè)備上不斷讀數(shù)據(jù)，并存入buffer1;進(jìn)程cut不斷將buffer1的內(nèi)容剪切到緩沖區(qū)buffer2，進(jìn)程put則不斷將buffer2的內(nèi)容在打印機(jī)上輸出。三個(gè)進(jìn)程并發(fā)執(zhí)行，協(xié)調(diào)工作。寫出該三個(gè)進(jìn)程并發(fā)執(zhí)行的同步模型。getcutputbuffer1buffer231.有三個(gè)進(jìn)程，進(jìn)程get從輸入設(shè)備上不斷讀數(shù)據(jù)，并存入b4buffer1buffer2getcutputempty1empty2full1full2分析存在如下同步關(guān)系：(1)只有buffer1為空，get才能工作，并使buffer1為滿。(2)要求buffer1為滿，同時(shí)buffer2為空，cut才能工作，工作結(jié)果使buffer1為空，buffer2為滿。(3)只有buffer2為滿，put才能工作，并使buffer2為空。4buffer1buffer2getcutputempty15解答：（1）設(shè)置信號(hào)量設(shè)信號(hào)量empty1表示緩沖區(qū)buffer1為空,初值為1設(shè)信號(hào)量full1表示緩沖區(qū)buffer1為滿,初值為0設(shè)信號(hào)量empty2表示緩沖區(qū)buffer2為空,初值為1設(shè)信號(hào)量full2表示緩沖區(qū)buffer2為滿,初值為0buffer1buffer2getcutputempty1empty2full1full25解答：buffer1buffer2getcutputemp6（2）同步算法描述如下：cut(){while(true){Wait(full1)

Wait(empty2)cut操作

Signal(empty1)

Signal(full2)}}get(){while(true){Wait(empty1)get操作

Signal(full1)}}put(){while(true){Wait(full2)put操作

Signal(empty2)}}buffer1buffer2getcutputempty1empty2full1full26（2）同步算法描述如下：cut()get()put(7semaphoreempty1=1,full1=0,empty2=1,full2=0;get(){while(true){Wait(empty1);get操作;Signal(full1);}}cut(){while(true){Wait(full1);Wait(empty2);cut操作;Signal(empty1);Signal(full2);}}put(){while(true){Wait(full2);put操作;Signal(empty2);}}main(){parbegin(get,cut,put);}7semaphoreempty1=1,full1=0,em82.用PV操作解決司機(jī)和售票員的問題。司機(jī)進(jìn)程：while(true){啟動(dòng)車輛正常駕駛到站停車}售票員進(jìn)程：while(true){關(guān)門售票開門}分析存在如下同步關(guān)系：(1)售票員關(guān)門后，司機(jī)才能開車。(2)司機(jī)到站停車后，售票員才能開門。設(shè)信號(hào)量close表示關(guān)門開車,初值為0；設(shè)信號(hào)量stop表示到站開門,初值為082.用PV操作解決司機(jī)和售票員的問題。司機(jī)進(jìn)程：售票員進(jìn)程9semaphoreclose=0,open=0;driver(){while(true){Wait(close)啟動(dòng)車輛;正常行駛;到站停車;

Signal(stop)}}

seller(){while(true){關(guān)門

Signal(close)

售票

Wait(stop)

開門}}main(){parbegin(driver,seller);}9semaphoreclose=0,open=0;sell103.有一個(gè)閱覽室，共有100個(gè)座位，讀者進(jìn)入時(shí)必須先在一張登記表上登記，該表為每一位列一表目，包括座號(hào)和讀者姓名等，讀者離開時(shí)要消掉登記的信息。試用PV操作描述讀者進(jìn)程之間的同步關(guān)系。分析：讀者填表進(jìn)入閱覽室，這時(shí)要考慮閱覽室里是否有座位；同時(shí)還要考慮登記表的互斥使用。設(shè)信號(hào)量seats=100，mutex=1。前者用于約束只能有100個(gè)進(jìn)程共享閱覽室，后者用來約束登記表的互斥使用。103.有一個(gè)閱覽室，共有100個(gè)座位，讀者進(jìn)入時(shí)必須先在一11semaphoreseats=100reader(){ while(true){ Wait（seats）；

選書讀書；

Signal（seats）；}}

Wait（mutex）； 填寫登記表；

Signal（mutex）；

Wait（mutex）； 消掉登記；

Signal（mutex）；11semaphoreseats=10012思考題某小型超級(jí)市場(chǎng)，可容納50個(gè)人同時(shí)購(gòu)物。入口處備有籃子，每個(gè)購(gòu)物者可拿一只籃子入內(nèi)購(gòu)物。出口處結(jié)帳，并歸還籃子（出、入口禁止多人同時(shí)通過）。試用PV操作寫出購(gòu)物者的同步算法。12思考題某小型超級(jí)市場(chǎng)，可容納50個(gè)人同時(shí)購(gòu)物。入口處備有第二部分單道程序和多道程序13第二部分132.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)(SimpleBatchProcessingSystem)（1955-1965，晶體管時(shí)代，出現(xiàn)監(jiān)控程序）編程語言：匯編語言

單道：內(nèi)存中僅有一道作業(yè)在運(yùn)行批處理：計(jì)算機(jī)系統(tǒng)對(duì)一批作業(yè)自動(dòng)進(jìn)行處理2.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)(Sim2.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)1．處理過程把一批作業(yè)(用戶程序+數(shù)據(jù)+作業(yè)說明書)以脫機(jī)方式輸入到磁盤上，并在系統(tǒng)中配以監(jiān)督程序(Monitor，OS雛形)將作業(yè)逐個(gè)送入內(nèi)存并運(yùn)行。2.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)2.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)

2．特征：?jiǎn)蔚佬?、順序性、自?dòng)性優(yōu)點(diǎn)：減少CPU空閑時(shí)間，提高資源利用率和系統(tǒng)吞吐量。缺點(diǎn)：人機(jī)交互性差，CPU和I/O設(shè)備忙閑不均(取決于作業(yè)的特性)。解決辦法：多道程序設(shè)計(jì)技術(shù)2.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)2.2操作系統(tǒng)的發(fā)展過程2.2.3多道批處理系統(tǒng)(MultiprogrammedBatchProcessingSystem)

（1965-1980，半導(dǎo)體、小規(guī)模集成電路時(shí)代）1．多道程序設(shè)計(jì)的基本概念在內(nèi)存中同時(shí)存放多個(gè)作業(yè)，使之同時(shí)處于運(yùn)行狀態(tài)(均已開始運(yùn)行但尚未結(jié)束)共享系統(tǒng)資源。單CPU系統(tǒng)中的多道程序運(yùn)行的特征宏觀上并行：并發(fā)程序都已開始執(zhí)行，但都未結(jié)束微觀上串行：并發(fā)程序輪流占有CPU交替執(zhí)行2.2操作系統(tǒng)的發(fā)展過程2.2.3多道批處理系統(tǒng)(MultAAΔt等待I/O的時(shí)間（6個(gè)Δt）（a）單道情況11078BBtAAΔt（b）兩道情況1107189tΔt（c）四道情況1107189BBAACDCD2310單道、兩道和四道情況1421/8Δt=0.125道程序/Δt2/9Δt=0.222道程序/ΔtAI/OAI/OBI/O4/11Δt=0.363道程序/Δt下一步A,B,C,D為程序，忽略外設(shè)；假定4個(gè)程序都需運(yùn)行2個(gè)Δt時(shí)間，在期間有6個(gè)Δt時(shí)間的I/O操作；吞吐率分別為：1/8=0.1252/9=0.2224/11=0.3634道程序情況比單道提高了近3倍。顯然不僅使內(nèi)存充分利用，還帶來處理機(jī)利用率的提高，使整個(gè)系統(tǒng)效率得以提高。下一步結(jié)束下一步多道程序設(shè)計(jì)的基本概念tAAΔt等待I/O的時(shí)間（6個(gè)Δt）（a）單道情況1107（a）單道情形：打印請(qǐng)求打印請(qǐng)求單道與多道程序運(yùn)行情況（b）多道情形：程序AOSI/O設(shè)備繪圖儀請(qǐng)求t1t2t3t4t5t6t7t8CPU打印機(jī)繪圖儀程序B打印完成繪圖完成CPU空閑t9t10仍有空閑A/B運(yùn)行?

用戶程序監(jiān)督程序I/O操作I/O中斷請(qǐng)求

啟動(dòng)I/OI/O完成中斷I/O中斷請(qǐng)求啟動(dòng)I/Ot1I/O中斷處理結(jié)束t2t3t4t5t6t7t8CPU

CPU空閑空閑多道程序設(shè)計(jì)的基本概念（a）單道情形：打印請(qǐng)求打印請(qǐng)求單道與多道程序運(yùn)行情況（b）例題1若內(nèi)存中有3道程序A、B、C，它們按A、B、C優(yōu)先次序運(yùn)行。各程序的計(jì)算軌跡為：A：計(jì)算(20)、I/O(30)、計(jì)算(10)B：計(jì)算(40)、I/O(20)、計(jì)算(10)C：計(jì)算(10)、I/O(30)、計(jì)算(20)如果三道程序都使用相同設(shè)備進(jìn)行I/O(即程序用串行方式使用設(shè)備，調(diào)度開銷忽略不計(jì))。試分別畫出單道和多道運(yùn)行的時(shí)間關(guān)系圖。兩種情況下，CPU的平均利用率各為多少?20例題1若內(nèi)存中有3道程序A、B、C，它們按A、B、C優(yōu)先次序單道21單道21多道22多道22例題2理解單道和多道程序執(zhí)行時(shí)的不同例：A、B兩個(gè)程序，程序A按順序使用CPU10s，設(shè)備甲5s，CPU5s，設(shè)備乙10s，CPU10s，程序Ｂ按順序使用設(shè)備甲10s，CPU10s，設(shè)備乙5s，CPU5s，設(shè)備乙10s。問：①在順序環(huán)境下執(zhí)行程序A和B，CPU利用率多少？②在多道環(huán)境下呢？答：①A和B順序執(zhí)行時(shí)，A執(zhí)行完畢B才開始，總共耗時(shí)80s，占用CPU40s，故CPU利用率為40/80=50%。②多道時(shí)，兩程序共耗時(shí)45s，故CPU利用率為40/45=88.89%CPU:A:B:CPU甲乙CPU等待乙CPU甲CPU等待乙CPUABAB空閑A10s20s30s40s45s例題2理解單道和多道程序執(zhí)行時(shí)的不同例：A、B兩個(gè)程序，程24第三部分處理機(jī)調(diào)度24第三部分253.低級(jí)調(diào)度的功能和類型1.低級(jí)調(diào)度的主要功能調(diào)度程序兩項(xiàng)任務(wù)：調(diào)度和分派。調(diào)度實(shí)現(xiàn)調(diào)度策略，確定就緒進(jìn)程/線程競(jìng)爭(zhēng)使用處理器的次序的裁決原則，即進(jìn)程/線程何時(shí)應(yīng)放棄CPU和選擇哪個(gè)來執(zhí)行；分派實(shí)現(xiàn)調(diào)度機(jī)制，確定如何時(shí)分復(fù)用CPU，處理上下文交換細(xì)節(jié)，完成進(jìn)程/線程和CPU的綁定和放棄的實(shí)際工作。253.低級(jí)調(diào)度的功能和類型1.低級(jí)調(diào)度的主要功能26調(diào)度機(jī)制邏輯功能程序模塊組成隊(duì)列管理程序：管理等待調(diào)度的進(jìn)程/線程（排隊(duì)）。上下文切換程序時(shí)：當(dāng)發(fā)生進(jìn)程/線程切換時(shí)，用來保存舊現(xiàn)場(chǎng)，調(diào)入新現(xiàn)場(chǎng)。分派程序：分派CPU給選中的進(jìn)程/線程。26調(diào)度機(jī)制邏輯功能程序模塊組成隊(duì)列管理程序：管理等待調(diào)度273.1.低級(jí)調(diào)度的基本類型第一類稱剝奪式：兩種處理器剝奪原則一是高優(yōu)先級(jí)進(jìn)程/線程可剝奪低優(yōu)先級(jí)進(jìn)程/線程，二是當(dāng)運(yùn)行進(jìn)程/線程時(shí)間片用完后被剝奪。第二類稱非剝奪式：一旦某個(gè)進(jìn)程/線程開始運(yùn)行后便不再讓出處理器。比較剝奪式策略的開銷大，但可以避免進(jìn)程/線程長(zhǎng)時(shí)間的獨(dú)占處理器；很多操作系統(tǒng)使用兩種測(cè)略的組合，內(nèi)核關(guān)鍵程序是非剝奪式的，用戶進(jìn)程是剝奪式的。273.1.低級(jí)調(diào)度的基本類型第一類稱剝奪式：281、先到先服務(wù)調(diào)度（first-come,first-served,FCFS）先請(qǐng)求CPU的進(jìn)程被首先分配到CPU，可用FIFO隊(duì)列來實(shí)現(xiàn)平均周轉(zhuǎn)時(shí)間通常相當(dāng)長(zhǎng)，與作業(yè)的提交和調(diào)度順序有關(guān)非搶占調(diào)度例

進(jìn)程

區(qū)間時(shí)間

P124P23P33P1P2P30242730平均周轉(zhuǎn)時(shí)間(24+27+30)/3=27P2P3P103630平均周轉(zhuǎn)時(shí)間(3+6+30)/3=133.2作業(yè)調(diào)度和低級(jí)調(diào)度算法281、先到先服務(wù)調(diào)度（first-come,first-s292.

最短作業(yè)優(yōu)先算法SJF算法以進(jìn)入系統(tǒng)的作業(yè)所要求的CPU時(shí)間為標(biāo)準(zhǔn)，總選取估計(jì)計(jì)算時(shí)間最短的作業(yè)投入運(yùn)行。算法易于實(shí)現(xiàn)，效率不高，主要弱點(diǎn)是忽視了作業(yè)等待時(shí)間。會(huì)出現(xiàn)饑餓現(xiàn)象。SJF的平均作業(yè)周轉(zhuǎn)時(shí)間比FCFS要小，故它的調(diào)度性能比FCFS好。實(shí)現(xiàn)SJF調(diào)度算法需要知道作業(yè)所需運(yùn)行時(shí)間，否則調(diào)度就沒有依據(jù)，要精確知道一個(gè)作業(yè)的運(yùn)行時(shí)間是辦不到的。292.

最短作業(yè)優(yōu)先算法SJF算法以進(jìn)入系統(tǒng)的作業(yè)所要求的303.最短剩余時(shí)間優(yōu)先算法SRTF把SJF算法改為搶占式的。一個(gè)新作業(yè)進(jìn)入就緒狀態(tài)，如果新作業(yè)需要的CPU時(shí)間比當(dāng)前正在執(zhí)行的作業(yè)剩余下來還需的CPU時(shí)間短，SRTF強(qiáng)行趕走當(dāng)前正在執(zhí)行作業(yè)。稱最短剩余時(shí)間優(yōu)先算法此算法不但適用于JOB調(diào)度，同樣也適用于進(jìn)程調(diào)度。303.最短剩余時(shí)間優(yōu)先算法SRTF把SJF算法改為搶占式的31SJF調(diào)度例：進(jìn)程

區(qū)間時(shí)間

P16P28P37P43SRTF調(diào)度例：進(jìn)程

到達(dá)時(shí)間

區(qū)間時(shí)間

P108P214P329P435P4P1P3P2P1P2P4P1P30391624平均周轉(zhuǎn)時(shí)間：

(9+24+16+3)/4均周轉(zhuǎn)時(shí)間：

((17-0)+(5-1)+(26-2)+(10-3))/4=1331SJF調(diào)度例：SRTF調(diào)度例：P4P1P3P2P1P2P321、設(shè)作業(yè)J1和J2的運(yùn)行時(shí)間t1<=t2，當(dāng)采用短作業(yè)優(yōu)先時(shí)，調(diào)度順序?yàn)镴1、J2，平均周轉(zhuǎn)時(shí)間為(t1+(t1+t2))/2=(2t1+t2)/2。不采用短作業(yè)優(yōu)先時(shí)，調(diào)度順序?yàn)镴2、J1，平均周轉(zhuǎn)時(shí)間為(t2+(t2+t1))/2＝(t1+2t2)/2。顯然，得證。2、假設(shè)當(dāng)n=k時(shí)成立，則當(dāng)n=k+1時(shí)，J1，J2，……

，Jk

，Jk+1，它們的運(yùn)行時(shí)間分別為：t1，t2，……，tk，

tk+1。(ti<=

ti+1)

當(dāng)采用短作業(yè)優(yōu)先時(shí)，調(diào)度順序?yàn)镴1，J2，……

，Jk

，Jk+1，所有作業(yè)的平均周轉(zhuǎn)時(shí)間為：T=[T1+T2+…+Tk+Tk+1]/n=

[t1+(t1+t2)+…+(t1+t2+…+tk)+(t1+t2+…+tk+tk+1)]/n

不采用短作業(yè)優(yōu)先時(shí)，假設(shè)調(diào)度順序?yàn)镴1,J2,…,Jk+1,Jk。

所有作業(yè)的平均周轉(zhuǎn)時(shí)間為：T’=[T1+T2+…+Tk+1+Tk]/n=

[t1+(t1+t2)+…+(t1+t2+…+tk+1)+(t1+t2+…+tk+1+tk)]/n則：T’-T=[(tk+1+tk+1+tk)-(tk+tk+tk+1)]/n=(tk+1-tk)/n>=0。

得證。證明：采用SJF調(diào)度算法可以使平均周轉(zhuǎn)時(shí)間最少。321、設(shè)作業(yè)J1和J2的運(yùn)行時(shí)間t1<=t2，證明：采用S331.系統(tǒng)有5個(gè)進(jìn)程:A,B,C,D,E。它們的到達(dá)時(shí)間以及估計(jì)運(yùn)行的時(shí)間如下圖所示：請(qǐng)計(jì)算使用下述調(diào)度算法時(shí)，進(jìn)程的周轉(zhuǎn)時(shí)間和進(jìn)程流的平均周轉(zhuǎn)時(shí)間。(1)FCFS(2)SPN(3)HRRN(4)RR(q=1)進(jìn)程到達(dá)時(shí)間(ms)估計(jì)運(yùn)行時(shí)間(ms)A03B26C44D65E82331.系統(tǒng)有5個(gè)進(jìn)程:A,B,C,D,E。它們34(1)FCFS算法：按照先來先服務(wù)原則，調(diào)度順序?yàn)锳,B,C,D,E，詳細(xì)情況如下圖所示因此，A的周轉(zhuǎn)時(shí)間為3ms；B的周轉(zhuǎn)時(shí)間為9-2=7ms；

C的周轉(zhuǎn)時(shí)間為13-4=9ms；

D的周轉(zhuǎn)時(shí)間為18-6=12ms；

E的周轉(zhuǎn)時(shí)間為20-8=12ms；平均周轉(zhuǎn)時(shí)間為（3+7+9+12+12）/5=8.6ms34(1)FCFS算法：按照先來先服務(wù)原則，調(diào)度順序?yàn)锳,B35(2)SPN算法：按照短進(jìn)程原則，調(diào)度順序?yàn)锳,B,E,C,D，詳細(xì)情況如下圖所示因此，A的周轉(zhuǎn)時(shí)間為3ms；B的周轉(zhuǎn)時(shí)間為9-2=7ms；

C的周轉(zhuǎn)時(shí)間為15-4=11ms；

D的周轉(zhuǎn)時(shí)間為20-6=14ms；

E的周轉(zhuǎn)時(shí)間為11-8=3ms；平均周轉(zhuǎn)時(shí)間為（3+7+11+14+3）/5=7.6ms051015201234535(2)SPN算法：按照短進(jìn)程原則，調(diào)度順序?yàn)锳,B,E,36(3)HRRN算法：初始時(shí)刻只有A，因此先調(diào)度A執(zhí)行。A的周轉(zhuǎn)時(shí)間為3ms。A執(zhí)行完，只有B就緒，因此再調(diào)度B執(zhí)行。B的周轉(zhuǎn)時(shí)間為9-2=7ms；B執(zhí)行后，C,D,E均就緒，按照最高響應(yīng)比調(diào)度原則，Rc=(9+4-4)/4=2.25，Rd=(9+5-6)/5=1.6，Re=(9+2-8)/2=1.5因此再調(diào)度C執(zhí)行，C的周轉(zhuǎn)時(shí)間為13-4=9ms；C執(zhí)行后，Rd=(13+5-6)/5=2.4,Re=(13+2-8)/2=3.5,因此調(diào)度E執(zhí)行，E的周轉(zhuǎn)時(shí)間為15-8=7ms；最后調(diào)度D，D的周轉(zhuǎn)時(shí)間為20-6=14ms36(3)HRRN算法：B執(zhí)行后，C,D,E均就緒，按照最高37即，調(diào)度過程如圖所示1234505101520平均周轉(zhuǎn)時(shí)間為（3+7+9+7+14）/5=8ms37即，調(diào)度過程如圖所示1234505101520平均周轉(zhuǎn)時(shí)38(4)RR(q=1)算法：按照時(shí)間片輪轉(zhuǎn)法原則，調(diào)度情況如下圖所示因此，A的周轉(zhuǎn)時(shí)間為4ms；B的周轉(zhuǎn)時(shí)間為18-2=16ms；

C的周轉(zhuǎn)時(shí)間為17-4=13ms；

D的周轉(zhuǎn)時(shí)間為20-6=14ms；

E的周轉(zhuǎn)時(shí)間為15-8=7ms；平均周轉(zhuǎn)時(shí)間為（4+16+13+14+7）/5=10.8ms38(4)RR(q=1)算法：按照時(shí)間片輪轉(zhuǎn)法原則，調(diào)度情39點(diǎn)評(píng)：各種調(diào)度算法下，進(jìn)程的調(diào)度順序及調(diào)度執(zhí)行的詳細(xì)過程需要以圖或文字的形式進(jìn)行說明。僅給出最后的結(jié)果是不完整的。39點(diǎn)評(píng)：40第四部分

死鎖40第四部分41考慮有5個(gè)進(jìn)程共享4類資源，它們的占有量和尚需量如下：進(jìn)程已分配尚需可用P0002300121623P110002000P203300140P310100813P400143000(1)當(dāng)前狀態(tài)安全嗎?(2)如果進(jìn)程2提出資源請(qǐng)求(0,1,2,0),按照銀行家算法，能否滿足要求？41考慮有5個(gè)進(jìn)程共享4類資源，它們的占有量和尚需量如下：進(jìn)42(1)利用安全性算法對(duì)上述狀態(tài)進(jìn)行分析，如下表所示，WorkABCDNeedABCDAllocationABCDFinishP0P2P3P1P4162316461976298639860012014008132000300000230330101010000014truetruetruetruetrue因?yàn)榇嬖诎踩蛄蠵0、P2、P3、P1、P4，所以系統(tǒng)是安全的。42(1)利用安全性算法對(duì)上述狀態(tài)進(jìn)行分析，如下表所示，Wo43(2)P2發(fā)出請(qǐng)求(0,1,2,0)后，系統(tǒng)按銀行家算法進(jìn)行檢查：Request(0,1,2,0)<=Need2(0,1,4,0);Request(0,1,2,0)<=Available(1,6,2,3);試探為P2分配資源，并修改數(shù)據(jù)：

Available=(1,5,0,3);Allocation2=(0,4,5,0)Need2=(0,0,2,0)。進(jìn)行安全性檢查，發(fā)現(xiàn)Available(1,5,0,3)<Needi，即Available不能滿足任何進(jìn)程的請(qǐng)求，故系統(tǒng)進(jìn)入不安全狀態(tài)。因此，P2提出的上述請(qǐng)求不能滿足，系統(tǒng)不能分配資源給它。43(2)P2發(fā)出請(qǐng)求(0,1,2,0)后，系統(tǒng)按銀行家算法44第五部分

虛擬內(nèi)存44第五部分邏輯地址轉(zhuǎn)化物理地址過程邏輯地址以十六進(jìn)制數(shù)給出根據(jù)頁(yè)大小劃分邏輯地址為頁(yè)號(hào)和頁(yè)內(nèi)地址以頁(yè)號(hào)查頁(yè)表，得到對(duì)應(yīng)內(nèi)存塊號(hào)物理地址＝頁(yè)號(hào)拼接位移量邏輯地址以十進(jìn)制數(shù)給出頁(yè)號(hào)＝虛地址/頁(yè)大小位移量＝虛地址mod頁(yè)大小以頁(yè)號(hào)查頁(yè)表，得到對(duì)應(yīng)內(nèi)存塊號(hào)物理地址＝塊號(hào)×頁(yè)大?。灰屏窟壿嫷刂忿D(zhuǎn)化物理地址過程邏輯地址以十六進(jìn)制數(shù)給出例1某虛擬存儲(chǔ)器的用戶編程空間共32個(gè)頁(yè)面，每頁(yè)為1KB，內(nèi)存為16KB。假定某時(shí)刻一用戶頁(yè)表中已調(diào)入內(nèi)存的頁(yè)面對(duì)應(yīng)的物理塊號(hào)如下表：頁(yè)號(hào)物理塊號(hào)051102437則邏輯地址0A5C（H）所對(duì)應(yīng)的物理地址為：_____例1某虛擬存儲(chǔ)器的用戶編程空間共32個(gè)頁(yè)面，每頁(yè)為1KB，內(nèi)例10A5CH＝0000,1010,0101,1100B頁(yè)號(hào)為2，對(duì)應(yīng)塊號(hào)為4，物理地址：0001，0010,0101,1100即：125CH頁(yè)號(hào)物理塊號(hào)051102437例10A5CH＝0000,1010,0101,1100B頁(yè)例2設(shè)頁(yè)面大小為1K字節(jié)，作業(yè)的0、1、2頁(yè)分別存放在第2、3、8塊中。求邏輯地址2500對(duì)應(yīng)的物理地址？則邏輯地址2500的頁(yè)號(hào)為2（2500/1024=2）頁(yè)內(nèi)地址為452（2500%1024＝452）。查頁(yè)表可知第2頁(yè)對(duì)應(yīng)的物理塊號(hào)為8。將塊號(hào)8與頁(yè)內(nèi)地址452拼接（8×1024＋452＝8644）得到物理地址為8644。例2設(shè)頁(yè)面大小為1K字節(jié)，作業(yè)的0、1、2頁(yè)分別存放在第2、【例3】某請(qǐng)求頁(yè)式存儲(chǔ)管理，允許用戶編程空間為32個(gè)頁(yè)面，每頁(yè)1KB，主存為16KB。如有一用戶程序有10頁(yè)長(zhǎng)，且某時(shí)刻該用戶頁(yè)面映射如下如果分別有對(duì)以下三個(gè)虛地址:0AC5H,1AC5H,3AC5H處的操作，試計(jì)算并說明存儲(chǔ)管理系統(tǒng)將如何處理：【例3】某請(qǐng)求頁(yè)式存儲(chǔ)管理，允許用戶編程空間為32個(gè)頁(yè)面，每【分析】本題考察虛地址與實(shí)際物理地址的轉(zhuǎn)化問題，首先有用戶空間地址確定虛頁(yè)號(hào)要用多少個(gè)二進(jìn)制位來表示，又已知頁(yè)面大小就可以推算出還需要的二進(jìn)制位數(shù)，兩者相加可知虛地址的長(zhǎng)度。從主存大小確定物理地址的二進(jìn)制位數(shù)。由虛地址的虛頁(yè)號(hào)位數(shù)查表確定是那一物理塊，換算成二進(jìn)制數(shù)，在連接后面的偏移值就是實(shí)際的物理地址?！痉治觥勘绢}考察虛地址與實(shí)際物理地址的轉(zhuǎn)化問題，首先有用戶空【解答】頁(yè)面大小為1KB，在虛地址中有10個(gè)二進(jìn)制位，用戶地址空間有32頁(yè)，虛頁(yè)號(hào)占5位，因此虛地址長(zhǎng)度為15位。又主存為16KB，所以物理地址14位。0AC5H的二進(jìn)制：000101011000101,其中需頁(yè)號(hào)為00010,即2，由表知是4號(hào)物理塊，即0100，所以相應(yīng)物理地址12C5H1AC5H的二進(jìn)制：001101011000101，虛頁(yè)號(hào)00110，即6，由表知沒有第6頁(yè)，將發(fā)生缺頁(yè)中斷，系統(tǒng)從外存中把第6頁(yè)調(diào)入內(nèi)存，然后更新頁(yè)表。3AC5H的二進(jìn)制：011101011000101，虛頁(yè)號(hào)為01110，即14，由于14>10,超過作業(yè)的地址空間長(zhǎng)度，系統(tǒng)發(fā)生地址越界中斷，程序運(yùn)行終止。【解答】頁(yè)面大小為1KB，在虛地址中有10個(gè)二進(jìn)制位，用戶地練習(xí)題1.一分頁(yè)存儲(chǔ)管理系統(tǒng)中邏輯地址長(zhǎng)度為16位，頁(yè)面大小為1KB字節(jié)，現(xiàn)有一邏輯地址為0A6FH，且第0、1、2、3、頁(yè)依次存放在物理塊3、7、11、10中。邏輯地址0A6FH對(duì)應(yīng)的物理地址是多少？邏輯地址0A6FH的二進(jìn)制表示如下：頁(yè)號(hào)頁(yè)內(nèi)地址0000，1010，0110，1111由此可知邏輯地址0A6FH的頁(yè)號(hào)為2，該頁(yè)存放在第11號(hào)物理塊中，用十六進(jìn)制表示塊號(hào)為B，所以物理地址為：0010，1110，0110，1111，即2E6FH。練習(xí)題1.一分頁(yè)存儲(chǔ)管理系統(tǒng)中邏輯地址長(zhǎng)度為16位，頁(yè)面大小練習(xí)題2.有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁(yè)大小為2KB，依次裝入內(nèi)存的第7、9、A、5塊，試將虛地址0AFEH，1ADDH轉(zhuǎn)換成內(nèi)存地址。虛地址0AFEH0000101011111110P＝1W＝01011111110PA＝00100101011111110＝4AFEH虛地址1ADDH0001101011011101P＝3W＝01011011101PA＝0010101011011101

＝2ADDH練習(xí)題2.有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁(yè)若在一分頁(yè)存儲(chǔ)管理系統(tǒng)中，某作業(yè)的頁(yè)表如右所示。已知頁(yè)面大小為1024字節(jié)，試將邏輯地址0A5CH，07EFH，3000，5012轉(zhuǎn)化為相應(yīng)的物理地址。頁(yè)號(hào)塊號(hào)02132136若在一分頁(yè)存儲(chǔ)管理系統(tǒng)中，某作業(yè)的頁(yè)表如右所示。已知頁(yè)面大小對(duì)于邏輯地址0A5CH0A5CH=0000101001011100頁(yè)號(hào)2，對(duì)應(yīng)物理塊1物理地址為0000011001011100即065CH對(duì)于邏輯地址07EFH0A5CH=0000011111101111頁(yè)號(hào)1，對(duì)應(yīng)物理塊3物理地址為0000111111101111即0FEFH對(duì)于邏輯地址3000P＝int(3000/1024)＝2W＝3000mod1024＝952查頁(yè)表第2頁(yè)在第1塊，所以物理地址為1976。對(duì)于邏輯地址5012P＝int(5012/1024)＝4W＝5012mod1024＝916因頁(yè)號(hào)超過頁(yè)表長(zhǎng)度，該邏輯地址非法。對(duì)于邏輯地址0A5CH習(xí)題解答3有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是8KB，頁(yè)大小為2KB，依次裝入內(nèi)存的第7、9、10、5塊，試將虛地址7145，3412轉(zhuǎn)換成內(nèi)存地址。虛地址3412P＝3412％2048＝1W＝3412mod2048＝1364MR=9*2048+1364=19796虛地址3412的內(nèi)存地址是：19796虛地址7145P＝7145％2048＝3W＝7145mod2048＝1001MR=5*2048+1001=11241虛地址7145的內(nèi)存地址是：11241習(xí)題解答3有一系統(tǒng)采用頁(yè)式存儲(chǔ)管理，有一作業(yè)大小是8KB，六.磁盤的調(diào)度算法磁盤是典型的共享設(shè)備。在用戶處理的信息量越來越大的情況下，對(duì)磁盤等共享設(shè)備的訪問也越來越頻繁，因而訪問調(diào)度是否得當(dāng)直接影響到系統(tǒng)的效率。磁盤調(diào)度的目標(biāo)：減少尋道時(shí)間有如下五種磁盤調(diào)度算法：一、FCFS（FisrtComeFirstSecond）二、SSTF（最短尋道優(yōu)先）三、掃描算法。四、循環(huán)掃描CSCAN五、N—Step—SCAN和FSCAN算法。六.磁盤的調(diào)度算法磁盤是典型的共享設(shè)備。在用戶處理的信息量圖5-23FCFS調(diào)度算法1.先來先服務(wù)FCFS(First-Come,FirstServed)僅用于請(qǐng)求磁盤I/O的進(jìn)程數(shù)目較少的場(chǎng)合。圖5-23FCFS調(diào)度算法1.先來先服務(wù)FCFS(Fi圖5-24SSTF調(diào)度算法2.最短尋道時(shí)間優(yōu)先SSTF(ShortestSeekTimeFirst)要求訪問的磁道與當(dāng)前磁頭距離最近，使每次的尋道時(shí)間最短圖5-24SSTF調(diào)度算法2.最短尋道時(shí)間優(yōu)先SSTSSTF算法雖然能獲得較好的尋道性能，卻可能導(dǎo)致某個(gè)進(jìn)程發(fā)生“饑餓”(Starvation)現(xiàn)象。Scan算法該算法不僅考慮到欲訪問的磁道與當(dāng)前磁道間的距離，更優(yōu)先考慮磁頭當(dāng)前的移動(dòng)方向。其原理是訪問的下一個(gè)對(duì)象應(yīng)是同方向的，且又距離最近的。一般自里向外訪問，直至再無更外的磁道需要訪問，才將磁臂換向自外向里，往返反復(fù)。這種算法又稱為“電梯算法”3.掃描(SCAN)算法SSTF算法雖然能獲得較好的尋道性能，卻可能導(dǎo)致某個(gè)進(jìn)程發(fā)生SCAN調(diào)度算法100道開始，增加方向被訪問下一個(gè)磁道移動(dòng)距離1505016010184249094583255339163811820平均尋道長(zhǎng)度：27.8SCAN調(diào)度算法100道開始，增加方向被訪問下一個(gè)磁道移動(dòng)距Cscan算法規(guī)定磁頭單項(xiàng)移動(dòng)，進(jìn)行循環(huán)掃描。一個(gè)方向讀完，不是象SCAN那樣回頭，而是循環(huán)。訪問時(shí)間：2TT+SmaxT是從外向里或從里向外單向掃描完要訪問的磁道的尋道時(shí)間。而Smax是將磁頭從最外面被訪問的磁道直接移到最里面欲訪問的磁道的尋道時(shí)間。4.循環(huán)掃描(CSCAN)算法Cscan算法規(guī)定磁頭單項(xiàng)移動(dòng)，進(jìn)行循環(huán)掃描。一個(gè)方向讀完，CSCAN調(diào)度算法100道開始，增加方向被訪問的下一個(gè)磁道移動(dòng)距離15050160101842418166382039155165839032平均尋道長(zhǎng)度：27.5CSCAN調(diào)度算法100道開始，增加方向被訪問的下一個(gè)磁道移若某磁盤共有200個(gè)柱面，其編號(hào)為0～199，假設(shè)已完成96號(hào)柱面的訪問請(qǐng)求，還有若干個(gè)請(qǐng)求者在等待服務(wù)，它們依次要訪問的柱面號(hào)為：175，52，157，36，159、106，l08，72，分別用先來先服務(wù)調(diào)度算法、最短尋道時(shí)間調(diào)度算法、電梯調(diào)度算法和單向掃描調(diào)度算法（向序號(hào)增加的方向移動(dòng)）來確定實(shí)際服務(wù)的次序，并計(jì)算上述兩種算法下移動(dòng)臂需移動(dòng)的距離。若某磁盤共有200個(gè)柱面，其編號(hào)為0～199，假設(shè)已完成96(1)先來先服務(wù)調(diào)度算法：實(shí)際服務(wù)的次序：96→175→52→157→36→159→106→108→72移動(dòng)臂需移動(dòng)的距離為：(175-96)+(175-52)+(157-52)+(157-36)+(159-36)+(159-106)+(108-106)+(108-72)=642移動(dòng)臂需移動(dòng)642柱面的距離。(2)最短尋找時(shí)間優(yōu)先調(diào)度算法：實(shí)際服務(wù)的次序：96→106→108→72→52→36→157→159→175移動(dòng)臂需移動(dòng)的距離為：(106-96)+(108-l06)+(108-72)+(72-52)+(52-36)+(157-36)+(159-l57)+(175-159)=223移動(dòng)臂需移動(dòng)223個(gè)柱面的距離。桂林電子科技大學(xué)信息科技學(xué)院操作系統(tǒng)習(xí)題復(fù)習(xí)課課件(1)電梯調(diào)度算法：實(shí)際服務(wù)的次序：96→106→108→157→159→175→72→52→36(106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-72)+(72-52)+(52-36)=218移動(dòng)臂需移動(dòng)218個(gè)柱面的距離。(2)單向掃描調(diào)度算法：實(shí)際服務(wù)的次序：96→106→108→157→159→175→36→52→72(106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(175-36)+(52-36)+(72-52)=254除了移動(dòng)臂由里向外返回所用的時(shí)間外，還需移動(dòng)254個(gè)柱面的距離。(1)電梯調(diào)度算法：七、最佳置換算法和先進(jìn)先出算法1、FIFO淘汰最先進(jìn)入內(nèi)存的頁(yè)面，即選擇在內(nèi)存中駐留時(shí)間最久的頁(yè)面予以淘汰。出發(fā)點(diǎn)：最早調(diào)入主存中的頁(yè)面不再使用的可能性越大，應(yīng)該最先淘汰。算法簡(jiǎn)單對(duì)具有按線性順序訪問的程序比較合適，而對(duì)其它情況效率不高七、最佳置換算法和先進(jìn)先出算法1、FIFO最佳置換算法和先進(jìn)先出算法進(jìn)程P執(zhí)行時(shí)的頁(yè)面走向?yàn)椋?,2,3,4,1,2,5,1,2,3,4,5；如果在內(nèi)存中分配3個(gè)頁(yè)面，則缺頁(yè)情況如下：12次訪問中有缺頁(yè)9次；最佳置換算法和先進(jìn)先出算法進(jìn)程P執(zhí)行時(shí)的頁(yè)面走向?yàn)椋?,2如果在內(nèi)存中分配4個(gè)頁(yè)面，則缺頁(yè)情況如下：12次訪問中有缺頁(yè)10次；Belady現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動(dòng)態(tài)特征是矛盾的，即被置換的頁(yè)面并不是進(jìn)程不會(huì)訪問的。如果在內(nèi)存中分配4個(gè)頁(yè)面，則缺頁(yè)情況如下：12次訪問中有缺頁(yè)習(xí)題1．某進(jìn)程執(zhí)行時(shí)的頁(yè)面走向?yàn)?23412512345，分別畫出其分配物理塊為3的最佳置換算法的置換圖。2．某進(jìn)程執(zhí)行時(shí)的頁(yè)面走向?yàn)?23412512345，分別畫出其分配物理塊為3和4的FIFO算法的置換圖。3．在請(qǐng)求分頁(yè)管理系統(tǒng)中，一個(gè)作業(yè)要依次訪問如下頁(yè)面：342143143145，采用LRU置換算法求出訪問過程中發(fā)生的缺頁(yè)中斷的次數(shù)及缺頁(yè)率。設(shè)分給作業(yè)的存儲(chǔ)塊數(shù)為3.習(xí)題1．某進(jìn)程執(zhí)行時(shí)的頁(yè)面走向?yàn)?2341254．在請(qǐng)求分頁(yè)管理系統(tǒng)中，一個(gè)作業(yè)要依次訪問如下頁(yè)面：232152453252，設(shè)分給作業(yè)的存儲(chǔ)塊數(shù)為3。若用最佳置換算法，先進(jìn)先出，LRU置換算法求出訪問過程中發(fā)生的缺頁(yè)次數(shù)及缺頁(yè)率。4．在請(qǐng)求分頁(yè)管理系統(tǒng)中，一個(gè)作業(yè)要依次訪問如下頁(yè)面：23習(xí)題1．某進(jìn)程執(zhí)行時(shí)的頁(yè)面走向?yàn)?23412512345，分別畫出其分配物理塊為3的最佳置換算法的置換圖。習(xí)題1．某進(jìn)程執(zhí)行時(shí)的頁(yè)面走向?yàn)?234125習(xí)題2．某進(jìn)程執(zhí)行時(shí)的頁(yè)面走向?yàn)?23412512345，分別畫出其分配物理塊為3和4的FIFO算法的置換圖。習(xí)題2．某進(jìn)程執(zhí)行時(shí)的頁(yè)面走向?yàn)?234125習(xí)題3．在請(qǐng)求分頁(yè)管理系統(tǒng)中，一個(gè)作業(yè)要依次訪問如下頁(yè)面：342143143145，采用LRU置換算法求出訪問過程中發(fā)生的缺頁(yè)中斷的次數(shù)及缺頁(yè)率。設(shè)分給作業(yè)的存儲(chǔ)塊數(shù)為3.習(xí)題3．在請(qǐng)求分頁(yè)管理系統(tǒng)中，一個(gè)作業(yè)要依次訪問如下頁(yè)面：34．在請(qǐng)求分頁(yè)管理系統(tǒng)中，一個(gè)作業(yè)要依次訪問如下頁(yè)面：232152453252，設(shè)分給作業(yè)的存儲(chǔ)塊數(shù)為3。若用最佳置換算法，先進(jìn)先出，LRU置換算法求出訪問過程中發(fā)生的缺頁(yè)次數(shù)及缺頁(yè)率。4．在請(qǐng)求分頁(yè)管理系統(tǒng)中，一個(gè)作業(yè)要依次訪問如下頁(yè)面：23桂林電子科技大學(xué)信息科技學(xué)院操作系統(tǒng)習(xí)題復(fù)習(xí)課課件請(qǐng)求分頁(yè)存儲(chǔ)管理方式中，假定系統(tǒng)為某進(jìn)程分配了4個(gè)頁(yè)框，頁(yè)面的引用順序?yàn)椋?、1、2、0、3、0、4、2、3、0、3、2、6、0，采用FIFO置換算法產(chǎn)生多少次頁(yè)面置換？缺頁(yè)率是多少？(2)頁(yè)面置換次數(shù)為3次(3)缺頁(yè)率為：7/14=50%請(qǐng)求分頁(yè)存儲(chǔ)管理方式中，假定系統(tǒng)為某進(jìn)程分配了4個(gè)頁(yè)框，頁(yè)面請(qǐng)求分頁(yè)存儲(chǔ)管理方式中，假設(shè)分配給某進(jìn)程的頁(yè)框數(shù)為3，若程序的頁(yè)面引用順序?yàn)椋?、2、3、4、1、2、5、0、2、3、2、5，采用最佳置換算法產(chǎn)生多少次頁(yè)面置換？缺頁(yè)率是多少？(2)頁(yè)面置換次數(shù)為4次(3)缺頁(yè)率為：7/12=58%請(qǐng)求分頁(yè)存儲(chǔ)管理方式中，假設(shè)分配給某進(jìn)程的頁(yè)框數(shù)為3，若程序79習(xí)題復(fù)習(xí)課1習(xí)題復(fù)習(xí)課80第一部分

同步和互斥問題2第一部分811.有三個(gè)進(jìn)程，進(jìn)程get從輸入設(shè)備上不斷讀數(shù)據(jù)，并存入buffer1;進(jìn)程cut不斷將buffer1的內(nèi)容剪切到緩沖區(qū)buffer2，進(jìn)程put則不斷將buffer2的內(nèi)容在打印機(jī)上輸出。三個(gè)進(jìn)程并發(fā)執(zhí)行，協(xié)調(diào)工作。寫出該三個(gè)進(jìn)程并發(fā)執(zhí)行的同步模型。getcutputbuffer1buffer231.有三個(gè)進(jìn)程，進(jìn)程get從輸入設(shè)備上不斷讀數(shù)據(jù)，并存入b82buffer1buffer2getcutputempty1empty2full1full2分析存在如下同步關(guān)系：(1)只有buffer1為空，get才能工作，并使buffer1為滿。(2)要求buffer1為滿，同時(shí)buffer2為空，cut才能工作，工作結(jié)果使buffer1為空，buffer2為滿。(3)只有buffer2為滿，put才能工作，并使buffer2為空。4buffer1buffer2getcutputempty183解答：（1）設(shè)置信號(hào)量設(shè)信號(hào)量empty1表示緩沖區(qū)buffer1為空,初值為1設(shè)信號(hào)量full1表示緩沖區(qū)buffer1為滿,初值為0設(shè)信號(hào)量empty2表示緩沖區(qū)buffer2為空,初值為1設(shè)信號(hào)量full2表示緩沖區(qū)buffer2為滿,初值為0buffer1buffer2getcutputempty1empty2full1full25解答：buffer1buffer2getcutputemp84（2）同步算法描述如下：cut(){while(true){Wait(full1)

Wait(empty2)cut操作

Signal(empty1)

Signal(full2)}}get(){while(true){Wait(empty1)get操作

Signal(full1)}}put(){while(true){Wait(full2)put操作

Signal(empty2)}}buffer1buffer2getcutputempty1empty2full1full26（2）同步算法描述如下：cut()get()put(85semaphoreempty1=1,full1=0,empty2=1,full2=0;get(){while(true){Wait(empty1);get操作;Signal(full1);}}cut(){while(true){Wait(full1);Wait(empty2);cut操作;Signal(empty1);Signal(full2);}}put(){while(true){Wait(full2);put操作;Signal(empty2);}}main(){parbegin(get,cut,put);}7semaphoreempty1=1,full1=0,em862.用PV操作解決司機(jī)和售票員的問題。司機(jī)進(jìn)程：while(true){啟動(dòng)車輛正常駕駛到站停車}售票員進(jìn)程：while(true){關(guān)門售票開門}分析存在如下同步關(guān)系：(1)售票員關(guān)門后，司機(jī)才能開車。(2)司機(jī)到站停車后，售票員才能開門。設(shè)信號(hào)量close表示關(guān)門開車,初值為0；設(shè)信號(hào)量stop表示到站開門,初值為082.用PV操作解決司機(jī)和售票員的問題。司機(jī)進(jìn)程：售票員進(jìn)程87semaphoreclose=0,open=0;driver(){while(true){Wait(close)啟動(dòng)車輛;正常行駛;到站停車;

Signal(stop)}}

seller(){while(true){關(guān)門

Signal(close)

售票

Wait(stop)

開門}}main(){parbegin(driver,seller);}9semaphoreclose=0,open=0;sell883.有一個(gè)閱覽室，共有100個(gè)座位，讀者進(jìn)入時(shí)必須先在一張登記表上登記，該表為每一位列一表目，包括座號(hào)和讀者姓名等，讀者離開時(shí)要消掉登記的信息。試用PV操作描述讀者進(jìn)程之間的同步關(guān)系。分析：讀者填表進(jìn)入閱覽室，這時(shí)要考慮閱覽室里是否有座位；同時(shí)還要考慮登記表的互斥使用。設(shè)信號(hào)量seats=100，mutex=1。前者用于約束只能有100個(gè)進(jìn)程共享閱覽室，后者用來約束登記表的互斥使用。103.有一個(gè)閱覽室，共有100個(gè)座位，讀者進(jìn)入時(shí)必須先在一89semaphoreseats=100reader(){ while(true){ Wait（seats）；

選書讀書；

Signal（seats）；}}

Wait（mutex）； 填寫登記表；

Signal（mutex）；

Wait（mutex）； 消掉登記；

Signal（mutex）；11semaphoreseats=10090思考題某小型超級(jí)市場(chǎng)，可容納50個(gè)人同時(shí)購(gòu)物。入口處備有籃子，每個(gè)購(gòu)物者可拿一只籃子入內(nèi)購(gòu)物。出口處結(jié)帳，并歸還籃子（出、入口禁止多人同時(shí)通過）。試用PV操作寫出購(gòu)物者的同步算法。12思考題某小型超級(jí)市場(chǎng)，可容納50個(gè)人同時(shí)購(gòu)物。入口處備有第二部分單道程序和多道程序91第二部分132.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)(SimpleBatchProcessingSystem)（1955-1965，晶體管時(shí)代，出現(xiàn)監(jiān)控程序）編程語言：匯編語言

單道：內(nèi)存中僅有一道作業(yè)在運(yùn)行批處理：計(jì)算機(jī)系統(tǒng)對(duì)一批作業(yè)自動(dòng)進(jìn)行處理2.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)(Sim2.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)1．處理過程把一批作業(yè)(用戶程序+數(shù)據(jù)+作業(yè)說明書)以脫機(jī)方式輸入到磁盤上，并在系統(tǒng)中配以監(jiān)督程序(Monitor，OS雛形)將作業(yè)逐個(gè)送入內(nèi)存并運(yùn)行。2.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)2.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)

2．特征：?jiǎn)蔚佬?、順序性、自?dòng)性優(yōu)點(diǎn)：減少CPU空閑時(shí)間，提高資源利用率和系統(tǒng)吞吐量。缺點(diǎn)：人機(jī)交互性差，CPU和I/O設(shè)備忙閑不均(取決于作業(yè)的特性)。解決辦法：多道程序設(shè)計(jì)技術(shù)2.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)2.2操作系統(tǒng)的發(fā)展過程2.2.3多道批處理系統(tǒng)(MultiprogrammedBatchProcessingSystem)

（1965-1980，半導(dǎo)體、小規(guī)模集成電路時(shí)代）1．多道程序設(shè)計(jì)的基本概念在內(nèi)存中同時(shí)存放多個(gè)作業(yè)，使之同時(shí)處于運(yùn)行狀態(tài)(均已開始運(yùn)行但尚未結(jié)束)共享系統(tǒng)資源。單CPU系統(tǒng)中的多道程序運(yùn)行的特征宏觀上并行：并發(fā)程序都已開始執(zhí)行，但都未結(jié)束微觀上串行：并發(fā)程序輪流占有CPU交替執(zhí)行2.2操作系統(tǒng)的發(fā)展過程2.2.3多道批處理系統(tǒng)(MultAAΔt等待I/O的時(shí)間（6個(gè)Δt）（a）單道情況11078BBtAAΔt（b）兩道情況1107189tΔt（c）四道情況1107189BBAACDCD2310單道、兩道和四道情況1421/8Δt=0.125道程序/Δt2/9Δt=0.222道程序/ΔtAI/OAI/OBI/O4/11Δt=0.363道程序/Δt下一步A,B,C,D為程序，忽略外設(shè)；假定4個(gè)程序都需運(yùn)行2個(gè)Δt時(shí)間，在期間有6個(gè)Δt時(shí)間的I/O操作；吞吐率分別為：1/8=0.1252/9=0.2224/11=0.3634道程序情況比單道提高了近3倍。顯然不僅使內(nèi)存充分利用，還帶來處理機(jī)利用率的提高，使整個(gè)系統(tǒng)效率得以提高。下一步結(jié)束下一步多道程序設(shè)計(jì)的基本概念tAAΔt等待I/O的時(shí)間（6個(gè)Δt）（a）單道情況1107（a）單道情形：打印請(qǐng)求打印請(qǐng)求單道與多道程序運(yùn)行情況（b）多道情形：程序AOSI/O設(shè)備繪圖儀請(qǐng)求t1t2t3t4t5t6t7t8CPU打印機(jī)繪圖儀程序B打印完成繪圖完成CPU空閑t9t10仍有空閑A/B運(yùn)行?

用戶程序監(jiān)督程序I/O操作I/O中斷請(qǐng)求

啟動(dòng)I/OI/O完成中斷I/O中斷請(qǐng)求啟動(dòng)I/Ot1I/O中斷處理結(jié)束t2t3t4t5t6t7t8CPU

CPU空閑空閑多道程序設(shè)計(jì)的基本概念（a）單道情形：打印請(qǐng)求打印請(qǐng)求單道與多道程序運(yùn)行情況（b）例題1若內(nèi)存中有3道程序A、B、C，它們按A、B、C優(yōu)先次序運(yùn)行。各程序的計(jì)算軌跡為：A：計(jì)算(20)、I/O(30)、計(jì)算(10)B：計(jì)算(40)、I/O(20)、計(jì)算(10)C：計(jì)算(10)、I/O(30)、計(jì)算(20)如果三道程序都使用相同設(shè)備進(jìn)行I/O(即程序用串行方式使用設(shè)備，調(diào)度開銷忽略不計(jì))。試分別畫出單道和多道運(yùn)行的時(shí)間關(guān)系圖。兩種情況下，CPU的平均利用率各為多少?98例題1若內(nèi)存中有3道程序A、B、C，它們按A、B、C優(yōu)先次序單道99單道21多道100多道22例題2理解單道和多道程序執(zhí)行時(shí)的不同例：A、B兩個(gè)程序，程序A按順序使用CPU10s，設(shè)備甲5s，CPU5s，設(shè)備乙10s，CPU10s，程序Ｂ按順序使用設(shè)備甲10s，CPU10s，設(shè)備乙5s，CPU5s，設(shè)備乙10s。問：①在順序環(huán)境下執(zhí)行程序A和B，CPU利用率多少？②在多道環(huán)境下呢？答：①A和B順序執(zhí)行時(shí)，A執(zhí)行完畢B才開始，總共耗時(shí)80s，占用CPU40s，故CPU利用率為40/80=50%。②多道時(shí)，兩程序共耗時(shí)45s，故CPU利用率為40/45=88.89%CPU:A:B:CPU甲乙CPU等待乙CPU甲CPU等待乙CPUABAB空閑A10s20s30s40s45s例題2理解單道和多道程序執(zhí)行時(shí)的不同例：A、B兩個(gè)程序，程102第三部分處理機(jī)調(diào)度24第三部分1033.低級(jí)調(diào)度的功能和類型1.低級(jí)調(diào)度的主要功能調(diào)度程序兩項(xiàng)任務(wù)：調(diào)度和分派。調(diào)度實(shí)現(xiàn)調(diào)度策略，確定就緒進(jìn)程/線程競(jìng)爭(zhēng)使用處理器的次序的裁決原則，即進(jìn)程/線程何時(shí)應(yīng)放棄CPU和選擇哪個(gè)來執(zhí)行；分派實(shí)現(xiàn)調(diào)度機(jī)制，確定如何時(shí)分復(fù)用CPU，處理上下文交換細(xì)節(jié)，完成進(jìn)程/線程和CPU的綁定和放棄的實(shí)際工作。253.低級(jí)調(diào)度的功能和類型1.低級(jí)調(diào)度的主要功能104調(diào)度機(jī)制邏輯功能程序模塊組成隊(duì)列管理程序：管理等待調(diào)度的進(jìn)程/線程（排隊(duì)）。上下文切換程序時(shí)：當(dāng)發(fā)生進(jìn)程/線程切換時(shí)，用來保存舊現(xiàn)場(chǎng)，調(diào)入新現(xiàn)場(chǎng)。分派程序：分派CPU給選中的進(jìn)程/線程。26調(diào)度機(jī)制邏輯功能程序模塊組成隊(duì)列管理程序：管理等待調(diào)度1053.1.低級(jí)調(diào)度的基本類型第一類稱剝奪式：兩種處理器剝奪原則一是高優(yōu)先級(jí)進(jìn)程/線程可剝奪低優(yōu)先級(jí)進(jìn)程/線程，二是當(dāng)運(yùn)行進(jìn)程/線程時(shí)間片用完后被剝奪。第二類稱非剝奪式：一旦某個(gè)進(jìn)程/線程開始運(yùn)行后便不再讓出處理器。比較剝奪式策略的開銷大，但可以避免進(jìn)程/線程長(zhǎng)時(shí)間的獨(dú)占處理器；很多操作系統(tǒng)使用兩種測(cè)略的組合，內(nèi)核關(guān)鍵程序是非剝奪式的，用戶進(jìn)程是剝奪式的。273.1.低級(jí)調(diào)度的基本類型第一類稱剝奪式：1061、先到先服務(wù)調(diào)度（first-come,first-served,FCFS）先請(qǐng)求CPU的進(jìn)程被首先分配到CPU，可用FIFO隊(duì)列來實(shí)現(xiàn)平均周轉(zhuǎn)時(shí)間通常相當(dāng)長(zhǎng)，與作業(yè)的提交和調(diào)度順序有關(guān)非搶占調(diào)度例

進(jìn)程

區(qū)間時(shí)間

P124P23P33P1P2P30242730平均周轉(zhuǎn)時(shí)間(24+27+30)/3=27P2P3P103630平均周轉(zhuǎn)時(shí)間(3+6+30)/3=133.2作業(yè)調(diào)度和低級(jí)調(diào)度算法281、先到先服務(wù)調(diào)度（first-come,first-s1072.

最短作業(yè)優(yōu)先算法SJF算法以進(jìn)入系統(tǒng)的作業(yè)所要求的CPU時(shí)間為標(biāo)準(zhǔn)，總選取估計(jì)計(jì)算時(shí)間最短的作業(yè)投入運(yùn)行。算法易于實(shí)現(xiàn)，效率不高，主要弱點(diǎn)是忽視了作業(yè)等待時(shí)間。會(huì)出現(xiàn)饑餓現(xiàn)象。SJF的平均作業(yè)周轉(zhuǎn)時(shí)間比FCFS要小，故它的調(diào)度性能比FCFS好。實(shí)現(xiàn)SJF調(diào)度算法需要知道作業(yè)所需運(yùn)行時(shí)間，否則調(diào)度就沒有依據(jù)，要精確知道一個(gè)作業(yè)的運(yùn)行時(shí)間是辦不到的。292.

最短作業(yè)優(yōu)先算法SJF算法以進(jìn)入系統(tǒng)的作業(yè)所要求的1083.最短剩余時(shí)間優(yōu)先算法SRTF把SJF算法改為搶占式的。一個(gè)新作業(yè)進(jìn)入就緒狀態(tài)，如果新作業(yè)需要的CPU時(shí)間比當(dāng)前正在執(zhí)行的作業(yè)剩余下來還需的CPU時(shí)間短，SRTF強(qiáng)行趕走當(dāng)前正在執(zhí)行作業(yè)。稱最短剩余時(shí)間優(yōu)先算法此算法不但適用于JOB調(diào)度，同樣也適用于進(jìn)程調(diào)度。303.最短剩余時(shí)間優(yōu)先算法SRTF把SJF算法改為搶占式的109SJF調(diào)度例：進(jìn)程

區(qū)間時(shí)間

P16P28P37P43SRTF調(diào)度例：進(jìn)程

到達(dá)時(shí)間

區(qū)間時(shí)間

P108P214P329P435P4P1P3P2P1P2P4P1P30391624平均周轉(zhuǎn)時(shí)間：

(9+24+16+3)/4均周轉(zhuǎn)時(shí)間：

((17-0)+(5-1)+(26-2)+(10-3))/4=1331SJF調(diào)度例：SRTF調(diào)度例：P4P1P3P2P1P2P1101、設(shè)作業(yè)J1和J2的運(yùn)行時(shí)間t1<=t2，當(dāng)采用短作業(yè)優(yōu)先時(shí)，調(diào)度順序?yàn)镴1、J2，平均周轉(zhuǎn)時(shí)間為(t1+(t1+t2))/2=(2t1+t2)/2。不采用短作業(yè)優(yōu)先時(shí)，調(diào)度順序?yàn)镴2、J1，平均周轉(zhuǎn)時(shí)間為(t2+(t2+t1))/2＝(t1+2t2)/2。顯然，得證。2、假設(shè)當(dāng)n=k時(shí)成立，則當(dāng)n=k+1時(shí)，J1，J2，……

，Jk

，Jk+1，它們的運(yùn)行時(shí)間分別為：t1，t2，……，tk，

tk+1。(ti<=

ti+1)

當(dāng)采用短作業(yè)優(yōu)先時(shí)，調(diào)度順序?yàn)镴1，J2，……

，Jk

，Jk+1，所有作業(yè)的平均周轉(zhuǎn)時(shí)間為：T=[T1+T2+…+Tk+Tk+1]/n=

[t1+(t1+t2)+…+(t1+t2+…+tk)+(t1+t2+…+tk+tk+1)]/n

不采用短作業(yè)優(yōu)先時(shí)，假設(shè)調(diào)度順序?yàn)镴1,J2,…,Jk+1,Jk。

所有作業(yè)的平均周轉(zhuǎn)時(shí)間為：T’=[T1+T2+…+Tk+1+Tk]/n=

[t1+(t1+t2)+…+(t1+t2+…+tk+1)+(t1+t2+…+tk+1+tk)]/n則：T’-T=[(tk+1+tk+1+tk)-(tk+tk+tk+1)]/n=(tk+1-tk)/n>=0。

得證。證明：采用SJF調(diào)度算法可以使平均周轉(zhuǎn)時(shí)間最少。321、設(shè)作業(yè)J1和J2的運(yùn)行時(shí)間t1<=t2，證明：采用S1111.系統(tǒng)有5個(gè)進(jìn)程:A,B,C,D,E。它們的到達(dá)時(shí)間以及估計(jì)運(yùn)行的時(shí)間如下圖所示：請(qǐng)計(jì)算使用下述調(diào)度算法時(shí)，進(jìn)程的周轉(zhuǎn)時(shí)間和進(jìn)程流的平均周轉(zhuǎn)時(shí)間。(1)FCFS(2)SPN(3)HRRN(4)RR(q=1)進(jìn)程到達(dá)時(shí)間(ms)估計(jì)運(yùn)行時(shí)間(ms)A03B26C44D65E82331.系統(tǒng)有5個(gè)進(jìn)程:A,B,C,D,E。它們112(1)FCFS算法：按照先來先服務(wù)原則，調(diào)度順序?yàn)锳,B,C,D,E，詳細(xì)情況如下圖所示因此，A的周轉(zhuǎn)時(shí)間為3ms；B的周轉(zhuǎn)時(shí)間為9-2=7ms；

C的周轉(zhuǎn)時(shí)間為13-4=9ms；

D的周轉(zhuǎn)時(shí)間為18-6=12ms；

E的周轉(zhuǎn)時(shí)間為20-8=12ms；平均周轉(zhuǎn)時(shí)間為（3+7+9+12+12）/5=8.6ms34(1)FCFS算法：按照先來先服務(wù)原則，調(diào)度順序?yàn)锳,B113(2)SPN算法：按照短進(jìn)程原則，調(diào)度順序?yàn)锳,B,E,C,D，詳細(xì)情況如下圖所示因此，A的周轉(zhuǎn)時(shí)間為3ms；B的周轉(zhuǎn)時(shí)間為9-2=7ms；

C的周轉(zhuǎn)時(shí)間為15-4=11ms；

D的周轉(zhuǎn)時(shí)間為20-6=14ms；

E的周轉(zhuǎn)時(shí)間為11-8=3ms；平均周轉(zhuǎn)時(shí)間為（3+7+11+14+3）/5=7.6ms051015201234535(2)SPN算法：按照短進(jìn)程原則，調(diào)度順序?yàn)锳,B,E,114(3)HRRN算法：初始時(shí)刻只有A，因此先調(diào)度A執(zhí)行。A的周轉(zhuǎn)時(shí)間為3ms。A執(zhí)行完，只有B就緒，因此再調(diào)度B執(zhí)行。B的周轉(zhuǎn)時(shí)間為9-2=7ms；B執(zhí)行后，C,D,E均就緒，按照最高響應(yīng)比調(diào)度原則，Rc=(9+4-4)/4=2.25，Rd=(9+5-6)/5=1.6，Re=(9+2-8)/2=1.5因此再調(diào)度C執(zhí)行，C的周轉(zhuǎn)時(shí)間為13-4=9ms；C執(zhí)行后，Rd=(13+5-6)/5=2.4,Re=(13+2-8)/2=3.5,因此調(diào)度E執(zhí)行，E的周轉(zhuǎn)時(shí)間為15-8=7ms；最后調(diào)度D，D的周轉(zhuǎn)時(shí)間為20-6=14ms36(3)HRRN算法：B執(zhí)行后，C,D,E均就緒，按照最高115即，調(diào)度過程如圖所示1234505101520平均周轉(zhuǎn)時(shí)間為（3+7+9+7+14）/5=8ms37即，調(diào)度過程如圖所示1234505101520平均周轉(zhuǎn)時(shí)116(4)RR(q=1)算法：按照時(shí)間片輪轉(zhuǎn)法原則，調(diào)度情況如下圖所示因此，A的周轉(zhuǎn)時(shí)間為4ms；B的周轉(zhuǎn)時(shí)間為18-2=16ms；

C的周轉(zhuǎn)時(shí)間為17-4=13ms；

D的周轉(zhuǎn)時(shí)間為20-6=14ms；

E的周轉(zhuǎn)時(shí)間為15-8=7ms；平均周轉(zhuǎn)時(shí)間為（4+16+13+14+7）/5=10.8ms38(4)RR(q=1)算法：按照時(shí)間片輪轉(zhuǎn)法原則，調(diào)度情117點(diǎn)評(píng)：各種調(diào)度算法下，進(jìn)程的調(diào)度順序及調(diào)度執(zhí)行的詳細(xì)過程需要以圖或文字的形式進(jìn)行說明。僅給出最后的結(jié)果是不完整的。39點(diǎn)評(píng)：118第四部分

死鎖40第四部分119考慮有5個(gè)進(jìn)程共享4類資源，它們的占有量和尚需量如下：進(jìn)程已分配尚需可用P0002300121623P110002000P203300140P310100813P400143000(1)當(dāng)前狀態(tài)安全嗎?(2)如果進(jìn)程2提出資源請(qǐng)求