進(jìn)程調(diào)度算法大致可分為先來先服務(wù)(FCFS),短作業(yè)優(yōu)先(SJF/SPF)，時(shí)間片輪轉(zhuǎn)(RR)和優(yōu)先級(jí)算法。這一節(jié)，我們主要來分析一下優(yōu)先級(jí)算法的優(yōu)劣并通過程序?qū)崿F(xiàn)。

高優(yōu)先權(quán)優(yōu)先調(diào)度可分為：

• 非搶占式優(yōu)先權(quán)

  基本原理：系統(tǒng)把處理機(jī)分配給就緒隊(duì)列中優(yōu)先權(quán)最高的進(jìn)程后，該進(jìn)程便一直執(zhí)行下去，直到完成；或因發(fā)生某時(shí)間使該進(jìn)程放棄處理機(jī)時(shí),系統(tǒng)才可將處理機(jī)重新分配給另一優(yōu)先權(quán)最高的進(jìn)程。

• 搶占式優(yōu)先權(quán)

  基本原理：系統(tǒng)把處理機(jī)優(yōu)先權(quán)最高的進(jìn)程，使之執(zhí)行。若在其執(zhí)行期間，只要又出現(xiàn)另一個(gè)優(yōu)先權(quán)更高的進(jìn)程，則立即停止當(dāng)前進(jìn)程的執(zhí)行，重新分配處理機(jī)給新來的優(yōu)先權(quán)更高的進(jìn)程。

優(yōu)先權(quán)類型：

• 靜態(tài)優(yōu)先權(quán)

  靜態(tài)優(yōu)先權(quán)是在創(chuàng)建進(jìn)程的時(shí)確定的，且在進(jìn)程的整個(gè)運(yùn)行期間保持不變。

• 動(dòng)態(tài)優(yōu)先權(quán)

  是指在創(chuàng)建進(jìn)程時(shí)確定的優(yōu)先權(quán)，在進(jìn)程的運(yùn)行期間會(huì)發(fā)生變化。

  
  

為了解決低優(yōu)先級(jí)的進(jìn)程在優(yōu)先級(jí)調(diào)度算法中的不公平處理，我們對(duì)優(yōu)先級(jí)調(diào)度算法進(jìn)行改進(jìn)提出了高響應(yīng)比優(yōu)先調(diào)度算法。

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

高響應(yīng)比優(yōu)先調(diào)度算法既考慮作業(yè)的執(zhí)行時(shí)間也考慮作業(yè)的等待時(shí)間，綜合了先來先服務(wù)和最短作業(yè)優(yōu)先兩種算法的特點(diǎn)。

該算法中的響應(yīng)比是指作業(yè)等待時(shí)間與運(yùn)行比值，響應(yīng)比公式定義如下：

響應(yīng)比 =（等待時(shí)間+要求服務(wù)時(shí)間）/ 要求服務(wù)時(shí)間即：RR=（w+s）/s=1+w/s，因此響應(yīng)比一定是大于1的。

優(yōu)缺點(diǎn)：

• 優(yōu)點(diǎn)：等待時(shí)間相同的作業(yè)，則要求服務(wù)的時(shí)間愈短，其優(yōu)先權(quán)愈高，——對(duì)短作業(yè)有利要求服務(wù)的時(shí)間相同的作業(yè)，則等待時(shí)間愈長(zhǎng)，其優(yōu)先權(quán)愈高，——是先來先服務(wù)? ? ? ? ?長(zhǎng)作業(yè)，優(yōu)先權(quán)隨等待時(shí)間的增加而提高，其等待時(shí)間足夠長(zhǎng)時(shí)，其優(yōu)先權(quán)便可升到很高， 從而也可獲得處理機(jī)——對(duì)長(zhǎng)作業(yè)有利，是一種折衷，既照顧了短作業(yè)，又考慮了作業(yè)到達(dá)的先后次序，又不會(huì)使長(zhǎng)作業(yè)長(zhǎng)期得不到服務(wù)。

• 缺點(diǎn)：要進(jìn)行響應(yīng)比計(jì)算，增加了系統(tǒng)開銷

算法思想：

非搶占式優(yōu)先權(quán)：

①首先也是按進(jìn)程的到達(dá)時(shí)間進(jìn)行排序。讓最先到達(dá)的進(jìn)程尾插進(jìn)入。②當(dāng)容器不空時(shí)，從尾部取出一個(gè)進(jìn)程來執(zhí)行，直至此進(jìn)程執(zhí)行完，設(shè)置一個(gè)變量記錄此進(jìn)程執(zhí)行過程中所有到達(dá)的進(jìn)程。③將這些到達(dá)的進(jìn)程依次尾插入容器中，然后對(duì)容器中的進(jìn)程按優(yōu)先級(jí)排序。（只排當(dāng)前進(jìn)程執(zhí)行期間到達(dá)的進(jìn)程）④此時(shí)也要考慮如果容器為空，但進(jìn)程數(shù)組中仍存在未到達(dá)的進(jìn)程，這時(shí)將要到達(dá)進(jìn)程加入進(jìn)程就緒隊(duì)列。

搶占式優(yōu)先權(quán)：

①首先也是按進(jìn)程的到達(dá)時(shí)間進(jìn)行排序。讓最先到達(dá)的進(jìn)程尾插進(jìn)入。②當(dāng)容器不空時(shí)，從尾部取出一個(gè)進(jìn)程來執(zhí)行。③如果在執(zhí)行期間沒有其他進(jìn)程到達(dá)，則將當(dāng)前進(jìn)程運(yùn)行完畢；如果在執(zhí)行期間有新的進(jìn)程達(dá)到，則需要記錄下當(dāng)前進(jìn)程運(yùn)行了多少時(shí)間，并更新當(dāng)前時(shí)間，然后把新到達(dá)的進(jìn)程加入到容器里面，接著把容器里面存在的進(jìn)程按照優(yōu)先級(jí)排序④此時(shí)也要考慮如果容器為空，但進(jìn)程數(shù)組中仍存在未到達(dá)的進(jìn)程，這時(shí)將要到達(dá)進(jìn)程加入進(jìn)程就緒容器。

來到例題看看結(jié)果：

非搶占：

? 程序運(yùn)行結(jié)果：

搶占：

???程序運(yùn)行結(jié)果：