Why use scheduling algorithm?
First of all, it should be stated that the application layer scheduling algorithm implemented here is for requests, not the process scheduling algorithm of the operating system. In normal processing of requests, if the request concurrency is small and comes one by one, we have no choice but to process requests one by one, but if the request concurrency is large, Then we have the right to choose which request to execute first, and choosing which request to execute first is the scheduling algorithm. We can know that the requests here are all requests we want to execute, but the execution order is different. Before that, will there be requests to execute and rejected requests? There are also some. That step is called flow restriction, You can read my article Leaky bucket (token bucket) current limiting algorithm
scheduling algorithm
First come first server (FCFS first come first server)
The algorithm is also called first in first out FIFO (first input first out). It is a very fair algorithm and its implementation is very simple. Using a queue, the nodes in the queue can be composed of two types
- Each node in the queue can be an object that stores HTTP request information (such as URL and request parameters). If it is such a node, we can call the thread executing the request task to obtain the information stored in this node when we leave the queue, and then execute it
- Each node in the queue can also be a blocked thread. If it is such a node, we can wake up the thread directly when we leave the queue, and it will automatically execute the task of processing the request
The following implementation uses the first node, and there is only one requested id information in the node, which is the simplest
class Node {
private int id;
public Node(int id) {
this.id = id;
}
@Override
public 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("Fetch request"+poll+"Start task");
}
}
}
Priority queuing
Why does priority appear? Isn't it fair? This is because privileged users do charge money, so we have to give priority to their requests, or just use the above node to add the priority attribute. There are many implementation methods as follows:
- The simplest thing is to use an array. Each time we add a request, we will sort it from small to large according to its priority (assuming that the priority with priority 0 is the highest). Then we will take out the request from the array subscript 0 every time, that is, the addition operation of the array will be very troublesome
- You can use a linked list, which, like an array, is sorted by priority from small to large. Each time you take out the request of the chain header, it is executed
- Heap can be used, but the operation of heap is complex. The small top heap is characterized by the smallest value of vertices, so it has the highest priority. You can take out the top every time, reconstruct the heap structure, take out the top again, and then reconstruct it. You can form a sorting array by repeating it all the time
- Multiple queues can be used. High priority users enter the high priority queue and low priority users enter the low priority queue. Each time, take out elements from the high priority queue until the high priority queue is empty
The third method is used below, because it is the simplest way to add a request. The request first finds its own queue and adds it at the end of the queue
class PNode {
private int id;
public int priority;
public PNode(int id, int priority) {
this.id = id;
this.priority = priority;
}
@Override
public 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++) {
// Priority I% 3, there are only three priorities: 0, 1 and 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("Fetch request"+poll+"Start task");
}
}
}
}
Round queuing
Circular queuing is also fair. Why put different requests into different queues? It may be because they belong to different categories, or when we queue, there may be many windows, and each window corresponds to a queue
Implementation: put it into different lists according to the category of each requested node, and then cycle the queue list. Each queue only takes out one request for execution at a time, and then it is the turn of the next queue. If a queue is empty, directly jump to the next queue
class RNode {
private int id;
public int type;
public RNode(int id, int type) {
this.id = id;
this.type = type;
}
@Override
public 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++) {
// Type I% 3, there are only three types: 0, 1 and 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("Fetch request"+poll+"Start task");
}
}
if (flag) break;
}
}
}
Weighted fair queuing
Recall the priority queuing above. Only when all the high priority requests are completed, the next priority request will be run. This obviously does not conform to the core socialist values, so it can be more fair. No matter how many krypton users are, krypton gold users only increase the probability of their request to run first. If they are lucky, Ordinary users' requests can also be run before krypton users' requests
Implementation method:
It is still necessary to divide requests into different queues according to priority, and only one queue of requests is taken out for processing each time. Therefore, the focus is on how to select this queue. There are the following ways:
Weighted polling
A selection list is generated according to the user priority, which can be an array. If there are only three priorities 0, 1 and 2, the array can be [0, 0, 0, 1, 1 and 2]. This means that the queue with priority 0 is selected three times to take out three tasks for execution, and then the queue with priority 1 is selected to take out two tasks for execution, Then select the 2 priority queue and take out one of the tasks for execution. If the 0 priority queue has no tasks, find the 1 priority queue. If the 1 priority queue has no tasks, find the 2 priority queue
class WNode {
private int id;
public int priority;
public WNode(int id, int priority) {
this.id = id;
this.priority = priority;
}
@Override
public 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);
}
// It can be built dynamically according to the number of priority categories
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("Fetch request"+poll+"Start task");
}
}
if (flag) break;
}
}
}
Weighted random
The above method is still too fixed. It is unfair to lucky ordinary users. You can use random numbers. Assuming that the random number range is 1-6, the random number is one of the three numbers 1-3. Select the queue with priority 0 to take out one of the tasks for execution, and the random number is one of the two numbers 4-5. Select the queue with priority 1 to take out one of the tasks for execution, If the random number is 6, select the queue with priority 2 to take out one of the tasks for execution. You can also use the above array and use the random value as the subscript
class WNode {
private int id;
public int priority;
public WNode(int id, int priority) {
this.id = id;
this.priority = priority;
}
@Override
public 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];
// The purpose of the loop is to find requests in the low priority queue when the high priority queue is empty
for (int j = priority; j < 3; j++) {
Queue<WNode> queue = queueList[j];
if (!queue.isEmpty()) {
flag = false;
WNode poll = queue.poll();
System.out.println("Fetch request"+poll+"Start task");
// Take out a request, jump out of the inner loop and continue to execute the outer loop
break;
}
j++;
}
// Only when random to the highest priority,
// Moreover, all priorities in the future are searched, and the loop is exited only when the request is not reached
if (priority == 0 && flag) break;
}
}
}