Table of Contents
A scheduling algorithm is a technique or method that is used to organize, manage and check work and workloads on a CPU. Types of scheduling algorithms are FCFS, SJF, priority scheduling, etc. To learn more let’s read it further.
Scheduling is based on the information that is available at a given time. We need some way to represent the state of the system and any processes in it and how it changes over time.
Gantt charts are used for this purpose. A Gantt chart is basically a glorified timeline that is used to depict the order of process execution graphically.
Each scheduling algorithm has its own criteria to choose the next job that will run on the CPU. Since CPU scheduler needs to be fast, actual algorithms are typically not very complex.
Related Content:
Timelines
Scheduling is based on the information that is available at a given time. We need some way to represent the state of the system and any processes in it and how it changes over time. Gantt charts are used for this purpose. A Gantt chart is basically a glorified timeline that is used to depict the order of process execution graphically. Below is an outline of a Gantt chart
First process name | Second process name | More processes |
Start-time 1st process end time second process end-time……End time
First come first served is the simplest CPU scheduling algorithm. It says that the process that enters first should get. FCFS algorithm is easy to understand. It is basically a queue like those we see in banks, shops, etc.
A drawback of the FCFS algorithm is that the processes may have to wait for excessively long amounts of time.
Example
Suppose that there are three processes that arrive in the order shown below. They all arrive at time 0, but the system has decided to serve them in this order.
Process name | Start time | Burst time |
Process 1 | 0 | 24 |
Process 2 | 0 | 3 |
Process 3 | 0 | 3 |
Gantt Cart for FCFS Example
If the processes are served in FCFS order, the Gantt chart would look like as follows:
Process 1 | Process 2 | Process 3 |
0 24 27 30
Process 1 is dispatched first and runs for 24-time units (there is no preemption). Once process 1 has finished, process 2 is dispatched and runs for 3-time units.
24-time units have already elapsed, so process 2 starts at time 24. Once process 2 has finished at time 27, the process is dispatched. When process 3 has finished there have been 30-time units used (24+3+3).
The waiting time for a particular process can be measured by taking its finish time and subtracting the burst time and its arrival time. The following table shows the waiting time for each process:
Process name | Arrival time | Burst time | Finish time | Waiting time |
Process 1 | 0 | 24 | 24 | 0 |
Process 2 | 0 | 3 | 27 | 24 |
Process 3 | 0 | 3 | 30 | 27 |
Waiting time = finish time – burst time – arrival time
The average waiting time for a whole set of processes can be calculated by adding all the individual waiting times and dividing by the number of processes. In the above example, the average waiting time is : (0+24+27)/ 3 = 17.
Another way to schedule jobs is to pick the job that will take the least amount of time to complete. In FCFS scheduling, the average waiting time could be reduced by running the short jobs first.
The SJF scheduling, the average waiting time could be reduced by running the short jobs first. The SJF scheduling algorithm picks the shortest job in terms of burst size and places it on the CPU.
There are two possible schemes of this scheduling algorithm
Shortest job first scheduling gives the minimum average waiting time for a given set of processes. If you run all the short jobs first, then each subsequent job has a relatively short waiting time. If you were to run all the long jobs first, then every subsequent job would have a longer time to wait.
Non-Preemptive SJF Example
In the following example there are four processes.
Process name | Arrival time | Burst time |
Process 1 | 0 | 7 |
Process 2 | 2 | 4 |
Process 3 | 4 | 2 |
Process 4 | 5 | 4 |
Gantt Chart for SJF example
Process 1 | Process 3 | Process 2 | Process 4 |
0 7 9 13 17
The waiting times for the processes in this example are:
Process name | Arrival time | Burst time | Finish time | Waiting time |
Process 1 | 0 | 7 | 7 | 0 |
Process 2 | 2 | 4 | 13 | 7 |
Process 3 | 4 | 2 | 9 | 3 |
Process 4 | 5 | 4 | 17 | 8 |
The average waiting time is : (0 + 9 + 3 + 8) / 4 = 5
Preemptive SJF Example
In the following example, there are again four processes. Note that process 3 now has a burst time of 1.
Process name | Arrival time | Burst time |
Process 1 | 0 | 7 |
Process 2 | 2 | 4 |
Process 3 | 4 | 1 |
Process 4 | 5 | 4 |
Gantt chart for SJF example
Process 1 | Process 2 | Process 3 | Process 2 | Process 4 | Process 1 |
0 2 4 5 7 11 16
The waiting times for the process in this example are:
Process name | Arrival time | Burst time | Finish time | Waiting time |
Process 1 | 0 | 7 | 16 | 9 |
Process 2 | 2 | 4 | 7 | 1 |
Process 3 | 4 | 1 | 5 | 0 |
Process 4 | 5 | 4 | 11 | 2 |
The average waiting time is : (9 + 1 + 0 + 2) / 4 =3
Another way to schedule jobs is to pick the job that has the highest priority. This requires that each process should have a priority associated with it.
The priority is generally an integer with some well-defined range e.g 1 to 10. The CPU is allocated to the process with the highest priority. In some systems, smaller numbers mean higher priority, in other systems larger numbers mean higher priority.
Priority scheduling can either be non-preemptive or preemptive. If there is preemption then a high-priority job can remove a low-priority job from the CPU and take over.
Non-preemptive example
Process name | Burst time | Priority |
Process 1 | 10 | 3 |
Process 2 | 1 | 1 |
Process 3 | 2 | 3 |
Process 4 | 1 | 4 |
Process 5 | 5 | 2 |
Assume that all processes arrived at time 0. First of all, process 2 will get the CPU as it has the highest priority 1 and will finish. Then process 5 will start execution. In non-preemptive priority scheduling, once a process gets the CPU, it will finish its work and then release the CPU.
Gantt chart for Non-preemptive priority scheduling
Process 2 | Process 5 | Process 1 | Process 3 | Process 4 |
0 1 6 16 18 19
The average waiting time is: (1 + 6 +16 + 18 + 19 ) / 5 =8.2
Preemptive example
Process name | Arrival time | Burst time | Priority |
Process 1 | 0 | 10 | 3 |
Process 2 | 2 | 1 | 1 |
Process 3 | 4 | 2 | 2 |
Process 4 | 6 | 1 | 4 |
Process 5 | 8 | 5 | 5 |
In the above example the execution takes place in the following sequence:
Gantt chart for preemptive priority scheduling
P1 | P2 | P1 | P3 | P1 | P4 | P5 |
0 2 3 4 6 13 14 19
Shortest job first scheduling is also a form of priority scheduling. In the case of shortest job scheduling, the priority is defined as the predicted next CPU burst.
One major problem with priority-based scheduling is that it may not be fair. Some low-priority processes may not ever get the chance to execute because higher priority processes keep steeling the CPU. One solution to this problem is to implement aging. The process of increasing the priority of a process as it gets order is known as aging.
Another way to schedule jobs is to align a small amount of time to each process in which it executes. The small time unit is usually called the time quantum or time slice.
The job is allocated to the CPU for the time quantum. When the time quantum expires, the process is preempted from the CPU and replaced by the next process in the circular queue.
Example
Process name | Burst time |
Process 1 | 24 |
Process 2 | 3 |
Process 3 | 3 |
Gantt chart for round-robin scheduling
Process 1 | Process 2 | Process 3 | Process 1 | Process 1 | Process 1 | Process 1 | Process 1 |
0 4 7 10 14 18 22 26 30
Process 1 gets the first 4 units of time. It requires another 20 units so it is preempted after the first time quantum. CPU is given to process 2 that does not require 4 units. It quits before its time quantum ends and the CPU is given to process 3.
Once each process has got a one-time quantum, the CPU is given to process 1 for additional time quantum. Average turnaround time is 47 / 3 = 16.
The round-robin algorithm does not allocate CPU to any process for more than one-time quantum in a row. If CPU burst exceeds time quantum, it is preempted and placed in the ready queue. That is why a round robin is called a preemptive scheduling algorithm.
The round robin scheduling algorithm will be similar to FCFS if the time quantum is very large. If the time quantum is larger than the largest CPU burst for all the processes, then no process will be preempted.
If the time quantum is made too small, then the context switch will take too much time. It is required when preempting one process from the CPU and replacing it with another.
The previous scheduling algorithms treated different kinds of processes in the same fashion, typically, there is a distinction between interactive processes and non-interactive processes. The interactive processes generally required a much faster response time than non-interactive processes.
These processes can be separated and can be scheduled separately. The interactive processes should be scheduled more quickly than non-interactive processes.
The ready queue can be split into different sub-queues. One sub-queue can be used for each type of process. An example of 5 level queuing strategies is shown below. The 0 has the highest priority and the 4 has the lowest priority.
The type of process is automatically identified when it enters the system. It is allocated to the correct queue. There is no way to change queues once a process has been allocated to a queue.
There are five queues in the above example. The individual jobs, as well as five queues, need to be scheduled. Two skills to schedule the queues are as follows:
In this scheme, jobs are first serviced 1. If there is no job in queue 1, then the jobs in queue 2 are serviced. Similarly, jobs in queue 3 are all serviced only if there are no jobs in queues 1 or 2 and so on.
Time Slice
In this scheme, each queue gets a time slice. The queues themselves are in a round robin queue. Jobs is each queue are executed for the specified amount of time. The control is then transferred to the next queue.
The main difference between a multi-level queuing strategy and a multi-level feedback queuing strategy is that jobs may move from one queue to another over time.
It is possible to implement aging this way. A process moves up to the next higher priority queue if it stays in one queue too long. The multi-level feedback queue strategy is defined by the following parameters:
Suppose there are three queues:
The scheduling will be implemented as follows:
A new job enters queue Q0, which is served FCFS. When it gains CPU, the job receives 8 milliseconds. If it does not finish in 8 milliseconds, the job is moved to queue Q1. At Q1, the job is again served FCFS and receives 16 additional milliseconds. If it still does not complete, it is preempted and moved to queue Q2.
Read More:
Having bad credit can make it challenging to obtain a personal loan, but it's not… Read More
Traveling doesn't have to break the bank. With some careful planning and smart strategies, you… Read More
Are you looking for a job in the fruit packing industry with the added benefit… Read More
Are you considering a move from the United States to Canada? Whether it's for a… Read More
A credit card is a financial tool that allows you to borrow money from a… Read More
Watching sports online for free can be challenging due to the licensing agreements and restrictions… Read More