操作系統(tǒng)算法的都有哪些
操作系統(tǒng)算法的都有哪些
操作系統(tǒng)(英語：operating system，縮寫作 OS)是管理計算機硬件與軟件資源的計算機程序，同時也是計算機系統(tǒng)的內(nèi)核與基石。操作系統(tǒng)需要處理如管理與配置內(nèi)存、決定系統(tǒng)資源供需的優(yōu)先次序、控制輸入設備與輸出設備、操作網(wǎng)絡與管理文件系統(tǒng)等基本事務。操作系統(tǒng)也提供一個讓用戶與系統(tǒng)交互的操作界面。操作系統(tǒng)的類型非常多樣，不同機器安裝的操作系統(tǒng)可從簡單到復雜，可從移動電話的嵌入式系統(tǒng)到超級計算機的大型操作系統(tǒng)。許多操作系統(tǒng)制造者對它涵蓋范疇的定義也不盡一致，例如有些操作系統(tǒng)集成了圖形用戶界面，而有些僅使用命令行界面，而將圖形用戶界面視為一種非必要的應用程序。下面是小編收集整理的操作系統(tǒng)算法的都有哪些范文，歡迎借鑒參考。
操作系統(tǒng)算法的都有哪些(一)
在操作系統(tǒng)中存在多種調(diào)度算法，其中有的調(diào)度算法適用于作業(yè)調(diào)度，有的調(diào)度算法適用于進程調(diào)度，有的調(diào)度算法兩者都適用。下面介紹幾種常用的調(diào)度算法。
先來先服務(FCFS)調(diào)度算法
FCFS調(diào)度算法是一種最簡單的調(diào)度算法，該調(diào)度算法既可以用于作業(yè)調(diào)度也可以用于進程調(diào)度。在作業(yè)調(diào)度中，算法每次從后備作業(yè)隊列中選擇最先進入該隊列的一個或幾個作業(yè)，將它們調(diào)入內(nèi)存，分配必要的資源，創(chuàng)建進程并放入就緒隊列。
在進程調(diào)度中，F(xiàn)CFS調(diào)度算法每次從就緒隊列中選擇最先進入該隊列的進程，將處理機分配給它，使之投入運行，直到完成或因某種原因而阻塞時才釋放處理機。
下面通過一個實例來說明FCFS調(diào)度算法的性能。假設系統(tǒng)中有4個作業(yè)，它們的提交時間分別是8、8.4、8.8、9，運行時間依次是2、1、0.5、0.2，系統(tǒng)釆用FCFS調(diào)度算法，這組作業(yè)的平均等待時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間見表2-3。
平均等待時間 t = (0+1.6+2.2+2.5)/4=1.575
平均周轉(zhuǎn)時間 T = (2+2.6+2.7+2.7)/4=2.5
平均帶權(quán)周轉(zhuǎn)時間 W = (1+2.6+5.牡13.5)/4=5.625
FCFS調(diào)度算法屬于不可剝奪算法。從表面上看，它對所有作業(yè)都是公平的，但若一個長作業(yè)先到達系統(tǒng)，就會使后面許多短作業(yè)等待很長時間，因此它不能作為分時系統(tǒng)和實時系統(tǒng)的主要調(diào)度策略。但它常被結(jié)合在其他調(diào)度策略中使用。例如，在使用優(yōu)先級作為調(diào)度策略的系統(tǒng)中，往往對多個具有相同優(yōu)先級的進程按FCFS原則處理。
FCFS調(diào)度算法的特點是算法簡單，但效率低;對長作業(yè)比較有利，但對短作業(yè)不利(相對SJF和高響應比);有利于CPU繁忙型作業(yè)，而不利于I/O繁忙型作業(yè)。
短作業(yè)優(yōu)先(SJF)調(diào)度算法
短作業(yè)(進程)優(yōu)先調(diào)度算法是指對短作業(yè)(進程)優(yōu)先調(diào)度的算法。短作業(yè)優(yōu)先(SJF)調(diào)度算法是從后備隊列中選擇一個或若干個估計運行時間最短的作業(yè)，將它們調(diào)入內(nèi)存運行。而短進程優(yōu)先(SPF)調(diào)度算法，則是從就緒隊列中選擇一個估計運行時間最短的進程，將處理機分配給它，使之立即執(zhí)行，直到完成或發(fā)生某事件而阻塞時，才釋放處理機。
例如，考慮表2-3中給出的一組作業(yè)，若系統(tǒng)釆用短作業(yè)優(yōu)先調(diào)度算法，其平均等待時間、平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間見表2-4。
平均等待時間 t = (0+2.3+1.4+1)/4=1.175
平均周轉(zhuǎn)時間 T = (2+3.3+1.9+1.2)/4=2.1
平均帶權(quán)周轉(zhuǎn)時間 W = (1+3.3+3.8+6)/4=3.525
SJF調(diào)度算法也存在不容忽視的缺點：
該算法對長作業(yè)不利，由表2-3和表2-4可知，SJF調(diào)度算法中長作業(yè)的周轉(zhuǎn)時間會增加。更嚴重的是，如果有一長作業(yè)進入系統(tǒng)的后備隊列，由于調(diào)度程序總是優(yōu)先調(diào)度那些 (即使是后進來的)短作業(yè)，將導致長作業(yè)長期不被調(diào)度(“饑餓”現(xiàn)象，注意區(qū)分“死鎖”。后者是系統(tǒng)環(huán)形等待，前者是調(diào)度策略問題)。
該算法完全未考慮作業(yè)的緊迫程度，因而不能保證緊迫性作業(yè)會被及時處理。
由于作業(yè)的長短只是根據(jù)用戶所提供的估計執(zhí)行時間而定的，而用戶又可能會有意或無意地縮短其作業(yè)的估計運行時間，致使該算法不一定能真正做到短作業(yè)優(yōu)先調(diào)度。
注意，SJF調(diào)度算法的平均等待時間、平均周轉(zhuǎn)時間最少。
優(yōu)先級調(diào)度算法
優(yōu)先級調(diào)度算法又稱優(yōu)先權(quán)調(diào)度算法，該算法既可以用于作業(yè)調(diào)度，也可以用于進程調(diào)度，該算法中的優(yōu)先級用于描述作業(yè)運行的緊迫程度。
在作業(yè)調(diào)度中，優(yōu)先級調(diào)度算法每次從后備作業(yè)隊列中選擇優(yōu)先級最髙的一個或幾個作業(yè)，將它們調(diào)入內(nèi)存，分配必要的資源，創(chuàng)建進程并放入就緒隊列。在進程調(diào)度中，優(yōu)先級調(diào)度算法每次從就緒隊列中選擇優(yōu)先級最高的進程，將處理機分配給它，使之投入運行。
根據(jù)新的更高優(yōu)先級進程能否搶占正在執(zhí)行的進程，可將該調(diào)度算法分為：
非剝奪式優(yōu)先級調(diào)度算法。當某一個進程正在處理機上運行時，即使有某個更為重要或緊迫的進程進入就緒隊列，仍然讓正在運行的進程繼續(xù)運行，直到由于其自身的原因而主動讓出處理機時(任務完成或等待事件)，才把處理機分配給更為重要或緊迫的進程。
剝奪式優(yōu)先級調(diào)度算法。當一個進程正在處理機上運行時，若有某個更為重要或緊迫的進程進入就緒隊列，則立即暫停正在運行的進程，將處理機分配給更重要或緊迫的進程。
而根據(jù)進程創(chuàng)建后其優(yōu)先級是否可以改變，可以將進程優(yōu)先級分為以下兩種：
靜態(tài)優(yōu)先級。優(yōu)先級是在創(chuàng)建進程時確定的，且在進程的整個運行期間保持不變。確定靜態(tài)優(yōu)先級的主要依據(jù)有進程類型、進程對資源的要求、用戶要求。
動態(tài)優(yōu)先級。在進程運行過程中，根據(jù)進程情況的變化動態(tài)調(diào)整優(yōu)先級。動態(tài)調(diào)整優(yōu)先級的主要依據(jù)為進程占有CPU時間的長短、就緒進程等待CPU時間的長短。
高響應比優(yōu)先調(diào)度算法
高響應比優(yōu)先調(diào)度算法主要用于作業(yè)調(diào)度，該算法是對FCFS調(diào)度算法和SJF調(diào)度算法的一種綜合平衡，同時考慮每個作業(yè)的等待時間和估計的運行時間。在每次進行作業(yè)調(diào)度時，先計算后備作業(yè)隊列中每個作業(yè)的響應比，從中選出響應比最高的作業(yè)投入運行。
根據(jù)公式可知：
當作業(yè)的等待時間相同時，則要求服務時間越短，其響應比越高，有利于短作業(yè)。
當要求服務時間相同時，作業(yè)的響應比由其等待時間決定，等待時間越長，其響應比越高，因而它實現(xiàn)的是先來先服務。
對于長作業(yè)，作業(yè)的響應比可以隨等待時間的增加而提高，當其等待時間足夠長時，其響應比便可升到很高，從而也可獲得處理機?？朔损囸I狀態(tài)，兼顧了長作業(yè)。
時間片輪轉(zhuǎn)調(diào)度算法
時間片輪轉(zhuǎn)調(diào)度算法主要適用于分時系統(tǒng)。在這種算法中，系統(tǒng)將所有就緒進程按到達時間的先后次序排成一個隊列，進程調(diào)度程序總是選擇就緒隊列中第一個進程執(zhí)行，即先來先服務的原則，但僅能運行一個時間片，如100ms。在使用完一個時間片后，即使進程并未完成其運行，它也必須釋放出(被剝奪)處理機給下一個就緒的進程，而被剝奪的進程返回到就緒隊列的末尾重新排隊，等候再次運行。
在時間片輪轉(zhuǎn)調(diào)度算法中，時間片的大小對系統(tǒng)性能的影響很大。如果時間片足夠大，以至于所有進程都能在一個時間片內(nèi)執(zhí)行完畢，則時間片輪轉(zhuǎn)調(diào)度算法就退化為先來先服務調(diào)度算法。如果時間片很小，那么處理機將在進程間過于頻繁切換，使處理機的開銷增大，而真正用于運行用戶進程的時間將減少。因此時間片的大小應選擇適當。
時間片的長短通常由以下因素確定：系統(tǒng)的響應時間、就緒隊列中的進程數(shù)目和系統(tǒng)的處理能力。
多級反饋隊列調(diào)度算法(集合了前幾種算法的優(yōu)點)
多級反饋隊列調(diào)度算法是時間片輪轉(zhuǎn)調(diào)度算法和優(yōu)先級調(diào)度算法的綜合和發(fā)展，如圖2-5 所示。通過動態(tài)調(diào)整進程優(yōu)先級和時間片大小，多級反饋隊列調(diào)度算法可以兼顧多方面的系統(tǒng)目標。例如，為提高系統(tǒng)吞吐量和縮短平均周轉(zhuǎn)時間而照顧短進程;為獲得較好的I/O設備利用率和縮短響應時間而照顧I/O型進程;同時，也不必事先估計進程的執(zhí)行時間。
多級反饋隊列調(diào)度算法
多級反饋隊列調(diào)度算法的實現(xiàn)思想如下：
1.應設置多個就緒隊列，并為各個隊列賦予不同的優(yōu)先級，第1級隊列的優(yōu)先級最高，第2級隊列次之，其余隊列的優(yōu)先級逐次降低。
2.賦予各個隊列中進程執(zhí)行時間片的大小也各不相同，在優(yōu)先級越高的隊列中，每個進程的運行時間片就越小。例如，第2級隊列的時間片要比第1級隊列的時間片長一倍， ……第i+1級隊列的時間片要比第i級隊列的時間片長一倍。
3.當一個新進程進入內(nèi)存后，首先將它放入第1級隊列的末尾，按FCFS原則排隊等待調(diào)度。當輪到該進程執(zhí)行時，如它能在該時間片內(nèi)完成，便可準備撤離系統(tǒng);如果它在一個時間片結(jié)束時尚未完成，調(diào)度程序便將該進程轉(zhuǎn)入第2級隊列的末尾，再同樣地按FCFS 原則等待調(diào)度執(zhí)行;如果它在第2級隊列中運行一個時間片后仍未完成，再以同樣的方法放入第3級隊列……如此下去，當一個長進程從第1級隊列依次降到第 n 級隊列后，在第 n 級隊列中便釆用時間片輪轉(zhuǎn)的方式運行。
4.僅當?shù)?級隊列為空時，調(diào)度程序才調(diào)度第2級隊列中的進程運行;僅當?shù)? ~ (i-1)級隊列均為空時，才會調(diào)度第i級隊列中的進程運行。如果處理機正在執(zhí)行第i級隊列中的某進程時，又有新進程進入優(yōu)先級較高的隊列(第 1 ~ (i-1)中的任何一個隊列)，則此時新進程將搶占正在運行進程的處理機，即由調(diào)度程序把正在運行的進程放回到第i級隊列的末尾，把處理機分配給新到的更高優(yōu)先級的進程。
多級反饋隊列的優(yōu)勢有：
終端型作業(yè)用戶：短作業(yè)優(yōu)先。
短批處理作業(yè)用戶：周轉(zhuǎn)時間較短。
長批處理作業(yè)用戶：經(jīng)過前面幾個隊列得到部分執(zhí)行，不會長期得不到處理。
操作系統(tǒng)算法的都有哪些(二)
學了半個學期的《操作系統(tǒng)》，是不是感覺“恍恍惚惚”?這周學的“銀行家算法”是不是很多同學被繞暈了?作業(yè)也讓人迷糊?那今天小編就給大家梳理梳理!
啥是銀行家算法?
銀行家算法是一種用來避免操作系統(tǒng)死鎖出現(xiàn)的有效算法。為了讓大家更好的理解，我們在解釋“銀行家算法”之前，先跟大家說說“死鎖”的概念。
死鎖?
是指兩個或兩個以上的進程在執(zhí)行過程中，由于競爭資源或者由于彼此通信而造成的一種阻塞的現(xiàn)象，若無外力作用，它們都將無法推進下去。此時稱系統(tǒng)處于死鎖狀態(tài)或系統(tǒng)產(chǎn)生了死鎖，這些永遠在互相等待的進程稱為死鎖進程。
死鎖產(chǎn)生的四個必要條件：
1) 互斥條件：在一段時間內(nèi)某資源只由一個進程占用。如果此時還有其它進程請求資源，則請求者只能等待，直至占有資源的進程用畢釋放。
2) 請求和保持條件：指進程已經(jīng)保持至少一個資源，但又提出了新的資源請求，而該資源已被其它進程占有，此時請求進程阻塞，但又對自己已獲得的其它資源保持不放。
3) 不搶占條件：指進程已獲得的資源，在未使用完之前，不能被剝奪，只能在使用完時由自己釋放。
4) 循環(huán)等待條件：指在發(fā)生死鎖時，必然存在一個進程——資源的環(huán)形鏈，即進程集合{P0，P1，P2，···，Pn}中的P0正在等待一個P1占用的資源;P1正在等待P2占用的資源，……，Pn正在等待已被P0占用的資源。
為實現(xiàn)“銀行家算法”，系統(tǒng)必須設置若干數(shù)據(jù)結(jié)構(gòu)。想更好解釋“銀行家算法”，那就得先跟大家先解釋操作系統(tǒng)安全狀態(tài)和不安全狀態(tài)，以及安全序列。
安全序列：
是指一個進程序列{P1，…，Pn}是安全的，即對于每一個進程Pi(1≤i≤n)，它以后尚需要的資源量不超過系統(tǒng)當前剩余資源量與所有進程Pj (j < i )當前占有資源量之和。
安全狀態(tài)：
如果存在一個由系統(tǒng)中所有進程構(gòu)成的安全序列P1，…，Pn，則系統(tǒng)處于安全狀態(tài)。安全狀態(tài)一定是沒有死鎖發(fā)生。
不安全狀態(tài)：
不存在一個安全序列。不安全狀態(tài)不一定導致死鎖。
接下來跟大家解釋一下“銀行家算法”的數(shù)據(jù)結(jié)構(gòu)與兩個向量!
數(shù)據(jù)結(jié)構(gòu)：
1)可利用資源向量Available
是個含有m個元素的數(shù)組，其中的每一個元素代表一類可利用的資源數(shù)目。如果Available[j]=K，則表示系統(tǒng)中現(xiàn)有Rj類資源K個。
2)最大需求矩陣Max
這是一個n×m的矩陣，它定義了系統(tǒng)中n個進程中的每一個進程對m類資源的最大需求。如果Max[i,j]=K，則表示進程i需要Rj類資源的最大數(shù)目為K。
3)分配矩陣Allocation
這也是一個n×m的矩陣，它定義了系統(tǒng)中每一類資源當前已分配給每一進程的資源數(shù)。如果Allocation[i,j]=K，則表示進程i當前已分得Rj類資源的 數(shù)目為K。
4)需求矩陣Need
這也是一個n×m的矩陣，用以表示每一個進程尚需的各類資源數(shù)。如果Need[i,j]=K，則表示進程i還需要Rj類資源K個，方能完成其任務。
下面是三者之間的關(guān)系:
Need[i,j]=Max[i,j]-Allocation[i,j]
兩個向量：
1)工作向量Work：表示系統(tǒng)可提供給進程繼續(xù)運行所需的各類資源數(shù)目，安全算法開始時，Work:=Available。
2)Finish[]：表示系統(tǒng)是否有足夠的資源分配給進程,使之運行完成。開始時先令Finish[i]:=false，當有足夠資源分配給進程時，再令Finish[i]:=true。
一些細小的知識點，上面已經(jīng)解釋得差不多了!接下來開始跟大家解釋“銀行家算法”啦!
銀行家算法：
設Request(i)是進程Pi的請求向量，如果Request(i)[j]=k，表示進程Pi需要K個R(j)類型的資源。當Pi發(fā)現(xiàn)資源請求后系統(tǒng)將進行下列步驟
(1)如果Request(i)[j] <= Need[i,j],邊轉(zhuǎn)向步驟2),否則認為出錯，因為它所請求的資源數(shù)已超過它所宣布的最大值。
(2)如果Request(i)[j] <= Available[i,j]，便轉(zhuǎn)向步驟3)，否則，表示尚無足夠資源，Pi需等待。
(3)系統(tǒng)試探著把資源分配給進程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)于“銀行家算法”的概念都解釋完畢啦!接下來讓我們來“實踐檢驗真理”!
操作系統(tǒng)算法的都有哪些(三)
磁盤調(diào)度在多道程序設計的計算機系統(tǒng)中，各個進程可能會不斷提出不同的對磁盤進行讀/寫操作的請求。由于有時候這些進程的發(fā)送請求的速度比磁盤響應的還要快，因此我們有必要為每個磁盤設備建立一個等待隊列，常用的磁盤調(diào)度算法有以下四種：
先來先服務算法(FCFS )，
最短尋道時間優(yōu)先算法(SSTF )，
掃描算法(SCAN )，
循環(huán)掃描算法(CSCAN )
例: 假定某磁盤共有200個柱面，編號為 0-199，如果在為訪問 143 號柱面的請求者服務后，當前正在為訪問 125 號柱面的請求服務，同時有若干請求者在等待服務，它們每次要訪問的柱面號為 86 ，147 ，91 ，177 ，94 ，150 ，102， 175 ，130
1 、先來先服務算法(FCFS )First Come First Service
這是一種比較簡單的磁盤調(diào)度算法。它根據(jù)進程請求訪問磁盤的先后次序進行調(diào)度。此算法的優(yōu)點是公平、簡單，且每個進程的請求都能依次得到處理，不會出現(xiàn)某一進程的請求長期得不到滿足的情況。此算法由于未對尋道進行優(yōu)化，在對磁盤的訪問請求比較多的情況下，此算法將降低設備服務的吞吐量，致使平均尋道時間可能較長，但各進程得到服務的響應時間的變化幅度較小。
先來先服務 (125)86.147.91.177.94.150.102.175.130
2 、最短尋道時間優(yōu)先算法(SSTF ) Shortest Seek Time First
該算法選擇這樣的進程，其要求訪問的磁道與當前磁頭所在的磁道距離最近，以使每次的尋道時間最短，該算法可以得到比較好的吞吐量，但卻不能保證平均尋道時間最短。其缺點是對用戶的服務請求的響應機會不是均等的，因而導致響應時間的變化幅度很大。在服務請求很多的情況下，對內(nèi)外邊緣磁道的請求將會無限期的被延遲，有些請求的響應時間將不可預期。
最短尋道時間優(yōu)先(125)130.147.150.175.177.102.94.91.86
3 、掃描算法(SCAN )電梯調(diào)度
掃描算法不僅考慮到欲訪問的磁道與當前磁道的距離，更優(yōu)先考慮的是磁頭的當前移動方向。例如，當磁頭正在自里向外移動時，掃描算法所選擇的下一個訪問對象應是其欲訪問的磁道既在當前磁道之外，又是距離最近的。這樣自里向外地訪問，直到再無更外的磁道需要訪問才將磁臂換向，自外向里移動。這時，同樣也是每次選擇這樣的進程來調(diào)度，即其要訪問的磁道，在當前磁道之內(nèi)，從而避免了饑餓現(xiàn)象的出現(xiàn)。由于這種算法中磁頭移動的規(guī)律頗似電梯的運行，故又稱為電梯調(diào)度算法。此算法基本上克服了最短尋道時間優(yōu)先算法的服務集中于中間磁道和響應時間變化比較大的缺點，而具有最短尋道時間優(yōu)先算法的優(yōu)點即吞吐量較大，平均響應時間較小，但由于是擺動式的掃描方法，兩側(cè)磁道被訪問的頻率仍低于中間磁道。
電梯調(diào)度(125)102.94.91.86.130.147.150.175.177
4 、循環(huán)掃描算法(CSCAN )
循環(huán)掃描算法是對掃描算法的改進。如果對磁道的訪問請求是均勻分布的，當磁頭到達磁盤的一端，并反向運動時落在磁頭之后的訪問請求相對較少。這是由于這些磁道剛被處理，而磁盤另一端的請求密度相當高，且這些訪問請求等待的時間較長，為了解決這種情況，循環(huán)掃描算法規(guī)定磁頭單向移動。例如，只自里向外移動，當磁頭移到最外的被訪問磁道時，磁頭立即返回到最里的欲訪磁道，即將最小磁道號緊接著最大磁道號構(gòu)成循環(huán)，進行掃描。
循環(huán)掃描 (125)130.147.150.175.177.86.91.94.102
5 、平均尋道距離
假設當前磁頭在 67 號，要求訪問的磁道號順序為 98,25,63,97,56,51,55,55,6
FIFO 算法的服務序列是：98,25,63,97,56,51,55,55,6
磁頭移動的總距離 distance =
(98-67)+(98-25)+(63-25)+(97-63)+(97-56)+(56-51)+(55-51)+(55-55)+(55-6)
SSTF 算法的服務序列是: 63,56,55,55,51,25,6,97,98
磁頭移動的總距離 distance =
(67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(97-6)+(98-97)
SCAN 算法的服務序列是：63,56,55,55,51,25,6,97,98
磁頭移動的總距離 distance =
(67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(97-6)+(98-97)
我發(fā)現(xiàn)這里例子舉的不好，SSTF 和 SCAN 算法的服務序列竟是一樣的，尷
尬!
CSCAN 算法的服務序列是：63,56,55,55,51,25,6,98,97
磁頭移動的總距離 distance =
(67-63)+(63-56)+(56-55)+(55-55)+(55-51)+(51-25)+(25-6)+(100-98)+(98-97)