The OS and the CPU
Overview of different scheduling algorithmsThere 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
- 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. E.g. 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 activityThe 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 cards, and pass each “program” player a different number of 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 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 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?
ThoughtsWhen do you think each algorithm might be used in the real world? Share your thoughts in the comments.
Understanding Computer Systems
Our purpose is to transform access to education.
We offer a diverse selection of courses from leading universities and cultural institutions from around the world. These are delivered one step at a time, and are accessible on mobile, tablet and desktop, so you can fit learning around your life.
We believe learning should be an enjoyable, social experience, so our courses offer the opportunity to discuss what you’re learning with others as you go, helping you make fresh discoveries and form new ideas.
You can unlock new opportunities with unlimited access to hundreds of online short courses for a year by subscribing to our Unlimited package. Build your knowledge with top universities and organisations.