I’m a process scheduler.

My responsibility is to schedule all the processes in the computer and allocate CPU resources to them.

1. Batch era

When the operating system created me, I was just going to use FCFS scheduling algorithm to simply maintain the order of the process. But I turned out to be way more than he ever imagined.

1.1 FCFS

FCFS is called “First Come First Serve”, where each process is lined up according to the time it enters memory. Whenever a process on the CPU finishes running or blocks, I choose the process at the top of the queue and take it to the CPU to execute.

Take these processes for example:

With FCFS, I would send them to the CPU in the order A, B, C, D, and E:

This algorithm sounds simple and fair, but it didn’t last long. I received a complaint from a short process: “Last time I had a long process in front of me, it took 200 seconds for it to run. It took me only one second to finish the run, because it wasn’t worth the extra time WAITING for him.”

When I think about it, FCFS does have this flaw — the response time of short processes is too long, and the user interaction experience will be worse.

So I decided to change the scheduling algorithm.

1.2 SPN

The algorithm I designed this time was called Shortest Process Next (SPN). Select the process with the shortest expected processing time each time. Therefore, when queuing, I move the short process from the queue to the front.

This time, short processes were well taken care of, and the average process response time was significantly reduced, which pleased me and the operating system.

But the long processes quit: those short processes cut the queue every day, so they often don’t get CPU resources, causing “hunger”.

There are growing calls to cancel the SPN algorithm.

That’s a big problem. FCFS has a long response time, but eventually all processes must have a chance to use CPU resources. The SPN algorithm, on the other hand, will never get a chance to execute if a stream of short processes is added to the queue – terrible.

Therefore, the short task first algorithm needs to be improved. Is there a way to take care of both short and long processes?

1.3 HRRN

After discussion with the operating system, we decided to combine two attributes of a process: wait time and demand service time — processes with long wait times and short demand service times (i.e., short processes) are more likely to be selected.

To quantify, we developed a formula: Response ratio = (wait time + request service time)/Request service time. The algorithm with the highest response ratio executes first. We call this “Highest Response Ratio Next” (HRRN).

This algorithm is well received by both short and long processes. Although my workload increased (I had to recalculate the response ratio of all waiting processes before each dispatch), it was worth it for the fairness of the processes.

2. Concurrent era

It’s a new era.

With the popularity of computers, the number of individual users increased dramatically, and the need for concurrency, or running more than one program at a time, arose. This stumps me – how can I run multiple programs with only one processor?

Fortunately, THE CPU woke me up: “Since my current computing speed is so fast, why not give full play to this advantage and make a” pseudo-parallel “out? “

“Pseudo-parallelism? What do you mean?”

“It looks parallel, but it’s actually serial. Each process alternates my resources for short periods of time, but to the human eye, these processes run as if they were “simultaneous.”

I had an Epiphany.

2.1 the RR

After the CPU’s reminder, I quickly developed a new scheduling algorithm — Round Robin (RR).

In this algorithm, each process will take turns using CPU resources, but when they start running, I turn on a timer for them, and if the timer runs out (or blocks), the process will be forced to “go off” and switch to the next process. As for the choice of the next process, just use FCFS.

New algorithms will inevitably face new problems, and now my question is, how to design the length of the time slice?

Intuitively, the shorter the time slice, the more processes can run in a fixed time, but the CPU said that switching process is to consume a lot of instruction cycles, too short a time slice will lead to a lot of CPU resources wasted on switching context. If the time slice is too long, short interactive instructions will respond slowly. So it depends on how long the interaction takes.

At this stage, my workload increased dramatically — instead of having to switch programs once in a dozen seconds, I now have to switch programs dozens of times a second.

2.2 VRR

The time slice rotation algorithm looks pretty fair — all process time slices are the same. But is that really the case?

I/ O-intensive processes don’t think so, he said to me: “Scheduler, slice rotation doesn’t take care of processes like ours! We often run into blocking operations before we get halfway through the CPU slice, and you kick us out. And we’re in blocking queues, and we tend to stay there for a long time. Once the blocking operation is over, we have to wait in the ready queue for a long time. Those processor-intensive processes that use most of the processor time degrade our performance and response time.”

Given the requirements of these processes, I decided to create a new secondary queue for them. The process that is cleared from blocking will enter the secondary queue. During process scheduling, the process in the secondary queue will be preferentially selected.

This is known as Virtual Round Robin (VRR).

The results show that this method is better than the rotation method. I’m proud of it.

2.3 Priority scheduling

One day, the operating system suddenly found me, mysterious said: “Scheduler, you know, I want to provide services for the whole system, but recently the user process is too much, resulting in my service process sometimes unable to respond. I’m a little concerned about the impact on system stability.”

This is a big deal. The system is unstable. The scheduling algorithm has to change!

If you want operating system services to get enough resources to run, let them have the highest CPU usage priority.

The priority scheduling algorithm was born.

I made it a rule that each process would be assigned a priority, and that the user process would not be given a higher priority than the kernel process.

When switching programs, I select a process from the priority 1 queue. If the priority 1 queue is empty, I select the process from the priority 2 queue, and so on.

Of course, to ensure that low-priority processes don’t starve, I will increase the priority of processes that wait longer.

Using this algorithm, I was much busier, not only switching processes a lot, but also having to adjust priorities dynamically. Maybe it’s just that with great power comes great responsibility.

But I know that because OF me, humans can run multiple programs on computers — and THAT makes me proud.

I hope you have learned something after reading my article.

Thanks for reading and we’ll see you soon!

Disclaimer: Original article, unauthorized reprint prohibited