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

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