操作系統(tǒng)算法的都有哪些

操作系統(tǒng)算法的都有哪些

　　操作系統(tǒng)(英語(yǔ)：operating system，縮寫作 OS)是管理計(jì)算機(jī)硬件與軟件資源的計(jì)算機(jī)程序，同時(shí)也是計(jì)算機(jī)系統(tǒng)的內(nèi)核與基石。操作系統(tǒng)需要處理如管理與配置內(nèi)存、決定系統(tǒng)資源供需的優(yōu)先次序、控制輸入設(shè)備與輸出設(shè)備、操作網(wǎng)絡(luò)與管理文件系統(tǒng)等基本事務(wù)。操作系統(tǒng)也提供一個(gè)讓用戶與系統(tǒng)交互的操作界面。操作系統(tǒng)的類型非常多樣，不同機(jī)器安裝的操作系統(tǒng)可從簡(jiǎn)單到復(fù)雜，可從移動(dòng)電話的嵌入式系統(tǒng)到超級(jí)計(jì)算機(jī)的大型操作系統(tǒng)。許多操作系統(tǒng)制造者對(duì)它涵蓋范疇的定義也不盡一致，例如有些操作系統(tǒng)集成了圖形用戶界面，而有些僅使用命令行界面，而將圖形用戶界面視為一種非必要的應(yīng)用程序。下面是小編收集整理的操作系統(tǒng)算法的都有哪些范文，歡迎借鑒參考。

　　操作系統(tǒng)算法的都有哪些(一)

　　在操作系統(tǒng)中存在多種調(diào)度算法，其中有的調(diào)度算法適用于作業(yè)調(diào)度，有的調(diào)度算法適用于進(jìn)程調(diào)度，有的調(diào)度算法兩者都適用。下面介紹幾種常用的調(diào)度算法。

　　先來(lái)先服務(wù)(FCFS)調(diào)度算法

　　FCFS調(diào)度算法是一種最簡(jiǎn)單的調(diào)度算法，該調(diào)度算法既可以用于作業(yè)調(diào)度也可以用于進(jìn)程調(diào)度。在作業(yè)調(diào)度中，算法每次從后備作業(yè)隊(duì)列中選擇最先進(jìn)入該隊(duì)列的一個(gè)或幾個(gè)作業(yè)，將它們調(diào)入內(nèi)存，分配必要的資源，創(chuàng)建進(jìn)程并放入就緒隊(duì)列。

　　在進(jìn)程調(diào)度中，F(xiàn)CFS調(diào)度算法每次從就緒隊(duì)列中選擇最先進(jìn)入該隊(duì)列的進(jìn)程，將處理機(jī)分配給它，使之投入運(yùn)行，直到完成或因某種原因而阻塞時(shí)才釋放處理機(jī)。

　　下面通過(guò)一個(gè)實(shí)例來(lái)說(shuō)明FCFS調(diào)度算法的性能。假設(shè)系統(tǒng)中有4個(gè)作業(yè)，它們的提交時(shí)間分別是8、8.4、8.8、9，運(yùn)行時(shí)間依次是2、1、0.5、0.2，系統(tǒng)釆用FCFS調(diào)度算法，這組作業(yè)的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間見(jiàn)表2-3。

　　平均等待時(shí)間 t = (0+1.6+2.2+2.5)/4=1.575

　　平均周轉(zhuǎn)時(shí)間 T = (2+2.6+2.7+2.7)/4=2.5

　　平均帶權(quán)周轉(zhuǎn)時(shí)間 W = (1+2.6+5.牡13.5)/4=5.625

　　FCFS調(diào)度算法屬于不可剝奪算法。從表面上看，它對(duì)所有作業(yè)都是公平的，但若一個(gè)長(zhǎng)作業(yè)先到達(dá)系統(tǒng)，就會(huì)使后面許多短作業(yè)等待很長(zhǎng)時(shí)間，因此它不能作為分時(shí)系統(tǒng)和實(shí)時(shí)系統(tǒng)的主要調(diào)度策略。但它常被結(jié)合在其他調(diào)度策略中使用。例如，在使用優(yōu)先級(jí)作為調(diào)度策略的系統(tǒng)中，往往對(duì)多個(gè)具有相同優(yōu)先級(jí)的進(jìn)程按FCFS原則處理。

　　FCFS調(diào)度算法的特點(diǎn)是算法簡(jiǎn)單，但效率低;對(duì)長(zhǎng)作業(yè)比較有利，但對(duì)短作業(yè)不利(相對(duì)SJF和高響應(yīng)比);有利于CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)。

　　短作業(yè)優(yōu)先(SJF)調(diào)度算法

　　短作業(yè)(進(jìn)程)優(yōu)先調(diào)度算法是指對(duì)短作業(yè)(進(jìn)程)優(yōu)先調(diào)度的算法。短作業(yè)優(yōu)先(SJF)調(diào)度算法是從后備隊(duì)列中選擇一個(gè)或若干個(gè)估計(jì)運(yùn)行時(shí)間最短的作業(yè)，將它們調(diào)入內(nèi)存運(yùn)行。而短進(jìn)程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊(duì)列中選擇一個(gè)估計(jì)運(yùn)行時(shí)間最短的進(jìn)程，將處理機(jī)分配給它，使之立即執(zhí)行，直到完成或發(fā)生某事件而阻塞時(shí)，才釋放處理機(jī)。

　　例如，考慮表2-3中給出的一組作業(yè)，若系統(tǒng)釆用短作業(yè)優(yōu)先調(diào)度算法，其平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間和平均帶權(quán)周轉(zhuǎn)時(shí)間見(jiàn)表2-4。

　　平均等待時(shí)間 t = (0+2.3+1.4+1)/4=1.175

　　平均周轉(zhuǎn)時(shí)間 T = (2+3.3+1.9+1.2)/4=2.1

　　平均帶權(quán)周轉(zhuǎn)時(shí)間 W = (1+3.3+3.8+6)/4=3.525

　　SJF調(diào)度算法也存在不容忽視的缺點(diǎn)：

　　該算法對(duì)長(zhǎng)作業(yè)不利，由表2-3和表2-4可知，SJF調(diào)度算法中長(zhǎng)作業(yè)的周轉(zhuǎn)時(shí)間會(huì)增加。更嚴(yán)重的是，如果有一長(zhǎng)作業(yè)進(jìn)入系統(tǒng)的后備隊(duì)列，由于調(diào)度程序總是優(yōu)先調(diào)度那些 (即使是后進(jìn)來(lái)的)短作業(yè)，將導(dǎo)致長(zhǎng)作業(yè)長(zhǎng)期不被調(diào)度(“饑餓”現(xiàn)象，注意區(qū)分“死鎖”。后者是系統(tǒng)環(huán)形等待，前者是調(diào)度策略問(wèn)題)。

　　該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)會(huì)被及時(shí)處理。

　　由于作業(yè)的長(zhǎng)短只是根據(jù)用戶所提供的估計(jì)執(zhí)行時(shí)間而定的，而用戶又可能會(huì)有意或無(wú)意地縮短其作業(yè)的估計(jì)運(yùn)行時(shí)間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。

　　注意，SJF調(diào)度算法的平均等待時(shí)間、平均周轉(zhuǎn)時(shí)間最少。

　　優(yōu)先級(jí)調(diào)度算法

　　優(yōu)先級(jí)調(diào)度算法又稱優(yōu)先權(quán)調(diào)度算法，該算法既可以用于作業(yè)調(diào)度，也可以用于進(jìn)程調(diào)度，該算法中的優(yōu)先級(jí)用于描述作業(yè)運(yùn)行的緊迫程度。

　　在作業(yè)調(diào)度中，優(yōu)先級(jí)調(diào)度算法每次從后備作業(yè)隊(duì)列中選擇優(yōu)先級(jí)最髙的一個(gè)或幾個(gè)作業(yè)，將它們調(diào)入內(nèi)存，分配必要的資源，創(chuàng)建進(jìn)程并放入就緒隊(duì)列。在進(jìn)程調(diào)度中，優(yōu)先級(jí)調(diào)度算法每次從就緒隊(duì)列中選擇優(yōu)先級(jí)最高的進(jìn)程，將處理機(jī)分配給它，使之投入運(yùn)行。

　　根據(jù)新的更高優(yōu)先級(jí)進(jìn)程能否搶占正在執(zhí)行的進(jìn)程，可將該調(diào)度算法分為：

　　非剝奪式優(yōu)先級(jí)調(diào)度算法。當(dāng)某一個(gè)進(jìn)程正在處理機(jī)上運(yùn)行時(shí)，即使有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，仍然讓正在運(yùn)行的進(jìn)程繼續(xù)運(yùn)行，直到由于其自身的原因而主動(dòng)讓出處理機(jī)時(shí)(任務(wù)完成或等待事件)，才把處理機(jī)分配給更為重要或緊迫的進(jìn)程。

　　剝奪式優(yōu)先級(jí)調(diào)度算法。當(dāng)一個(gè)進(jìn)程正在處理機(jī)上運(yùn)行時(shí)，若有某個(gè)更為重要或緊迫的進(jìn)程進(jìn)入就緒隊(duì)列，則立即暫停正在運(yùn)行的進(jìn)程，將處理機(jī)分配給更重要或緊迫的進(jìn)程。

　　而根據(jù)進(jìn)程創(chuàng)建后其優(yōu)先級(jí)是否可以改變，可以將進(jìn)程優(yōu)先級(jí)分為以下兩種：

　　靜態(tài)優(yōu)先級(jí)。優(yōu)先級(jí)是在創(chuàng)建進(jìn)程時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。確定靜態(tài)優(yōu)先級(jí)的主要依據(jù)有進(jìn)程類型、進(jìn)程對(duì)資源的要求、用戶要求。

　　動(dòng)態(tài)優(yōu)先級(jí)。在進(jìn)程運(yùn)行過(guò)程中，根據(jù)進(jìn)程情況的變化動(dòng)態(tài)調(diào)整優(yōu)先級(jí)。動(dòng)態(tài)調(diào)整優(yōu)先級(jí)的主要依據(jù)為進(jìn)程占有CPU時(shí)間的長(zhǎng)短、就緒進(jìn)程等待CPU時(shí)間的長(zhǎng)短。

　　高響應(yīng)比優(yōu)先調(diào)度算法

　　高響應(yīng)比優(yōu)先調(diào)度算法主要用于作業(yè)調(diào)度，該算法是對(duì)FCFS調(diào)度算法和SJF調(diào)度算法的一種綜合平衡，同時(shí)考慮每個(gè)作業(yè)的等待時(shí)間和估計(jì)的運(yùn)行時(shí)間。在每次進(jìn)行作業(yè)調(diào)度時(shí)，先計(jì)算后備作業(yè)隊(duì)列中每個(gè)作業(yè)的響應(yīng)比，從中選出響應(yīng)比最高的作業(yè)投入運(yùn)行。

　　根據(jù)公式可知：

　　當(dāng)作業(yè)的等待時(shí)間相同時(shí)，則要求服務(wù)時(shí)間越短，其響應(yīng)比越高，有利于短作業(yè)。

　　當(dāng)要求服務(wù)時(shí)間相同時(shí)，作業(yè)的響應(yīng)比由其等待時(shí)間決定，等待時(shí)間越長(zhǎng)，其響應(yīng)比越高，因而它實(shí)現(xiàn)的是先來(lái)先服務(wù)。

　　對(duì)于長(zhǎng)作業(yè)，作業(yè)的響應(yīng)比可以隨等待時(shí)間的增加而提高，當(dāng)其等待時(shí)間足夠長(zhǎng)時(shí)，其響應(yīng)比便可升到很高，從而也可獲得處理機(jī)。克服了饑餓狀態(tài)，兼顧了長(zhǎng)作業(yè)。

　　時(shí)間片輪轉(zhuǎn)調(diào)度算法

　　時(shí)間片輪轉(zhuǎn)調(diào)度算法主要適用于分時(shí)系統(tǒng)。在這種算法中，系統(tǒng)將所有就緒進(jìn)程按到達(dá)時(shí)間的先后次序排成一個(gè)隊(duì)列，進(jìn)程調(diào)度程序總是選擇就緒隊(duì)列中第一個(gè)進(jìn)程執(zhí)行，即先來(lái)先服務(wù)的原則，但僅能運(yùn)行一個(gè)時(shí)間片，如100ms。在使用完一個(gè)時(shí)間片后，即使進(jìn)程并未完成其運(yùn)行，它也必須釋放出(被剝奪)處理機(jī)給下一個(gè)就緒的進(jìn)程，而被剝奪的進(jìn)程返回到就緒隊(duì)列的末尾重新排隊(duì)，等候再次運(yùn)行。

　　在時(shí)間片輪轉(zhuǎn)調(diào)度算法中，時(shí)間片的大小對(duì)系統(tǒng)性能的影響很大。如果時(shí)間片足夠大，以至于所有進(jìn)程都能在一個(gè)時(shí)間片內(nèi)執(zhí)行完畢，則時(shí)間片輪轉(zhuǎn)調(diào)度算法就退化為先來(lái)先服務(wù)調(diào)度算法。如果時(shí)間片很小，那么處理機(jī)將在進(jìn)程間過(guò)于頻繁切換，使處理機(jī)的開(kāi)銷增大，而真正用于運(yùn)行用戶進(jìn)程的時(shí)間將減少。因此時(shí)間片的大小應(yīng)選擇適當(dāng)。

　　時(shí)間片的長(zhǎng)短通常由以下因素確定：系統(tǒng)的響應(yīng)時(shí)間、就緒隊(duì)列中的進(jìn)程數(shù)目和系統(tǒng)的處理能力。

　　多級(jí)反饋隊(duì)列調(diào)度算法(集合了前幾種算法的優(yōu)點(diǎn))

　　多級(jí)反饋隊(duì)列調(diào)度算法是時(shí)間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級(jí)調(diào)度算法的綜合和發(fā)展，如圖2-5 所示。通過(guò)動(dòng)態(tài)調(diào)整進(jìn)程優(yōu)先級(jí)和時(shí)間片大小，多級(jí)反饋隊(duì)列調(diào)度算法可以兼顧多方面的系統(tǒng)目標(biāo)。例如，為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時(shí)間而照顧短進(jìn)程;為獲得較好的I/O設(shè)備利用率和縮短響應(yīng)時(shí)間而照顧I/O型進(jìn)程;同時(shí)，也不必事先估計(jì)進(jìn)程的執(zhí)行時(shí)間。

　　多級(jí)反饋隊(duì)列調(diào)度算法

　　多級(jí)反饋隊(duì)列調(diào)度算法的實(shí)現(xiàn)思想如下：

　　1.應(yīng)設(shè)置多個(gè)就緒隊(duì)列，并為各個(gè)隊(duì)列賦予不同的優(yōu)先級(jí)，第1級(jí)隊(duì)列的優(yōu)先級(jí)最高，第2級(jí)隊(duì)列次之，其余隊(duì)列的優(yōu)先級(jí)逐次降低。

　　2.賦予各個(gè)隊(duì)列中進(jìn)程執(zhí)行時(shí)間片的大小也各不相同，在優(yōu)先級(jí)越高的隊(duì)列中，每個(gè)進(jìn)程的運(yùn)行時(shí)間片就越小。例如，第2級(jí)隊(duì)列的時(shí)間片要比第1級(jí)隊(duì)列的時(shí)間片長(zhǎng)一倍， ……第i+1級(jí)隊(duì)列的時(shí)間片要比第i級(jí)隊(duì)列的時(shí)間片長(zhǎng)一倍。

　　3.當(dāng)一個(gè)新進(jìn)程進(jìn)入內(nèi)存后，首先將它放入第1級(jí)隊(duì)列的末尾，按FCFS原則排隊(duì)等待調(diào)度。當(dāng)輪到該進(jìn)程執(zhí)行時(shí)，如它能在該時(shí)間片內(nèi)完成，便可準(zhǔn)備撤離系統(tǒng);如果它在一個(gè)時(shí)間片結(jié)束時(shí)尚未完成，調(diào)度程序便將該進(jìn)程轉(zhuǎn)入第2級(jí)隊(duì)列的末尾，再同樣地按FCFS 原則等待調(diào)度執(zhí)行;如果它在第2級(jí)隊(duì)列中運(yùn)行一個(gè)時(shí)間片后仍未完成，再以同樣的方法放入第3級(jí)隊(duì)列……如此下去，當(dāng)一個(gè)長(zhǎng)進(jìn)程從第1級(jí)隊(duì)列依次降到第 n 級(jí)隊(duì)列后，在第 n 級(jí)隊(duì)列中便釆用時(shí)間片輪轉(zhuǎn)的方式運(yùn)行。

　　4.僅當(dāng)?shù)?級(jí)隊(duì)列為空時(shí)，調(diào)度程序才調(diào)度第2級(jí)隊(duì)列中的進(jìn)程運(yùn)行;僅當(dāng)?shù)? ~ (i-1)級(jí)隊(duì)列均為空時(shí)，才會(huì)調(diào)度第i級(jí)隊(duì)列中的進(jìn)程運(yùn)行。如果處理機(jī)正在執(zhí)行第i級(jí)隊(duì)列中的某進(jìn)程時(shí)，又有新進(jìn)程進(jìn)入優(yōu)先級(jí)較高的隊(duì)列(第 1 ~ (i-1)中的任何一個(gè)隊(duì)列)，則此時(shí)新進(jìn)程將搶占正在運(yùn)行進(jìn)程的處理機(jī)，即由調(diào)度程序把正在運(yùn)行的進(jìn)程放回到第i級(jí)隊(duì)列的末尾，把處理機(jī)分配給新到的更高優(yōu)先級(jí)的進(jìn)程。

　　多級(jí)反饋隊(duì)列的優(yōu)勢(shì)有：

　　終端型作業(yè)用戶：短作業(yè)優(yōu)先。

　　短批處理作業(yè)用戶：周轉(zhuǎn)時(shí)間較短。

　　長(zhǎng)批處理作業(yè)用戶：經(jīng)過(guò)前面幾個(gè)隊(duì)列得到部分執(zhí)行，不會(huì)長(zhǎng)期得不到處理。

　　操作系統(tǒng)算法的都有哪些(二)

　　學(xué)了半個(gè)學(xué)期的《操作系統(tǒng)》，是不是感覺(jué)“恍恍惚惚”?這周學(xué)的“銀行家算法”是不是很多同學(xué)被繞暈了?作業(yè)也讓人迷糊?那今天小編就給大家梳理梳理!

　　啥是銀行家算法?

　　銀行家算法是一種用來(lái)避免操作系統(tǒng)死鎖出現(xiàn)的有效算法。為了讓大家更好的理解，我們?cè)诮忉尅般y行家算法”之前，先跟大家說(shuō)說(shuō)“死鎖”的概念。

　　死鎖?

　　是指兩個(gè)或兩個(gè)以上的進(jìn)程在執(zhí)行過(guò)程中，由于競(jìng)爭(zhēng)資源或者由于彼此通信而造成的一種阻塞的現(xiàn)象，若無(wú)外力作用，它們都將無(wú)法推進(jìn)下去。此時(shí)稱系統(tǒng)處于死鎖狀態(tài)或系統(tǒng)產(chǎn)生了死鎖，這些永遠(yuǎn)在互相等待的進(jìn)程稱為死鎖進(jìn)程。

　　死鎖產(chǎn)生的四個(gè)必要條件：

　　1) 互斥條件：在一段時(shí)間內(nèi)某資源只由一個(gè)進(jìn)程占用。如果此時(shí)還有其它進(jìn)程請(qǐng)求資源，則請(qǐng)求者只能等待，直至占有資源的進(jìn)程用畢釋放。

　　2) 請(qǐng)求和保持條件：指進(jìn)程已經(jīng)保持至少一個(gè)資源，但又提出了新的資源請(qǐng)求，而該資源已被其它進(jìn)程占有，此時(shí)請(qǐng)求進(jìn)程阻塞，但又對(duì)自己已獲得的其它資源保持不放。

　　3) 不搶占條件：指進(jìn)程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時(shí)由自己釋放。

　　4) 循環(huán)等待條件：指在發(fā)生死鎖時(shí)，必然存在一個(gè)進(jìn)程——資源的環(huán)形鏈，即進(jìn)程集合{P0，P1，P2，···，Pn}中的P0正在等待一個(gè)P1占用的資源;P1正在等待P2占用的資源，……，Pn正在等待已被P0占用的資源。

　　為實(shí)現(xiàn)“銀行家算法”，系統(tǒng)必須設(shè)置若干數(shù)據(jù)結(jié)構(gòu)。想更好解釋“銀行家算法”，那就得先跟大家先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)，以及安全序列。

　　安全序列：

　　是指一個(gè)進(jìn)程序列{P1，…，Pn}是安全的，即對(duì)于每一個(gè)進(jìn)程Pi(1≤i≤n)，它以后尚需要的資源量不超過(guò)系統(tǒng)當(dāng)前剩余資源量與所有進(jìn)程Pj (j < i )當(dāng)前占有資源量之和。

　　安全狀態(tài)：

　　如果存在一個(gè)由系統(tǒng)中所有進(jìn)程構(gòu)成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒(méi)有死鎖發(fā)生。

　　不安全狀態(tài)：

　　不存在一個(gè)安全序列。不安全狀態(tài)不一定導(dǎo)致死鎖。

　　接下來(lái)跟大家解釋一下“銀行家算法”的數(shù)據(jù)結(jié)構(gòu)與兩個(gè)向量!

　　數(shù)據(jù)結(jié)構(gòu)：

　　1)可利用資源向量Available

　　是個(gè)含有m個(gè)元素的數(shù)組，其中的每一個(gè)元素代表一類可利用的資源數(shù)目。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個(gè)。

　　2)最大需求矩陣Max

　　這是一個(gè)n×m的矩陣，它定義了系統(tǒng)中n個(gè)進(jìn)程中的每一個(gè)進(jìn)程對(duì)m類資源的最大需求。如果Max[i,j]=K，則表示進(jìn)程i需要Rj類資源的最大數(shù)目為K。

　　3)分配矩陣Allocation

　　這也是一個(gè)n×m的矩陣，它定義了系統(tǒng)中每一類資源當(dāng)前已分配給每一進(jìn)程的資源數(shù)。如果Allocation[i,j]=K，則表示進(jìn)程i當(dāng)前已分得Rj類資源的 數(shù)目為K。

　　4)需求矩陣Need

　　這也是一個(gè)n×m的矩陣，用以表示每一個(gè)進(jìn)程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進(jìn)程i還需要Rj類資源K個(gè)，方能完成其任務(wù)。

　　下面是三者之間的關(guān)系:

　　Need[i,j]=Max[i,j]-Allocation[i,j]

　　兩個(gè)向量：

　　1)工作向量Work：表示系統(tǒng)可提供給進(jìn)程繼續(xù)運(yùn)行所需的各類資源數(shù)目，安全算法開(kāi)始時(shí)，Work:=Available。

　　2)Finish[]：表示系統(tǒng)是否有足夠的資源分配給進(jìn)程,使之運(yùn)行完成。開(kāi)始時(shí)先令Finish[i]:=false，當(dāng)有足夠資源分配給進(jìn)程時(shí)，再令Finish[i]:=true。

　　一些細(xì)小的知識(shí)點(diǎn)，上面已經(jīng)解釋得差不多了!接下來(lái)開(kāi)始跟大家解釋“銀行家算法”啦!

　　銀行家算法：

　　設(shè)Request(i)是進(jìn)程Pi的請(qǐng)求向量，如果Request(i)[j]=k，表示進(jìn)程Pi需要K個(gè)R(j)類型的資源。當(dāng)Pi發(fā)現(xiàn)資源請(qǐng)求后系統(tǒng)將進(jìn)行下列步驟

　　(1)如果Request(i)[j] <= Need[i,j],邊轉(zhuǎn)向步驟2),否則認(rèn)為出錯(cuò)，因?yàn)樗?qǐng)求的資源數(shù)已超過(guò)它所宣布的最大值。

　　(2)如果Request(i)[j] <= Available[i,j]，便轉(zhuǎn)向步驟3)，否則，表示尚無(wú)足夠資源，Pi需等待。

　　(3)系統(tǒng)試探著把資源分配給進(jìn)程Pi，并需要修改下面數(shù)據(jù)結(jié)構(gòu)中的數(shù)值;

　　Available[j] = Available[j] - Request(i)[j];

　　Allocation[i,j] = Allocation[i,j] + Request(i)[j];

　　Need[i,j] = Need[i,j] - Request(i)[j];

　　(4)系統(tǒng)執(zhí)行安全性算法,檢查此次資源分配后,系統(tǒng)是否處于安全狀態(tài)。

　　所有關(guān)于“銀行家算法”的概念都解釋完畢啦!接下來(lái)讓我們來(lái)“實(shí)踐檢驗(yàn)真理”!

　　操作系統(tǒng)算法的都有哪些(三)

　　磁盤調(diào)度在多道程序設(shè)計(jì)的計(jì)算機(jī)系統(tǒng)中，各個(gè)進(jìn)程可能會(huì)不斷提出不同的對(duì)磁盤進(jìn)行讀/寫操作的請(qǐng)求。由于有時(shí)候這些進(jìn)程的發(fā)送請(qǐng)求的速度比磁盤響應(yīng)的還要快，因此我們有必要為每個(gè)磁盤設(shè)備建立一個(gè)等待隊(duì)列，常用的磁盤調(diào)度算法有以下四種：

　　先來(lái)先服務(wù)算法(FCFS )，

　　最短尋道時(shí)間優(yōu)先算法(SSTF )，

　　掃描算法(SCAN )，

　　循環(huán)掃描算法(CSCAN )

　　例: 假定某磁盤共有200個(gè)柱面，編號(hào)為 0-199，如果在為訪問(wèn) 143 號(hào)柱面的請(qǐng)求者服務(wù)后，當(dāng)前正在為訪問(wèn) 125 號(hào)柱面的請(qǐng)求服務(wù)，同時(shí)有若干請(qǐng)求者在等待服務(wù)，它們每次要訪問(wèn)的柱面號(hào)為 86 ，147 ，91 ，177 ，94 ，150 ，102， 175 ，130

　　1 、先來(lái)先服務(wù)算法(FCFS )First Come First Service

　　這是一種比較簡(jiǎn)單的磁盤調(diào)度算法。它根據(jù)進(jìn)程請(qǐng)求訪問(wèn)磁盤的先后次序進(jìn)行調(diào)度。此算法的優(yōu)點(diǎn)是公平、簡(jiǎn)單，且每個(gè)進(jìn)程的請(qǐng)求都能依次得到處理，不會(huì)出現(xiàn)某一進(jìn)程的請(qǐng)求長(zhǎng)期得不到滿足的情況。此算法由于未對(duì)尋道進(jìn)行優(yōu)化，在對(duì)磁盤的訪問(wèn)請(qǐng)求比較多的情況下，此算法將降低設(shè)備服務(wù)的吞吐量，致使平均尋道時(shí)間可能較長(zhǎng)，但各進(jìn)程得到服務(wù)的響應(yīng)時(shí)間的變化幅度較小。

　　先來(lái)先服務(wù) (125)86.147.91.177.94.150.102.175.130

　　2 、最短尋道時(shí)間優(yōu)先算法(SSTF ) Shortest Seek Time First

　　該算法選擇這樣的進(jìn)程，其要求訪問(wèn)的磁道與當(dāng)前磁頭所在的磁道距離最近，以使每次的尋道時(shí)間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時(shí)間最短。其缺點(diǎn)是對(duì)用戶的服務(wù)請(qǐng)求的響應(yīng)機(jī)會(huì)不是均等的，因而導(dǎo)致響應(yīng)時(shí)間的變化幅度很大。在服務(wù)請(qǐng)求很多的情況下，對(duì)內(nèi)外邊緣磁道的請(qǐng)求將會(huì)無(wú)限期的被延遲，有些請(qǐng)求的響應(yīng)時(shí)間將不可預(yù)期。

　　最短尋道時(shí)間優(yōu)先(125)130.147.150.175.177.102.94.91.86

　　3 、掃描算法(SCAN )電梯調(diào)度

　　掃描算法不僅考慮到欲訪問(wèn)的磁道與當(dāng)前磁道的距離，更優(yōu)先考慮的是磁頭的當(dāng)前移動(dòng)方向。例如，當(dāng)磁頭正在自里向外移動(dòng)時(shí)，掃描算法所選擇的下一個(gè)訪問(wèn)對(duì)象應(yīng)是其欲訪問(wèn)的磁道既在當(dāng)前磁道之外，又是距離最近的。這樣自里向外地訪問(wèn)，直到再無(wú)更外的磁道需要訪問(wèn)才將磁臂換向，自外向里移動(dòng)。這時(shí)，同樣也是每次選擇這樣的進(jìn)程來(lái)調(diào)度，即其要訪問(wèn)的磁道，在當(dāng)前磁道之內(nèi)，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動(dòng)的規(guī)律頗似電梯的運(yùn)行，故又稱為電梯調(diào)度算法。此算法基本上克服了最短尋道時(shí)間優(yōu)先算法的服務(wù)集中于中間磁道和響應(yīng)時(shí)間變化比較大的缺點(diǎn)，而具有最短尋道時(shí)間優(yōu)先算法的優(yōu)點(diǎn)即吞吐量較大，平均響應(yīng)時(shí)間較小，但由于是擺動(dòng)式的掃描方法，兩側(cè)磁道被訪問(wèn)的頻率仍低于中間磁道。

　　電梯調(diào)度(125)102.94.91.86.130.147.150.175.177

　　4 、循環(huán)掃描算法(CSCAN )

　　循環(huán)掃描算法是對(duì)掃描算法的改進(jìn)。如果對(duì)磁道的訪問(wèn)請(qǐng)求是均勻分布的，當(dāng)磁頭到達(dá)磁盤的一端，并反向運(yùn)動(dòng)時(shí)落在磁頭之后的訪問(wèn)請(qǐng)求相對(duì)較少。這是由于這些磁道剛被處理，而磁盤另一端的請(qǐng)求密度相當(dāng)高，且這些訪問(wèn)請(qǐng)求等待的時(shí)間較長(zhǎng)，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向移動(dòng)。例如，只自里向外移動(dòng)，當(dāng)磁頭移到最外的被訪問(wèn)磁道時(shí)，磁頭立即返回到最里的欲訪磁道，即將最小磁道號(hào)緊接著最大磁道號(hào)構(gòu)成循環(huán)，進(jìn)行掃描。

　　循環(huán)掃描 (125)130.147.150.175.177.86.91.94.102

　　5 、平均尋道距離

　　假設(shè)當(dāng)前磁頭在 67 號(hào)，要求訪問(wèn)的磁道號(hào)順序?yàn)?98,25,63,97,56,51,55,55,6

　　FIFO 算法的服務(wù)序列是：98,25,63,97,56,51,55,55,6

　　磁頭移動(dòng)的總距離 distance =

　　(98-67)+(98-25)+(63-25)+(97-63)+(97-56)+(56-51)+(55-51)+(55-55)+(55-6)

　　SSTF 算法的服務(wù)序列是: 63,56,55,55,51,25,6,97,98

　　磁頭移動(dòng)的總距離 distance =

　　(67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(97-6)+(98-97)

　　SCAN 算法的服務(wù)序列是：63,56,55,55,51,25,6,97,98

　　磁頭移動(dòng)的總距離 distance =

　　(67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(97-6)+(98-97)

　　我發(fā)現(xiàn)這里例子舉的不好，SSTF 和 SCAN 算法的服務(wù)序列竟是一樣的，尷

　　尬!

　　CSCAN 算法的服務(wù)序列是：63,56,55,55,51,25,6,98,97

　　磁頭移動(dòng)的總距離 distance =

　　(67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(100-98)+(98-97)