One of the main purpose of the Operating System is to control the hardware and more specifically the CPU. The CPU performs all the jobs/processes requested by the different applications. A scheduler is a program of the Operating System that manages the amount of time that is allocated to each job that the CPU needs to process. To do so the scheduler keeps a list of all the jobs that need to be processed. This is called the job queue. The scheduler also uses a scheduling algorithm to determine in which order these jobs will be processed and the amount of processing time to allocate to each job.
The main job scheduling algorithms are:
- FCFS: First Come First Served
- Round Robin
- Shortest Job First
- Shortest Remaining Time First
- Multilevel Feedback Queues
The type of algorithm used by an OS depends on the main functions and characteristics of the system and the typical workload and type of jobs the system will need to process. For instance the scheduler inside a networked printer, the scheduler of a personal tablet computer, the scheduler of a smart speaker and the scheduler of a high spec web-server may all use a different approach to managing their job queue!
Use the tabs below to investigate the characteristics, strengths and drawbacks of the main job scheduling algorithms
FCFS (First Come First Served):
Jobs are executed in the order they arrive. The first job to arrive is the first to be executed, and the process continues in this manner.
- Pros: Simple to implement.
- Cons: Can lead to long wait times, especially if a long job arrives before shorter ones (known as the “convoy effect”).
Typically a networked printer may use a First Come First Served approach to process each printing job in order they were received/added to the printer queue.
Round Robin (RR):
Each job gets a fixed time slice (quantum). If a job doesn’t finish within its time slice, it’s moved to the back of the queue, and the next job in line is given CPU time.
- Pros: A fair approach that prevents any job from monopolising the CPU.
- Cons: Performance can degrade if time slices are too short or too long.
Typically this can be used by multi-user systems such as web servers which have to deal with concurrent requests from many users and want to make sure that each user’s request is processed fairly.
Shortest Job First (SJF):
The job with the shortest burst time (estimated CPU time required) is executed first.
- Pros: Minimises average waiting time.
- Cons: Difficult to predict the exact burst time of a job, and can lead to starvation of longer jobs.
Shortest Remaining Time First (SRTF):
A preemptive version of SJF. The job with the shortest remaining time to completion is executed first. If a new job arrives with a shorter remaining time than the current job, the current job is preempted.
- Pros: Reduces waiting time and responds dynamically to new jobs.
- Cons: Can lead to frequent context switching and is complex to implement.
- Cons: Difficult to predict the exact remaining time of a job, and can lead to starvation of longer jobs.
Multilevel Feedback Queues (MLFQ):
Jobs are placed in different priority queues. If a job doesn’t finish quickly enough, it is moved to a lower priority queue with longer time slices. Jobs that use too much CPU time may be demoted, while I/O-bound jobs can be promoted to higher-priority queues.
- Pros: Adapts well to different types of jobs and improves overall system performance.
- Cons: Complex to manage and implement.
Python Challenge
A scheduler is part of the Operating system. It would most likely have been programmed using low-level (assembly) language. However for the purpose of this task, we are going to use a Python program to create a high-level demo to show how some of the main scheduling algorithms would process a given job queue.
Python Code
We have started the code for you have implemented the First Come First Served algorithm (FCFS).
Your task is to use a similar approach to implement the following scheduling algorithms:
First Come First Served algorithm (FCFS)
Round Robin algorithm
Shortest Remaining Time First algorithm
Solution...
The solution for this challenge is available to full members!Find out how to become a member:
➤ Members' Area
LMC Simulator
Logic Gates Circuits
Network Designer
Flowchart Studio
Online Python IDE