操作系統總匯

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、） 由Belady于1966年提出的一種理論上的算法，所淘汰的頁面，將是永不使用的或是在最長時間內不被訪問的頁面（向將來看）。 例如，假定系統為某進程分配3個物理塊，并考慮有以下頁面引用串，需要注意的是：在某進程中，(有些頁面經常被訪問，如全局變量，常用函數，某些例程等)引用串：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%。特點：理論上，性能最佳；實際上，無法實現；通常用該算法來評價其他算法

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

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

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

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

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

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