操作系統(tǒng)算法總結(jié).doc

操作系統(tǒng)原理算法總結(jié)一、進程(作業(yè))調(diào)度算法l 先來先服務(wù)調(diào)度算法（FCFS）：每次調(diào)度是從就緒隊列中，選擇一個最先進入就緒隊列的進程，把處理器分配給該進程，使之得到執(zhí)行。該進程一旦占有了處理器，它就一直運行下去，直到該進程完成或因發(fā)生事件而阻塞，才退出處理器。特點：利于長進程，而不利于短進程。 l 短進程（作業(yè)）優(yōu)先調(diào)度算法(SPF)：它是從就緒隊列中選擇一個估計運行時間最短的進程，將處理器分配給該進程，使之占有處理器并執(zhí)行，直到該進程完成或因發(fā)生事件而阻塞，然后退出處理器，再重新調(diào)度。 l 時間片輪轉(zhuǎn)調(diào)度算法 ：系統(tǒng)將所有的就緒進程按進入就緒隊列的先后次序排列。每次調(diào)度時把CPU分配給隊首進程，讓其執(zhí)行一個時間片，當(dāng)時間片用完，由計時器發(fā)出時鐘中斷，調(diào)度程序則暫停該進程的執(zhí)行，使其退出處理器，并將它送到就緒隊列的末尾，等待下一輪調(diào)度執(zhí)行。 l 優(yōu)先權(quán)調(diào)度算法 ：它是從就緒隊列中選擇一個優(yōu)先權(quán)最高的進程，讓其獲得處理器并執(zhí)行。 l 高響應(yīng)比優(yōu)先調(diào)度算法：它是從就緒隊列中選擇一個響應(yīng)比最高的進程，讓其獲得處理器執(zhí)行，直到該進程完成或因等待事件而退出處理器為止。特點：既照顧了短進程，又考慮了進程到達的先后次序，也不會使長進程長期得不到服務(wù)，因此是一個比較全面考慮的算法，但每次進行調(diào)度時，都需要對各個進程計算響應(yīng)比。所以系統(tǒng)開銷很大，比較復(fù)雜。 l 多級隊列調(diào)度算法基本概念： 作業(yè)周轉(zhuǎn)時間（Ti）完成時間(Tei)提交時間(Tsi) 作業(yè)平均周轉(zhuǎn)時間(T)周轉(zhuǎn)時間/作業(yè)個數(shù) 作業(yè)帶權(quán)周轉(zhuǎn)時間（Wi）周轉(zhuǎn)時間/運行時間 響應(yīng)比（等待時間運行時間）/運行時間二、存儲器連續(xù)分配方式中分區(qū)分配算法n 首次適應(yīng)分配算法（FF）：對空閑分區(qū)表記錄的要求是按地址遞增的順序排列的，每次分配時，總是從第1條記錄開始順序查找空閑分區(qū)表，找到第一個能滿足作業(yè)長度要求的空閑區(qū)，分割這個空閑區(qū)，一部分分配給作業(yè)，另一部分仍為空閑區(qū)。保留了高址部分的大空閑區(qū)。 n 循環(huán)首次適應(yīng)算法：每次分配均從上次分配的位置之后開始查找。 使內(nèi)存中的空閑區(qū)分布得更均勻n 最佳適應(yīng)分配算法(BF)：是按作業(yè)要求從所有的空閑分區(qū)中挑選一個能滿足作業(yè)要求的最小空閑區(qū)，這樣可保證不去分割一個更大的區(qū)域，使裝入大作業(yè)時比較容易得到滿足。為實現(xiàn)這種算法，把空閑區(qū)按長度遞增次序登記在空閑區(qū)表中，分配時，順序查找。 基本概念：分頁：地址轉(zhuǎn)換：頁號邏輯地址/頁長頁內(nèi)地址邏輯地址mod頁長物理地址塊號*塊長+塊內(nèi)地址+用戶區(qū)基址分段：邏輯地址段號段內(nèi)地址物理地址段始址段內(nèi)地址三、頁面置換算法l 最佳置換算法（OPT) ：選擇以后永不使用或在最長時間內(nèi)不再被訪問的內(nèi)存頁面予以淘汰。不現(xiàn)實的算法l 先進先出置換算法（FIFO）：選擇最先進入內(nèi)存的頁面予以淘汰。 存在Belady現(xiàn)象，抖動現(xiàn)象。l 最近最久未使用算法（LRU）：選擇在最近一段時間內(nèi)最久沒有使用過的頁，把它淘汰。 l Clock置換算法（LRU算法的近似實現(xiàn)）：給每一幀關(guān)聯(lián)一個附加位，稱為使用位?；靖拍睿核?、磁盤調(diào)度n 先來先服務(wù)（FCFS）：是按請求訪問者的先后次序啟動磁盤驅(qū)動器，而不考慮它們要訪問的物理位置n 最短尋道時間優(yōu)先（SSTF）：讓離當(dāng)前磁道最近的請求訪問者啟動磁盤驅(qū)動器，即是讓查找時間最短的那個作業(yè)先執(zhí)行，而不考慮請求訪問者到來的先后次序，這樣就克服了先來先服務(wù)調(diào)度算法中磁臂移動過大的問題，但容易造成進程饑餓現(xiàn)象n 掃描算法（SCAN）或電梯調(diào)度算法：總是從磁臂當(dāng)前位置開始，沿磁臂的移動方向去選擇離當(dāng)前磁臂最近的那個柱面的訪問者。如果沿磁臂的方向無請求訪問時，就改變磁臂的移動方向。在這種調(diào)度方法下磁臂的移動類似于電梯的調(diào)度，所以它也稱為電梯調(diào)度算法。n 循環(huán)掃描算法（CSCAN）：循環(huán)掃描調(diào)度算法是在掃描算法的基礎(chǔ)上改進的。磁臂改為單項移動，由外向里。當(dāng)前位置開始沿磁臂的移動方向去選擇離當(dāng)前磁臂最近的哪個柱面的訪問者。如果沿磁臂的方向無請求訪問時，再回到最外，訪問柱面號最小的作業(yè)請求。五、信號量問題（解題思路）n 分清哪些是互斥問題（互斥訪問臨界資源的），哪些是同步問題（具有前后執(zhí)行順序要求的）。n 對互斥問題要設(shè)置互斥信號量，不管有互斥關(guān)系的進程有幾個或幾類，通常只設(shè)置一個互斥信號量，且初值為1，代表一次只允許一個進程對臨界資源訪問。n 對同步問題要設(shè)置同步信號量，通常同步信號量的個數(shù)與參與同步的進程種類有關(guān)，即同步關(guān)系涉及幾類進程，就有幾個同步信號量。同步信號量表示該進程是否可以開始或該進程是否已經(jīng)結(jié)束。n 在每個進程中用于實現(xiàn)互斥的PV操作必須成對出現(xiàn)；用于實現(xiàn)同步的PV操作也必須成對出現(xiàn)，但可以分別出現(xiàn)在不同的進程中；在某個進程中如果同時存在互斥與同步的P操作，則其順序不能顛倒，必須先執(zhí)行對同步信號量的P操作，再執(zhí)行對互斥信號量的P操作，但V操作的順序沒有嚴(yán)格要求。 六、銀行家算法七、地址變換八、進程的概念與程序的區(qū)別進程：程序在并發(fā)環(huán)境下的執(zhí)行過程。進程與程序的主要區(qū)別：(1)程序是永存的，進程是暫時的(2)程序是靜態(tài)的觀念，進程是動態(tài)的觀念(3)進程由三部分組成：程序+數(shù)據(jù)+進程控制塊（描述進程活動情況的數(shù)據(jù)結(jié)構(gòu)）(4)進程和程序不是一一對應(yīng)的一個程序可對應(yīng)多個進程即多個進程可執(zhí)行同一程序一個進程可以執(zhí)行一個或幾個程序九、進程的狀態(tài)轉(zhuǎn)換 (1) 就緒態(tài)-運行態(tài) 處理機空閑(2) 運行態(tài)-就緒態(tài) 時間片用完、 (3) 運行態(tài)-阻塞態(tài) 等待某事件發(fā)生(4) 阻塞態(tài)-就緒態(tài) 等待事件已發(fā)生十、進程調(diào)度 非搶占方式分派程序一旦把處理機分配給某進程后便讓它一直運行下去，直到進程完成或發(fā)生 搶占方式當(dāng)一個進程正在運行時，系統(tǒng)可以基于某種原則，剝奪已分配給它的處理機，將之分配給其它進程。搶占原則：優(yōu)先權(quán)原則、短進程優(yōu)先原則、時間片原則十一、產(chǎn)生死鎖的必要條件產(chǎn)生死鎖的原因有二，一是競爭資源，二是進程推進順序非法互斥條件:指進程對所分配到的資源進行排它性使用。請求和保持