目錄

一、先來先服務(wù)算法

1、算法思想

2、算法規(guī)則

3、用于作業(yè)/進(jìn)程調(diào)度

4、是否可搶占?

5、優(yōu)缺點

優(yōu)點：

缺點：

6、是否會導(dǎo)致饑餓

7、例子

二、短作業(yè)優(yōu)先算法

1、算法思想

2、算法規(guī)則

3、用于作業(yè)/進(jìn)程調(diào)度

4、是否可搶占?

5、優(yōu)缺點

優(yōu)點:

缺點:

6、是否會導(dǎo)致饑餓

7、例子

（1）非搶占式

（2）搶占式

三·、最高響應(yīng)比優(yōu)先算法

1、算法思想

2、算法規(guī)則

3、用于作業(yè)/進(jìn)程調(diào)度

4、是否可搶占?

5、優(yōu)缺點

6、是否會導(dǎo)致饑餓

7、例子

注意：

---

一、先來先服務(wù)算法

1、算法思想

主要從“公平”的角度考慮（類似于我們生活中排隊買東西的例子)

2、算法規(guī)則

按照作業(yè)/進(jìn)程到達(dá)的先后順序進(jìn)行服務(wù)

3、用于作業(yè)/進(jìn)程調(diào)度

用于作業(yè)調(diào)度時，考慮的是哪個作業(yè)先到達(dá)后備隊列;

用于進(jìn)程調(diào)度時，考慮的是哪個進(jìn)程先到達(dá)就緒隊列。

4、是否可搶占?

非搶占式的算法

5、優(yōu)缺點

優(yōu)點：

公平、算法實現(xiàn)簡單

缺點：

排在長作業(yè)(進(jìn)程）后面的短作業(yè)需要等待很長時間，帶權(quán)周轉(zhuǎn)時間很大，對短作業(yè)來說用戶體驗不好。

即，FCFS算法對長作業(yè)有利，對短作業(yè)不利(Eg :排隊買奶茶.)

6、是否會導(dǎo)致饑餓

不會導(dǎo)致饑餓

7、例子

（1）根據(jù)先來先服務(wù)的規(guī)則，調(diào)度順序是P1,P2,P3,P4。

二、短作業(yè)優(yōu)先算法

1、算法思想

追求最少的平均等待時間，最少的平均周轉(zhuǎn)時間、最少的平均帶權(quán)周轉(zhuǎn)時間。

2、算法規(guī)則

最短的作業(yè)或進(jìn)程先得到服務(wù)（所謂“最短”，是指要求服務(wù)時間最短)

3、用于作業(yè)/進(jìn)程調(diào)度

即可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。

用于進(jìn)程調(diào)度時稱為“短進(jìn)程優(yōu)先(SPF, Shortest Process First）算法”。

4、是否可搶占?

SJF和SPF是非搶占式的算法。

但是，也有搶占式的版本――最短剩余時間優(yōu)先算法( SRTN, Shortest Remaining Time Next)

5、優(yōu)缺點

優(yōu)點:

“最短的”平均等待時間、平均周轉(zhuǎn)時間。

缺點:

不公平。對短作業(yè)有利，對長作業(yè)不利?？赡墚a(chǎn)生饑餓現(xiàn)象。另外，作業(yè)/進(jìn)程的運(yùn)行時間是由用戶提供的，并不一定真實，不一定能做到真正的短作業(yè)優(yōu)先。??

6、是否會導(dǎo)致饑餓

會。

如果源源不斷地有短作業(yè)/進(jìn)程到來，可能使長作業(yè)/進(jìn)程長時間得不到服務(wù)，產(chǎn)生“饑餓”現(xiàn)象。

如果一直得不到服務(wù)，則稱為“餓死”。

7、例子

（1）非搶占式

（2）搶占式

三·、最高響應(yīng)比優(yōu)先算法

1、算法思想

要綜合考慮作業(yè)/進(jìn)程的等待時間和要求服務(wù)的時間

2、算法規(guī)則

在每次調(diào)度時先計算各個作業(yè)/進(jìn)程的響應(yīng)比，選擇響應(yīng)比最高的作業(yè)/進(jìn)程為其服務(wù)。

3、用于作業(yè)/進(jìn)程調(diào)度

即可用于作業(yè)調(diào)度，也可用于進(jìn)程調(diào)度。

4、是否可搶占?

非搶占式的算法。

因此只有當(dāng)前運(yùn)行的作業(yè)/進(jìn)程主動放棄處理機(jī)時，才需要調(diào)度，才需要計算響應(yīng)比。

5、優(yōu)缺點

綜合考慮了等待時間和運(yùn)行時間（要求服務(wù)時間)

等待時間相同時，要求服務(wù)時間短的優(yōu)先(SJF的優(yōu)點)

要求服務(wù)時間相同時，等待時間長的優(yōu)先（FCFS的優(yōu)點)

對于長作業(yè)來說，隨著等待時間越來越久，其響應(yīng)比也會越來越大，從而避免了長作業(yè)饑餓的問題

6、是否會導(dǎo)致饑餓

不會

7、例子

每次進(jìn)程結(jié)束后都要重新計算響應(yīng)比。

注意：

（1）這幾種算法主要關(guān)心對用戶的公平性、平均周轉(zhuǎn)時間、平均等待時間等評價系統(tǒng)整體性能的指標(biāo)，但是不關(guān)心“響應(yīng)時間”，也并不區(qū)分任務(wù)的緊急程度，因此對于用戶來說，交互性很糟糕。

（2）因此這三種算法一般適合用于早期的批處理系統(tǒng)，當(dāng)然，FCFS算法也常結(jié)合其他的算法使用，在現(xiàn)在也扮演著很重要的角色。
?