Operating System — Scheduling

Understand Scheduling in just 5 minutes

Photo by Lukas Blazek on Unsplash

Your computer is performing hundreds and thousands of tasks at the same time every day. Have you ever thought about how it handles so many things in a stable and organised way?

What is Scheduling?

Scheduling is the procedure of deciding which process to run next and allocate resources to it to perform tasks. We often mention “Context Switching” when discussing scheduling. It is the actual switching procedure, from one process to another.

When does context switching happen?

The image below shows the lifecycle of a process. If you want to know more about process management, feel free check out my previous article.

Operating System — Process Management

Process lifecycle

There are many ways to make context switching happen:

1. Whenever a process goes to blocking / waiting state (wait()/sleep())
2. When a POSIX signal arrives (SIGCHLD)
3. When an interrupt arrives (keystroke)
4. When the OS scheduler interrupts and stops the process (round-robin, round-robin with priority)

Take a deep look on context switching

You may be wondering what context switching is actually doing in.

Suppose a process gives up running on the CPU. For examples, calling sleep().

Then, the scheduler is going to choose the next process to run.

Backup all current context

But, before the scheduler can seize the control of the CPU, CPU has to backup all current context of that process to the kernel-space memory:

• current register values
• program counter (which line of code the current program is at)

Load context of process from the main memory

If the scheduler decides to schedule another process in the ready queue, the schedule has to load the context of that process from the main memory to the CPU.

This entire operation is called “Context Switching”.

Context Switching is expensive

Direct costs in kernel:

• Save and restore registers, etc.
• Switch address space (expensive instructions)

Indirect costs:

• cache
• buffer cache
• TLB misses

What is process scheduling?

Scheduling is required because the number of computing resource — the CPU — is limited.

When a process is chosen by the scheduler, the process would have the CPU until:

• the process voluntarily waits for I/O
• the process voluntarily releases the CPU (e.g. exit())
• the process detects particular kinds of interrupts (e.g. periodic clock interrupt)

In old days, it was called “time-sharing”. Nowadays, all systems are time-sharing.

For process scheduling, there are different scheduling algorithms.

Scheduling algorithms

Shortest-job-first (SJF)

Whenever a new process arrives at the system, the scheduler steps in and selects the next task based on their remaining CPU requirements.

Scheduler will CPUs to handle process A first as there is only one process

Scheduler will assign CPUs to handle the new process (process B) first as it requires the least resources

After running process B, the CPUs will continue to handle process A

If new process (process C) with lower resources requirement arraives, the CPUs will switch to handle it first

After running process C, the CPUs will continue to handle process A

Process D will be ignored for now as process A requires less resources

Process D will be handled after finishing process A

Done

The drawback of this algorithm is the number of context switching can be high as context switching is expensive.

Round-robin

Round-Robin (RR) scheduling is preemptive.

Processes are running one-by-one as a circular queue and with no priority.

• New processes are added to the tail of the ready queue
• New process arrives will not trigger a new selection decision

Every process is given a quantum of 2, or the amount of time allowed to execute

CPUs will handle process A first and only process the given quantun

After process A has used up the quantum, scheduler will then assign CPUs to handle the next process, which is process B

Whenever the quantum of a process is used up, the process releases the CPU and this is the preemption.

Process B will consume the quantum

Then, the scheduler steps in and it chooses the next process which has a non-zero quantum to run.

After process Bhas used up the quantum, scheduler will then assign CPUs to handle the next process, which is process C

After finishing process C, CPUs will then handle process D

After a round, the quantums of the processes have been reset

If all processes in the system have used up the quantum, they will be re-charged to their initial values.

CPUS will handle process A

CPUs have finished processing process B

At the meanwhile, quantum of process A are reset

Done

Priority Scheduling

A task is given a priority and is usually an integer.

• A scheduler selects the next process based on the priority
• Higher priority process + Round-Robin = priority queue + new process arrival triggers a new selection

Static priority scheduling

Static priority scheduling

Process is assigned a fix priority when they are submitted to the system. The highest priority class will be selected. The tasks are usually short-lived, but important

To prevent high-priority tasks from running indefinitely, lower priority classes will be scheduled only when the upper priority classes has no tasks.

Multiple queue priority scheduling

Multiple queue priority scheduling

It is still a priority scheduler. But, at each priority class, different schedulers may be deployed. The priority can be a mix of static and dynamic.

Next Steps

If you’re reading this line, congratulations!!! You made it. You have learnt the basics of scheduling and the most common scheduling algorithms.

Feel free to check other articles about operating system below:

Overview of Operating System

To know more about my backend learning path, check out my journey here:

My Backend Developer Learning Journey 我的後端學習之旅