1、第三章：處理機(jī)調(diào)度與死鎖3.1：高級(jí)調(diào)度對(duì)象是作業(yè)，作用是將作業(yè)從外存調(diào)入內(nèi)存； 低級(jí)調(diào)度的對(duì)象是進(jìn)程，作用是決定哪個(gè)進(jìn)程將獲得處理機(jī)而運(yùn)行。常見的低級(jí)調(diào)度有非搶占方式和搶占方式兩種搶占式調(diào)度主要有以下原則優(yōu)先權(quán)原則:重要作業(yè)賦予高優(yōu)先權(quán),優(yōu)先占用處理機(jī)短作業(yè)(進(jìn)程)優(yōu)先原則:執(zhí)行時(shí)間短的進(jìn)程優(yōu)先執(zhí)行時(shí)間片原則:時(shí)間片用完后停止執(zhí)行,適用于分時(shí)系統(tǒng) 中級(jí)調(diào)度；運(yùn)行頻率:低級(jí)調(diào)度>中級(jí)調(diào)度>高級(jí)調(diào)度3.2調(diào)度隊(duì)列模型與調(diào)度準(zhǔn)則1.調(diào)度隊(duì)列模型(最基本的一種)：每個(gè)進(jìn)程在執(zhí)行時(shí),可能有以下三種情況 進(jìn)程在給定時(shí)間片內(nèi)已完成,釋放處理機(jī)后為完成狀態(tài) 進(jìn)程在時(shí)間片內(nèi)未完成,進(jìn)入就緒隊(duì)列末尾

2、 進(jìn)程在執(zhí)行期間因某事件而阻塞,進(jìn)入阻塞隊(duì)列2.選擇調(diào)度方式和調(diào)度算法的若干準(zhǔn)則：面向用戶的準(zhǔn)則：(1) 周轉(zhuǎn)時(shí)間短；(2)響應(yīng)時(shí)間快；(3)截止時(shí)間保證；(4)優(yōu)先權(quán)準(zhǔn)則面向系統(tǒng)的準(zhǔn)則：(1)系統(tǒng)吞吐量高；(2)處理機(jī)利用率高；(3)各類資源的平衡利用3.3調(diào)度算法周轉(zhuǎn)時(shí)間=結(jié)束執(zhí)行時(shí)間-進(jìn)入磁盤時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間=周轉(zhuǎn)時(shí)間/服務(wù)時(shí)間高響應(yīng)比=(等待時(shí)間+服務(wù)時(shí)間)/服務(wù)時(shí)間 或=等待時(shí)間/服務(wù)時(shí)間1. 先來先服務(wù)和短作業(yè)優(yōu)先算法先來先服務(wù)調(diào)度算法(FCFS) 有利于長作業(yè)（CPU繁忙型）,而不利于短作業(yè)(IO繁忙型)短作業(yè)優(yōu)先算法（JFS）不利于長作業(yè)*特別注意這兩種算法在內(nèi)存總量有限情況下

3、的應(yīng)用，且在不移動(dòng)的可變分區(qū)方式下的內(nèi)存具體實(shí)例見ppt2. 高優(yōu)先權(quán)優(yōu)先調(diào)度算法(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)的是先來先服務(wù)。 所以說該算法是FCFS與JFS的結(jié)合3. 基于時(shí)間片的輪轉(zhuǎn)調(diào)度算法（按照老師方法做題）書本P96圖3-63.4實(shí)時(shí)調(diào)度實(shí)現(xiàn)實(shí)時(shí)調(diào)度的基本條件：1.提供必要的信息就緒時(shí)間（開始截止時(shí)間和完成截止時(shí)間；處理時(shí)間；資源要求；優(yōu)先級(jí)）2. 系統(tǒng)處理能力強(qiáng)假定系統(tǒng)中有m個(gè)周期性的硬實(shí)時(shí)任務(wù),它們的處理時(shí)間可表示為Ci,周

4、期時(shí)間表示為Pi,則在單處理機(jī)情況下,必須滿足下面的限制條件,系統(tǒng)才是可調(diào)度的。若采用多處理機(jī)（N個(gè)），則滿足即可。3. 采用搶占式調(diào)度機(jī)制 4.具有快速切換機(jī)制實(shí)時(shí)調(diào)度算法分類：（1）按實(shí)時(shí)任務(wù)性質(zhì)分：硬實(shí)時(shí)調(diào)度算法，軟實(shí)時(shí)調(diào)度算法。（2）按調(diào)度方式分：非搶占式調(diào)度算法，搶占式調(diào)度算法。（3）按調(diào)度時(shí)間分：靜態(tài)調(diào)度算法，動(dòng)態(tài)調(diào)度算法。（4）在多處理機(jī)下，還分為集中式調(diào)度和分布式調(diào)度。常用的幾種實(shí)時(shí)調(diào)度算法：1.最早截止時(shí)間優(yōu)先EDF算法2.最低松弛度優(yōu)先即LLF算法3.5產(chǎn)生死鎖的原因和必要條件產(chǎn)生死鎖的原因：（1）競爭資源（可剝奪性資源，如內(nèi)存處理機(jī)；非可剝奪性資源，如打印機(jī)，磁帶機(jī)；臨時(shí)

5、性資源：由一個(gè)進(jìn)程產(chǎn)生,被另一進(jìn)程使用后就再也無用的資源）（2）進(jìn)程推進(jìn)順序不當(dāng)引起死鎖 產(chǎn)生死鎖的必要條件：1.互斥條件（對(duì)資源的排他性使用）2.請(qǐng)求和保持條件（在已經(jīng)擁有了至少一個(gè)資源后又申請(qǐng)其他被占用的資源）3.不剝奪條件（進(jìn)程已獲得的資源在未使用完之前不能被剝奪。）4.環(huán)路等待條件（發(fā)生死鎖時(shí),必然存在一個(gè)進(jìn)程-資源的環(huán)形鏈） 只要一個(gè)不滿足，則就能破壞死鎖。處理死鎖的基本方法：(1)預(yù)防死鎖(2)避免死鎖(3)檢測死鎖(4)解除死鎖3.6預(yù)防死鎖的方法因?yàn)楫a(chǎn)生死鎖的四個(gè)條件中的1.互斥條件無法被改變，所以就只能從其他四個(gè)入手。分為：1.摒棄請(qǐng)求和保持條件；2.摒棄不剝奪條件；3.摒棄

6、環(huán)路等待條件利用銀行家算法避免死鎖（例題見ppt后題）3.7 死鎖的檢測與解除死鎖的檢測可以在資源分配圖中采用死鎖定理，詳見書本P112-113死鎖的解除有兩種方法：（1）剝奪資源(從其他進(jìn)程剝奪資源給死鎖進(jìn)程)（2）撤銷進(jìn)程第四章存儲(chǔ)器管理4.1程序的裝入與鏈接源程序要運(yùn)行通常經(jīng)過編譯，鏈接，裝入等幾個(gè)步驟程序的裝入可分為：1.絕對(duì)裝入方式2.可重定位裝入方式3.動(dòng)態(tài)運(yùn)行時(shí)裝入方式程序的鏈接分為：1.靜態(tài)鏈接方式2. 裝入時(shí)動(dòng)態(tài)鏈接(邊裝入邊鏈接)3. 運(yùn)行時(shí)動(dòng)態(tài)鏈接(對(duì)某些模塊的鏈接推遲到執(zhí)行時(shí)才去做)4.2連續(xù)分配方式連續(xù)分配方式為一個(gè)用戶程序分配一個(gè)連續(xù)的內(nèi)存空間1. 單一連續(xù)分配：只

7、能用于單用戶、單任務(wù)的操作。這種方式把系統(tǒng)中的內(nèi)存分為系統(tǒng)區(qū)和用戶區(qū)兩部分,系統(tǒng)區(qū)僅提供給OS使用。2. 固定分區(qū)分配：最簡單的可運(yùn)行多道程序的存儲(chǔ)管理方式。將內(nèi)存用戶空間劃分為若干個(gè)固定大小的區(qū)域,每個(gè)分區(qū)中只裝入一道作業(yè)。3. 動(dòng)態(tài)分區(qū)分配：根據(jù)進(jìn)程的實(shí)際需要,動(dòng)態(tài)地為之分配內(nèi)存空間。分區(qū)分配算法: (1)首次適應(yīng)算法FF（要求空閑分區(qū)鏈以地址遞增的次序鏈接。在分配內(nèi)存時(shí)，從鏈?zhǔn)组_始順序查找，知道找到一個(gè)大小符合的空閑分區(qū)）(2)循環(huán)首次適應(yīng)算法（從上次找到的空閑分區(qū)的下一空閑分區(qū)開始查找，知道找到合適的）(3)最佳適應(yīng)算法（要求將所有空閑分區(qū)按其容量從小到大的順序形成空閑分區(qū)鏈。每次分配

8、時(shí)，總把既能滿足要求又是最小的分配出去。）(4)最差(壞)適應(yīng)算法（與（3）相反，從大到小，找最大的分出去）(5)快速適應(yīng)算法(分類搜索法)回收內(nèi)存的四種情況P1254.伙伴系統(tǒng)：不斷地平分較大的空閑內(nèi)存塊來獲得較小的空閑內(nèi)存塊，直到獲得所需的內(nèi)存塊；當(dāng)內(nèi)存釋放時(shí)，盡可能的合并空閑內(nèi)存塊。（分配與合并都采用以2的冪次方為單位）5. 可重定位分區(qū)分配：把內(nèi)存中的所有作業(yè)移動(dòng)，使他們相鄰接，即可把分散的空閑小分區(qū)拼為大分區(qū)。6. 對(duì)換：指把內(nèi)存中暫時(shí)不能運(yùn)行的進(jìn)程或者暫時(shí)不用的程序和數(shù)據(jù),調(diào)出到外存上，把已具備運(yùn)行條件的進(jìn)程或進(jìn)程所需要的程序和數(shù)據(jù),調(diào)入內(nèi)存。在具有對(duì)換功能的OS中，把外存分為文件

9、區(qū)和對(duì)換區(qū)，前者用于存放文件，后者用于存放從內(nèi)存換出的進(jìn)程。如果允許一個(gè)進(jìn)程直接分散地裝入到許多不相鄰接的分區(qū)中,稱為離散分配方式。離散分配方式有分頁存儲(chǔ)管理方式（離散分配的基本單位是頁）、分段存儲(chǔ)管理方式（離散分配的基本單位是段）和段頁存儲(chǔ)管理方式4.3基本分頁存儲(chǔ)管理方式頁面與頁表將用戶作業(yè)的地址空間分成若干個(gè)大小相同的區(qū)域,稱為頁面或頁,并為每個(gè)頁從“0”開始編號(hào)；相應(yīng)的，主存空間也分成與頁大小相同的若干個(gè)存儲(chǔ)塊,或稱為物理塊。在為進(jìn)程分配內(nèi)存時(shí)，以塊為單位將進(jìn)程中的若干個(gè)頁分別裝入多個(gè)可以不相鄰接的物理塊中。為每個(gè)進(jìn)程建立一張頁面映像表,簡稱頁表,頁表大多駐留在內(nèi)存中，是實(shí)現(xiàn)從頁號(hào)到物

10、理塊號(hào)的地址映射。（訪問兩次內(nèi)存）程序的邏輯地址包括頁號(hào)和頁內(nèi)地址(頁內(nèi)位移量)。若給定一個(gè)邏輯地址空間中的地址為A,頁面的大小為L,則頁號(hào)P和頁內(nèi)地址d可按下式求得: 例:系統(tǒng)頁面大小為1KB,邏輯地址為2170B,求頁號(hào)與頁內(nèi)地址。解答：頁號(hào) P=INT2170/1024=2；頁內(nèi)地址d=2170 mod 1024 =122B第0頁 01023第1頁 10242047第2頁 20483071地址變換機(jī)構(gòu)：用于實(shí)現(xiàn)從邏輯地址到物理地址的轉(zhuǎn)換以頁號(hào)查頁表,得到對(duì)應(yīng)頁裝入內(nèi)存的塊號(hào)。內(nèi)存地址物理塊號(hào)×頁大小頁內(nèi)地址例題1: 有一系統(tǒng)采用分頁存儲(chǔ)管理,有一作業(yè)大小是8KB,頁大小為2KB

11、,依次裝入內(nèi)存的第7、9、A、5,試將邏輯地址0AFEH字節(jié)轉(zhuǎn)換成內(nèi)存地址。答:邏輯地址0AFEH字節(jié)0000 1010 1111 1110 (頁面大小為2KB，即2的11方，從末尾往前數(shù)11位即為頁內(nèi)地址，剩余為頁號(hào))P1； W010 1111 1110字節(jié)頁號(hào)1對(duì)應(yīng)的塊號(hào)為9，2進(jìn)制為1001，加上頁內(nèi)地址即為0100 1010 1111 1110（前面補(bǔ)0）內(nèi)存地址0100 1010 1111 11104AFEH字節(jié)例題2：有一系統(tǒng)采用分頁存儲(chǔ)管理,有一作業(yè)大小是8KB,頁大小為2KB,依次裝入內(nèi)存的第7、9、10、5塊,試將邏輯地址7145字節(jié)轉(zhuǎn)換成內(nèi)存地址。答：邏輯地址 7145字節(jié)

12、 ，頁大小為2KB=2048BPINT7145/20483；W7145 mod 20481001字節(jié)所以內(nèi)存地址=5*2048+1001=11241字節(jié)，即邏輯地址7145字節(jié)的內(nèi)存地址是:11241字節(jié)。4.4 基本分段存儲(chǔ)管理方式在分段式存儲(chǔ)管理中，為每個(gè)分段分配一個(gè)連續(xù)的分區(qū)，而各段可以離散的移入內(nèi)存的不同分區(qū)中。供用戶使用的邏輯地址為段號(hào)(段名)+段內(nèi)地址。在裝入作業(yè)時(shí),用一張段表記錄每個(gè)分段在主存中的起始地址和長度，實(shí)現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。（訪問兩次內(nèi)存）分頁存儲(chǔ)管理的主要目的是為了提高內(nèi)存利用率,分段存儲(chǔ)管理的主要目的是為了滿足用戶在編程和使用上的要求。分頁和分段的主要區(qū)別

13、：頁是信息的物理單位，為了系統(tǒng)管理而存在；1.段是信息的邏輯單位，是為了滿足用戶而存在。2.頁的大小固定且由系統(tǒng)決定，而段的長度卻不固定,決定于用戶所編寫的程序。3. 分頁的作業(yè)地址空間是一維的，而分段的作業(yè)地址空間則是二維的。段頁式存儲(chǔ)管理方式：段頁式管理中,邏輯地址由段號(hào)、段內(nèi)頁號(hào)及頁內(nèi)地址三部分所組成（訪問三次內(nèi)存）4.5虛擬存儲(chǔ)器的基本概念程序在運(yùn)行之前，沒必要全部裝入內(nèi)存，僅需將要用的調(diào)入，其余部分留在盤上。在程序運(yùn)行時(shí)，若所需要的頁（段）尚未調(diào)入，則請(qǐng)求調(diào)入，若內(nèi)存已滿，則將暫時(shí)不用的置換出去虛擬存儲(chǔ)器是指具有請(qǐng)求調(diào)入功能和置換功能,能從邏輯上對(duì)內(nèi)存容量加以擴(kuò)充的一種存儲(chǔ)器系統(tǒng)。虛

14、擬存儲(chǔ)器的實(shí)現(xiàn)主要通過請(qǐng)求分頁系統(tǒng)和請(qǐng)求分段系統(tǒng)兩種方式。虛擬存儲(chǔ)器的特征主要為：離散性、多次性（將一個(gè)作業(yè)分多次調(diào)入）、對(duì)換性、虛擬性.4.6請(qǐng)求分頁存儲(chǔ)管理方式缺頁中斷：在請(qǐng)求分頁系統(tǒng)中，每當(dāng)所要訪問的頁面不在內(nèi)存中時(shí)，便產(chǎn)生一缺頁中斷，請(qǐng)求OS將所缺之頁調(diào)入內(nèi)存。4.7頁面置換算法1.FIFO頁面置換算法；2.LRU頁面置換算法（可以通過棧來實(shí)現(xiàn)，具體見書本P152）；3.Clock置換算法第五章設(shè)備管理5.1 I/O系統(tǒng)（1）I/O設(shè)備的類型：按傳輸速率分類：低速設(shè)備，中速設(shè)備，高速設(shè)備。 按信息交換的單位分類：塊設(shè)備（基本特征是其傳輸速率較高，可尋址，屬于有結(jié)構(gòu)設(shè)備，磁盤就屬于塊設(shè)備

15、）；字符設(shè)備（基本特征是其傳輸速率較低，不可尋址，通常采用中斷驅(qū)動(dòng)方式，屬于無結(jié)構(gòu)設(shè)備，例:交互式終端、打印機(jī)）按設(shè)備的共享屬性分類：獨(dú)占設(shè)備（不可尋址），共享設(shè)備（可尋址且可以隨機(jī)訪問），虛擬設(shè)備（2）設(shè)備并不是直接與CPU通信，而是通過設(shè)備控制器（位于CPU和設(shè)備之間，接收CPU發(fā)來的命令,控制一個(gè)或多個(gè)I/O設(shè)備,以實(shí)現(xiàn)I/O設(shè)備和計(jì)算機(jī)之間的數(shù)據(jù)交換）。設(shè)備與設(shè)備控制器之間的接口有：數(shù)據(jù)信號(hào)線：用于在設(shè)備和設(shè)備控制器之間傳送數(shù)據(jù)信號(hào)控制信號(hào)線：作為由設(shè)備控制器向I/O設(shè)備發(fā)送控制信號(hào)時(shí)的通路狀態(tài)信號(hào)線：用于傳送指示設(shè)備當(dāng)前狀態(tài)的信號(hào)設(shè)備控制器的組成：設(shè)備控制器與處理機(jī)的接口；設(shè)備控制器

16、與設(shè)備的接口；I/O邏輯。（3）I/O通道是一種特殊處理機(jī)，只具有執(zhí)行I/O指令的能力。位于CPU和設(shè)備控制器之間，即實(shí)現(xiàn)內(nèi)存與外設(shè)之間的傳輸。沒有自己的內(nèi)存，與CPU共享內(nèi)存。通道類型：(1) 字節(jié)多路通道連接中低速設(shè)備；（2）數(shù)組選擇通道高速傳輸數(shù)據(jù)，每次只有一臺(tái)設(shè)備進(jìn)行數(shù)據(jù)傳送,形成獨(dú)占；(3)數(shù)組多路通道結(jié)合了（1）（2）的優(yōu)點(diǎn)。解決瓶頸問題的方法是增加通路。5.2 I/O控制方式內(nèi)存與外設(shè)的控制方式主要有四種:程序I/O方式（有“忙等待” 現(xiàn)象）、中斷驅(qū)動(dòng)I/O方式（以字節(jié)為單位，CPU與I/O設(shè)備并行操作）、直接存儲(chǔ)訪問DMA I/O控制方式（在DMA控制器的作用下，數(shù)據(jù)傳輸?shù)幕?/p>

17、單位為塊，如磁盤）和I/O通道控制方式。DMA控制器的組成：主機(jī)與DMA控制器的接口，DMA控制器與塊設(shè)備的接口，I/O控制邏輯。（為了實(shí)現(xiàn)在主機(jī)與DMA控制器之間成塊數(shù)據(jù)的直接交換, 必須在DMA控制器中設(shè)置如下四類寄存器:命令/狀態(tài)寄存器CR，內(nèi)存地址寄存器MAR，數(shù)據(jù)寄存器DR，數(shù)據(jù)計(jì)數(shù)器DC）。5.3 緩沖管理引入緩沖區(qū)目的：(1)緩和CPU與I/O設(shè)備間速度不匹配的矛盾。 (2)減少對(duì)CPU的中斷頻率,放寬對(duì)CPU中斷響應(yīng)時(shí)間的限制。 (3)提高CPU和I/O設(shè)備之間的并行性。 根據(jù)系統(tǒng)設(shè)置緩沖區(qū)的個(gè)數(shù),將緩沖技術(shù)分為:單緩沖、雙緩沖、循環(huán)緩沖、緩沖池。當(dāng)輸入與輸出速度基本匹配時(shí),雙

18、緩沖能獲得較好效果;當(dāng)速度相差較大時(shí),可引入多個(gè)緩沖,組織成循環(huán)緩沖（多個(gè)緩沖區(qū)）的形式。循環(huán)緩沖：用于裝輸入數(shù)據(jù)的空緩沖區(qū)R，已裝滿數(shù)據(jù)的滿緩沖區(qū)G，計(jì)算進(jìn)程正在使用的現(xiàn)行工作緩沖區(qū)C。多個(gè)指針：指示計(jì)算進(jìn)程下一可用緩沖區(qū)Nextg，指示輸入進(jìn)程下一可用空緩沖區(qū)Nexti，指示計(jì)算進(jìn)程正在使用的緩沖區(qū)Current(1)Nexti指針追趕上Nextg指針輸入進(jìn)程速度大于計(jì)算進(jìn)程,全部空緩沖區(qū)已滿,無可用緩沖區(qū),輸入進(jìn)程阻塞(2)Nextg指針追趕上Nexti指針計(jì)算進(jìn)程速度大于輸入進(jìn)程,全部緩沖區(qū)空,無可用數(shù)據(jù),計(jì)算進(jìn)程阻塞。緩沖池：因?yàn)橐陨系膶Ｓ镁彌_的利用率不高,因此設(shè)置公用緩沖池。5.4

19、設(shè)備分配SPOOLing系統(tǒng)的組成：輸入井和輸出井：在磁盤上的兩個(gè)存儲(chǔ)空間。輸入井模擬脫機(jī)輸入,暫存輸入數(shù)據(jù)；輸出井模擬脫機(jī)輸出,暫存輸出數(shù)據(jù)。輸入緩沖區(qū)和輸出緩沖區(qū)：在內(nèi)存中。用來緩和CPU與磁盤之間的速度的矛盾輸入進(jìn)程SPi和輸出進(jìn)程SPo：模擬脫機(jī)I/O時(shí)的外圍控制機(jī)。SPi模擬脫機(jī)輸入時(shí)的外圍控制機(jī)；SPo模擬脫機(jī)輸出時(shí)的外圍控制機(jī)。5.5 磁盤存儲(chǔ)器管理磁盤調(diào)度先來先服務(wù)FCFS；最短尋道時(shí)間優(yōu)先SSTF（有“饑餓”現(xiàn)象）；掃描(SCAN)算法（可防止進(jìn)程出現(xiàn)“饑餓”現(xiàn)象，又稱為 “電梯調(diào)度算法”）；循環(huán)掃描(CSCAN)算法；N-Step-SCAN（將磁盤請(qǐng)求隊(duì)列分成若干個(gè)長度為N的子隊(duì)列,磁盤調(diào)度將按FCFS算法依次處理這些子隊(duì)列。而每處理一個(gè)隊(duì)列時(shí)又是按SCAN算法。當(dāng)N很大時(shí)，趨于SCAN算法，N=1時(shí)，蛻化為FCFS算法） 磁盤高速緩存：利用內(nèi)存中的存儲(chǔ)空間,來暫存從磁盤中讀出的一系列盤塊中的信息。是一組在邏輯上屬于磁盤,而物理上是駐留在內(nèi)存中的盤塊。提高磁盤I/O速度的其它方法：提前讀，延遲寫，優(yōu)化物理塊分布，虛擬盤。六文件管理6.1文件和文件系統(tǒng)文件可分為有結(jié)構(gòu)文件(記錄式文件)和無結(jié)構(gòu)文件（流式文件），有結(jié)構(gòu)文件中，文件由若干