Updated date:

Uniprocessor Scheduling Policies

Key terms

Arrival Time : Time at which any process arrives in ready queue.

Burst Time : Time required by CPU for execution of a process. It is also called as Running Time or Execution Time.

Completion Time : Time at which process completes its execution.

Turn Around Time : is the total amount of time spent by a process in the system, from submission time to completion.

Waiting Time : How much time processes spend in the ready queue waiting their turn to get on the CPU

Response Time : The time taken in an interactive program from the issuance of a command to the commence of a response to that command.

Preemptive Scheduling : It is used if there is process switching from running state to ready state or from ready state to waiting state.

FCFS Scheduling

  • Simplest CPU Scheduling
  • non-preemptive decision mode
  • upon process creation, link its PCB to the rear of the FIFO queue
  • Scheduler allocates the CPU to the process at the front of the FIFO queue

Consider:
Process Burst Time
P1 24
P2 03
P3 03
Process execution order P1->P2->P3
Average waiting time (0+24+27)/3=7

Shortest Process Next Scheduling (SJF)

  • Associate the length of the next CPU burst with each process
  • Assign the process with shortest CPU burst requirement to the CPU
  • Non-preemptive scheduling
  • Suitable for batch processing (long term scheduling)
  • Ties broken by FIFO method
  • Method falls prey to the halting problem
  • Longer process has to wait for longer time


Consider an example:
Process Burst Time
P1 6
P2 8
P3 7
P4 3
Scheduling is done as P4->P1->P3->P2
Average waiting time (3+16+9+0)/4=7
Comparing with FIFO, the avg waiting time is (0+6+14+21)/4=10.25

The SJF algorithm although optimal cannot be implemented at the level of short-term CPU scheduling because there is no way to know the length of the next CPU burst. An SJF algorithm is simply a priority algorithm where the priority is the inverse of the next CPU burst.

Shortest Remaining Time First scheduling

  • Preemptive version of SJN (Shortest Job First)
  • Preemptive at job arrival time
  • Highest priority to process that needs least time to complete

Consider:
Process Arrival Burst Time
P1 0 7
P2 2 4
P3 4 1
P4 5 4

At time 0 only Job P1 is requesting for service, so P1 enters the CPU and served for 2 units of time.
At time 2 P2 enters the system, Now comparing P1 which requires 5 units of work time and P2 requires 4 unit of work time, therefore preemption occurs and the CPU switches to P2.
At time 4 P3 enters the system, Now P1 requires 5 unit of work, P2 requires 2 unit of work and P3 requires 1 unit of work, so again a context-switch occurs and P3 is selected to complete.
At time 5 P4 enters the system, Now all process in question has arrived. The algorithm selects the job P2 which needs the least amount of time and P2 is being served for 2 units of time completes its remaining task. Next, comparing P4 and P1, P4 continues to execute till its completion, and finally P1 completes to end.


Scheduling is done as P1->P2->P3->P2->P4->P1
avg waiting time (9+1+0+2)/4=3 (preemptive version)
Comparing with non-preemptive, avg waiting time of SJF is 4

taking another example,
Process Arrival Burst
P1 0 8
P2 1 4
P3 2 9
P4 3 5
Schedule of execution P1 P2 P4 P1 P3
1 2-5 6-10 11-17 18-26
average waiting time ((10-1)+(1-1)+(17-2)+(5-3))/4=6.5

Round Robin Scheduling

  • Preemptive in nature based on time quantum
  • All user process treated of same priority
  • Ready queue treated as circular queue
  • New process added to the rear of the ready queue
  • Preempted process added to the rear of the ready queue
  • No process is allowed to use CPU more than 1 time-slice when other jobs waiting in ready queue.

Each process gets a small unit of CPU time, by a timer interrupt set after the time quantum; after this time has elapsed the process is preempted and added to the end of the ready queue.

  • Higher average turnaround time than SJF, but better response time
  • Designed for time sharing systems.

Consider an example:
Process Execution Time
P1 25
P2 5
P3 5
Scheduling is done as P1 -> P2 -> P3 -> P1
using quantum=5, 0-5 6-10 11-15 16-35

Illustrating another example of Round Robin scheduling, the chart below shows the gantt chart in the top row, and the second row showing the FIFO queue contents in respect to time.
In Round Robin process scheduling, we need to remember the following points:
1. Newly arrived process are put in the tail of the ready queue.
2. No process can use more than 1 time-slice when some other process waiting in the ready queue.
3. Preempted process are added to the tail of the ready queue, and the process in front of the FIFO queue is selected for its turn for 1 time slice.

Considering another example using RR scheduling with time quantum=2

P1:- Arrival time=0, Time units required=5;
P2:- Arrival time=1, Time units required=7;
P3:- Arrival time=3, Time units required=4; New process and preempted process are all put at the tail of the ready queue; After preemption, the CPU picks the next job waiting in front of the queue.

In the example, P1 arrives at time 0, so P1 gets executed by the CPU first.
At time 2, P1 gets preempted and added to the tail of the queue, also P2 (front of queue) which was waiting starts executing its turn for 1 time slice. At time 3 P3 enters the system, and P3 is put at the tail of the queue, behind P1.
At time 4 P2 is preempted and put in the tail of the ready queue, behind P3. The next process waiting in front is P1, so P1 executes for another time slice. Now all process have arrived, we can imagine our circular queue as P1-P3-P2, executing in turn till its execution time has completed.
The gantt chart yields:
P1(2) - P2(4) - P1(6) - P3(8) - P2(10) - P1(11) - P3(13) - P2(16)
Thus the Completion order sequence is P1 at time 11, P3 at time 13, P2 at time 16.

Round Robin Scheduling example

Round Robin Scheduling

Round Robin Scheduling

Priority scheduling

A priority number is associated with each process. The CPU is allocated to the process with the highest priority. (smallest integer = high priority)

Problem: Starvation - low priority process may never execute
Solution: Aging - as time progresses, increase the priority of the process

Consider:
Process Burst Priority
P1 10 3
P2 1 1
P3 2 4
P4 1 5
P5 5 2
Scheduling order P2 -> P5 -> P1 -> P3 -> P4
0-1 2-6 7-16 17-18 19
average waiting time = 8.2

CPU Scheduling explained

Process Scheduling example

Uniprocessor Scheduling

Uniprocessor Scheduling

© 2020 Dipankar Basu