CPU Scheduling Algorithms

On a single-core processor, a CPU can only execute one instruction at a time. But what if multiple processes (computer programs) all want to run at the same time? This is known as multitasking, and for it to work, the OS must let each program in turn run a certain number of instructions on the CPU, swapping between them in short bursts. The OS will have to control how CPU time (and hence number of CPU instructions) is allocated between different processes – it will have to schedule the different processes.

Scheduling Algorithms: An Overview

There are many different algorithms for scheduling computer programs, with different advantages and disadvantages. In all cases, we want to make sure that each program gets a fair amount of processor time, so that all of the programs have a chance to run and complete. We also want to make sure that we make the best use of our computing resources: for example, we don’t want a program to be blocking the use of the CPU while it waits for a file to be slowly read into RAM from a hard disk.

Here are a few common scheduling algorithms.

First Come, First Served (FCFS)

Whichever program is added to the queue first is run until it finishes. Then the next program in the queue is run, and so on.

Shortest Job Next (SJN)

For this algorithm, the OS needs to know (or guess) the time each program will take to run. It picks the program which will take the shortest amount of time as the one to run next.

Priority Scheduling

The OS assigns each program a priority. This could be based on how much memory they take, or how important they are for maintaining a responsive user interface. The program with the highest priority is picked to run next.

Shortest Remaining Time

This is similar to Shortest Job Next, except that if a new program is started, the OS compares the time it needs with the time the currently running program has left. If the new program would finish sooner, then the currently running program is switched out and the CPU starts processing the new program.

Round Robin (RR) scheduling

Time on the CPU is divided into equal parts called “time slices”. Time slices are allocated to each program equally and cyclically. This means that if we had a list of three programs running, the CPU would run:

• Program 1 for one time slice
• Program 2 for one time slice
• Program 3 for one time slice

and would repeat this order until one of the programs finished.

Multilevel Queues

In this algorithm, programs are split into different queues by type — for example, system programs, or interactive programs. The programs of each type form a “queue”.

• • One algorithm will determine how CPU time is split between these queues. For example, one possibility is that the queues have different priorities, and programs in higher priority queues always run before those in lower priority queues (similar to priority scheduling).
  • For each queue, a different queue scheduling algorithm will decide how the CPU time is split within that queue. For example, one queue may use Round Robin scheduling, while another uses priority scheduling.

Analogy: A Real-Life Queue!

Most of these algorithms can be compared to different ways of managing a real-life queue, such as a school dinner queue. The most common way to serve school dinners is First Come First Served, but other methods are possible. The queue could prioritise those who want cold food, as they won’t take up much serving time (Shortest Job Next), or those who need to get to a lunch club (priority scheduling). Alternatively, different classes may be called to queue up for lunch at different times (multilevel queueing, with priority queueing between classes and FCFS within classes).

You may find it useful to ask students which of these they think are fairest, and why, before explaining the link to CPU scheduling.

Unplugged activity

The different scheduling algorithms can be demonstrated with an unplugged activity. Split students into groups of about five. In each group, one person will represent the CPU, while the others will represent different programs.

Take a pack of playing cards, and pass each “program” player a different number of playing cards (to simulate programs that require a lot of processor time and programs that are quick).

The person representing the CPU should then choose a scheduling algorithm to implement, and collect all the playing cards, one at a time, to represent allocating slices of CPU time. For example, for Round Robin scheduling, they would take one card at a time from each other group member in turn.

Once they have completed all the jobs, another person in the group should take the role of the CPU. The playing cards should be redistributed amongst the others in the group and the CPU should simulate a different algorithm.

You may want to use the suits to represent different programs to make it clearer what the CPU is currently running.

Ask your students the following.

• For each algorithm, how long did it take to get a short job done? How about a long job?
• Which algorithm is the most efficient for a long job / a short job / a job that arrives first?
• Overall, what are the pros and cons of each algorithm?

You may want to give this a try yourself beforehand to develop your understanding of the algorithms.

Thoughts

When do you think each algorithm might be used in the real world?