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

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

同步和互斥問題2第一部分31.有三個進(jìn)程，進(jìn)程get從輸入設(shè)備上不斷讀數(shù)據(jù)，并存入buffer1;進(jìn)程cut不斷將buffer1的內(nèi)容剪切到緩沖區(qū)buffer2，進(jìn)程put則不斷將buffer2的內(nèi)容在打印機(jī)上輸出。三個進(jìn)程并發(fā)執(zhí)行，協(xié)調(diào)工作。寫出該三個進(jìn)程并發(fā)執(zhí)行的同步模型。getcutputbuffer1buffer231.有三個進(jìn)程，進(jìn)程get從輸入設(shè)備上不斷讀數(shù)據(jù)，并存入b4buffer1buffer2getcutputempty1empty2full1full2分析存在如下同步關(guān)系：(1)只有buffer1為空，get才能工作，并使buffer1為滿。(2)要求buffer1為滿，同時buffer2為空，cut才能工作，工作結(jié)果使buffer1為空，buffer2為滿。(3)只有buffer2為滿，put才能工作，并使buffer2為空。4buffer1buffer2getcutputempty15解答：（1）設(shè)置信號量設(shè)信號量empty1表示緩沖區(qū)buffer1為空,初值為1設(shè)信號量full1表示緩沖區(qū)buffer1為滿,初值為0設(shè)信號量empty2表示緩沖區(qū)buffer2為空,初值為1設(shè)信號量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){啟動車輛正常駕駛到站停車}售票員進(jìn)程：while(true){關(guān)門售票開門}分析存在如下同步關(guān)系：(1)售票員關(guān)門后，司機(jī)才能開車。(2)司機(jī)到站停車后，售票員才能開門。設(shè)信號量close表示關(guān)門開車,初值為0；設(shè)信號量stop表示到站開門,初值為082.用PV操作解決司機(jī)和售票員的問題。司機(jī)進(jìn)程：售票員進(jìn)程9semaphoreclose=0,open=0;driver(){while(true){Wait(close)啟動車輛;正常行駛;到站停車;

Signal(stop)}}

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

Signal(close)

售票

Wait(stop)

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

選書讀書；

Signal（seats）；}}

Wait（mutex）； 填寫登記表；

Signal（mutex）；

Wait（mutex）； 消掉登記；

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

單道：內(nèi)存中僅有一道作業(yè)在運(yùn)行批處理：計算機(jī)系統(tǒng)對一批作業(yè)自動進(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è)逐個送入內(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．特征：單道性、順序性、自動性優(yōu)點(diǎn)：減少CPU空閑時間，提高資源利用率和系統(tǒng)吞吐量。缺點(diǎn)：人機(jī)交互性差，CPU和I/O設(shè)備忙閑不均(取決于作業(yè)的特性)。解決辦法：多道程序設(shè)計技術(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ī)模集成電路時代）1．多道程序設(shè)計的基本概念在內(nèi)存中同時存放多個作業(yè)，使之同時處于運(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的時間（6個Δ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個程序都需運(yùn)行2個Δt時間，在期間有6個Δt時間的I/O操作；吞吐率分別為：1/8=0.1252/9=0.2224/11=0.3634道程序情況比單道提高了近3倍。顯然不僅使內(nèi)存充分利用，還帶來處理機(jī)利用率的提高，使整個系統(tǒng)效率得以提高。下一步結(jié)束下一步多道程序設(shè)計的基本概念tAAΔt等待I/O的時間（6個Δt）（a）單道情況1107（a）單道情形：打印請求打印請求單道與多道程序運(yùn)行情況（b）多道情形：程序AOSI/O設(shè)備繪圖儀請求t1t2t3t4t5t6t7t8CPU打印機(jī)繪圖儀程序B打印完成繪圖完成CPU空閑t9t10仍有空閑A/B運(yùn)行?

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

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

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

進(jìn)程

區(qū)間時間

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

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

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

區(qū)間時間

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

到達(dá)時間

區(qū)間時間

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

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

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

，Jk

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

tk+1。(ti<=

ti+1)

當(dāng)采用短作業(yè)優(yōu)先時，調(diào)度順序為J1，J2，……

，Jk

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

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

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

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

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

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

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

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

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

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

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

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

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

死鎖40第四部分41考慮有5個進(jìn)程共享4類資源，它們的占有量和尚需量如下：進(jìn)程已分配尚需可用P0002300121623P110002000P203300140P310100813P400143000(1)當(dāng)前狀態(tài)安全嗎?(2)如果進(jìn)程2提出資源請求(0,1,2,0),按照銀行家算法，能否滿足要求？41考慮有5個進(jìn)程共享4類資源，它們的占有量和尚需量如下：進(jìn)42(1)利用安全性算法對上述狀態(tài)進(jìn)行分析，如下表所示，WorkABCDNeedABCDAllocationABCDFinishP0P2P3P1P4162316461976298639860012014008132000300000230330101010000014truetruetruetruetrue因為存在安全序列P0、P2、P3、P1、P4，所以系統(tǒng)是安全的。42(1)利用安全性算法對上述狀態(tài)進(jìn)行分析，如下表所示，Wo43(2)P2發(fā)出請求(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)程的請求，故系統(tǒng)進(jìn)入不安全狀態(tài)。因此，P2提出的上述請求不能滿足，系統(tǒng)不能分配資源給它。43(2)P2發(fā)出請求(0,1,2,0)后，系統(tǒng)按銀行家算法44第五部分

虛擬內(nèi)存44第五部分邏輯地址轉(zhuǎn)化物理地址過程邏輯地址以十六進(jìn)制數(shù)給出根據(jù)頁大小劃分邏輯地址為頁號和頁內(nèi)地址以頁號查頁表，得到對應(yīng)內(nèi)存塊號物理地址＝頁號拼接位移量邏輯地址以十進(jìn)制數(shù)給出頁號＝虛地址/頁大小位移量＝虛地址mod頁大小以頁號查頁表，得到對應(yīng)內(nèi)存塊號物理地址＝塊號×頁大?。灰屏窟壿嫷刂忿D(zhuǎn)化物理地址過程邏輯地址以十六進(jìn)制數(shù)給出例1某虛擬存儲器的用戶編程空間共32個頁面，每頁為1KB，內(nèi)存為16KB。假定某時刻一用戶頁表中已調(diào)入內(nèi)存的頁面對應(yīng)的物理塊號如下表：頁號物理塊號051102437則邏輯地址0A5C（H）所對應(yīng)的物理地址為：_____例1某虛擬存儲器的用戶編程空間共32個頁面，每頁為1KB，內(nèi)例10A5CH＝0000,1010,0101,1100B頁號為2，對應(yīng)塊號為4，物理地址：0001，0010,0101,1100即：125CH頁號物理塊號051102437例10A5CH＝0000,1010,0101,1100B頁例2設(shè)頁面大小為1K字節(jié)，作業(yè)的0、1、2頁分別存放在第2、3、8塊中。求邏輯地址2500對應(yīng)的物理地址？則邏輯地址2500的頁號為2（2500/1024=2）頁內(nèi)地址為452（2500%1024＝452）。查頁表可知第2頁對應(yīng)的物理塊號為8。將塊號8與頁內(nèi)地址452拼接（8×1024＋452＝8644）得到物理地址為8644。例2設(shè)頁面大小為1K字節(jié)，作業(yè)的0、1、2頁分別存放在第2、【例3】某請求頁式存儲管理，允許用戶編程空間為32個頁面，每頁1KB，主存為16KB。如有一用戶程序有10頁長，且某時刻該用戶頁面映射如下如果分別有對以下三個虛地址:0AC5H,1AC5H,3AC5H處的操作，試計算并說明存儲管理系統(tǒng)將如何處理：【例3】某請求頁式存儲管理，允許用戶編程空間為32個頁面，每【分析】本題考察虛地址與實際物理地址的轉(zhuǎn)化問題，首先有用戶空間地址確定虛頁號要用多少個二進(jìn)制位來表示，又已知頁面大小就可以推算出還需要的二進(jìn)制位數(shù)，兩者相加可知虛地址的長度。從主存大小確定物理地址的二進(jìn)制位數(shù)。由虛地址的虛頁號位數(shù)查表確定是那一物理塊，換算成二進(jìn)制數(shù)，在連接后面的偏移值就是實際的物理地址?！痉治觥勘绢}考察虛地址與實際物理地址的轉(zhuǎn)化問題，首先有用戶空【解答】頁面大小為1KB，在虛地址中有10個二進(jìn)制位，用戶地址空間有32頁，虛頁號占5位，因此虛地址長度為15位。又主存為16KB，所以物理地址14位。0AC5H的二進(jìn)制：000101011000101,其中需頁號為00010,即2，由表知是4號物理塊，即0100，所以相應(yīng)物理地址12C5H1AC5H的二進(jìn)制：001101011000101，虛頁號00110，即6，由表知沒有第6頁，將發(fā)生缺頁中斷，系統(tǒng)從外存中把第6頁調(diào)入內(nèi)存，然后更新頁表。3AC5H的二進(jìn)制：011101011000101，虛頁號為01110，即14，由于14>10,超過作業(yè)的地址空間長度，系統(tǒng)發(fā)生地址越界中斷，程序運(yùn)行終止?！窘獯稹宽撁娲笮?KB，在虛地址中有10個二進(jìn)制位，用戶地練習(xí)題1.一分頁存儲管理系統(tǒng)中邏輯地址長度為16位，頁面大小為1KB字節(jié)，現(xiàn)有一邏輯地址為0A6FH，且第0、1、2、3、頁依次存放在物理塊3、7、11、10中。邏輯地址0A6FH對應(yīng)的物理地址是多少？邏輯地址0A6FH的二進(jìn)制表示如下：頁號頁內(nèi)地址0000，1010，0110，1111由此可知邏輯地址0A6FH的頁號為2，該頁存放在第11號物理塊中，用十六進(jìn)制表示塊號為B，所以物理地址為：0010，1110，0110，1111，即2E6FH。練習(xí)題1.一分頁存儲管理系統(tǒng)中邏輯地址長度為16位，頁面大小練習(xí)題2.有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為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è)大小是8KB，頁若在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如右所示。已知頁面大小為1024字節(jié)，試將邏輯地址0A5CH，07EFH，3000，5012轉(zhuǎn)化為相應(yīng)的物理地址。頁號塊號02132136若在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如右所示。已知頁面大小對于邏輯地址0A5CH0A5CH=0000101001011100頁號2，對應(yīng)物理塊1物理地址為0000011001011100即065CH對于邏輯地址07EFH0A5CH=0000011111101111頁號1，對應(yīng)物理塊3物理地址為0000111111101111即0FEFH對于邏輯地址3000P＝int(3000/1024)＝2W＝3000mod1024＝952查頁表第2頁在第1塊，所以物理地址為1976。對于邏輯地址5012P＝int(5012/1024)＝4W＝5012mod1024＝916因頁號超過頁表長度，該邏輯地址非法。對于邏輯地址0A5CH習(xí)題解答3有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為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è)大小是8KB，六.磁盤的調(diào)度算法磁盤是典型的共享設(shè)備。在用戶處理的信息量越來越大的情況下，對磁盤等共享設(shè)備的訪問也越來越頻繁，因而訪問調(diào)度是否得當(dāng)直接影響到系統(tǒng)的效率。磁盤調(diào)度的目標(biāo)：減少尋道時間有如下五種磁盤調(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)僅用于請求磁盤I/O的進(jìn)程數(shù)目較少的場合。圖5-23FCFS調(diào)度算法1.先來先服務(wù)FCFS(Fi圖5-24SSTF調(diào)度算法2.最短尋道時間優(yōu)先SSTF(ShortestSeekTimeFirst)要求訪問的磁道與當(dāng)前磁頭距離最近，使每次的尋道時間最短圖5-24SSTF調(diào)度算法2.最短尋道時間優(yōu)先SSTSSTF算法雖然能獲得較好的尋道性能，卻可能導(dǎo)致某個進(jìn)程發(fā)生“饑餓”(Starvation)現(xiàn)象。Scan算法該算法不僅考慮到欲訪問的磁道與當(dāng)前磁道間的距離，更優(yōu)先考慮磁頭當(dāng)前的移動方向。其原理是訪問的下一個對象應(yīng)是同方向的，且又距離最近的。一般自里向外訪問，直至再無更外的磁道需要訪問，才將磁臂換向自外向里，往返反復(fù)。這種算法又稱為“電梯算法”3.掃描(SCAN)算法SSTF算法雖然能獲得較好的尋道性能，卻可能導(dǎo)致某個進(jìn)程發(fā)生SCAN調(diào)度算法100道開始，增加方向被訪問下一個磁道移動距離1505016010184249094583255339163811820平均尋道長度：27.8SCAN調(diào)度算法100道開始，增加方向被訪問下一個磁道移動距Cscan算法規(guī)定磁頭單項移動，進(jìn)行循環(huán)掃描。一個方向讀完，不是象SCAN那樣回頭，而是循環(huán)。訪問時間：2TT+SmaxT是從外向里或從里向外單向掃描完要訪問的磁道的尋道時間。而Smax是將磁頭從最外面被訪問的磁道直接移到最里面欲訪問的磁道的尋道時間。4.循環(huán)掃描(CSCAN)算法Cscan算法規(guī)定磁頭單項移動，進(jìn)行循環(huán)掃描。一個方向讀完，CSCAN調(diào)度算法100道開始，增加方向被訪問的下一個磁道移動距離15050160101842418166382039155165839032平均尋道長度：27.5CSCAN調(diào)度算法100道開始，增加方向被訪問的下一個磁道移若某磁盤共有200個柱面，其編號為0～199，假設(shè)已完成96號柱面的訪問請求，還有若干個請求者在等待服務(wù)，它們依次要訪問的柱面號為：175，52，157，36，159、106，l08，72，分別用先來先服務(wù)調(diào)度算法、最短尋道時間調(diào)度算法、電梯調(diào)度算法和單向掃描調(diào)度算法（向序號增加的方向移動）來確定實際服務(wù)的次序，并計算上述兩種算法下移動臂需移動的距離。若某磁盤共有200個柱面，其編號為0～199，假設(shè)已完成96(1)先來先服務(wù)調(diào)度算法：實際服務(wù)的次序：96→175→52→157→36→159→106→108→72移動臂需移動的距離為：(175-96)+(175-52)+(157-52)+(157-36)+(159-36)+(159-106)+(108-106)+(108-72)=642移動臂需移動642柱面的距離。(2)最短尋找時間優(yōu)先調(diào)度算法：實際服務(wù)的次序：96→106→108→72→52→36→157→159→175移動臂需移動的距離為：(106-96)+(108-l06)+(108-72)+(72-52)+(52-36)+(157-36)+(159-l57)+(175-159)=223移動臂需移動223個柱面的距離。桂林電子科技大學(xué)信息科技學(xué)院操作系統(tǒng)習(xí)題復(fù)習(xí)課課件(1)電梯調(diào)度算法：實際服務(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移動臂需移動218個柱面的距離。(2)單向掃描調(diào)度算法：實際服務(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除了移動臂由里向外返回所用的時間外，還需移動254個柱面的距離。(1)電梯調(diào)度算法：七、最佳置換算法和先進(jìn)先出算法1、FIFO淘汰最先進(jìn)入內(nèi)存的頁面，即選擇在內(nèi)存中駐留時間最久的頁面予以淘汰。出發(fā)點(diǎn)：最早調(diào)入主存中的頁面不再使用的可能性越大，應(yīng)該最先淘汰。算法簡單對具有按線性順序訪問的程序比較合適，而對其它情況效率不高七、最佳置換算法和先進(jìn)先出算法1、FIFO最佳置換算法和先進(jìn)先出算法進(jìn)程P執(zhí)行時的頁面走向為：1,2,3,4,1,2,5,1,2,3,4,5；如果在內(nèi)存中分配3個頁面，則缺頁情況如下：12次訪問中有缺頁9次；最佳置換算法和先進(jìn)先出算法進(jìn)程P執(zhí)行時的頁面走向為：1,2如果在內(nèi)存中分配4個頁面，則缺頁情況如下：12次訪問中有缺頁10次；Belady現(xiàn)象的原因：FIFO算法的置換特征與進(jìn)程訪問內(nèi)存的動態(tài)特征是矛盾的，即被置換的頁面并不是進(jìn)程不會訪問的。如果在內(nèi)存中分配4個頁面，則缺頁情況如下：12次訪問中有缺頁習(xí)題1．某進(jìn)程執(zhí)行時的頁面走向為123412512345，分別畫出其分配物理塊為3的最佳置換算法的置換圖。2．某進(jìn)程執(zhí)行時的頁面走向為123412512345，分別畫出其分配物理塊為3和4的FIFO算法的置換圖。3．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如下頁面：342143143145，采用LRU置換算法求出訪問過程中發(fā)生的缺頁中斷的次數(shù)及缺頁率。設(shè)分給作業(yè)的存儲塊數(shù)為3.習(xí)題1．某進(jìn)程執(zhí)行時的頁面走向為12341254．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如下頁面：232152453252，設(shè)分給作業(yè)的存儲塊數(shù)為3。若用最佳置換算法，先進(jìn)先出，LRU置換算法求出訪問過程中發(fā)生的缺頁次數(shù)及缺頁率。4．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如下頁面：23習(xí)題1．某進(jìn)程執(zhí)行時的頁面走向為123412512345，分別畫出其分配物理塊為3的最佳置換算法的置換圖。習(xí)題1．某進(jìn)程執(zhí)行時的頁面走向為1234125習(xí)題2．某進(jìn)程執(zhí)行時的頁面走向為123412512345，分別畫出其分配物理塊為3和4的FIFO算法的置換圖。習(xí)題2．某進(jìn)程執(zhí)行時的頁面走向為1234125習(xí)題3．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如下頁面：342143143145，采用LRU置換算法求出訪問過程中發(fā)生的缺頁中斷的次數(shù)及缺頁率。設(shè)分給作業(yè)的存儲塊數(shù)為3.習(xí)題3．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如下頁面：34．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如下頁面：232152453252，設(shè)分給作業(yè)的存儲塊數(shù)為3。若用最佳置換算法，先進(jìn)先出，LRU置換算法求出訪問過程中發(fā)生的缺頁次數(shù)及缺頁率。4．在請求分頁管理系統(tǒng)中，一個作業(yè)要依次訪問如下頁面：23桂林電子科技大學(xué)信息科技學(xué)院操作系統(tǒng)習(xí)題復(fù)習(xí)課課件請求分頁存儲管理方式中，假定系統(tǒng)為某進(jìn)程分配了4個頁框，頁面的引用順序為：6、1、2、0、3、0、4、2、3、0、3、2、6、0，采用FIFO置換算法產(chǎn)生多少次頁面置換？缺頁率是多少？(2)頁面置換次數(shù)為3次(3)缺頁率為：7/14=50%請求分頁存儲管理方式中，假定系統(tǒng)為某進(jìn)程分配了4個頁框，頁面請求分頁存儲管理方式中，假設(shè)分配給某進(jìn)程的頁框數(shù)為3，若程序的頁面引用順序為：0、2、3、4、1、2、5、0、2、3、2、5，采用最佳置換算法產(chǎn)生多少次頁面置換？缺頁率是多少？(2)頁面置換次數(shù)為4次(3)缺頁率為：7/12=58%請求分頁存儲管理方式中，假設(shè)分配給某進(jìn)程的頁框數(shù)為3，若程序79習(xí)題復(fù)習(xí)課1習(xí)題復(fù)習(xí)課80第一部分

同步和互斥問題2第一部分811.有三個進(jìn)程，進(jìn)程get從輸入設(shè)備上不斷讀數(shù)據(jù)，并存入buffer1;進(jìn)程cut不斷將buffer1的內(nèi)容剪切到緩沖區(qū)buffer2，進(jìn)程put則不斷將buffer2的內(nèi)容在打印機(jī)上輸出。三個進(jìn)程并發(fā)執(zhí)行，協(xié)調(diào)工作。寫出該三個進(jìn)程并發(fā)執(zhí)行的同步模型。getcutputbuffer1buffer231.有三個進(jìn)程，進(jìn)程get從輸入設(shè)備上不斷讀數(shù)據(jù)，并存入b82buffer1buffer2getcutputempty1empty2full1full2分析存在如下同步關(guān)系：(1)只有buffer1為空，get才能工作，并使buffer1為滿。(2)要求buffer1為滿，同時buffer2為空，cut才能工作，工作結(jié)果使buffer1為空，buffer2為滿。(3)只有buffer2為滿，put才能工作，并使buffer2為空。4buffer1buffer2getcutputempty183解答：（1）設(shè)置信號量設(shè)信號量empty1表示緩沖區(qū)buffer1為空,初值為1設(shè)信號量full1表示緩沖區(qū)buffer1為滿,初值為0設(shè)信號量empty2表示緩沖區(qū)buffer2為空,初值為1設(shè)信號量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){啟動車輛正常駕駛到站停車}售票員進(jìn)程：while(true){關(guān)門售票開門}分析存在如下同步關(guān)系：(1)售票員關(guān)門后，司機(jī)才能開車。(2)司機(jī)到站停車后，售票員才能開門。設(shè)信號量close表示關(guān)門開車,初值為0；設(shè)信號量stop表示到站開門,初值為082.用PV操作解決司機(jī)和售票員的問題。司機(jī)進(jìn)程：售票員進(jìn)程87semaphoreclose=0,open=0;driver(){while(true){Wait(close)啟動車輛;正常行駛;到站停車;

Signal(stop)}}

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

Signal(close)

售票

Wait(stop)

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

選書讀書；

Signal（seats）；}}

Wait（mutex）； 填寫登記表；

Signal（mutex）；

Wait（mutex）； 消掉登記；

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

單道：內(nèi)存中僅有一道作業(yè)在運(yùn)行批處理：計算機(jī)系統(tǒng)對一批作業(yè)自動進(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è)逐個送入內(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．特征：單道性、順序性、自動性優(yōu)點(diǎn)：減少CPU空閑時間，提高資源利用率和系統(tǒng)吞吐量。缺點(diǎn)：人機(jī)交互性差，CPU和I/O設(shè)備忙閑不均(取決于作業(yè)的特性)。解決辦法：多道程序設(shè)計技術(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ī)模集成電路時代）1．多道程序設(shè)計的基本概念在內(nèi)存中同時存放多個作業(yè)，使之同時處于運(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的時間（6個Δ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個程序都需運(yùn)行2個Δt時間，在期間有6個Δt時間的I/O操作；吞吐率分別為：1/8=0.1252/9=0.2224/11=0.3634道程序情況比單道提高了近3倍。顯然不僅使內(nèi)存充分利用，還帶來處理機(jī)利用率的提高，使整個系統(tǒng)效率得以提高。下一步結(jié)束下一步多道程序設(shè)計的基本概念tAAΔt等待I/O的時間（6個Δt）（a）單道情況1107（a）單道情形：打印請求打印請求單道與多道程序運(yùn)行情況（b）多道情形：程序AOSI/O設(shè)備繪圖儀請求t1t2t3t4t5t6t7t8CPU打印機(jī)繪圖儀程序B打印完成繪圖完成CPU空閑t9t10仍有空閑A/B運(yùn)行?

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

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

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

進(jìn)程

區(qū)間時間

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

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

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

區(qū)間時間

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

到達(dá)時間

區(qū)間時間

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

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

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

，Jk

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

tk+1。(ti<=

ti+1)

當(dāng)采用短作業(yè)優(yōu)先時，調(diào)度順序為J1，J2，……

，Jk

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

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

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

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

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

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

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

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

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

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

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

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

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

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