操作系統(tǒng)期末復習(共8頁)

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

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

3、總量有限情況下的應用，且在不移動的可變分區(qū)方式下的內(nèi)存具體實例見ppt高優(yōu)先權優(yōu)先調(diào)度算法(1)如果(rgu)作業(yè)的等待時間相同,則要求(yoqi)服務的時間愈短,其優(yōu)先權愈高,因而(yn r)該算法有利于短作業(yè)。(2)當要求服務的時間相同時,作業(yè)的優(yōu)先權決定于其等待時間,等待時間愈長,其優(yōu)先權愈高,因而它實現(xiàn)的是先來先服務。 所以說該算法是FCFS與JFS的結合3. 基于時間片的輪轉調(diào)度算法（按照老師方法做題）書本P96圖3-63.4實時調(diào)度實現(xiàn)實時調(diào)度的基本條件：1.提供必要的信息就緒時間（開始截止時間和完成截止時間；處理時間；資源要求；優(yōu)先級）2. 系統(tǒng)處理能力強假定系統(tǒng)中有m個周期性的

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

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

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

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

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

9、備運行條件的進程或進程所需要的程序和數(shù)據(jù),調(diào)入內(nèi)存。在具有對換功能的OS中，把外存分為文件區(qū)和對換區(qū)，前者用于存放文件，后者用于存放從內(nèi)存換出的進程。如果允許一個進程直接分散地裝入到許多不相鄰接的分區(qū)中,稱為離散分配方式。離散分配方式有分頁存儲管理方式（離散分配的基本單位是頁）、分段存儲管理方式（離散分配的基本單位是段）和段頁存儲管理方式4.3基本分頁存儲管理方式頁面與頁表將用戶作業(yè)的地址空間分成若干個大小相同的區(qū)域,稱為頁面或頁,并為每個頁從“0”開始編號；相應的，主存空間也分成與頁大小相同的若干個存儲塊,或稱為物理塊。在為進程分配內(nèi)存時，以塊為單位將進程中的若干個頁分別裝入多個可以不相鄰接

10、的物理塊中。為每個進程建立一張頁面映像表,簡稱頁表,頁表大多駐留在內(nèi)存中，是實現(xiàn)從頁號到物理塊號的地址映射。（訪問兩次內(nèi)存）程序的邏輯地址包括頁號和頁內(nèi)地址(頁內(nèi)位移量)。若給定一個邏輯地址空間中的地址為A,頁面的大小為L,則頁號P和頁內(nèi)地址d可按下式求得: 例:系統(tǒng)頁面大小為1KB,邏輯地址為2170B,求頁號與頁內(nèi)地址。解答：頁號 P=INT2170/1024=2；頁內(nèi)地址d=2170 mod 1024 =122B第0頁 01023第1頁 10242047第2頁 20483071地址變換機構：用于實現(xiàn)從邏輯地址到物理地址的轉換以頁號查頁表,得到對應頁裝入內(nèi)存的塊號。內(nèi)存地址物理塊號頁大小頁

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

12、2KB,依次裝入內(nèi)存的第7、9、10、5塊,試將邏輯地址7145字節(jié)轉換成內(nèi)存地址。答：邏輯地址 7145字節(jié) ，頁大小為2KB=2048BPINT7145/20483；W7145 mod 20481001字節(jié)所以內(nèi)存地址=5*2048+1001=11241字節(jié)，即邏輯地址7145字節(jié)的內(nèi)存地址是:11241字節(jié)。4.4 基本分段存儲管理方式在分段式存儲管理中，為每個分段分配一個連續(xù)的分區(qū)，而各段可以離散的移入內(nèi)存的不同分區(qū)中。供用戶使用的邏輯地址為段號(段名)+段內(nèi)地址。在裝入作業(yè)時,用一張段表記錄每個分段在主存中的起始地址和長度，實現(xiàn)從邏輯段到物理內(nèi)存區(qū)的映射。（訪問兩次內(nèi)存）分頁存儲管理

13、的主要目的是為了提高內(nèi)存利用率,分段存儲管理的主要目的是為了滿足用戶在編程和使用上的要求。分頁和分段的主要區(qū)別：頁是信息的物理單位，為了系統(tǒng)管理而存在；1.段是信息的邏輯單位，是為了滿足用戶而存在。2.頁的大小固定且由系統(tǒng)決定，而段的長度卻不固定,決定于用戶所編寫的程序。3. 分頁的作業(yè)地址空間是一維的，而分段的作業(yè)地址空間則是二維的。段頁式存儲管理方式：段頁式管理中,邏輯地址由段號、段內(nèi)頁號及頁內(nèi)地址三部分所組成（訪問三次內(nèi)存）4.5虛擬存儲器的基本概念程序在運行之前，沒必要全部裝入內(nèi)存，僅需將要用的調(diào)入，其余部分留在盤上。在程序運行時，若所需要的頁（段）尚未調(diào)入，則請求調(diào)入，若內(nèi)存已滿，則

14、將暫時不用的置換出去虛擬存儲器是指具有請求調(diào)入功能和置換功能,能從邏輯上對內(nèi)存容量加以擴充的一種存儲器系統(tǒng)。虛擬存儲器的實現(xiàn)主要通過請求分頁系統(tǒng)和請求分段系統(tǒng)兩種方式。虛擬存儲器的特征主要為：離散性、多次性（將一個作業(yè)分多次調(diào)入）、對換性、虛擬性.4.6請求分頁存儲管理方式缺頁中斷：在請求分頁系統(tǒng)中，每當所要訪問的頁面不在內(nèi)存中時，便產(chǎn)生一缺頁中斷，請求OS將所缺之頁調(diào)入內(nèi)存。4.7頁面置換算法1.FIFO頁面置換算法；2.LRU頁面置換算法（可以通過棧來實現(xiàn)，具體見書本P152）；3.Clock置換算法第五章設備管理5.1 I/O系統(tǒng)(xtng)（1）I/O設備(shbi)的類型：按傳輸速率

15、分類(fn li)：低速設備，中速設備，高速設備。 按信息交換的單位分類：塊設備（基本特征是其傳輸速率較高，可尋址，屬于有結構設備，磁盤就屬于塊設備）；字符設備（基本特征是其傳輸速率較低，不可尋址，通常采用中斷驅(qū)動方式，屬于無結構設備，例:交互式終端、打印機）按設備的共享屬性分類：獨占設備（不可尋址），共享設備（可尋址且可以隨機訪問），虛擬設備（2）設備并不是直接與CPU通信，而是通過設備控制器（位于CPU和設備之間，接收CPU發(fā)來的命令,控制一個或多個I/O設備,以實現(xiàn)I/O設備和計算機之間的數(shù)據(jù)交換）。設備與設備控制器之間的接口有：數(shù)據(jù)信號線：用于在設備和設備控制器之間傳送數(shù)據(jù)信號控制信號

16、線：作為由設備控制器向I/O設備發(fā)送控制信號時的通路狀態(tài)信號線：用于傳送指示設備當前狀態(tài)的信號設備控制器的組成：設備控制器與處理機的接口；設備控制器與設備的接口；I/O邏輯。（3）I/O通道是一種特殊處理機，只具有執(zhí)行I/O指令的能力。位于CPU和設備控制器之間，即實現(xiàn)內(nèi)存與外設之間的傳輸。沒有自己的內(nèi)存，與CPU共享內(nèi)存。通道類型：字節(jié)多路通道連接中低速設備；（2）數(shù)組選擇通道高速傳輸數(shù)據(jù)，每次只有一臺設備進行數(shù)據(jù)傳送,形成獨占；(3)數(shù)組多路通道結合了（1）（2）的優(yōu)點。解決瓶頸問題的方法是增加通路。5.2 I/O控制方式內(nèi)存與外設的控制方式主要有四種:程序I/O方式（有“忙等待” 現(xiàn)象）

17、、中斷驅(qū)動I/O方式（以字節(jié)為單位，CPU與I/O設備并行操作）、直接存儲訪問DMA I/O控制方式（在DMA控制器的作用下，數(shù)據(jù)傳輸?shù)幕締挝粸閴K，如磁盤）和I/O通道控制方式。DMA控制器的組成：主機與DMA控制器的接口，DMA控制器與塊設備的接口，I/O控制邏輯。（為了實現(xiàn)在主機與DMA控制器之間成塊數(shù)據(jù)的直接交換, 必須在DMA控制器中設置如下四類寄存器:命令/狀態(tài)寄存器CR，內(nèi)存地址寄存器MAR，數(shù)據(jù)寄存器DR，數(shù)據(jù)計數(shù)器DC）。5.3 緩沖管理引入緩沖區(qū)目的：(1)緩和CPU與I/O設備間速度不匹配的矛盾。 (2)減少對CPU的中斷頻率,放寬對CPU中斷響應時間的限制。 (3)提高

18、CPU和I/O設備之間的并行性。 根據(jù)系統(tǒng)設置緩沖區(qū)的個數(shù),將緩沖技術分為:單緩沖、雙緩沖、循環(huán)緩沖、緩沖池。當輸入與輸出速度基本(jbn)匹配時,雙緩沖(hunchng)能獲得較好效果;當速度(sd)相差較大時,可引入多個緩沖,組織成循環(huán)緩沖（多個緩沖區(qū)）的形式。循環(huán)緩沖：用于裝輸入數(shù)據(jù)的空緩沖區(qū)R，已裝滿數(shù)據(jù)的滿緩沖區(qū)G，計算進程正在使用的現(xiàn)行工作緩沖區(qū)C。多個指針：指示計算進程下一可用緩沖區(qū)Nextg，指示輸入進程下一可用空緩沖區(qū)Nexti，指示計算進程正在使用的緩沖區(qū)Current(1)Nexti指針追趕上Nextg指針輸入進程速度大于計算進程,全部空緩沖區(qū)已滿,無可用緩沖區(qū),輸入進程

19、阻塞(2)Nextg指針追趕上Nexti指針計算進程速度大于輸入進程,全部緩沖區(qū)空,無可用數(shù)據(jù),計算進程阻塞。緩沖池：因為以上的專用緩沖的利用率不高,因此設置公用緩沖池。5.4設備分配SPOOLing系統(tǒng)的組成：輸入井和輸出井：在磁盤上的兩個存儲空間。輸入井模擬脫機輸入,暫存輸入數(shù)據(jù)；輸出井模擬脫機輸出,暫存輸出數(shù)據(jù)。輸入緩沖區(qū)和輸出緩沖區(qū)：在內(nèi)存中。用來緩和CPU與磁盤之間的速度的矛盾輸入進程SPi和輸出進程SPo：模擬脫機I/O時的外圍控制機。SPi模擬脫機輸入時的外圍控制機；SPo模擬脫機輸出時的外圍控制機。5.5 磁盤存儲器管理磁盤調(diào)度先來先服務FCFS；最短尋道時間優(yōu)先SSTF（有“

20、饑餓”現(xiàn)象）；掃描(SCAN)算法（可防止進程出現(xiàn)“饑餓”現(xiàn)象，又稱為 “電梯調(diào)度算法”）；循環(huán)掃描(CSCAN)算法；N-Step-SCAN（將磁盤請求隊列分成若干個長度為N的子隊列,磁盤調(diào)度將按FCFS算法依次處理這些子隊列。而每處理一個隊列時又是按SCAN算法。當N很大時，趨于SCAN算法，N=1時，蛻化為FCFS算法） 磁盤高速緩存：利用內(nèi)存中的存儲空間,來暫存從磁盤中讀出的一系列盤塊中的信息。是一組在邏輯上屬于磁盤,而物理上是駐留在內(nèi)存中的盤塊。提高磁盤I/O速度的其它方法：提前讀，延遲寫，優(yōu)化物理塊分布，虛擬盤。六文件管理6.1文件和文件系統(tǒng)文件可分為有結構文件(記錄式文件)和無結構文件（流式文件），有結構文件中，文件由若干個相關記錄組成,而無結構文件則被看成字符流。文件類型：按用途分類：系統(tǒng)文件，用戶文件，庫文件按文件中數(shù)據(jù)的形式分類：源文件，目標文件，可執(zhí)行