Scheduling
Process Scheduling
In computer systems multiple processes may be waiting to be executed by the processor and the processor needs to decided and how to schedule processing. There are multiple scheduling algorithms that can be used, depending on the system. These include:
- Round Robin
- First Come First Served
- Short Job First
- Shortest Remaining Time First
Process Priorities
In most computer systems, processes have different priorities, depending on their function within the system.
Calculations
Process Scheduling Calculations
Turnaround Time
Turnaround time = Completion time – arrival time
This is the duration between a process arriving and it terminating
Waiting Time
Waiting time = Turnaround time – burst time
This is how long a process waits idle before it is fully executed.
Average Waiting Time
Average Waiting Time = Waiting time for all processes / Number of processes
This is how long a process has to wait on average before it is fully processed.
States
Process States
Processes can be in one of 3 states.
Running
This is where the process is currently being executed by the processor
Ready
This is where the process is loaded into memory, ready to be executed.
Blocked
This is where the process is waiting for an event to occur before it is processed.
Round Robin
Round Robin Scheduling
In round-robin scheduling the processor works on each process in a circular manner. Each process is assigned an equal time-slice (aka quantum) for execution. Once the time-slice has been used up the process is blocked and will have to wait until the next time round to carry on executing. If a process completes before it reaches it’s quantum limit then it self terminates the processor moves onto the next process.
Advantages
- All processes are treated equally
- All processes are guaranteed to be processed eventually
Disadvantages
- Results in a high average waiting time
FCFS
First Come First Served Scheduling
Here jobs are executed in the order in which they arrived.
Advantages
- All processes will be processed eventually.
Disadvantages
- Large processes will cause a bottleneck (Convoy Effect)
SJF
Shortest Job First Scheduling
Here the process with the shortest estimated burst time is executed first. As new processes arrive their estimated burst is compared with the current process to see which process is to be executed.
Advantages
- Can result in a lower average waiting time
Disadvantages
- Requires the ability to accurately estimate burst times
- Can result in priority inversion, depending on the system
SRTF
Shortest Remaining Time First Scheduling
Here the job with the least amount of remaining burst time is processed first. If a new job arrives with a shorter burst time than the job currently being executed then the current job is moved to the blocked queue and the new job is executed.
Useful in batch systems where smaller jobs need to be given priority.
Advantages
- Can result in the lowest average waiting time
Disadvantages
- A certain amount of processing time is required to calculate remaining burst times and switch between tasks (context switching)
- The system must be able to accurately estimate burst times for each process, therefore SRTF can only be used in certain systems.