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

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