操作系統(tǒng)十大算法具體內(nèi)容

1、一、進程調(diào)度 如何從就緒隊列中選擇一個進程使其運行？ 從就緒隊列中按一定的策略選擇一個進程，使其占有處理機。 進程調(diào)度的時機 正在運行的進程運行完畢。 正在執(zhí)行的進程被阻塞，加入等待隊列 時間片到 高優(yōu)先級的進程進入就緒隊列進程調(diào)度的評價指標 進程的等待時間 CPU的利用率 系統(tǒng)資源的利用率 響應(yīng)時間 周轉(zhuǎn)時間一般用平均周轉(zhuǎn)時間來衡量一個調(diào)度算法的好壞。1、先來先服務(wù)法、先來先服務(wù)法 根據(jù)進程到達就緒隊列的次序，總是選擇先到達的進程運行。 優(yōu)點：公平性；管理簡單（隊列）。 看右邊表格中的例子： 由于進程到達的隨機性，可能使系統(tǒng)中的短作業(yè)等待時間長。作業(yè)CPU時間156224352、時間片輪轉(zhuǎn)法

2、（、時間片輪轉(zhuǎn)法（RR） 時間片：系統(tǒng)允許進程一次使用處理機的最長時間。 回憶：分時系統(tǒng)的工作原理。 工作原理：就緒隊列中的進程，每次最多使用一個時間片。 硬件支持：計時器。時間片到，發(fā)生“計時中斷”。 問題：時間片的大小如何確定？時間片的長短 就緒隊列長短：越長，時間片越短。 響應(yīng)時間的要求： 計算機的性能 進程切換的系統(tǒng)開銷：一個進程讓出處理機，另一個進程占有處理機。3、進程調(diào)度算法-優(yōu)先數(shù)調(diào)度法 總是從就緒隊列中選擇優(yōu)先級最高的進程。 問題1：優(yōu)先數(shù)如何確定？ 進程類別：系統(tǒng)進程，用戶進程，前臺，后臺等 進程運行時間 作業(yè)的優(yōu)先級等優(yōu)先數(shù)調(diào)度法 問題2：當一個更高優(yōu)先級的進程到達就緒隊列

3、時，如何處理？ 搶占式 非搶占式：一旦分配CPU，就一直占用，直到主動放棄為止。 問題3：如果一個低優(yōu)先級的進程在就緒隊列中等待太長時間？ 動態(tài)優(yōu)先數(shù)動態(tài)優(yōu)先數(shù)：進程的優(yōu)先級隨系統(tǒng)情況不斷變化。多級輪轉(zhuǎn)調(diào)度法 時間片輪轉(zhuǎn)與優(yōu)先數(shù)結(jié)合。 按優(yōu)先級將作業(yè)排成不同的隊列。 先按優(yōu)先級調(diào)度，優(yōu)先級相同的，按時間片輪轉(zhuǎn)。 前臺作業(yè)與后臺作業(yè) 交互式作業(yè) 批處理作業(yè)二、可變分區(qū)存儲管理原理在作業(yè)要求裝入主存時，根據(jù)作業(yè)的大小從空閑內(nèi)存區(qū)中“切出”一片連續(xù)的區(qū)域。 分區(qū)的大小和個數(shù)是不確定的 初始時，系統(tǒng)中只有一個連續(xù)的用戶區(qū)域，隨著作業(yè)的到達和撤消，用戶區(qū)就被劃分為若干個大小不等的區(qū)域。內(nèi)存內(nèi)存OS作業(yè)A

4、作業(yè)B作業(yè)C可變分區(qū)存儲管理的原理 空閑區(qū)的管理空閑區(qū)的管理 空閑分區(qū)表空閑分區(qū)表 序號 起始地址 大小 狀態(tài) 注意注意：這里的狀態(tài)是指該表目的狀態(tài)，其值表示該表目是空閑還是已使用。 空閑分區(qū)鏈空閑分區(qū)鏈空閑區(qū)大小；下一空閑區(qū)起始地址 1 、內(nèi)存分配與回收 （1 1）最先適應(yīng)分配算法）最先適應(yīng)分配算法 空閑分區(qū)表按地址地址從小小到大大排列，從第一個開始，找到第一個滿足條件的分區(qū)，根據(jù)作業(yè)的大小切出一片連續(xù)的區(qū)域。 分配算法內(nèi)存分配與回收作業(yè)請求LP=1是否越界？Y不能分配狀態(tài)為空閑？NP=P+1長度LNY長度=L狀態(tài)置為“空表目”YN起始地址=起始地址+L長度=長度-L最先適應(yīng)分配算法 （2）

5、最優(yōu)適應(yīng)分配算法最優(yōu)適應(yīng)分配算法 原理：原理：將空閑區(qū)按大小大小從小到大排列，將滿足需求的最小的空閑區(qū)分配給作業(yè)。 好處：好處：為了更好地滿足大作業(yè)的需求。 缺點：缺點：這樣切下的空閑區(qū)容易變成“碎碎片片”。 算法流程與最先適配法相同。 分配算法 （3 3）最壞適配算法）最壞適配算法 從滿足需求的最大最大的空閑區(qū)中為作業(yè)分配空間。 空閑分區(qū)表按大小大小從大大到小小排列。 優(yōu)點：切完后的空閑區(qū)仍能滿足某個作業(yè)的需求，減少碎片的數(shù)量。 缺點：但對大作業(yè)不利。 其流程為： 分配算法用戶作業(yè)請求取分區(qū)表的第一個表項長度起始地址起始地址長度長度長度狀態(tài)置空表目不能分配 如何判斷待回收區(qū)是否與空閑區(qū)相連？

6、 地址+長度=下一空閑區(qū)首地址 空閑區(qū)的管理：為了便于空閑區(qū)的合并，采用鏈鏈接結(jié)構(gòu)接結(jié)構(gòu)。 按地址從小到大排序。 第一塊和最后一塊的情況。注 意回收算法回收算法、待回收區(qū)：其起始地址為，長度為。、上空閑區(qū)和下空閑區(qū)、可能的四種情況：（）上下都不空。（）上空，下不空。（）下空，上不空。（）上下都為空。待回收區(qū)作業(yè)區(qū)作業(yè)區(qū)上下都不空上下都不空待回收區(qū)作業(yè)區(qū)上空下不空上空下不空在空閑分區(qū)表中找一個空表目，將其內(nèi)容填入。上空閑區(qū)：大小大小待回收區(qū)作業(yè)區(qū)待回收區(qū)下空上不空下空上不空下空閑區(qū)：起始地址=A大小=大小+L上下都為空上下都為空上空閑區(qū)：長度=長度+L+下空閑區(qū)起址不變。注注 意意 如何判斷待回

7、收區(qū)是否與空閑區(qū)相連？ 地址+長度=下一空閑區(qū)首地址 空閑區(qū)的管理：為了便于空閑區(qū)的合并，采用鏈接結(jié)構(gòu)。 按地址從小到大排序。 第一塊和最后一塊的情況。可變分區(qū)存在的問題及解決辦法 碎片問題：一些很小的內(nèi)存區(qū)域 。 移動技術(shù) 將離散的碎片集合在一起。 不是任何時候都可以移動。 移動技術(shù)需要很大的系統(tǒng)開銷。 保護問題 界地址法：基址和長度寄存器。三、 頁式存儲管理 “等分”內(nèi)存 把內(nèi)存劃分為大小相同的“塊” 把用戶作業(yè)空間劃分為大小相同的“頁” 頁和塊的大小相同 在把作業(yè)加載到內(nèi)存時，頁和頁之間不再連續(xù)。但頁內(nèi)連續(xù)。 也不必把所有的頁都一次性加載內(nèi)存，只需要加載那些馬上要用到的頁。其余的頁在需要

8、時再加載?；驹眄撌街鞔婵臻g的分配與回收 用戶需求：用戶需求：需要多少塊？ 內(nèi)存空閑塊的管理：內(nèi)存空閑塊的管理：位示圖位示圖。 位示圖：位示圖：在內(nèi)存中劃出一片區(qū)域，用一位代表一個塊，該位的值表示所代表的塊的狀態(tài)： 0：空閑；1：已分配。 主存分配主存分配 塊號與字號、字長的關(guān)系：系統(tǒng)的字長一定，內(nèi)存塊從0開始編號，則有： 塊號=字號*字長+位號 字號=塊號/字長 （取整的意思） 位號=塊號 MOD 字長 用戶作業(yè)請求：塊數(shù)B掃描位示圖，查找為0的位空閑塊數(shù)BN無法分配計算塊號建立頁表頁號塊號071122321頁表根據(jù)頁號查頁表，得到塊號。根據(jù)塊號和頁內(nèi)地址計算物理地址1、頁面調(diào)度 先進先出

9、法（先進先出法（FIFOFIFO）：）：將最先調(diào)入內(nèi)存的頁調(diào)出內(nèi)存 最近最久未使用算法（最近最久未使用算法（LRULRU：least recently usedleast recently used）：將最近一段時間內(nèi)沒有用過的頁調(diào)出內(nèi)存。實現(xiàn)這種算法的一種方法是在頁表中為每一頁增加一個引用位標志，記錄該頁面自上次被訪問以來所經(jīng)歷的時間，每訪問一次都應(yīng)重新計時。當需要替換時，檢查每頁的引用位，從中選出計時值最大的那一頁調(diào)出。四、頁式虛擬存儲技術(shù) 最近最不經(jīng)常使用算法（最近最不經(jīng)常使用算法（LFULFU）：）：最近一段時間內(nèi)使用次數(shù)最少的頁調(diào)出內(nèi)存。 為每一個在內(nèi)存的頁設(shè)置一個計數(shù)器，選擇計數(shù)器

10、中的值最小的調(diào)出。 注意：注意：LRU、LFU之間的區(qū)別。 例題例題 有一個分頁式虛擬存儲管理系統(tǒng)，每個進程在內(nèi)存有3頁數(shù)據(jù)區(qū)、1頁程序區(qū)，剛開始時數(shù)據(jù)區(qū)為空?，F(xiàn)有一個進程有以下訪問序列： 1，5，4，1，2，3，2，1，5，4，2，4，3，5，1若系統(tǒng)采用：（1）最近最少使用（LRU）淘汰算法（2）先進先出（FIFO）淘汰算法請計算缺頁次數(shù)和發(fā)生缺頁中斷后的淘汰頁號。 分析分析 （1）采用FIFO方法 將內(nèi)存中的頁按進入的先后次序排隊，后來的加入隊尾，先來的先出去。訪問隊列：1 5 4 1 2 3 2 1 5 4 2 4 3 5 1 1 5 4 4 2 3 3 1 5 4 2 2 3 5 1

11、內(nèi) 存 1 5 5 4 2 2 3 1 5 4 4 2 3 5 1 1 5 4 4 2 3 1 5 5 4 2 3缺頁中斷 頁面替換 1 5 4 2 3 1 5 4 3答案：缺頁中斷的次數(shù)為12次，頁面替換的次序是：1 5 4 2 3 1 5 4 3。FIFOFIFO方法方法訪問隊列：1 5 4 1 2 3 2 1 5 4 2 4 3 5 1 1 5 4 4 2 3 3 3 5 4 2 2 3 5 1內(nèi) 存 1 5 5 1 2 2 2 1 5 4 4 2 3 5 1 1 4 1 1 1 2 1 5 5 4 4 3缺頁中斷 頁面替換 5 4 3 2 1 5 2 4答案：缺頁中斷的次數(shù)為11次，頁

12、面替換的次序是：5 4 3 2 1 5 2 4LRU LRU 算法算法五、磁盤空間的管理1、空閑空間的管理 （1）位示圖：用一個位來表示一個塊。如果字長為32位，則字號、位號、塊號之間的關(guān)系是： 塊號=字號*字長+位號 字號=塊號/字長 位號=塊號 MOD 字長 （2）空閑空間鏈：在空閑塊中利用幾個字節(jié)，存放下一空閑塊的塊號。2成組鏈接法假設(shè)初始化時系統(tǒng)已把專用塊讀入內(nèi)存L單元開始的區(qū)域中，分配和回收的算法如下：（1）分配一個空閑塊 查L單元內(nèi)容（即空閑塊數(shù)）； 當空閑塊數(shù)1時； i L空閑塊數(shù)（把i作為主存地址）； 從i單元得到一空閑塊號； 把該塊分配給申請者； 空閑塊數(shù)減1。 當空閑塊數(shù)1

13、 時 取出L1單元內(nèi)容（一組的第一塊塊號 ）； 其值0，無空閑塊，申請者等待； 不等于零把該塊內(nèi)容復制到專用塊，并將該塊分配給 申請者； 把專用塊內(nèi)容讀到主存L開始的區(qū)域。（2）歸還一空閑塊（即把歸還的塊號加到空閑塊鏈中） 取L單元的空閑塊數(shù)； 當空閑塊數(shù)100 時 空閑塊數(shù)加1； j L空閑塊數(shù)（把j作為主存地址） ； 歸還塊號填入j單元。 當空閑塊數(shù)100 時 把主存中登記的信息寫入歸還塊中； 把歸還塊號填入L1單元； 將L單元置成1。磁盤空間管理（3）空閑空間表首塊號長度必須連續(xù)分配。七、磁盤調(diào)度七、磁盤調(diào)度 磁盤是共享設(shè)備，可以同時為多個進程服務(wù)。 目前的磁盤都是活動磁頭，因此讀寫時間

14、包括： 查找時間：磁頭移動到正確的磁道的時間。 延遲時間（等待時間）：磁頭等待盤片旋轉(zhuǎn)到正確的扇區(qū)下的時間。 傳輸時間：數(shù)據(jù)從磁盤讀到內(nèi)存的時間。 在上述三個時間中，查找時間、延遲時間可以通過調(diào)度策略來改善。 移臂調(diào)度和旋轉(zhuǎn)調(diào)度。1、移臂調(diào)度 將移動臂移動到指定柱面的調(diào)度。 影響尋找時間的長短。 當有若干個設(shè)備讀寫請求時，應(yīng)該先響應(yīng)哪一個？ 原則：盡量避免移動臂頻繁地來回移動。 先來先服務(wù) 最短查找時間優(yōu)先 電梯法引例：引例： 假定一個活動磁盤有200個磁道，編號為0199。當前磁頭正在54道上服務(wù)，并且剛剛完成了39道上的請求。現(xiàn)有如下的磁盤訪問請求序列（磁道號）：86、147、91、173

15、、95、148、101、26、169、80、129、22試給出采用下列移臂調(diào)度算法后移動臂移動的順序和移動總量（總磁道數(shù)）。（1） 先來先服務(wù)法（2） 最短尋找時間優(yōu)先（3） 電梯法移臂調(diào)度的評價 尋找時間越短越好。 尋找時間與移動臂移動的磁道數(shù)成正比。 因此，我們用移動臂移動的磁道數(shù)來評價某一個移臂調(diào)度的策略的好壞。移臂調(diào)度策略 先來先服務(wù)：根據(jù)請求的到達先后次序，響應(yīng)請求。 173 169 148 147 129 101 95 91 86 80 54 26 22磁頭移動的順序為：86、147、91、173、95、148、101、26、169、80、129、22磁頭的移動總量為：（86-54

16、）+（147-86）+（147-91）+（173-91）+（173-95）+（148-95）+（148-101）+（101-26）+（169-26）+（169-80）+（129-80）+（129-22）=872最短查找時間優(yōu)先 從當前位置開始，響應(yīng)磁頭移動距離最短的請求。 也就是離當前位置最近的請求。 注意：它不考慮移動臂移動的方向。首先從訪問隊列中找離54磁道最近的訪問請求，結(jié)果是80，再從剩下的訪問請求中找離80最近的，是86。直到所有訪問請求響應(yīng)完為止。173 169 148 147 129 101 95 91 86 80 54 26 22磁頭移動次序為：80、86、91、95、101、

17、129、147、148、169、173、26、22磁頭移動的總磁道數(shù)為：（80-54）+（86-80）+（91-86）+（95-91）+（101-95）+（129-101）+（147-129）+（148-147）+（169-148）+（173-169）+（173-26）+（26-22）=270 電梯法 沿著當前磁頭移動的方向，響應(yīng)進程的請求。當該方向上無請求時，磁頭就改變方向。 因此，一定要知道當前磁頭的移動方向。從題意可知：磁頭的移動方向為從外向內(nèi)移動，也就是從0向199的移動。根據(jù)電梯法的調(diào)度原理，磁頭的移動如下圖所示： 173 169 148 147 129 101 95 91 86 8

18、0 54 26 22磁頭移動次序為：80、86、91、95、101、129、147、148、169、173、26、22磁頭移動的總磁道數(shù)為：（80-54）+（86-80）+（91-86）+（95-91）+（101-95）+（129-101）+（147-129）+（148-147）+（169-148）+（173-169）+（173-26）+（26-22）=270 旋轉(zhuǎn)調(diào)度 移動臂定位后，有多個訪問者等待訪問該柱面時。 使延遲時間最短。 根據(jù)延遲時間來決定調(diào)度次序的調(diào)度。 三種情況： （1）同一磁道上的不同扇區(qū)。 （2）不同磁道上的不同扇區(qū)。 （3）不同磁道上的具有相同編號的扇區(qū)。 對（1）（2）

19、總是對先到達磁頭位置下的扇區(qū)進行信息傳遞；(3）因同時到達，則從中任意選擇一個進行傳遞，其余等磁盤再次把扇區(qū)轉(zhuǎn)到磁頭位置時才有可能被選中。信息的優(yōu)化分布例：例：某系統(tǒng)對磁盤初始化時把每個盤面分成8個扇區(qū)，今有8個邏輯記錄被存放在同一個磁道上供處理程序使用，處理程序要求順序處理這8個記錄，每次請求從磁盤上讀一個記錄，然后對讀出的記錄要花5毫秒的時間處理，以后再讀下一個記錄進行處理，直到8個記錄都處理結(jié)束。假定磁盤轉(zhuǎn)速為20毫秒/周，則處理這8個記錄所花費的時間是多少？順序存放始點旋轉(zhuǎn)方向12345678花費時間 讀一個記錄需要2.5毫秒。 處理一個記錄的時間為5毫秒。 當處理完一個記錄（5毫秒）

20、后，讀寫磁頭已旋轉(zhuǎn)到第4個記錄位置。 為了處理第2個記錄，必須等待磁盤把第2個記錄旋轉(zhuǎn)到讀寫磁頭位置下面。 需要15毫秒的延遲時間。 因此，總時間為： 8（2.5+5）+7 15=165MS優(yōu)化分布61234578八、作業(yè)調(diào)度算法 先來先服務(wù)算法 注意：不是先進入的一定先被選中，只有滿足資源需求的作業(yè)才可能被選中。 計算時間短的作業(yè)優(yōu)先算法 響應(yīng)比高者優(yōu)先算法：響應(yīng)比響應(yīng)比=等待時間/運行時間 優(yōu)先數(shù)調(diào)度法 均衡調(diào)度算法：根據(jù)作業(yè)對資源的要求進行分類，作業(yè)調(diào)度輪流從不同類的作業(yè)中去挑選作業(yè)運行。例例：在一個單道批處理系統(tǒng)中，一組作業(yè)的提交時刻和運行時間如下表所示，試計算以下三種作業(yè)調(diào)度算法的平

21、均周轉(zhuǎn)時間。（1）先來先服務(wù)法。（2）短作業(yè)優(yōu)先 （3）響應(yīng)比高者優(yōu)先。作業(yè) 提交時間（小時）運行時間（小時） 1 8：00 1 2 8：50 0.5 3 9:00 0.2 4 9:10 0.1（1）先來先服務(wù)算法：）先來先服務(wù)算法：8:009:009:30 9:42 9:48123460分鐘分鐘30分鐘分鐘12分鐘分鐘6分鐘分鐘（2）短作業(yè)優(yōu)先算法：）短作業(yè)優(yōu)先算法：8:00 8:50 9:00 9:10 9:12 9:18 9:48 123360分分12分分446分分230分分（3）響應(yīng)比高者優(yōu)先：）響應(yīng)比高者優(yōu)先：2的響應(yīng)比的響應(yīng)比=10/303的響應(yīng)比的響應(yīng)比=0/12因此，作業(yè)因此，

22、作業(yè)2先調(diào)度運行先調(diào)度運行9:00 9:303的響應(yīng)比的響應(yīng)比=30/124的響應(yīng)比的響應(yīng)比=20/6因此，作業(yè)因此，作業(yè)4先調(diào)度運行先調(diào)度運行9:30 9:36最后，作業(yè)最后，作業(yè)3調(diào)度運行：調(diào)度運行：9:36 9:481243作業(yè)調(diào)度算法例題 假設(shè)有一個多道程序設(shè)計系統(tǒng)，采用可變分區(qū)方式管理主存儲器，且不能移動已在主存儲器中的作業(yè)。若供用戶使用的主存空間為200KB，系統(tǒng)配備5臺磁帶機。該系統(tǒng)對磁帶機采用靜態(tài)分配，忽略外設(shè)工作時間和系統(tǒng)調(diào)用所花的時間，有下列4個作業(yè)，采用計算時間最短者優(yōu)先算法進行調(diào)度。 填充下表中的空白處:作業(yè)進輸入井時間 要求計算時間 需要主存量申請磁帶機數(shù)開始執(zhí)行時間

23、 完成時間周轉(zhuǎn)時間A8:30 24分 30KB 2B8:40 33分 50KB 2C8:50 12分 110KB 3D9:00 42分 40KB 2解題思路 1、作業(yè)調(diào)度的時機： （1）一個作業(yè)到達后備隊列 （2）一個作業(yè)執(zhí)行完畢 2、先決條件：必須先滿足作業(yè)的資源需求 3、考慮調(diào)度的算法答 案作業(yè)進輸入井時間 要求計算時間 需要主存量申請磁帶機數(shù)裝入主存時間開始執(zhí)行時間完成時間周轉(zhuǎn)時間A8:30 24分 30KB 28:30 8:308:5424B8:40 33分 50KB 28:40 8:549:2646C8:50 12分 110KB 38:54 9:269:3848D9:00 42分 4

24、0KB 29:26 9:3810:2080九、銀行家算法 思想：允許用戶分批申請貸款，每次貸款之前，都要檢查是否安全。 數(shù)據(jù)結(jié)構(gòu)： 系統(tǒng)中總的資源 進程運行所需資源（總數(shù)） 已經(jīng)分配的資源數(shù) P 還需要申請的資源數(shù) R銀行家算法的算法過程 準備：計算系統(tǒng)中的剩余資源F；計算進程請求資源R （1）找到一個進程Pi，滿足Ri=Ri，則說明系統(tǒng)不安全。 （5）若所有進程都能夠運行結(jié)束，則系統(tǒng)安全。銀行家算法的應(yīng)用 現(xiàn)有三個進程P1、P2、P3，共享A、B、C三類資源，進程對資源的需求量和目前分配情況如下表： 進程 已占有資源數(shù) 最大需求數(shù) A B C A B C P1 2 6 3 2 6 5 P2

25、2 0 1 2 0 1 P3 2 1 0 2 8 5 若系統(tǒng)還有剩余資源分別為：A類2個，B類6個，C類2個。請回答下列問題：（1）目前系統(tǒng)是否處于安全狀態(tài)？（2）如果進程P3提出申請（0，5，2）個資源，系統(tǒng)是否能為它分配資源？ （1） 系統(tǒng)當前的空閑資源為：（2，6，2）進程要運行結(jié)束，還需請求的資源為： 進 程 A B C P1 0 0 2 P2 0 0 0 P3 0 7 5由于P2不需要申請更多的資源，可以運行結(jié)束，釋放它占有的資源（2，0，1），空閑資源變?yōu)椋海?，6，3）?？臻e資源滿足P1的資源要求，P1運行結(jié)束，釋放它占有的資源（2，6，3），空閑資源變?yōu)椋海?，12，6）?？臻e資源滿足P3的資源請求，P3可以運行結(jié)束。系統(tǒng)中的進程能在有限時間內(nèi)全部運行結(jié)束，所以系統(tǒng)是安全的。（2） 假設(shè)可以為進程P3分配它申請的資源（0，5，2），則系統(tǒng)當前狀況是：空閑資源為：（2，1，0）進程要運行結(jié)束，還需請求的資源為：進進 程程 A B C P1 0 0 2 P2 0 0 0 P3 0 2 3進程P2運行，釋放它所占有的資源（2，0，1），系統(tǒng)空閑資源變?yōu)椋海?，1，1）。由于空閑資源不能滿足系統(tǒng)中任一進程的資源請求，進程P1和P3陷入無限期等待，系統(tǒng)出現(xiàn)死鎖。所以，系統(tǒng)不