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

1習題復習課1習題復習課2第一部分

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

Signal(stop)}}

seller(){while(true){關門

Signal(close)

售票

Wait(stop)

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

選書讀書；

Signal（seats）；}}

Wait（mutex）； 填寫登記表；

Signal（mutex）；

Wait（mutex）； 消掉登記；

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

單道：內存中僅有一道作業(yè)在運行批處理：計算機系統(tǒng)對一批作業(yè)自動進行處理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è)說明書)以脫機方式輸入到磁盤上，并在系統(tǒng)中配以監(jiān)督程序(Monitor，OS雛形)將作業(yè)逐個送入內存并運行。2.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)2.2操作系統(tǒng)的發(fā)展過程2.2.2單道批處理系統(tǒng)

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

（1965-1980，半導體、小規(guī)模集成電路時代）1．多道程序設計的基本概念在內存中同時存放多個作業(yè)，使之同時處于運行狀態(tài)(均已開始運行但尚未結束)共享系統(tǒng)資源。單CPU系統(tǒng)中的多道程序運行的特征宏觀上并行：并發(fā)程序都已開始執(zhí)行，但都未結束微觀上串行：并發(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為程序，忽略外設；假定4個程序都需運行2個Δt時間，在期間有6個Δt時間的I/O操作；吞吐率分別為：1/8=0.1252/9=0.2224/11=0.3634道程序情況比單道提高了近3倍。顯然不僅使內存充分利用，還帶來處理機利用率的提高，使整個系統(tǒng)效率得以提高。下一步結束下一步多道程序設計的基本概念tAAΔt等待I/O的時間（6個Δt）（a）單道情況1107（a）單道情形：打印請求打印請求單道與多道程序運行情況（b）多道情形：程序AOSI/O設備繪圖儀請求t1t2t3t4t5t6t7t8CPU打印機繪圖儀程序B打印完成繪圖完成CPU空閑t9t10仍有空閑A/B運行?

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

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

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

進程

區(qū)間時間

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

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

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

區(qū)間時間

P16P28P37P43SRTF調度例：進程

到達時間

區(qū)間時間

P108P214P329P435P4P1P3P2P1P2P4P1P30391624平均周轉時間：

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

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

，Jk

，Jk+1，它們的運行時間分別為：t1，t2，……，tk，

tk+1。(ti<=

ti+1)

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

，Jk

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

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

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

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

C的周轉時間為13-4=9ms；

D的周轉時間為18-6=12ms；

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

C的周轉時間為15-4=11ms；

D的周轉時間為20-6=14ms；

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

C的周轉時間為17-4=13ms；

D的周轉時間為20-6=14ms；

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

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

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

＝2ADDH練習題2.有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁若在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如右所示。已知頁面大小為1024字節(jié)，試將邏輯地址0A5CH，07EFH，3000，5012轉化為相應的物理地址。頁號塊號02132136若在一分頁存儲管理系統(tǒng)中，某作業(yè)的頁表如右所示。已知頁面大小對于邏輯地址0A5CH0A5CH=0000101001011100頁號2，對應物理塊1物理地址為0000011001011100即065CH對于邏輯地址07EFH0A5CH=0000011111101111頁號1，對應物理塊3物理地址為0000111111101111即0FEFH對于邏輯地址3000P＝int(3000/1024)＝2W＝3000mod1024＝952查頁表第2頁在第1塊，所以物理地址為1976。對于邏輯地址5012P＝int(5012/1024)＝4W＝5012mod1024＝916因頁號超過頁表長度，該邏輯地址非法。對于邏輯地址0A5CH習題解答3有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，頁大小為2KB，依次裝入內存的第7、9、10、5塊，試將虛地址7145，3412轉換成內存地址。虛地址3412P＝3412％2048＝1W＝3412mod2048＝1364MR=9*2048+1364=19796虛地址3412的內存地址是：19796虛地址7145P＝7145％2048＝3W＝7145mod2048＝1001MR=5*2048+1001=11241虛地址7145的內存地址是：11241習題解答3有一系統(tǒng)采用頁式存儲管理，有一作業(yè)大小是8KB，六.磁盤的調度算法磁盤是典型的共享設備。在用戶處理的信息量越來越大的情況下，對磁盤等共享設備的訪問也越來越頻繁，因而訪問調度是否得當直接影響到系統(tǒng)的效率。磁盤調度的目標：減少尋道時間有如下五種磁盤調度算法：一、FCFS（FisrtComeFirstSecond）二、SSTF（最短尋道優(yōu)先）三、掃描算法。四、循環(huán)掃描CSCAN五、N—Step—SCAN和FSCAN算法。六.磁盤的調度算法磁盤是典型的共享設備。在用戶處理的信息量圖5-23FCFS調度算法1.先來先服務FCFS(First-Come,FirstServed)僅用于請求磁盤I/O的進程數(shù)目較少的場合。圖5-23FCFS調度算法1.先來先服務FCFS(Fi圖5-24SSTF調度算法2.最短尋道時間優(yōu)先SSTF(ShortestSeekTimeFirst)要求訪問的磁道與當前磁頭距離最近，使每次的尋道時間最短圖5-24SSTF調度算法2.最短尋道時間優(yōu)先SSTSSTF算法雖然能獲得較好的尋道性能，卻可能導致某個進程發(fā)生“饑餓”(Starvation)現(xiàn)象。Scan算法該算法不僅考慮到欲訪問的磁道與當前磁道間的距離，更優(yōu)先考慮磁頭當前的移動方向。其原理是訪問的下一個對象應是同方向的，且又距離最近的。一般自里向外訪問，直至再無更外的磁道需要訪問，才將磁臂換向自外向里，往返反復。這種算法又稱為“電梯算法”3.掃描(SCAN)算法SSTF算法雖然能獲得較好的尋道性能，卻可能導致某個進程發(fā)生SCAN調度算法100道開始，增加方向被訪問下一個磁道移動距離1505016010184249094583255339163811820平均尋道長度：27.8SCAN調度算法100道開始，增加方向被訪問下一個磁道移動距Cscan算法規(guī)定磁頭單項移動，進行循環(huán)掃描。一個方向讀完，不是象SCAN那樣回頭，而是循環(huán)。訪問時間：2TT+SmaxT是從外向里或從里向外單向掃描完要訪問的磁道的尋道時間。而Smax是將磁頭從最外面被訪問的磁道直接移到最里面欲訪問的磁道的尋道時間。4.循環(huán)掃描(CSCAN)算法Cscan算法規(guī)定磁頭單項移動，進行循環(huán)掃描。一個方向讀完，CSCAN調度算法100道開始，增加方向被訪問的下一個磁道移動距離15050160101842418166382039155165839032平均尋道長度：27.5CSCAN調度算法100道開始，增加方向被訪問的下一個磁道移若某磁盤共有200個柱面，其編號為0～199，假設已完成96號柱面的訪問請求，還有若干個請求者在等待服務，它們依次要訪問的柱面號為：175，52，157，36，159、106，l08，72，分別用先來先服務調度算法、最短尋道時間調度算法、電梯調度算法和單向掃描調度算法（向序號增加的方向移動）來確定實際服務的次序，并計算上述兩種算法下移動臂需移動的距離。若某磁盤共有200個柱面，其編號為0～199，假設已完成96(1)先來先服務調度算法：實際服務的次序：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)先調度算法：實際服務的次序：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個柱面的距離。桂林電子科技大學信息科技學院操作系統(tǒng)習題復習課課件(1)電梯調度算法：實際服務的次序：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)單向掃描調度算法：實際服務的次序：96→106→108→157→159→175→36→52→72(106-96)+(108-l06)+(157-108)+(159-l57)+(175-159)+(17