CPU Scheduling Algorithms

重要的CPU調(diào)度算法如下：

• FCFS Scheduling（First-Come, First-Served）
• SJF Scheduling（Shortest-Job-First）
  • Non-Preemptive SJF Scheduling
  • Preemptive SJF Scheduling
• Priority Scheduling
• RR Scheduling（Round Robin）

FCFS與SJF

這里只說FCFS和SJF。

---

先到先服務(wù)調(diào)度：先請(qǐng)求CPU的進(jìn)程被首先分配到CPU，可采用FIFO隊(duì)列實(shí)現(xiàn)。

---

ProcessBurst Time

P1	24
P2	3
P3	3

Suppose that the processes arrive in the order: P1 , P2 , P3 The Gantt Chart for the schedule is:

Waiting time for P1 = 0; P2 = 24; P3 = 27
Average waiting time: (0 + 24 + 27)/3 = 17

FCFS策略的平均等待時(shí)間通常相當(dāng)長。例子中，平均等待時(shí)間為17ms。

---

Suppose that the processes arrive in the order: P2 , P3 , P1 The Gantt chart for the schedule is:

Waiting time for P1 = 6; P2 = 0; P3 = 3
Average waiting time: (6 + 0 + 3)/3 = 3
Convoy effect : short process behind long process.

進(jìn)程區(qū)間變化很大時(shí)，平均等待時(shí)間也會(huì)變化很大。
護(hù)航現(xiàn)象（convoy effect）：所有其他進(jìn)程都等待一個(gè)大進(jìn)程釋放CPU，導(dǎo)致CPU和設(shè)備的使用率變得更低。
FCFS調(diào)度算法是非搶占的。一旦CPU被分配給了一個(gè)進(jìn)程，該進(jìn)程就會(huì)保持CPU知道釋放CPU為止。

---

最短作業(yè)優(yōu)先調(diào)度：將每個(gè)進(jìn)程與其下一個(gè)CPU區(qū)間相關(guān)聯(lián)。當(dāng)CPU為可用時(shí)，它會(huì)賦給具有最短后續(xù)CPU區(qū)間的進(jìn)程。如果兩個(gè)進(jìn)程具有同樣長度的CPU區(qū)間，那么可以使用FCFS調(diào)度來處理。

---

ProcessBurst Time

P1	6
P2	8
P3	7
P4	3

The Gantt Chart for the schedule is:

Waiting time for P1 = 3; P2 = 16; P3 = 9; P4 = 0
Average waiting time: (3 + 16 + 9 + 0)/4 = 7

如果使用FCFS調(diào)度方案，平均等待時(shí)間為10.25ms。
可以證明對(duì)于給定的一組進(jìn)程SJF算法的平均等待時(shí)間最小。通過將短進(jìn)程移到長進(jìn)程之前，短進(jìn)程等待時(shí)間的減少大于長進(jìn)程等待時(shí)間的增加。因而，平均等待時(shí)間減少了。

詳解SJF

SJF的困難是如何知道下一個(gè)CPU請(qǐng)求的長度。
對(duì)于長期調(diào)度：可以使用用戶在提交作業(yè)時(shí)制定的作業(yè)時(shí)間極限作為長度，因此，在長期調(diào)度中經(jīng)常使用SJF。
對(duì)于短期調(diào)度：無法獲得下一個(gè)CPU區(qū)間的長度，因此，只能試圖近似SJF調(diào)度。

---

SJF算法可能是搶占的或非搶占的。
當(dāng)一個(gè)新進(jìn)程到達(dá)就緒隊(duì)列而以前進(jìn)程正在執(zhí)行時(shí)，就需要選擇。新進(jìn)程與當(dāng)前運(yùn)行進(jìn)程所產(chǎn)生的CPU區(qū)間相比，可能有一個(gè)更短的下一個(gè)CPU區(qū)間。
可搶占SJF算法可能會(huì)搶占當(dāng)前運(yùn)行進(jìn)程，有時(shí)稱最短剩余時(shí)間優(yōu)先調(diào)度；
非搶占SJF算法會(huì)允許當(dāng)前運(yùn)行進(jìn)程先完成其CPU區(qū)間。

---

ProcessArrival TimeBurst Time

P1	0.0	7
P2	2.0	4
P3	4.0	1
P4	5.0	4

SJF (non-preemptive)

Waiting time for P1 = 0; P2 = 6; P3 = 3; P4 = 7
Average waiting time = (0 + 6 + 3 + 7)/4 = 4

---

ProcessArrival TimeBurst Time

P1	0.0	7
P2	2.0	4
P3	4.0	1
P4	5.0	4

SJF (preemptive)

Waiting time for P1 = 9; P2 = 1; P3 = 0; P4 = 2
Average waiting time = (9 + 1 + 0 +2)/4 = 3

---

洛谷P1223題

題目要求

P1223題目鏈接

分析

其實(shí)本題正是如此，OS難以知道和確定接下來哪個(gè)進(jìn)程剩余時(shí)間最短，但這里知道啊！

所謂的“最優(yōu)策略”，來自于貪心算法，需要先排個(gè)序，耗時(shí)短的先結(jié)束任務(wù)可以使得總平均等待時(shí)間最短。

AC代碼（Java語言描述）

import java.util.Arrays; import java.util.Comparator; import java.util.Scanner;public class Main {private static class Person {Integer time;int id;public Person(int time, int id) {this.time = time;this.id = id;}}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int num = scanner.nextInt();Person[] array = new Person[num];for (int i = 0; i < num; i++) {array[i] = new Person(scanner.nextInt(), i+1);}scanner.close();Arrays.sort(array, Comparator.comparing(person -> person.time));long waitingTime = 0, sum = 0;StringBuilder result = new StringBuilder();for (Person p : array) {waitingTime += sum;sum += p.time;result.append(p.id).append(" ");}System.out.println(result.toString().trim());System.out.printf("%.2f", waitingTime/(double)num);} }

總結(jié)

FCFS算法和SJF算法是兩種重要的算法。FCFS其實(shí)基于普通隊(duì)列即可實(shí)現(xiàn)。比起算法本身，更重要的是領(lǐng)會(huì)到SJF算法的思想，并能在處理實(shí)際問題的時(shí)候得以啟發(fā)，這樣就很好啦！

另外，OS 的 SJF CPU調(diào)度算法也應(yīng)該深刻理解，這是涉及計(jì)算機(jī)原理的重要知識(shí)。

希望對(duì)不懂SJF算法的讀者一些啟示，也希望幫助對(duì)洛谷P1223題理解不深的讀者加深理解。
總之，希望對(duì)大家有所幫助！

總結(jié)

以上是生活随笔為你收集整理的深入理解 操作系统 SJF算法（以洛谷P1223题为例）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。