目錄

一、先來先服務算法

1、算法思想

2、算法規(guī)則

3、用于作業(yè)/進程調度

4、是否可搶占?

5、優(yōu)缺點

優(yōu)點：

缺點：

6、是否會導致饑餓

7、例子

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

1、算法思想

2、算法規(guī)則

3、用于作業(yè)/進程調度

4、是否可搶占?

5、優(yōu)缺點

優(yōu)點:

缺點:

6、是否會導致饑餓

7、例子

（1）非搶占式

（2）搶占式

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

1、算法思想

2、算法規(guī)則

3、用于作業(yè)/進程調度

4、是否可搶占?

5、優(yōu)缺點

6、是否會導致饑餓

7、例子

注意：

---

一、先來先服務算法

1、算法思想

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

2、算法規(guī)則

按照作業(yè)/進程到達的先后順序進行服務

3、用于作業(yè)/進程調度

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

用于進程調度時，考慮的是哪個進程先到達就緒隊列。

4、是否可搶占?

非搶占式的算法

5、優(yōu)缺點

優(yōu)點：

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

缺點：

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

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

6、是否會導致饑餓

不會導致饑餓

7、例子

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

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

1、算法思想

追求最少的平均等待時間，最少的平均周轉時間、最少的平均帶權周轉時間。

2、算法規(guī)則

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

3、用于作業(yè)/進程調度

即可用于作業(yè)調度，也可用于進程調度。

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

4、是否可搶占?

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

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

5、優(yōu)缺點

優(yōu)點:

“最短的”平均等待時間、平均周轉時間。

缺點:

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

6、是否會導致饑餓

會。

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

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

7、例子

（1）非搶占式

（2）搶占式

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

1、算法思想

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

2、算法規(guī)則

在每次調度時先計算各個作業(yè)/進程的響應比，選擇響應比最高的作業(yè)/進程為其服務。

3、用于作業(yè)/進程調度

即可用于作業(yè)調度，也可用于進程調度。

4、是否可搶占?

非搶占式的算法。

因此只有當前運行的作業(yè)/進程主動放棄處理機時，才需要調度，才需要計算響應比。

5、優(yōu)缺點

綜合考慮了等待時間和運行時間（要求服務時間)

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

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

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

6、是否會導致饑餓

不會

7、例子

每次進程結束后都要重新計算響應比。

注意：

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

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