Introduction
Operating Systems require a way to manage what order they should execute each process in, in a somewhat fair manner. People expect computers to run quickly, even when there are many background processes.
Types of Scheduling
Pre-emptive - The OS actively manages the tasks, such as MFQs, SRT, and RR. Non pre-emptive - Once a job is started, there is no control until it is done, such as FCFS or SJF
Scheduling Algorithms
Round Robin (RR)
- Round robin is the most basic of scheduler.
- In this system each time a job comes in to be completed it is added to the end of a queue.
- Each job is given an amount of CPU time to be completed in.
- There is no risk of a backlog of tasks being created, if a task doesn't finish in the time block, it will be executed after.
- If the job completes within this time, then the next job is loaded.
- If the job is not completed, then it is pushed to the bottom of the queue and waits for its next slot of CPU time.
- This is fine if all the jobs are similar in size and similar in priority.
- This system ignores any priority of a job and ignores that each job will take different amounts of time so can be very inefficient.
First Come First Served (FCFS)
Jobs are processed in chronological order by which they entered the queue. Although this is easy to implement, FCFS again does not allocate processor time based on priority. There is no risk of processor starvation - where a process does not get the chance to execute, just like RR.
Multilevel Feedback Queue (MFQ)
This makes use of multiple queues, each which is ordered based on a different priority. This can be difficult to implement due to deciding which job to prioritise based on a combination of priorities. The CPU will switch between queues to get jobs to complete if a job is waiting too long in one queue it will be moved to a higher priority location in another queue to get the job completed quicker. Each separate queue has its own scheduler to maintain that queue. This system offers the best results, but is very CPU intensive.
Microsoft Windows uses MFQ
Shortest Job First (SJF)
SJF selects the shortest job in the queue to complete first. As it is always looking for the shortest job first, larger processes can face “starvation” and not get completed. Shortest job first is not very feasible for implementation as the operating system rarely knows the amount of time to complete each new job. The OS has to use estimation based on a record of all previous jobs.
Shortest Remaining Time (SRT)
SJF is a pre-emptive version of shortest job first. As a job arrives, it is compared to the currently running job (which is currently the shortest job) if it is longer than the current job then it is added to a queue. If the new job is shorter than the current job, then the current job is pushed to the queue and the new job is worked on. This scheduler requires very little CPU usage as it only makes a comparison as a job arrives or as it completes a job Short jobs are always completed quickly, but bigger jobs will face starvation.