操作系統(tǒng)總匯

1、 第三章 §3.1 調(diào)度的基本概念 (一） 一、調(diào)度的類型和模型 一個(gè)批處理型作業(yè)從進(jìn)入系統(tǒng)并駐留在外存的后備隊(duì)列上開始，直至作業(yè)運(yùn)行完畢，可能要經(jīng)歷三級(jí)調(diào)度過程：1、高級(jí)調(diào)度 又稱為作業(yè)調(diào)度，作用：把外存上處于后備隊(duì)列中的作業(yè)調(diào)入內(nèi)存，并為他們創(chuàng)建進(jìn)程、分配資源、排在就緒隊(duì)列上，準(zhǔn)備執(zhí)行，因此，有時(shí)把它稱為接納調(diào)度。分時(shí)系統(tǒng)、實(shí)時(shí)系統(tǒng)中通常不具備作業(yè)調(diào)度。2、低級(jí)調(diào)度 又稱為進(jìn)程調(diào)度，它決定就緒隊(duì)列中哪個(gè)進(jìn)程將獲得處理機(jī)，然后由分派程序執(zhí)行把處理機(jī)分配給進(jìn)程的操作。在OS中都必須配置。3、中級(jí)調(diào)度 目的：提高內(nèi)存利用率和系統(tǒng)吞吐量。作用：使暫時(shí)不能運(yùn)行的進(jìn)程從內(nèi)存調(diào)至外存，進(jìn)入就緒

2、駐外存狀態(tài)或掛起狀態(tài)。把外存上又具備運(yùn)行條件的就緒進(jìn)程，重新調(diào)入內(nèi)存，并修改為就緒狀態(tài)，掛在就緒隊(duì)列上。又稱對(duì)換。 一.、先來先服務(wù)（FCFS）算法 FCFS（First Come First Server ）法，又稱為先進(jìn)先出（FIFO）算法，就緒進(jìn)程按照進(jìn)入的先后次序排列，調(diào)度程序總是選擇隊(duì)首的進(jìn)程執(zhí)行。 這是一種非剝奪式的調(diào)度算法，簡單、易實(shí)現(xiàn)。 對(duì)短進(jìn)程易出現(xiàn)等待時(shí)間長，服務(wù)質(zhì)量差。 該算法有利于CPU繁忙型的進(jìn)程，不利于I/O繁忙型的進(jìn) 程。 該算法只能用于輔助算法。二、短作業(yè)（進(jìn)程）優(yōu)先（SJ(P)F）算法 短作業(yè)優(yōu)先（SJF）調(diào)度算法:是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最

3、短作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程則是從就緒隊(duì)列中選擇估計(jì)時(shí)間最短的進(jìn)程，把處理機(jī)分配給它。 SJ(P)F調(diào)度算法也存在不容忽視的缺點(diǎn)：（1）對(duì)長作業(yè)不利。如果有一長作業(yè)進(jìn)入系統(tǒng)的后備隊(duì)列，由于總是優(yōu)先調(diào)度那些短作業(yè)（進(jìn)程），將導(dǎo)致長作業(yè)長期不被調(diào)度。（2）完全未考慮作業(yè)的緊迫程度，不能保證緊迫性作業(yè)（進(jìn)程）會(huì)被及時(shí)處理。（3）作業(yè)（進(jìn)程）的長短根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的不一定能真正做到短作業(yè)優(yōu)先調(diào)度。 三、 最高優(yōu)先權(quán)（HPF）優(yōu)先調(diào)度算法1. 優(yōu)先權(quán)調(diào)度算法的類型1） 非搶占式優(yōu)先權(quán)算法把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后便一直執(zhí)行下去直至完成；或發(fā)生某事件使該進(jìn)程放棄處理

4、機(jī)時(shí)，可再將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。用于批處理系統(tǒng)和某些對(duì)實(shí)時(shí)性要求不嚴(yán)的實(shí)時(shí)系統(tǒng)中。2） 搶占式優(yōu)先權(quán)調(diào)度算法把處理機(jī)分配給優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。在執(zhí)行期間，只要又出現(xiàn)優(yōu)先權(quán)更高的進(jìn)程，就重新將處理機(jī)分配給新到的優(yōu)先權(quán)最高的進(jìn)程。能更好地滿足緊迫作業(yè)的要求，常用于要求比較嚴(yán)格的實(shí)時(shí)系統(tǒng)中，以及對(duì)性能要求較高的批處理和分時(shí)系統(tǒng)中。2. 優(yōu)先權(quán)的類型1）靜態(tài)優(yōu)先權(quán) ：在創(chuàng)建進(jìn)程時(shí)確定在進(jìn)程的整個(gè)運(yùn)行期間保持不變。一般地，用某一范圍內(nèi)的一個(gè)整數(shù)來表示的，例如，07或0255中的某一整數(shù)，又把該整數(shù)稱為優(yōu)先數(shù)。 靜態(tài)優(yōu)先權(quán)法優(yōu)缺點(diǎn)：簡單，系統(tǒng)開銷小不精確，僅在要求不高的系統(tǒng)中使用

5、2） 動(dòng)態(tài)優(yōu)先權(quán)高響應(yīng)比優(yōu)先調(diào)度算法 優(yōu)先權(quán)隨進(jìn)程推進(jìn)或隨其等待時(shí)間的增加而改變的，以便獲得更好的調(diào)度性能。 引入動(dòng)態(tài)優(yōu)先權(quán)，并使作業(yè)優(yōu)先級(jí)隨著等待時(shí)間的增加而以速率a提高。該優(yōu)先權(quán)的變化規(guī)律為：優(yōu)先權(quán) =（等待時(shí)間+要求服務(wù)時(shí)間） /要求服務(wù)時(shí)間優(yōu)先權(quán) = RP =響應(yīng)時(shí)間/要求服務(wù)時(shí)間RP ：響應(yīng)比 四、高響應(yīng)比優(yōu)先調(diào)度算法（HRN） HRN（Highest Response ratio Next）算法將短進(jìn)程優(yōu)先與動(dòng)態(tài)優(yōu)先級(jí)相結(jié)合。所謂高響應(yīng)是指進(jìn)程獲得調(diào)度的響應(yīng)，即優(yōu)先數(shù)R。 R =（W+T）/T = 1+W/T T 估計(jì)進(jìn)程執(zhí)行的時(shí)間。 W 進(jìn)程等待的時(shí)間。 由于等待時(shí)間與服務(wù)時(shí)間之

6、和，就是系統(tǒng)對(duì)該作業(yè)的響應(yīng)時(shí)間，故該優(yōu)先權(quán)又相當(dāng)于響應(yīng)比RP。據(jù)此，又可表示為： 隨著進(jìn)程等待時(shí)間的增加，優(yōu)先權(quán)動(dòng)態(tài)增加。 對(duì)等待相同時(shí)間的短進(jìn)程比長進(jìn)程優(yōu)先權(quán)增加得多。 長進(jìn)程隨著等待時(shí)間增加也會(huì)被調(diào)度。 例：有4個(gè)作業(yè)A、B、C、D，它們的到達(dá)時(shí)間分別為8.00，8.50，9.00，9.50，各自要求服務(wù)時(shí)間為2.00，0.50，0.10，0.20，求它們平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間? (1) 如果作業(yè)的等待時(shí)間相同，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，因而該算法有利于短作業(yè)。 (2) 當(dāng)要求服務(wù)的時(shí)間相同時(shí)，作業(yè)的優(yōu)先權(quán)決定于其等待時(shí)間，等待時(shí)間愈長，其優(yōu)先權(quán)愈高，因而它實(shí)現(xiàn)的是先來先

7、服務(wù)。 (3) 對(duì)于長作業(yè)，作業(yè)的優(yōu)先級(jí)可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長時(shí)，其優(yōu)先級(jí)便可升到很高， 從而也可獲得處理機(jī)。優(yōu)點(diǎn)：兼顧長短作業(yè)。缺點(diǎn)：由于做響應(yīng)比計(jì)算故增加了系統(tǒng)開銷 該算法主要用于分時(shí)系統(tǒng)，按照公平服務(wù)的原則，為進(jìn)程分配CPU時(shí)間片。是一種剝奪式的算法。 輪轉(zhuǎn)法的關(guān)鍵是時(shí)間片的選?。?時(shí)間片太大，則輪轉(zhuǎn)法蛻化為FCFS法。 時(shí)間片太小，則增加CPU的額外開銷。 影響時(shí)間片設(shè)置的主要因素： 系統(tǒng)響應(yīng)時(shí)間R、就緒進(jìn)程數(shù)N、計(jì)算機(jī)處理能力等。 時(shí)間片長度： q = R / N max§3.7 死鎖的基本概念（一）死鎖（deadlock） 是OS的一種隨機(jī)故障，是

8、指多個(gè)進(jìn)程在運(yùn)行過程中因爭奪資源而造成的一種僵局，當(dāng)進(jìn)程處于這種僵持狀態(tài)時(shí)，若無外力作用，他們都將無法再向前推進(jìn)。 例如： 系統(tǒng)中共有5臺(tái)打印機(jī)，進(jìn)程A需要4臺(tái)，進(jìn)程B需要4臺(tái)，進(jìn)程A、B并發(fā)執(zhí)行時(shí)進(jìn)程A已經(jīng)占3臺(tái)，進(jìn)程B已經(jīng)占2臺(tái)。則此時(shí)陷入死鎖狀態(tài)。一、死鎖的原因1、爭奪資源引起死鎖2、進(jìn)程推動(dòng)順序不當(dāng)引起的死鎖 二。死鎖的必要條件 由于產(chǎn)生死鎖的根本原因是爭奪共享資源，從而得到產(chǎn)生死鎖的必要條件是： 互斥條件 進(jìn)程互斥使用臨界資源。 不剝奪條件 資源只能由占有它的進(jìn)程釋放，不能 被其它進(jìn)程剝奪。 非剝奪資源 請(qǐng)求和保持條件 進(jìn)程在申請(qǐng)新資源的同時(shí)，保持對(duì)某 些資源的占有。 環(huán)路等待條件

9、存在循環(huán)等待鏈，在鏈中每個(gè)進(jìn)程都 在等待它的前一進(jìn)程所持有的資源。利用銀行家算法避免死鎖 1. 銀行家算法中的數(shù)據(jù)結(jié)構(gòu) (1) 可利用資源向量Available。 (2) 最大需求矩陣Max。 (3) 分配矩陣Allocation。 (4) 需求矩陣Need。 2. 銀行家算法 設(shè)Requesti是進(jìn)程Pi的請(qǐng)求向量，如果Requestij=K，表示進(jìn)程Pi需要K個(gè)Rj類型的資源。當(dāng)Pi發(fā)出資源請(qǐng)求后，系統(tǒng)按下述步驟進(jìn)行檢查： (1) 如果RequestijNeedi,j，便轉(zhuǎn)向步驟2；否則認(rèn)為出錯(cuò)，因?yàn)樗枰馁Y源數(shù)已超過它所宣布的最大值。 (2) 如果RequestijAvailable

10、j，便轉(zhuǎn)向步驟(3)；否則， 表示尚無足夠資源，Pi須等待。 (3) 系統(tǒng)試探著把資源分配給進(jìn)程Pi，并修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值： Availablej=Availablej-Requestij; Allocationi,j=Allocationi,j+Requestij; Needi,j=Needi,j-Requestij; (4) 系統(tǒng)執(zhí)行安全性算法，檢查此次資源分配后，系統(tǒng)是否處于安全狀態(tài)。若安全，才正式將資源分配給進(jìn)程Pi，以完成本次分配；否則，將本次的試探分配作廢，恢復(fù)原來的資源分配狀態(tài)，讓進(jìn)程Pi等待。 3. 安全性算法 (1) 設(shè)置兩個(gè)向量： 工作向量Work: 它表示系統(tǒng)提供給

11、進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，它含有m個(gè)元素，在執(zhí)行安全算法開始時(shí)，Work=Available; Finish: 它表示系統(tǒng)是否有足夠的資源分配給進(jìn)程，使之運(yùn)行完成。開始時(shí)先做Finishi =false; 當(dāng)有足夠資源分配給進(jìn)程時(shí)， 再令Finishi=true。 (2) 從進(jìn)程集合中找到一個(gè)能滿足下述條件的進(jìn)程： Finishi=false; Needi,jWorkj； 若找到，執(zhí)行步驟(3)， 否則，執(zhí)行步驟(4)。 (3) 當(dāng)進(jìn)程Pi獲得資源后，可順利執(zhí)行，直至完成，并釋放出分配給它的資源，故應(yīng)執(zhí)行： Workj=Workj+Allocationi,j; Finishi=true;

12、 go to step 2; (4) 如果所有進(jìn)程的Finishi=true都滿足，則表示系統(tǒng)處于安全狀態(tài)；否則，系統(tǒng)處于不安全狀態(tài)。 實(shí)例 4. 銀行家算法之例 假定系統(tǒng)中有五個(gè)進(jìn)程P0, P1, P2, P3, P4和三類資源A, B, C，各種資源的數(shù)量分別為10、5、7，在T0時(shí)刻的資源分配情況如圖 3-15 所示。 (1) T0時(shí)刻的安全性： (2) P1請(qǐng)求資源：P1發(fā)出請(qǐng)求向量Request1(1，0，2)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request1(1, 0, 2)Need1(1, 2, 2) Request1(1, 0, 2)Available1(3, 3, 2) 系統(tǒng)先假

13、定可為P1分配資源，并修改Available, Allocation1和Need1向量，由此形成的資源變化情況如圖 3-15 中的圓括號(hào)所示。 再利用安全性算法檢查此時(shí)系統(tǒng)是否安全。 圖 3-17 P1申請(qǐng)資源時(shí)的安全性檢查 (3) P4請(qǐng)求資源：P4發(fā)出請(qǐng)求向量Request4(3，3，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request4(3, 3, 0)Need4(4, 3, 1); Request4(3, 3, 0) Available(2, 3, 0)，讓P4等待。 (4) P0請(qǐng)求資源：P0發(fā)出請(qǐng)求向量Requst0(0，2，0)，系統(tǒng)按銀行家算法進(jìn)行檢查： Request0(0, 2

14、, 0)Need0(7, 4, 3); Request0(0, 2, 0)Available(2, 3, 0); 系統(tǒng)暫時(shí)先假定可為P0分配資源，并修改有關(guān)數(shù)據(jù)，如圖 3-18 所示。 圖 3-18 為P0分配資源后的有關(guān)資源數(shù)據(jù) 5銀行家算法是一種 算法。A死鎖解除 B死鎖避免C. 死鎖預(yù)防 D. 死鎖檢測(cè)6.假設(shè)有4個(gè)進(jìn)程各需要2個(gè)同類資源，試問系統(tǒng)最少應(yīng)提供( )個(gè)該類資源，才保證不會(huì)發(fā)生死鎖？A. 3 B. 4 C. 5 D. 67.一作業(yè)8：00到達(dá)系統(tǒng)，估計(jì)運(yùn)行時(shí)間為1小時(shí)，若10：00開始執(zhí)行該作業(yè)，其響應(yīng)比是 。A.2B.1C.3D.0.5答：B C C3.某計(jì)算機(jī)系統(tǒng)中有8臺(tái)

15、打印機(jī)，有K個(gè)進(jìn)程競爭使用，每個(gè)進(jìn)程最多需要3臺(tái)打印機(jī)。該系統(tǒng)可能會(huì)發(fā)生死鎖的K的最小值是 （ ） A2    B.3     C.4     D.5        解：C 不死鎖需要2K+1<8，最多支持3個(gè)進(jìn)程并發(fā)。注意問的如果是“不會(huì)發(fā)生死鎖的最大值”就選B。 4個(gè)以上就死鎖，所以會(huì)死鎖的最小值是4。別看錯(cuò)了。1.假設(shè)系統(tǒng)中有4個(gè)進(jìn)程P1、P2、P3、P4，三類資源

16、R1、R2、R3，數(shù)量分別為9、3、6，在T0時(shí)刻的資源分配情況如表1所示。表1 T0時(shí)刻資源分配表 （1）試問此刻系統(tǒng)是否安全？為什么？（本題4分）（2）當(dāng)P2進(jìn)程發(fā)出請(qǐng)求Request2(1，0，1)，問系統(tǒng)是否將資源分配給它？為什么？ 第四章第三節(jié)    連續(xù)分配方式 為用戶程序分配一個(gè)連續(xù)的內(nèi)存空間，曾被廣泛應(yīng)用，且現(xiàn)在仍被采用。單一連續(xù)分配固定分區(qū)分配動(dòng)態(tài)分區(qū)分配可重定位分區(qū)分配分區(qū)分配算法*FF首次適應(yīng)算法：空閑分區(qū)按起址遞增次序排列，從頭開始直至找到第一個(gè)滿足要求的空閑分區(qū)。 特點(diǎn)：內(nèi)存低端會(huì)留下小的空閑區(qū)，高端有大的空閑區(qū)；每次查找從低址開始，會(huì)增

17、加查找開銷。 *NF循環(huán)首次適應(yīng)算法(下次適應(yīng)) ：從上次分配的空閑區(qū)位置之后開始查找(到最后分區(qū)時(shí)再回到開頭) 特點(diǎn)：減少查詢次數(shù)，內(nèi)存分配均勻；但缺乏大的空閑分區(qū)。*BF最佳適應(yīng)算法：空閑分區(qū)按大小遞增的次序排列，從頭開始找到第一個(gè)滿足要求的空閑分區(qū)。 特點(diǎn)：會(huì)留下大量難以利用的小碎片。WF最差適應(yīng)算法：空閑分區(qū)按大小遞減的次序排列，最前面的最大的空閑分區(qū)就是找到的分區(qū)。 特點(diǎn)：查找速度快，分配后剩下的可用空間比較大；但一段時(shí)間后會(huì)缺乏較大空閑區(qū)。 以上四種算法，統(tǒng)稱為順序搜索法。 這些算法各有利弊，到底哪種最好不能一概而論，而應(yīng)針對(duì)具體作業(yè)序列來分析。對(duì)于某一作業(yè)序列來說，某種算法能將該

18、作業(yè)序列中所有作業(yè)安置完畢，那么我們說該算法對(duì)這一作業(yè)序列是合適的。例：有作業(yè)序列：作業(yè)A要求18K；作業(yè)B要求25K，作業(yè)C要求30K。系統(tǒng)中空閑區(qū)按三種算法組成的空閑區(qū)隊(duì)列：經(jīng)分析可知：最佳適應(yīng)法對(duì)這個(gè)作業(yè)序列是合適的，而其它兩種對(duì)該作業(yè)序列是不合適的。4、可重定位分區(qū)分配動(dòng)態(tài)重定位的引入（）隨著系統(tǒng)接收的作業(yè)的增加，內(nèi)存中連續(xù)的大塊分區(qū)不復(fù)存在，產(chǎn)生了大量的“碎片”。新的作業(yè)無法裝入到每個(gè)“碎片”小分區(qū)上運(yùn)行，但所有碎片的空間總和可能大于需求。通過“拼接”或“緊湊” 來實(shí)現(xiàn)程序的浮動(dòng)（動(dòng)態(tài)重定位）。碎片定義：碎片：內(nèi)存中不能被利用的小分區(qū)稱為“零頭”或“碎片”。 離散分配方式基本思想：將

19、一個(gè)進(jìn)程分散的裝入不相鄰的分區(qū)中。離散分配的基本單位是頁，則稱為分頁存儲(chǔ)管理方式；如果離散分配的基本單位是段，則稱為分段存儲(chǔ)管理方式?？毂硪朐騝pu存取一個(gè)數(shù)據(jù)時(shí)要兩次訪問內(nèi)存第一次是訪問頁表，找到指定頁的物理塊號(hào)，再將塊號(hào)與頁內(nèi)偏移量w拼接形成物理地址。第二次訪問內(nèi)存是從所得地址中獲得所需數(shù)據(jù)（或向此地址中寫入數(shù)據(jù)）cpu的工作效率大約減少一半例：檢索聯(lián)想寄存器的時(shí)間為20ns，訪問內(nèi)存的時(shí)間為100ns。如果能在聯(lián)想存儲(chǔ)器中檢索出頁號(hào)，則cpu存取數(shù)據(jù)共需要 ，如果不能在聯(lián)想存儲(chǔ)器中找到該頁號(hào)，則總共需要 。再假定訪問聯(lián)想存儲(chǔ)器的命中率分別為0%，50%，80%，90%，98%，計(jì)算有

20、效訪問時(shí)間。有效訪問時(shí)間：T命中率：hT=h*t1+（1-h）*t22、基本原理在分段存儲(chǔ)管理方式中，作業(yè)的地址空間被劃分為若干個(gè)段，每個(gè)段定義一組邏輯信息。每個(gè)段都從0開始編址，采用一段連續(xù)的地址空間。段的長度由相應(yīng)的邏輯信息組的長度決定，因而段長不等整個(gè)作業(yè)的地址空間分成多個(gè)段，是二維的。4、分段與分頁的主要區(qū)別（重點(diǎn)）頁是信息的物理單位，分頁是為了滿足系統(tǒng)管理的需要；段是信息的邏輯單位，分段是為了滿足用戶的需要；頁的大小固定且由系統(tǒng)決定，段的長度不固定，決定于用戶所編寫的程序，通常由編譯程序在對(duì)源程序進(jìn)行編譯時(shí)，根據(jù)信息的性質(zhì)來劃分。分頁系統(tǒng)中的邏輯地址空間是一維的，程序員只需利用一個(gè)記

21、憶符，即可表示一個(gè)地址；分段系統(tǒng)中的是二維的，程序員在標(biāo)識(shí)一個(gè)地址時(shí)，既需給出段名，又需給出段內(nèi)地址。局部性原理幾個(gè)論點(diǎn)程序多數(shù)情況是順序執(zhí)行的過程調(diào)用會(huì)使程序的執(zhí)行由一部分區(qū)域轉(zhuǎn)至另一部分區(qū)域，但過程調(diào)用的深度大多不超過5。程序?qū)?huì)在一段時(shí)間內(nèi)都局限在這些過程的范圍內(nèi)運(yùn)行。循環(huán)結(jié)構(gòu)雖只由少數(shù)指令構(gòu)成，但是他們將多次執(zhí)行程序包括許多對(duì)數(shù)據(jù)結(jié)構(gòu)的處理。局部性表現(xiàn)時(shí)間局限性。某指令一旦執(zhí)行，則不久后該指令可能再次執(zhí)行；某數(shù)據(jù)被訪問過，則不久后該數(shù)據(jù)可能再次被訪問。空間局限性。程序在一段時(shí)間內(nèi)訪問的地址，可能集中在一定的范圍之內(nèi)，其典型的情況便是程序的順序執(zhí)行。虛擬存儲(chǔ)器定義：虛擬存儲(chǔ)器是指具有請(qǐng)求

22、調(diào)入功能和置換功能，能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。其邏輯容量由內(nèi)存和外存之和所決定，其運(yùn)行速度接近于內(nèi)存速度，而每位的成本卻又接近于外存。3、虛擬存儲(chǔ)器的特征離散性 最基本在內(nèi)存分配時(shí)采用離散分配方式；多次性一個(gè)作業(yè)被分成多次調(diào)入內(nèi)存運(yùn)行；對(duì)換性允許在作業(yè)的運(yùn)行過程中進(jìn)行換進(jìn)、換出；虛擬性 最重要能從邏輯上擴(kuò)充內(nèi)存容量，使用戶“看到”的內(nèi)存容量遠(yuǎn)大于實(shí)際大小。（總?cè)萘坎怀^物理內(nèi)存和外存交換區(qū)容量之和）該特征是以上兩個(gè)特征為基礎(chǔ)的。第八節(jié)  頁面置換算法*最佳置換算法（OPT）*先進(jìn)先出（FIFO）*最近最久未使用置換算法（LRU） 最少使用置換算法（LFU

23、） 由Belady于1966年提出的一種理論上的算法，所淘汰的頁面，將是永不使用的或是在最長時(shí)間內(nèi)不被訪問的頁面（向?qū)砜矗?例如，假定系統(tǒng)為某進(jìn)程分配3個(gè)物理塊，并考慮有以下頁面引用串，需要注意的是：在某進(jìn)程中，(有些頁面經(jīng)常被訪問，如全局變量，常用函數(shù)，某些例程等)引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 1、最佳置換算法（OPT）引用串：7，0，1，2，0，3，0，4，2，3，0，3，2，1，2，0，1，7，0，1 采用最佳置換算法，共發(fā)生9次缺頁，缺頁率9/20=45%。特點(diǎn)：理論上，性能最佳；實(shí)際上，無法實(shí)現(xiàn)；通常用該算法來評(píng)價(jià)其他算法

24、的優(yōu)劣。2、先進(jìn)先出（FIFO）基本思想： FIFO置換算法的思想是：當(dāng)發(fā)生頁面置換時(shí)，總是選擇在內(nèi)存駐留時(shí)間最久的頁面予以淘汰。對(duì)于上例，利用FIFO置換算法時(shí)，當(dāng)訪問2號(hào)頁面時(shí)，由于7號(hào)頁面駐留時(shí)間最長，故將7號(hào)頁面置換出去，同理，對(duì)其它頁面置換情況參照如下表所示。 從表上可以看出，采用FIFO置換算法，共發(fā)生15次缺頁，缺頁率為15/20=75%， 特點(diǎn)：實(shí)現(xiàn)簡單與進(jìn)程實(shí)際的運(yùn)行不相適應(yīng)先進(jìn)先出算法雖然簡單，但從數(shù)據(jù)分析可以看出該算法效果不夠理想，由于程序執(zhí)行具有局部性原理，所以該算法不能保證經(jīng)常被訪問的頁面不被淘汰。同時(shí)，在FIFO置換算法中，隨著分配給進(jìn)程的物理塊增多，反而缺頁率增大

25、了，這種現(xiàn)象稱為Belady異常。只有FIFO置換算法有這種奇怪現(xiàn)象，其它算法沒有。下面來看一個(gè)例子，設(shè)某進(jìn)程的頁面引用串如下：1，2，3，4，1，2，5，1，2，3，4，5當(dāng)該進(jìn)程分得3、4物理塊時(shí)，其缺頁次數(shù)分別是9，10。(具體分析)3、最近最久未使用置換算法（LRU）基本思想： 根據(jù)頁面調(diào)入內(nèi)存后的使用情況進(jìn)行決策。 由于無法預(yù)測(cè)各頁面將來的使用情況，只能利用“最近的過去”作為“最近將來”的近似，選擇最近最久未使用的頁面予以淘汰。特點(diǎn)：性能較好實(shí)現(xiàn)復(fù)雜，需要硬件支持（每頁配置一個(gè)寄存器、棧），增加系統(tǒng)負(fù)擔(dān)。從上可以看出，采用LRU算法時(shí)，系統(tǒng)缺頁12次，缺頁率為12/20=60%算法實(shí)

26、現(xiàn)： 該算法賦予每個(gè)頁面一個(gè)訪問字段，用來記錄一個(gè)頁面自上次被訪問以來所經(jīng)歷的時(shí)間T,當(dāng)須淘汰一個(gè)頁面時(shí)，選擇現(xiàn)有頁面中其T值最大的，即最近最久未使用的頁面予以淘汰。4、最少使用置換算法（LFU）(不講)選擇在最近時(shí)期使用最少的頁面淘汰。（頻率）為每個(gè)頁面配一個(gè)計(jì)數(shù)器。需為在內(nèi)存中的每個(gè)頁面設(shè)置一個(gè)移位寄存器，用來記錄該頁面被訪問的頻率。每次訪問某頁時(shí)，便將該移位寄存器的最高位置1，此后每隔一定時(shí)間自動(dòng)右移一位。最近一段時(shí)間最少使用的頁面是Ri 最小的頁。 第五章6.1.4 I/O通道1、雖然設(shè)備控制器已能大大減少CPU對(duì)I/O的干預(yù)，但當(dāng)主機(jī)所配置的外設(shè)很多時(shí)，CPU的負(fù)擔(dān)仍然很重。為此，在

27、CPU和設(shè)備控制器之間增設(shè)通道以建立獨(dú)立的I/O操作。不僅數(shù)據(jù)的傳送能夠獨(dú)立于CPU，也使得對(duì)I/O操作的組織、管理和結(jié)束處理盡量獨(dú)立。2、通道是一種特殊的處理機(jī)，具有執(zhí)行I/O指令的能力。通過執(zhí)行通道程序來控制I/O操作。 3、通道與一般的處理機(jī)又有所不同：其指令類型單一，即由于通道硬件比較簡單，其所能執(zhí)行的指令主要局限于與I/O操作有關(guān)的指令。主要為與I/O有關(guān)的指令；通道沒有自己的內(nèi)存，與CPU共享內(nèi)存。I/O性能經(jīng)常成為系統(tǒng)的瓶頸（1）CPU性能不等于系統(tǒng)性能響應(yīng)時(shí)間也是一個(gè)重要因素（2）CPU性能越高，與I/O差距越大彌補(bǔ)：更多的進(jìn)程（3）進(jìn)程切換多，系統(tǒng)開銷大通道價(jià)格昂貴，使機(jī)器中

28、的通道數(shù)量勢(shì)必較少，這往往使它成了I/O的瓶頸。解決“瓶頸”問題的最有效的方法，便是增加設(shè)備到主機(jī)間的通路而不增加通道。多通路:解決“瓶頸”問題的方法（交叉連接）在不增加通道的情況下，增加設(shè)備到主機(jī)間的通路：（把一個(gè)設(shè)備連接到多個(gè)控制器上，一個(gè)控制器又連接到多個(gè)通道上）5.3.1 緩沖的引入 （p209）（1）緩和CPU與I/O設(shè)備間速度不匹配的矛盾。 (2) 減少對(duì)CPU的中斷頻率， 放寬對(duì)CPU中斷響應(yīng)時(shí)間的限制。 (3) 提高CPU和I/O設(shè)備之間的并行性。 5.3.3 I/O緩沖的組織形式單緩沖區(qū)(Single Buffer)雙緩沖區(qū)(Double Buffer)循環(huán)緩沖區(qū)(Circu

29、lar Buffer)緩沖池（Buffer pool)5.6.1 磁盤訪問時(shí)間 1) 尋道時(shí)間Ts 這是指把磁臂(磁頭)移動(dòng)到指定磁道上所經(jīng)歷的時(shí)間。該時(shí)間是啟動(dòng)磁臂的時(shí)間s與磁頭移動(dòng)n條磁道所花費(fèi)的時(shí)間之和， 即Ts=m×n+s其中，m是一常數(shù)，與磁盤驅(qū)動(dòng)器的速度有關(guān)，對(duì)一般磁盤， m=0.2；對(duì)高速磁盤，m0.1,磁臂的啟動(dòng)時(shí)間約為2 ms。 這樣，對(duì)一般的溫盤， 其尋道時(shí)間將隨尋道距離的增加而增大， 大體上是530 ms。 2) 旋轉(zhuǎn)延遲時(shí)間T 這是指定扇區(qū)移動(dòng)到磁頭下面所經(jīng)歷的時(shí)間。對(duì)于硬盤，典型的旋轉(zhuǎn)速度大多為5400 r/min，每轉(zhuǎn)需時(shí)11.1 ms，平均旋轉(zhuǎn)延遲時(shí)間T為5.55 ms；對(duì)于軟盤，其旋轉(zhuǎn)速度為300 r/min或600 r/min，這樣，平均T為50100 ms。 3) 傳輸時(shí)間Tt 這是指把數(shù)據(jù)從磁盤讀出或向磁盤寫入數(shù)據(jù)所經(jīng)歷的時(shí)間。5.6.2 磁盤調(diào)度先來先服務(wù)算法（FCFS）最短尋道時(shí)間優(yōu)先（SSTF）掃描算法（SCAN）循環(huán)掃描算法（CSCAN）1. 先來先服務(wù)FCFS(First-Come, First