Process Scheduling

Process scheduling algorithms

Linux is multitasking operating system. It gives feel to user that there are many tasks which are running simultaneously in system. However, there is only one processor, which can execute only one task at a time, how is this possible? This is where scheduling of process come into picture.

Kernel, wisely switches processes from processor to give feeling of simultaneous execution. The switching rate should be decided cautiously, as if it is too low, task would not look simultaneous, if it too high, kernel will be too busy switching processes. Following are the criteria which are usually looked for when deciding on scheduling approach:
1. Throughput : Number of processes which complete in per unit of time
2. Response time : It is difference between the time when process is taken for execution and the time it was submitted.
3. Turnaround time : It is difference between time when process finishes execution and time when it was submitted.
4. Fair chance : It should not happen that some process starve in need of process for execution.

Following are the approaches which are usually adopted by operating systems for scheduling :

1. First Come First Serve

This approach works on FIFO principle i.e the process which comes first is scheduled first. It gives very good response time but throughput and turnaround time may not be very good. Process moves to wait queue when it request some I/O. Other process is selected from head of runnable queue and granted processor.

For example if arrival rate of process is as follows, execution sequence is given below

Process
CPU burst
P1
4
P3
8
P2
6
 

2. Round Robin

Kernel gives a particular quantum of time to every process for which it can execute on processor. If that quantum finishes or process requests I/O, processes is taken at back of queue till the time again gets the time to execute.It’s non preemptive approach.

Round Robin approach
For example if arrival rate of process is as follows, execution sequence is given  below
Process
CPU Burst
P1
4
P2
6
P3
8

3. Shortest Job First

In this approach, kernels selects a process which has shortest time for execution to finish. It reduces the average response time.  There is another preemptive variant of it called as Shortest Remaining Time First. It takes into consideration the remaining time of task and task can be preempted in between unlike Shortest Job First where process runs to completion.

For example if arrival rate of process is as follows, execution sequence is given  below:

Process
CPU Burst
P1
4
P2
6
P3
8

There are two terms we should be knowing while learning scheduling.
One, is CPU bound and I/O bound processes. If a process uses CPU most of the time during execution, it is called as cpu bound process. If a process does I/O operation most of the time and uses CPU sporadically, process is called as I/O bound process.

Second is preemptive and non-preemptive : If other process can preempt or interrupt execution of current process and move it from the process, we call it as preemptive system. If other process does not have that capability, it is called non-preemptive system.
Above explanations of scheduling algorithms are too simplistic. Let’s spice them up 🙂 As in Round Robin approach, every process gets equal amount of time on process, that means kernel treats every process with equal priority. Is that the case in real word? No.

So let’s take priority into consideration now during scheduling a process. This is called as priority scheduling. Of all the process which are runnable, the process which has highest process will get the processor.

There are two kinds of priorities associated with a given process

1. Static priority : It is the priority which remains same throughout the lifetime of process.
2. Dynamic priority : This is adjusted during run time by the process using some parameters like remaining time, base priority etc.  Scheduler uses this priority of boost chances of execution of process which are not scheduled for long time or decrease chances of process of execution which are executed for long time.