文章目錄

• 為什么要用調度算法？
• 調度算法
• • 先來先服務(FCFS First-Come First-Server)
  • 優先權排隊(Priority Queuing)
  • 循環排隊(Round Queuing)
  • 加權公平排隊(Weighted Fair Queuing)
  • • 加權輪詢
    • 加權隨機

為什么要用調度算法？

首先要聲明這里實現的是應用層調度算法，針對的是請求，而不是操作系統的進程調度算法，在平常處理請求時，如果請求并發量不大，是一個接一個過來的，那我們沒有選擇只有一個接一個處理請求了，但是如果請求并發量很多，那我們就有選擇先執行哪個請求的權力了，而選擇先執行哪個請求就是調度算法，可以知道這里的請求都是我們要執行的請求，只是執行的順序先后不同而已，在這之前呢，會不會有要執行的請求和被拒絕執行的請求呢，也是有的，那個步驟叫做限流，可以看我這篇文章 漏桶(令牌桶)限流算法

調度算法

先來先服務(FCFS First-Come First-Server)

該算法也叫先進先出 FIFO(First Input First Outer)，這是非常公平的算法，實現也非常簡單，使用一個隊列，隊列中的節點可以有兩種構成

隊列中每個結點可以是存儲著HTTP請求信息（如URL和請求參數）的對象，如果是這種節點，我們可以在出隊列時調用執行處理請求任務的線程獲取這個節點存儲的信息，然后執行就可以了

隊列中每個結點也可以是一個阻塞的線程，如果是這種節點，我們可以在出隊列的時候直接喚醒該線程，它會自動執行處理請求的任務的

下面實現使用第一種節點，而且節點里面只有一個請求的id信息，這樣最簡單

class Node {private int id;public Node(int id) {this.id = id;}@Overridepublic String toString() {return "Node{" +"id=" + id +'}';} } public class FCFSalgorithm {public static void main(String[] args) {Queue<Node> queue = new LinkedList<>();for (int i = 0; i < 10; i++) {queue.add(new Node(i));}while (!queue.isEmpty()) {Node poll = queue.poll();System.out.println("取出請求"+poll+"開始執行任務");}} }

優先權排隊(Priority Queuing)

為什么會出現優先權呢，難道公平不好嗎，這是因為特權用戶確實充了錢，所以我們得優先處理它的請求，還是用上面的節點只是增加了優先級priority屬性，實現方式有很多種如下：

最簡單的是使用一個數組，每次添加請求時按它的優先級從小到大排序，（假設優先級為0的優先級最高），則我們每次取出請求就從數組下標0取出來就行了，就是數組的添加操作會很麻煩

可以使用一個鏈表，和數組一樣按優先級從小到大排序，每次取出鏈表頭的請求執行

可以使用堆，不過堆的操作比較復雜，小頂堆的特點是頂點的值最小，所以其優先級最高，可以每次把頂取出來，再重新構造堆結構，再把頂取出來，再重新構造，一直重復就可以組成一個排序數組了

可以使用多個隊列，高優先級的用戶進入高優先級隊列，低優先級的用戶進入低優先級隊列，每次先從高優先級隊列中取出元素，直到高優先級隊列為空才從低優先級隊列取出元素
下面使用第三種方式，因為這樣添加請求最簡單，請求先找到屬于自己的隊列，在隊尾添加即可

class PNode {private int id;public int priority;public PNode(int id, int priority) {this.id = id;this.priority = priority;}@Overridepublic String toString() {return "PNode{" +"id=" + id +", priority=" + priority +'}';} }public class PriorityQueuingAlgorithm {public static void main(String[] args) {Queue<PNode>[] queueList = new Queue[3];for (int i = 0; i < 10; i++) {// 優先級i % 3，則只有0,1,2三種優先級PNode pNode = new PNode(i, i % 3);if (queueList[pNode.priority] == null) {queueList[pNode.priority] = new LinkedList<>();}Queue<PNode> queue = queueList[pNode.priority];queue.add(pNode);}for (Queue<PNode> queue : queueList) {while (!queue.isEmpty()) {PNode poll = queue.poll();System.out.println("取出請求"+poll+"開始執行任務");}}} }

循環排隊(Round Queuing)

循環排隊也是公平的，為什么把不同的請求放入不同的隊列呢，可能因為它們屬于不同的類別，或者像我們排隊時可能有很多個窗口，每個窗口對應一個隊列
實現：根據每個請求的節點的類別把它放入不同的列表，然后循環隊列列表每個隊列一次只取出一個請求執行，然后輪到下一個隊列，如果一個隊列為空，直接跳到下一個隊列

class RNode {private int id;public int type;public RNode(int id, int type) {this.id = id;this.type = type;}@Overridepublic String toString() {return "RNode{" +"id=" + id +", type=" + type +'}';} }public class RoundQueuingAlgorithm {public static void main(String[] args) {Queue<RNode>[] queueList = new Queue[3];for (int i = 0; i < 10; i++) {// 類型 i % 3，則只有0,1,2三種類型RNode rNode = new RNode(i, i % 3);if (queueList[rNode.type] == null) {queueList[rNode.type] = new LinkedList<>();}Queue<RNode> queue = queueList[rNode.type];queue.add(rNode);}while (true) {boolean flag = true;for (Queue<RNode> queue : queueList) {if (!queue.isEmpty()) {flag = false;RNode poll = queue.poll();System.out.println("取出請求"+poll+"開始執行任務");}}if (flag) break;}} }

加權公平排隊(Weighted Fair Queuing)

回想一下我們上面的優先級排隊，只有當優先級高的請求全部運行完了，才會運行下一優先級的請求，這很明顯不符合社會主義核心價值觀，所以可以更加公平，讓氪金用戶不管氪多少，都只是增大他請求先運行的幾率，如果運氣好，普通用戶的請求也能在氪金用戶請求之前運行
實現方式：
仍然需要按優先級把請求分到不同的隊列，每次也只拿出其中一個隊列的請求進行處理，所以重點就在怎樣選擇這個隊列，有以下方式：

加權輪詢

根據用戶優先級生成一個選擇列表，可以是一個數組，假如只有三個優先級 0，1，2，那么數組可以為[0, 0, 0, 1, 1, 2] 這樣，表示先選擇三次0優先級的隊列取出其中三個任務執行，再選擇1優先級的隊列取出其中兩個任務執行，再選擇2優先級的隊列取出其中一個任務執行，如果0優先級隊列沒有任務了，就找1優先級隊列，如果1優先級沒有了就找2優先級隊列

class WNode {private int id;public int priority;public WNode(int id, int priority) {this.id = id;this.priority = priority;}@Overridepublic String toString() {return "WNode{" +"id=" + id +", priority=" + priority +'}';} }public class WeightedFairQueuingAlgorithm {public static void main(String[] args) {Queue<WNode>[] queueList = new Queue[3];for (int i = 0; i < 10; i++) {WNode wNode = new WNode(i, i % 3);if (queueList[wNode.priority] == null) {queueList[wNode.priority] = new LinkedList<>();}Queue<WNode> queue = queueList[wNode.priority];queue.add(wNode);}// 可以根據優先級種類數動態構建的int[] dispatch = new int[]{0,0,0,1,1,2};while (true) {boolean flag = true;for (int index : dispatch) {Queue<WNode> queue = queueList[index];if (!queue.isEmpty()) {flag = false;WNode poll = queue.poll();System.out.println("取出請求"+poll+"開始執行任務");}}if (flag) break;}} }

加權隨機

上面那種方式還是太固定了，對運氣好的普通用戶不公平，可以使用隨機數，假設隨機數范圍為1-6，則隨機數是1-3三個數中一個，選擇0優先級的隊列取出其中一個任務執行，隨機數是4-5兩個數中一個，選擇1優先級的隊列取出其中一個任務執行，隨機數是6則選擇2優先級的隊列取出其中一個任務執行，也可以使用上面的數組，用隨機值作為下標

class WNode {private int id;public int priority;public WNode(int id, int priority) {this.id = id;this.priority = priority;}@Overridepublic String toString() {return "WNode{" +"id=" + id +", priority=" + priority +'}';} }public class WeightedFairQueuingAlgorithm {public static void main(String[] args) {Queue<WNode>[] queueList = new Queue[3];for (int i = 0; i < 100; i++) {WNode wNode = new WNode(i, i % 3);if (queueList[wNode.priority] == null) {queueList[wNode.priority] = new LinkedList<>();}Queue<WNode> queue = queueList[wNode.priority];queue.add(wNode);}Random random = new Random();int[] dispatch = new int[]{0,0,0,1,1,2};while (true) {boolean flag = true;int i = random.nextInt(6);int priority = dispatch[i];// 循環是為了當隨到的高優先級隊列為空，可以往低優先級隊列找請求for (int j = priority; j < 3; j++) {Queue<WNode> queue = queueList[j];if (!queue.isEmpty()) {flag = false;WNode poll = queue.poll();System.out.println("取出請求"+poll+"開始執行任務");// 取出一個請求，跳出內循環，繼續執行外循環break;}j++;}// 只有當隨機到最高優先級，// 而且把往后所有優先級都找遍都沒到到請求才退出循環if (priority == 0 && flag) break;}} }

總結

以上是生活随笔為你收集整理的Java 实现调度算法 包括 FCFS(FIFO)、优先权排队、循环排队、加权公平排队(WFQ)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。