This is the 29th day of my participation in the August More Text Challenge
In our daily life, we often hear such terms as train scheduling and dispatcher. In programming, the operating system is the one we most contact with. Because of the limited resources of the operating system and more processes running on the operating system, scheduling will be used at this time to do the most things with limited resources. In scheduling, there are several commonly used algorithms: first come, first served (FCFS), short Job First (SJF), time slice rotation (RR) and priority scheduling (HPF). The following are several scheduling algorithms.
First come, first served (FCFS)
- An overview of the
First come, first service, first is exquisite, like we went to a restaurant food, first come, first dozen rice, then people would line up If you encounter a task blocking this algorithm needs to wait for other resources can perform follow-up after operation, it would have been blocked in this task, other subsequent tasks need to queue for a long time, In this case, resources will be wasted. This algorithm is only applicable to services with balanced processing time. In this case, too much time will not be wasted.
- Introduction to algorithm Implementation
This algorithm can be implemented using BlockingQueue, where the queue heads are taken out in the order they were put in first, and then executed. The tasks that need to be executed are put in the end
- Simple code
public class FCFS {
public static void main(String[] args) throws InterruptedException {
final LinkedBlockingQueue<Runnable> queue = new LinkedBlockingQueue(5);
// Simulate executing a task
new Thread(() -> {
while (true) {
try {
queue.take().run();
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}).start();
// Simulate the storage task
for (int i = 0; i < 5; i++) {
intfinalI = i; queue.put(() -> { System.out.println(finalI); }); }}}Copy the codeShort work priority (SJF)
- An overview of the
During each scheduling, a task with short execution time is selected from the pool to be scheduled, and the tasks executed in each scheduling are all tasks with short execution time. Since the execution time is informed to the scheduler based on its own estimation, it may not be very accurate. This algorithm is suitable for the task time difference is bigger of the two scenarios, the execution time larger went back on, such as short execution time after completion of the execution of the execution, but the algorithm for priority is higher, are not so friendly and a long task execution time, for long assignment of tasks, may have been occupied by a short homework assignment to be enforced.
- Introduction to algorithm Implementation
TreeMap can be used to implement this algorithm. The map automatically sorts according to key values and obtains the smallest key each time to perform tasks.
- Simple code
public class SJF {
public static void main(String[] args) {
final TreeMap<Integer, Runnable> map = new TreeMap<>();
// Simulate executing a task
new Thread(() -> {
while (true) {
Map.Entry<Integer, Runnable> entry = map.pollFirstEntry();
if(entry ! =null) {
System.out.println("The current key." + entry.getKey());
entry.getValue().run();
}
}
}).start();
// Simulate the storage task
for (int i = 0; i < 5; i++) {
map.put(new Random().nextInt(1000), () -> {
System.out.println("Execution time :"+new Random().nextInt(10)); }); }}}Copy the codeExecution Result:
As can be seen from the result, the smallest key is taken from the map for execution each time, and the actual execution time of the task is not concerned.
Time slice rotation (RR)
- An overview of the
Slice rotation is one of the oldest, simplest, and most widely used algorithms used by operating systems. A period of time is allocated for all tasks to be executed. When the time slice is used up, the execution of the task is suspended and the time slice is allocated to other tasks. After the task obtains the time slice, it can continue to execute the task. Because in the execution, the process will keep switching, in the process of switching will also cause a waste of resources, so in programming we sometimes use multi-thread execution task is not necessarily faster than single thread execution, because CPU switching will also cause a certain waste.
- Introduction to algorithm Implementation
There is no good implementation of the algorithm
Priority scheduling (HPF)
- An overview of the
Priority scheduling is to determine the order of execution according to the priority of the task. When scheduling tasks, the order of execution is determined according to the priority of the task to be executed, and the task with higher priority is selected for execution each time, just like the concept of VIP and VVIP in life, the task with higher priority is executed first.
- Introduction to algorithm Implementation
TreeMap can also be used to implement this algorithm, but the key is stored in priority, and the task with a larger key is selected for execution each time
- Simple code
public class HPF {
public static void main(String[] args) {
final TreeMap<Integer, Runnable> map = new TreeMap<>();
// Simulate executing a task
new Thread(() -> {
while (true) {
Map.Entry<Integer, Runnable> entry = map.pollLastEntry();
if(entry ! =null) {
System.out.println("The current key." + entry.getKey());
entry.getValue().run();
}
}
}).start();
// Simulate the storage task
for (int i = 1; i<= 5; i++) {
map.put(i, () -> System.out.println("Execution time :" + new Random().nextInt(1000))); }}}Copy the codeThe execution result
If the key of the first execution is 2, it is possible that the following data is not saved during the execution of the task, so the task of 1 is taken to be executed first. When the second execution is carried out, more tasks are stored in it, and the tasks are executed in descending order according to the priority of the key