CPU Scheduling Algorithms in Operating Systems (Priority, Round Robin)

CPU Scheduling Algorithms in Operating Systems - Priority, Round Robin

Round Robin Scheduling Algorithm [RR]

  • It is a preemptive scheduling algorithm. It is designed especially for time-sharing systems.
  • In this algorithm, the CPU switches between the processes.
  • When the time quantum expired, the CPU switched to another job.
  • The small unit of time is called time quantum or time slice.
  • The quantum is generally from 10 to 100 milliseconds. The time quantum generally depends on the operating system.
  • In this algorithm, the ready queue is a circular queue. The new process is added to the tail of the ready queue.
ProcessBurst time (in milliseconds)Arrival TimeFinish Time
P130044
P26021
P38024

Time quantum: 5 seconds

P1P2P3P1P2P3P1P1P1P1
05101520212429343944

Average turnaround time:

Turn around time = Finished time – Arrival time
Turnaround time for P1= 44 – 0= 44
Turnaround time for P2= 21 – 0= 21
Turnaround time for P3= 24 – 0= 24
Average turn around time = (44 + 21 + 24) / 3
                         = 89 / 3
                         = 29.66 milliseconds

Average waiting time:

Waiting time = Turn Around Time  – Burst time
Waiting time for P1= 44 – 30= 14
Waiting time for P2= 21 – 6= 15
Waiting time for P3= 24 – 8= 16
Average waiting time = (14 + 15 + 16) / 3
                     = 45 / 3
                     = 15 milliseconds

Average Response time:

Response time = First response – Arrival time
Response time for P1= 0 – 0= 0
Response time for P2= 5 – 0= 0
Response time for P3= 10 – 0= 0
Average Response time = (0 + 5 + 10) / 3
                      = 15 / 3
                      = 5 milliseconds

Priority Scheduling [PR]

Generally, there are two types of priorities Internal Priority and External Priority. The External Priority is external to the operating system.

The CPU is allocated to the highest priority process. If the priority is equal, then it is scheduled in FCFS order.

Priorities are generally some fixed range of numbers like 0 to 4095. There is no general agreement that 0 is the highest or lowest priority. Some systems use low numbers to represent high priority. Others use low numbers to represent low priority. We assume a low number to represent high priority.

The priorities use some measurable quantity/quantities to compute the priorities of the process. For example, Time limits, Memory requirements, the number of open files, and the ratio of average I/O burst to average CPU burst have been used in computing priorities.

ProcessBurst time (in milliseconds)Priority
P162
P2124
P315
P431
P543
P4P1P5P2P3
039132526

Average waiting time:

Waiting time for P1= 3
Waiting time for P2= 13
Waiting time for P3= 25
Waiting time for P4= 0
Waiting time for P5= 9
Average waiting time = (3 + 13 + 25 + 0 + 9) / 5
                     = 50 / 5
                     = 10 milliseconds

Average Turn Around time:

Turn Around Time for P2= 9
Turn Around Time for P3= 25
Turn Around Time for P4= 26
Turn Around Time for P5= 3
Turn Around Time for P5= 13
Average Turn Around time = (9 + 25 + 26 + 3 + 13) / 5
                     = 76 / 5
                     = 15.2 milliseconds

Priority scheduling can be either preemptive or non-preemptive. When a process arrives at the ready queue its priority is compared with the currently executing process.

In preemptive scheduling, if the newly arrived process priority is more than the priority of the currently executing process then the CPU switches to the new process otherwise continue the same process.

The new process is simply attached to the tail of the ready queue.

The major problem with priority scheduling is starvation. Starvation means only high-priority processes are executing, but low-priority jobs are waiting for the CPU for the longest period of time.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top