數據結構和算法專題---5、調度算法與應用

本章我們會對調度算法做個簡單介紹，包括常用的調度算法（FCFS、SJF、RR、HPF）的概述、實現方式、典型場景做個說明。

什么是調度算法

調度算法常見于操作系統中，因為系統資源有限，當有多個進程（或多個進程發出的請求）要使用這些資源時，就必須按照一定的原則選擇進程（請求）來占用資源。這就是所謂的調度。在現實生活中也是一樣，比如會議室的占用。

先來先服務（FCFS）

概念

先來先服務，很好理解，就是按照服務提交申請的順序，依次執行。講究先來后到。

實現

定義一個Task類作為任務實例，BlockingQueue作為服務隊列

package com.ls.cloud.sys.alg.schedule;/*** 任務類*/
public class Task {//任務名稱private String name;//任務提交的時間private Long addTime;//任務的執行時間private int servTime;//任務優先級private int level;public Task(String name, int servTime) {this.name = name;this.servTime = servTime;this.addTime = System.currentTimeMillis();}public Task(String name, int servTime,int level) {this.name = name;this.servTime = servTime;this.level = level;this.addTime = System.currentTimeMillis();}public void execute() {try {// ！重點：執行時睡眠，表示該任務耗時servTime毫秒Thread.currentThread().sleep(servTime);} catch (InterruptedException e) {e.printStackTrace();}System.out.println(String.format("execute:name=%s,level=%s,addTime=%s,servTime=%s",name,level, addTime, servTime));}
}

package com.ls.cloud.sys.alg.schedule;import java.util.Random;
import java.util.concurrent.LinkedBlockingQueue;public class FCFS {public static void main(String[] args) throws InterruptedException {//阻塞隊列，FCFS的基礎final LinkedBlockingQueue<Task> queue = new LinkedBlockingQueue(5);//服務線程，任務由該線程獲取和執行new Thread(new Runnable(){@Overridepublic void run() {while (true) {try {queue.take().execute();} catch (Exception e) {e.printStackTrace();}}}}).start();//向隊列中每隔100ms防入一個任務for (int i = 0; i < 5; i++) {System.out.println("add task:"+i);queue.put(new Task("task"+i,new Random().nextInt(1000)));}}}

結果

add task:0
add task:1
add task:2
add task:3
add task:4
execute:name=task0,level=0,addTime=1701829693127,servTime=67
execute:name=task1,level=0,addTime=1701829693127,servTime=593
execute:name=task2,level=0,addTime=1701829693127,servTime=903
execute:name=task3,level=0,addTime=1701829693127,servTime=719
execute:name=task4,level=0,addTime=1701829693127,servTime=283

add按順序放入，時間有序
execute也按時間順序執行，而不管后面的servTime，也就是不管執行任務長短，先來先執行

優缺點

多應用于cpu密集型任務場景，對io密集型的不利。
時間相對均衡的業務可以排隊處理，比如現實中排隊打卡進站。
如果業務需要依賴大量的外部因素，執行時間片長短不一，FCFS算法不利于任務的整體處理進度，可能會因為一個長時間業務的阻塞而造成大量等待。

短作業優先（SJF）

概念

執行時間短的優先得到資源。即執行前申報一個我需要占據cpu的時間，根據時間長短，短的優先被調度。我不占時間所以我先來。

實現

使用TreeMap可以實現優先級的任務排序。

package com.ls.cloud.sys.alg.schedule;import javax.swing.text.html.parser.Entity;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;public class SJF {public static void main(String[] args) throws InterruptedException {//有序Map，將服務時間作為key排序final TreeMap<Integer,Task> treeMap = new TreeMap();//向隊列中放入5個任務for (int i = 0; i < 5; i++) {System.out.println("add task:"+i);int servTime = new Random().nextInt(1000);//注意，key是servTime，即執行預估時間treeMap.put(servTime,new Task("task"+i,servTime));}//服務線程，任務由該線程獲取和執行new Thread(new Runnable(){@Overridepublic void run() {while (true) {try {//有序Map中，服務時間短的，置于頂部，那么自然就會優先被取出Map.Entry<Integer,Task> entry = treeMap.pollFirstEntry();if (entry == null){Thread.currentThread().sleep(100);}else {entry.getValue().execute();}} catch (Exception e) {e.printStackTrace();}}}}).start();}
}

結果

add task:0
add task:1
add task:2
add task:3
add task:4
execute:name=task2,level=0,addTime=1701842880485,servTime=503
execute:name=task1,level=0,addTime=1701842880485,servTime=622
execute:name=task4,level=0,addTime=1701842880485,servTime=862
execute:name=task3,level=0,addTime=1701842880485,servTime=941
execute:name=task0,level=0,addTime=1701842880485,servTime=952

add任務有序，確實按照從前往后順序提交的
execute任務無序，按servtime排序，說明執行時間段的得到了優先執行

優缺點

適用于任務時間差別較大的場景，仍然以進站為例，拿出公交卡的優先刷卡，還沒辦卡的讓一讓。
解決了FCFS整體處理時間長的問題，降低平均等待時間，提高了系統吞吐量。
未考慮作業的緊迫程度，因而不能保證緊迫性作業（進程）的及時處理
對長作業的不利，可能等待很久而得不到執行
時間基于預估和申報，主觀性因素在內，無法做到100%的精準

時間片輪轉（RR）

概念

時間片逐個掃描輪詢，輪到誰誰執行。大家公平裁決來者有份，誰也別插隊。像是棋牌游戲中的發牌操作，做到了時間和機會上的平均性。

實現

基于數組做為數據插槽方式實現。

package com.ls.cloud.sys.alg.schedule;import java.util.Random;public class RR {//定義數組作為插槽，每個插槽中可以放入任務Integer[] integers;//length插槽的個數public RR(int length){integers = new Integer[length];}//將任務放入插槽public void addTask(int value){int slot = 0;//不停查找空的插槽while (true) {//發現空位，將當前任務放入if (integers[slot] == null){integers[slot] = value;System.out.println(String.format("------------------------->add task index=%s,value=%s",slot,value));break;}//如果當前位置有任務占用，看下一個位置slot++;//如果插槽遍歷完還是沒有空位置，那么從頭開始再找，繼續下一個輪回if (slot == integers.length){slot = 0;}}}//執行任務。輪詢的策略就在這里public void execute(){//開啟一個線程處理任務。在現實中可能有多個消費者來處理new Thread(new Runnable() {@Overridepublic void run() {int index = 0;while (true) {//指針輪詢，如果到達尾部，下一步重新轉向開頭// 數據物理結構是一個數組，邏輯上是一個環if (index == integers.length){index = 0;}//如果當前位置沒有任務，輪詢到下一個插槽if (integers[index] == null){index++;continue;}else{//隨機等待，表示模擬當前任務有一個執行時間try {Thread.currentThread().sleep(new Random().nextInt(1000));} catch (InterruptedException e) {e.printStackTrace();}//模擬任務執行的內容，也就是打印一下當前插槽和里面的值System.out.println(String.format("execute index=%s,value=%s",index,integers[index]));//執行完，將當前插槽清空，騰出位置來給后續任務使用integers[index] = null;}}}}).start();}public static void main(String[] args) {//測試開始，定義3個插槽RR rr = new RR(3);//喚起執行者線程，開始輪詢rr.execute();//放置10個任務for (int i = 0; i < 10; i++) {rr.addTask(i);}}
}

結果

------------------------->add task index=0,value=0
------------------------->add task index=1,value=1
------------------------->add task index=2,value=2
execute index=0,value=0
------------------------->add task index=0,value=3
execute index=1,value=1
------------------------->add task index=1,value=4
execute index=2,value=2
------------------------->add task index=2,value=5
execute index=0,value=3
execute index=1,value=4
------------------------->add task index=1,value=6
------------------------->add task index=0,value=7
execute index=2,value=5
------------------------->add task index=2,value=8
execute index=0,value=7
execute index=1,value=6
------------------------->add task index=1,value=9
execute index=2,value=8
execute index=1,value=9

add任務index無序，value有序，說明是按順序提交的，但是插槽無序，哪里有空放哪里
execute執行index有序value無序，說明任務是輪詢執行的，每個插槽里的任務不一定是誰

優缺點

做到了機會的相對平均，不會因為某個任務執行時間超長而永遠得不到執行
缺乏任務主次的處理。重要的任務無法得到優先執行，必須等到時間片輪到自己，著急也沒用

優先級調度（HPF）

概述

進程調度每次將處理機分配給具有最高優先級的就緒進程。最高優先級算法可與不同的CPU方式結合形成可搶占式最高優先級算法和不可搶占式最高優先級算法。

實現

在Task類中新增一個屬性level作為優先級標識

package com.ls.cloud.sys.alg.schedule;/*** 任務類*/
public class Task {//任務名稱private String name;//任務提交的時間private Long addTime;//任務的執行時間private int servTime;//任務優先級private int level;public Task(String name, int servTime) {this.name = name;this.servTime = servTime;this.addTime = System.currentTimeMillis();}public Task(String name, int servTime,int level) {this.name = name;this.servTime = servTime;this.level = level;this.addTime = System.currentTimeMillis();}public void execute() {try {// ！重點：執行時睡眠，表示該任務耗時servTime毫秒Thread.currentThread().sleep(servTime);} catch (InterruptedException e) {e.printStackTrace();}System.out.println(String.format("execute:name=%s,level=%s,addTime=%s,servTime=%s",name,level, addTime, servTime));}
}

package com.ls.cloud.sys.alg.schedule;import java.util.Map;
import java.util.Random;
import java.util.TreeMap;public class HPF {public static void main(String[] args) throws InterruptedException {//有序Map，將服務優先級作為key排序final TreeMap<Integer, Task> treeMap = new TreeMap();//向隊列中放入5個任務for (int i = 0; i < 5; i++) {System.out.println("add task:" + i);int servTime = new Random().nextInt(1000);//注意放入的key，是優先級，這里用i標識treeMap.put(i, new Task("task" + i, servTime,i));}//服務線程，任務由該線程獲取和執行new Thread(new Runnable() {@Overridepublic void run() {while (true) {try {//有序Map中，優先級最高的，在底部部，那么自然就會優先被取出Map.Entry<Integer, Task> entry = treeMap.pollLastEntry();if (entry == null) {Thread.currentThread().sleep(100);} else {entry.getValue().execute();}} catch (Exception e) {e.printStackTrace();}}}}).start();}
}

結果

add task:0
add task:1
add task:2
add task:3
add task:4
execute:name=task4,level=4,addTime=1701843942807,servTime=452
execute:name=task3,level=3,addTime=1701843942807,servTime=433
execute:name=task2,level=2,addTime=1701843942807,servTime=196
execute:name=task1,level=1,addTime=1701843942807,servTime=166
execute:name=task0,level=0,addTime=1701843942806,servTime=97