Scheduling (1.2.1)
- 20p13280
- Jan 13
- 5 min read
Scheduling is how and when a process (can be referred to as a "job") is swapped in and out of the CPU (given time slices) to allow for multitasking. A schedular handles this, it manages which process to execute next and it manages the length of time the next process can execute for.
The ready queue is where all processes are kept, then a process is removed from the queue and enteres a running state where the CPU is executing it. A process can either finish execution and leave the system or it can get blocked and require input/output (more data or an operation like a keyboard press or waiting on a hard drive) before it can continue. Whilst a process is blocked it doesn't block other processes from execeuting, it will relinquish control to another process once the process has been placed within a blocked state. Blocked processes are placed into a specific blocked queue that relates to the event that is being waited on.
The scheduler assigns each process a certain small amount of time, if the process goes over this it's suspended and the task is moved to the back of the ready queue to go again.
There are 2 types of scheduling algorithms, Pre-emptive and non pre-emptive.
A pre-emptive scheduling algorithm is where jobs are actively made to start and stop by the operating system. Within pre-emptive the scheduler can interrupt jobs to run another high-priority task instead, such as responding to an OS event or an interrupt. A non pre-emptive scheduling method leaves a process alone once it's started until it's complete.
Scheduling Algorithms
First Come First Serve (FCFS)
Non Pre-emptive
This is a simple algorithm where jobs are added to the end of a queue and then selects a job from the front of the queue to be placed into a running state. As First Come First Serve is non-pre-emptive it means that there is no time slices used, so each process can cause the task queue to wait if a job takes a long time.
Round Robin (RR)
Pre-emptive
Within Round Robin each process is given a time-slice, each CPU time-slice each one of the processes can execute and use their time-slice, then the CPU will move onto the next task. Once the CPU has gone through all the jobs it will then return back to the first process and repeat giving each a time-slice and let's it run again. As Round Robin is pre-emptive it means that it uses time slices and as a result it means that it's used for multitasking as each process seems to be executing at the same time due to the giving each job a time slice and going through each process.
The pseudocode for Round Robin scheduling looks like this:
REPEAT
IF Ready to run queue is NOT empty THEN
Restore the process at the head of the queue
END IF
Run process for fixed length of time
IF process is NOT complete
Add process to the back of the queue
ENDIF
UNTIL ready to run queue is empty.Shortest Job First (SJF)
Non Pre-emptive
Shortest Job First is a very performance focussed and optimised scheduling algorithm. When a new process is added, it's placed in a specific location within the ready queue based on how much time it will take to process. So this means the shortest and fastest jobs will be at the front of the queue and will be executed first. Over-time this gets faster and more optimised as the OS needs to gather information on how long processs take so that is can analyse all the task length data and properly estimate how long a task will take. Since it's non pre-emptive it means there are no time slices and so processes can run for as long as they need to complete.
A downside to Shortest Job First (SJF) is that many larger jobs may never be able to run if shorter jobs keep being added to the front of the queue, leaving longer jobs to get further and further back in the queue.
Shortest Remaining Time (SRT)
Pre-emptive
Shortest Remaining Time is simular to Shortest Job First, however SRT is pre-emptive so processes can be interrupted or pre-empted (where an active process is interrupted to allow a higher-priority task). When a job is added to the queue, the time remaining on the process is checked agains other processes and will be placed infront of all processes that will take longer time to run. This is an improvement compared to Shortest Job First as it means that larger jobs will have a chance to run rather than being kept at the back of the queue as smaller processes are being added, it also increases the priority of larger jobs once its remaining time goes down.
By design the queue has to remain sorted at all times by remaining time, not just re-calculated whenever a new job is added. A jobs remaining time can be referred to as a "burst time".
Multi Level Feedback Queues (MFQ)
A Multi Level Feedback Queue is made up of multiple queues, each having a different priority assigned to them. These queues work on First Come First Serve, where the front of priority level 0 is always run before the head of level 1 and level 2.
Within the example below, the scheduler will always go to Level 0 (the highest priority first) and run the head if there is a process there. If there is no process there then the scheduler works down the priority queues in order looking for a job at the head of the queue.
An approach like this can cause starvation (where many tasks aren't able to run as the scheduler never runs anything outside of the top priorities), this is why MFQ implements a promotion system and demotion system. Processes can be promoted or demoted if they meet the following rules:
New processes are ALWAYS added to the end of level 0 (top priority)
If a process gives up their job on the CPU on it's own accord it will be re-added to the same priority queue at the end of the queue.
If a process is stopped or interrupted by the schedular (pre-empted) it will get demoted to a lower queue.
If a process enteres a Blocked state because it's waiting on I/O it will be promoted one level.
Sources
Comments