進(jìn)程的調(diào)度

進(jìn)程的調(diào)度是由操作系統(tǒng)完成的，其目的是為了在一個(gè)進(jìn)程占用CPU執(zhí)行自己的操作后，選擇下一個(gè)進(jìn)程來占用CPU。調(diào)度發(fā)生的原因很簡(jiǎn)單，每個(gè)進(jìn)程都希望能夠占用CPU進(jìn)行工作。因此，調(diào)度程序會(huì)進(jìn)行上下文切換，并選擇一個(gè)進(jìn)程來執(zhí)行其功能。

那么，什么時(shí)候進(jìn)行調(diào)度呢？調(diào)度的原則又是什么呢？

什么時(shí)候調(diào)度進(jìn)程

進(jìn)程的調(diào)度可以理解為在進(jìn)程的狀態(tài)發(fā)生變化時(shí)進(jìn)行。以下是一些進(jìn)程狀態(tài)的示例：

• 就緒態(tài) -> 運(yùn)行態(tài)：當(dāng)一個(gè)進(jìn)程被創(chuàng)建后，它進(jìn)入就緒隊(duì)列中等待執(zhí)行。當(dāng)操作系統(tǒng)從就緒隊(duì)列中選擇一個(gè)進(jìn)程時(shí)，它進(jìn)入運(yùn)行態(tài)并開始執(zhí)行。

• 運(yùn)行態(tài) -> 阻塞態(tài)：當(dāng)一個(gè)進(jìn)程執(zhí)行I/O操作時(shí)，它可能會(huì)進(jìn)入阻塞態(tài)，等待I/O操作完成。此時(shí)，操作系統(tǒng)會(huì)將當(dāng)前進(jìn)程放入阻塞隊(duì)列，并切換到其他可運(yùn)行的進(jìn)程繼續(xù)執(zhí)行。

• 運(yùn)行態(tài) -> 結(jié)束態(tài)：當(dāng)一個(gè)進(jìn)程完成其任務(wù)或遇到終止指令時(shí)，它會(huì)進(jìn)入結(jié)束態(tài)。操作系統(tǒng)會(huì)從就緒隊(duì)列中選擇下一個(gè)進(jìn)程進(jìn)行執(zhí)行。

因?yàn)檫M(jìn)程的狀態(tài)發(fā)生變化時(shí)，操作系統(tǒng)需要考慮是否切換進(jìn)程來占用CPU執(zhí)行業(yè)務(wù)。因此，只要進(jìn)程狀態(tài)發(fā)生變化，就會(huì)觸發(fā)進(jìn)程調(diào)度。

以什么原則來調(diào)度進(jìn)程

進(jìn)程調(diào)度的原則主要有以下五種：

CPU利用率：調(diào)度程序應(yīng)始終保持CPU處于繁忙狀態(tài)運(yùn)行，以提高CPU的利用率。

系統(tǒng)吞吐率：系統(tǒng)吞吐率是指在一定時(shí)間內(nèi)完成的進(jìn)程數(shù)量。調(diào)度程序應(yīng)盡量選擇能夠快速完成的進(jìn)程，以提高系統(tǒng)的吞吐率。

周轉(zhuǎn)時(shí)間：指一個(gè)進(jìn)程從創(chuàng)建到完成的總時(shí)間。調(diào)度程序應(yīng)盡量減少進(jìn)程的周轉(zhuǎn)時(shí)間，以提高系統(tǒng)的效率。也可以這么理解：周轉(zhuǎn)時(shí)間的計(jì)算公式為：周轉(zhuǎn)時(shí)間 = 完成時(shí)間 - 創(chuàng)建時(shí)間；

等待時(shí)間：等待時(shí)間并不是所謂的阻塞時(shí)間，而是在就緒隊(duì)列中等待被執(zhí)行的時(shí)間；

響應(yīng)時(shí)間：指用戶發(fā)出請(qǐng)求后系統(tǒng)作出響應(yīng)的時(shí)間。用戶與其交互這之間所產(chǎn)生的消耗時(shí)間越少，響應(yīng)越好；

就是一句話，進(jìn)程越快越短越好；

進(jìn)程調(diào)度算法

調(diào)度算法基本分為兩類：非搶占式調(diào)度算法、搶占式的調(diào)度算法；

非搶占式調(diào)度算法：這個(gè)算法就是之前說的所有進(jìn)程都進(jìn)行排隊(duì)等待，只有前面的進(jìn)程都執(zhí)行完了或者自己主動(dòng)讓出CPU，才可以輪到后面的進(jìn)程執(zhí)行。常見的非搶占式算法有：先來先服務(wù)（FCFS，F(xiàn)irst-Come, First-Served）和短作業(yè)優(yōu)先（SJF，Shortest Job First）等。

搶占式調(diào)度算法：也就是時(shí)間片機(jī)制，每個(gè)進(jìn)程都只占用CPU的一個(gè)時(shí)間片操作，執(zhí)行完了就必須讓出CPU使用權(quán)限給下一個(gè)進(jìn)程使用。常見的搶占式算法有：輪轉(zhuǎn)調(diào)度（Round Robin）、最短剩余時(shí)間優(yōu)先（SRTF，Shortest Remaining Time First）和優(yōu)先級(jí)調(diào)度等。

接下來我們?cè)敿?xì)看下各個(gè)調(diào)度算法的優(yōu)劣：

先來先服務(wù)

這個(gè)是一種最簡(jiǎn)單的進(jìn)程調(diào)度算法，所有進(jìn)程按照到達(dá)時(shí)間的先后順序排隊(duì)，先到達(dá)的進(jìn)程先被調(diào)度執(zhí)行。這種調(diào)度算法類似于Java中的隊(duì)列，采用先進(jìn)先出（FIFO）的原則。

這種調(diào)度算法存在一個(gè)明顯的問題，即如果一個(gè)進(jìn)程執(zhí)行時(shí)間較長(zhǎng)，后面的進(jìn)程就必須等待。

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

時(shí)間片輪轉(zhuǎn)調(diào)度是一種常見的進(jìn)程調(diào)度算法，它將CPU時(shí)間劃分為固定大小的時(shí)間片（也稱為時(shí)間量），每個(gè)進(jìn)程在一個(gè)時(shí)間片內(nèi)執(zhí)行，如果時(shí)間片用完后仍未執(zhí)行完，則被移至就緒隊(duì)列的末尾，等待下一輪調(diào)度。雖然解決了排隊(duì)產(chǎn)生的問題，但是時(shí)間片如何劃分呢？如果時(shí)間片過長(zhǎng)，可能會(huì)導(dǎo)致資源浪費(fèi)，因?yàn)槟承┻M(jìn)程可能只需要很短的時(shí)間就能執(zhí)行完畢，但它們?nèi)匀粫?huì)占用整個(gè)時(shí)間片。另一方面，如果時(shí)間片過短，會(huì)導(dǎo)致進(jìn)程切換的頻率增加，增加了上下文切換的開銷，可能降低系統(tǒng)的性能。因此時(shí)間片的長(zhǎng)度，需要有大致合理的數(shù)值。（《現(xiàn)代操作系統(tǒng)》的觀點(diǎn)是建議時(shí)間片長(zhǎng)度在20ms~50ms）。

最短作業(yè)優(yōu)先

最短作業(yè)優(yōu)先調(diào)度算法是一種非搶占式的調(diào)度算法，它根據(jù)進(jìn)程的執(zhí)行時(shí)間長(zhǎng)短進(jìn)行排隊(duì)，將作業(yè)時(shí)間短的進(jìn)程排在前面先執(zhí)行。

我都不知道進(jìn)程的執(zhí)行時(shí)間長(zhǎng)短的，系統(tǒng)咋知道的？其實(shí)系統(tǒng)通過預(yù)估進(jìn)程的執(zhí)行時(shí)間來進(jìn)行調(diào)度，一般可以使用過去的歷史執(zhí)行時(shí)間進(jìn)行估算。但是預(yù)估的準(zhǔn)不準(zhǔn)呢，那肯定不準(zhǔn)，所以問題來了，預(yù)估的準(zhǔn)確性是一個(gè)問題。如果預(yù)估不準(zhǔn)確，可能會(huì)導(dǎo)致進(jìn)程的等待時(shí)間增加或者執(zhí)行時(shí)間不均衡。如果短時(shí)間的進(jìn)程一直在排在前面執(zhí)行，那么長(zhǎng)時(shí)間的進(jìn)程可能會(huì)一直等待執(zhí)行的機(jī)會(huì)。

最短剩余時(shí)間優(yōu)先

他是搶占式的調(diào)度算法，可以利用CPU的時(shí)間片機(jī)制，是基于最短作業(yè)優(yōu)先算法的改進(jìn)版本。該算法會(huì)根據(jù)進(jìn)程的剩余執(zhí)行時(shí)間進(jìn)行排隊(duì)，將剩余執(zhí)行時(shí)間最短的進(jìn)程優(yōu)先執(zhí)行。但是這個(gè)時(shí)間也是預(yù)估的而且每個(gè)進(jìn)程的剩余執(zhí)行時(shí)間需要進(jìn)行實(shí)時(shí)監(jiān)控和計(jì)算。

如果沒有時(shí)間片的限制，SRTF算法會(huì)變成最短作業(yè)優(yōu)先算法，因?yàn)槊總€(gè)進(jìn)程都能從頭到尾一次性執(zhí)行完畢。

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

它根據(jù)進(jìn)程的優(yōu)先級(jí)來確定執(zhí)行順序。每個(gè)進(jìn)程都有一個(gè)優(yōu)先級(jí)值，通常在創(chuàng)建進(jìn)程時(shí)由操作系統(tǒng)分配。如果多個(gè)進(jìn)程的優(yōu)先級(jí)相同，則按照先來先服務(wù)（FIFO）的方式依次執(zhí)行。進(jìn)程的優(yōu)先級(jí)一般都已經(jīng)由操作系統(tǒng)在創(chuàng)建的時(shí)候都已經(jīng)設(shè)定好了的，如果硬要設(shè)置的話，可以去任務(wù)管理器看看；

優(yōu)先級(jí)調(diào)度可以細(xì)分為搶占式和非搶占式；這個(gè)就不用說了，我單獨(dú)說下?lián)屨际剑趽屨际絻?yōu)先級(jí)調(diào)度中，如果有高優(yōu)先級(jí)的進(jìn)程到達(dá)，當(dāng)前正在執(zhí)行的進(jìn)程會(huì)被中斷，讓高優(yōu)先級(jí)的進(jìn)程先執(zhí)行。

所以說他仍然有點(diǎn)問題，那就是低優(yōu)先級(jí)的進(jìn)程需要排很長(zhǎng)時(shí)間的隊(duì)才可以執(zhí)行；

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

多級(jí)反饋隊(duì)列調(diào)度是一種綜合了優(yōu)先級(jí)調(diào)度和時(shí)間片輪轉(zhuǎn)調(diào)度的進(jìn)程調(diào)度算法。它通過多個(gè)就緒隊(duì)列按照優(yōu)先級(jí)和時(shí)間片的不同來排列進(jìn)程，以實(shí)現(xiàn)更加靈活和高效的調(diào)度，但是他并不是按照優(yōu)先級(jí)依次進(jìn)入就緒隊(duì)列的，而是都在第一級(jí)隊(duì)列開始執(zhí)行，執(zhí)行完就放入第二級(jí)隊(duì)列，依次往下排而已，這個(gè)優(yōu)先級(jí)只是單獨(dú)對(duì)于就緒隊(duì)列來講的并不是進(jìn)程的優(yōu)先級(jí)；

他就兼顧了長(zhǎng)短作業(yè)的場(chǎng)景，因?yàn)槎套鳂I(yè)很可能在前面的就緒隊(duì)列中已經(jīng)執(zhí)行完了，而后面的長(zhǎng)作業(yè)占用的CPU時(shí)間片也更長(zhǎng)了。

這個(gè)算法類比銀行辦手續(xù)的場(chǎng)景：

• 銀行大廳中本身三個(gè)排隊(duì)隊(duì)列，隊(duì)列1優(yōu)先級(jí)最高但是辦理的時(shí)間卻是最短的，這也對(duì)應(yīng)著優(yōu)先級(jí)越高時(shí)間片越短；

• 新來的客戶都先進(jìn)入隊(duì)列1叫號(hào)排隊(duì)，但是只辦理1分鐘的業(yè)務(wù)，辦理不完的客戶都去隊(duì)列2依次排隊(duì)，當(dāng)隊(duì)列1中的客戶全辦理完之后，工作人員開始處理隊(duì)列2中的客戶，然后依次排隊(duì)，直至隊(duì)列中的進(jìn)程都處理完畢為止；

• 但是如果在辦理其他隊(duì)列的過程中又有新客戶來了，則會(huì)終止當(dāng)前客戶的辦理并重新進(jìn)入對(duì)尾排隊(duì)，工作人員會(huì)立馬處理隊(duì)列1中的客戶。

可以發(fā)現(xiàn)，對(duì)于要辦理短業(yè)務(wù)的客戶來說，可以很快的輪到并解決。對(duì)于要辦理長(zhǎng)業(yè)務(wù)的客戶，一下子解決不了，就可以放到下一個(gè)隊(duì)列，雖然等待的時(shí)間稍微變長(zhǎng)了，但是輪到自己的辦理時(shí)間也變長(zhǎng)了，

多級(jí)反饋隊(duì)列調(diào)度算法兼顧了優(yōu)先級(jí)和時(shí)間片的特點(diǎn)，能夠適應(yīng)不同類型的進(jìn)程和任務(wù)。通過合理設(shè)置每個(gè)隊(duì)列的優(yōu)先級(jí)和時(shí)間片長(zhǎng)度，可以根據(jù)實(shí)際情況提高系統(tǒng)的執(zhí)行效率和響應(yīng)速度。

總結(jié)

進(jìn)程調(diào)度是操作系統(tǒng)中重要的任務(wù)之一。調(diào)度程序根據(jù)進(jìn)程的狀態(tài)變化，選擇下一個(gè)進(jìn)程來占用CPU執(zhí)行任務(wù)。調(diào)度的原則包括CPU利用率、系統(tǒng)吞吐率、周轉(zhuǎn)時(shí)間、等待時(shí)間和響應(yīng)時(shí)間等。調(diào)度算法分為非搶占式和搶占式兩種類型，其中常見的算法包括先來先服務(wù)、時(shí)間片輪轉(zhuǎn)、最短作業(yè)優(yōu)先、最短剩余時(shí)間優(yōu)先、優(yōu)先級(jí)調(diào)度和多級(jí)反饋隊(duì)列調(diào)度。每種算法都有其優(yōu)點(diǎn)和缺點(diǎn)，