Tag: Round Robin

CPU Scheduling | Practice Problems | Numericals

CPU Scheduling Algorithms-

 

Various CPU scheduling algorithms are-

 

PRACTICE PROBLEMS BASED ON CPU SCHEDULING ALGORITHMS-

 

Problem-01:

 

Consider three process, all arriving at time zero, with total execution time of 10, 20 and 30 units respectively. Each process spends the first 20% of execution time doing I/O, the next 70% of time doing computation, and the last 10% of time doing I/O again. The operating system uses a shortest remaining compute time first scheduling algorithm and schedules a new process either when the running process gets blocked on I/O or when the running process finishes its compute burst. Assume that all I/O operations can be overlapped as much as possible. For what percentage of does the CPU remain idle?

  1. 0%
  2. 10.6%
  3. 30.0%
  4. 89.4%

 

Solution-

 

According to question, we have-

 

Total Burst TimeI/O BurstCPU BurstI/O Burst
Process P110271
Process P2204142
Process P3306213

 

The scheduling algorithm used is Shortest Remaining Time First.

 

Gantt Chart-

 

 

Percentage of time CPU remains idle

= (5 / 47) x 100

= 10.638%

Thus, Option (B) is correct.

 

Problem-02:

 

Consider the set of 4 processes whose arrival time and burst time are given below-

 

Process No.Arrival TimeBurst Time
CPU BurstI/O BurstCPU Burst
P10322
P20241
P32132
P45221

 

If the CPU scheduling policy is Shortest Remaining Time First, calculate the average waiting time and average turn around time.

 

Solution-

 

Gantt Chart-

 

 

Now, we know-

  • Turn Around time = Exit time – Arrival time
  • Waiting time = Turn Around time – Burst time

 

Also read- Various Times Of Process

 

Process IdExit timeTurn Around timeWaiting time
P11111 – 0 = 1111 – (3+2) = 6
P277 – 0 = 77 – (2+1) = 4
P399 – 2 = 77 – (1+2) = 4
P41616 – 5 = 1111 – (2+1) = 8

 

Now,

  • Average Turn Around time = (11 + 7 + 7 + 11) / 4 = 36 / 4 = 9 units
  • Average waiting time = (6 + 4 + 4 + 8) / 4 = 22 / 5 = 4.4 units

 

Problem-03:

 

Consider the set of 4 processes whose arrival time and burst time are given below-

 

Process No.Arrival TimePriority Burst Time
CPU BurstI/O BurstCPU Burst
P102153
P223331
P331231

 

If the CPU scheduling policy is Priority Scheduling, calculate the average waiting time and average turn around time. (Lower number means higher priority)

 

Solution-

 

The scheduling algorithm used is Priority Scheduling.

 

Gantt Chart-

 

 

Now, we know-

  • Turn Around time = Exit time – Arrival time
  • Waiting time = Turn Around time – Burst time

 

Process IdExit timeTurn Around timeWaiting time
P11010 – 0 = 1010 – (1+3) = 6
P21515 – 2 = 1313 – (3+1) = 9
P399 – 3 = 66 – (2+1) = 3

 

Now,

  • Average Turn Around time = (10 + 13 + 6) / 3 = 29 / 3 = 9.67 units
  • Average waiting time = (6 + 9 + 3) / 3 = 18 / 3 = 6 units

 

Next Article- Introduction to Process Synchronization

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Round Robin | Round Robin Scheduling | Examples

Round Robin Scheduling-

 

In Round Robin Scheduling,

  • CPU is assigned to the process on the basis of FCFS for a fixed amount of time.
  • This fixed amount of time is called as time quantum or time slice.
  • After the time quantum expires, the running process is preempted and sent to the ready queue.
  • Then, the processor is assigned to the next arrived process.
  • It is always preemptive in nature.

 

Round Robin Scheduling is FCFS Scheduling with preemptive mode.

 

 

Advantages-

 

  • It gives the best performance in terms of average response time.
  • It is best suited for time sharing system, client server architecture and interactive system.

 

Disadvantages-

 

  • It leads to starvation for processes with larger burst time as they have to repeat the cycle many times.
  • Its performance heavily depends on time quantum.
  • Priorities can not be set for the processes.

 

Important Notes-

 

Note-01:

 

With decreasing value of time quantum,

  • Number of context switch increases
  • Response time decreases
  • Chances of starvation decreases

 

Thus, smaller value of time quantum is better in terms of response time.

 

Note-02:

 

With increasing value of time quantum,

  • Number of context switch decreases
  • Response time increases
  • Chances of starvation increases

 

Thus, higher value of time quantum is better in terms of number of context switch.

 

Note-03:

 

  • With increasing value of time quantum, Round Robin Scheduling tends to become FCFS Scheduling.
  • When time quantum tends to infinity, Round Robin Scheduling becomes FCFS Scheduling.

 

Also read- FCFS Scheduling

 

Note-04:

 

  • The performance of Round Robin scheduling heavily depends on the value of time quantum.
  • The value of time quantum should be such that it is neither too big nor too small.

 

PRACTICE PROBLEMS BASED ON ROUND ROBIN SCHEDULING-

 

Problem-01:

 

Consider the set of 5 processes whose arrival time and burst time are given below-

 

Process IdArrival timeBurst time
P105
P213
P321
P432
P543

 

If the CPU scheduling policy is Round Robin with time quantum = 2 unit, calculate the average waiting time and average turn around time.

 

Solution-

 

Gantt Chart-

 

Ready Queue-

P5, P1, P2, P5, P4, P1, P3, P2, P1

 

 

Now, we know-

  • Turn Around time = Exit time – Arrival time
  • Waiting time = Turn Around time – Burst time

 

Also read- Various Times of Process

 

Process IdExit timeTurn Around timeWaiting time
P11313 – 0 = 1313 – 5 = 8
P21212 – 1 = 1111 – 3 = 8
P355 – 2 = 33 – 1 = 2
P499 – 3 = 66 – 2 = 4
P51414 – 4 = 1010 – 3 = 7

 

Now,

  • Average Turn Around time = (13 + 11 + 3 + 6 + 10) / 5 = 43 / 5 = 8.6 unit
  • Average waiting time = (8 + 8 + 2 + 4 + 7) / 5 = 29 / 5 = 5.8 unit

 

Problem-02:

 

Consider the set of 6 processes whose arrival time and burst time are given below-

 

Process IdArrival timeBurst time
P104
P215
P322
P431
P546
P663

 

If the CPU scheduling policy is Round Robin with time quantum = 2, calculate the average waiting time and average turn around time.

 

Solution-

 

Gantt chart-

 

Ready Queue-

P5, P6, P2, P5, P6, P2, P5, P4, P1, P3, P2, P1

 

 

Now, we know-

  • Turn Around time = Exit time – Arrival time
  • Waiting time = Turn Around time – Burst time

 

Process IdExit timeTurn Around timeWaiting time
P188 – 0 = 88 – 4 = 4
P21818 – 1 = 1717 – 5 = 12
P366 – 2 = 44 – 2 = 2
P499 – 3 = 66 – 1 = 5
P52121 – 4 = 1717 – 6 = 11
P61919 – 6 = 1313 – 3 = 10

 

Now,

  • Average Turn Around time = (8 + 17 + 4 + 6 + 17 + 13) / 6 = 65 / 6 = 10.84 unit
  • Average waiting time = (4 + 12 + 2 + 5 + 11 + 10) / 6 = 44 / 6 = 7.33 unit

 

Problem-03:

 

Consider the set of 6 processes whose arrival time and burst time are given below-

 

Process IdArrival timeBurst time
P155
P246
P337
P419
P522
P663

 

If the CPU scheduling policy is Round Robin with time quantum = 3, calculate the average waiting time and average turn around time.

 

Solution-

 

Gantt chart-

 

Ready Queue-

P3, P1, P4, P2, P3, P6, P1, P4, P2, P3, P5, P4

 

 

Now, we know-

  • Turn Around time = Exit time – Arrival time
  • Waiting time = Turn Around time – Burst time

 

Process IdExit timeTurn Around timeWaiting time
P13232 – 5 = 2727 – 5 = 22
P22727 – 4 = 2323 – 6 = 17
P33333 – 3 = 3030 – 7 = 23
P43030 – 1 = 2929 – 9 = 20
P566 – 2 = 44 – 2 = 2
P62121 – 6 = 1515 – 3 = 12

 

Now,

  • Average Turn Around time = (27 + 23 + 30 + 29 + 4 + 15) / 6 = 128 / 6 = 21.33 unit
  • Average waiting time = (22 + 17 + 23 + 20 + 2 + 12) / 6 = 96 / 6 = 16 unit

 

Problem-04:

 

Four jobs to be executed on a single processor system arrive at time 0 in the order A, B, C, D. Their burst CPU time requirements are 4, 1, 8, 1 time units respectively. The completion time of A under round robin scheduling with time slice of one time unit is-

  1. 10
  2. 4
  3. 8
  4. 9

 

Solution-

 

Process IdArrival timeBurst time
A04
B01
C08
D01

 

Gantt chart-

 

Ready Queue-

C, A, C, A, C, A, D, C, B, A

 

 

Clearly, completion time of process A = 9 unit.

Thus, Option (D) is correct.

 

To gain better understanding about Round Robin Scheduling,

Watch this Video Lecture

 

Next Article- Priority Scheduling

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.