Tag: CPU Scheduling

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.

SJF Scheduling | SRTF | CPU Scheduling

SJF Scheduling-

 

In SJF Scheduling,

  • Out of all the available processes, CPU is assigned to the process having smallest burst time.
  • In case of a tie, it is broken by FCFS Scheduling.

 

 

  • SJF Scheduling can be used in both preemptive and non-preemptive mode.
  • Preemptive mode of Shortest Job First is called as Shortest Remaining Time First (SRTF).

 

Advantages-

 

  • SRTF is optimal and guarantees the minimum average waiting time.
  • It provides a standard for other algorithms since no other algorithm performs better than it.

 

Disadvantages-

 

  • It can not be implemented practically since burst time of the processes can not be known in advance.
  • It leads to starvation for processes with larger burst time.
  • Priorities can not be set for the processes.
  • Processes with larger burst time have poor response time.

 

PRACTICE PROBLEMS BASED ON SJF SCHEDULING-

 

Problem-01:

 

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

 

Process IdArrival timeBurst time
P131
P214
P342
P406
P523

 

If the CPU scheduling policy is SJF non-preemptive, 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
P177 – 3 = 44 – 1 = 3
P21616 – 1 = 1515 – 4 = 11
P399 – 4 = 55 – 2 = 3
P466 – 0 = 66 – 6 = 0
P51212 – 2 = 1010 – 3 = 7

 

Now,

  • Average Turn Around time = (4 + 15 + 5 + 6 + 10) / 5 = 40 / 5 = 8 unit
  • Average waiting time = (3 + 11 + 3 + 0 + 7) / 5 = 24 / 5 = 4.8 unit

 

Problem-02:

 

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

 

Process IdArrival timeBurst time
P131
P214
P342
P406
P523

 

If the CPU scheduling policy is SJF preemptive, 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

 

Process IdExit timeTurn Around timeWaiting time
P144 – 3 = 11 – 1 = 0
P266 – 1 = 55 – 4 = 1
P388 – 4 = 44 – 2 = 2
P41616 – 0 = 1616 – 6 = 10
P51111 – 2 = 99 – 3 = 6

 

Now,

  • Average Turn Around time = (1 + 5 + 4 + 16 + 9) / 5 = 35 / 5 = 7 unit
  • Average waiting time = (0 + 1 + 2 + 10 + 6) / 5 = 19 / 5 = 3.8 unit

 

Problem-03:

 

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

 

Process IdArrival timeBurst time
P107
P215
P323
P431
P542
P651

 

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

 

Process IdExit timeTurn Around timeWaiting time
P11919 – 0 = 1919 – 7 = 12
P21313 – 1 = 1212 – 5 = 7
P366 – 2 = 44 – 3 = 1
P444 – 3 = 11 – 1 = 0
P599 – 4 = 55 – 2 = 3
P677 – 5 = 22 – 1 = 1

 

Now,

  • Average Turn Around time = (19 + 12 + 4 + 1 + 5 + 2) / 6 = 43 / 6 = 7.17 unit
  • Average waiting time = (12 + 7 + 1 + 0 + 3 + 1) / 6 = 24 / 6 = 4 unit

 

Problem-04:

 

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

 

Process IdArrival timeBurst time
P109
P214
P329

 

If the CPU scheduling policy is SRTF, 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

 

Process IdExit timeTurn Around timeWaiting time
P11313 – 0 = 1313 – 9 = 4
P255 – 1 = 44 – 4 = 0
P32222- 2 = 2020 – 9 = 11

 

Now,

  • Average Turn Around time = (13 + 4 + 20) / 3 = 37 / 3 = 12.33 unit
  • Average waiting time = (4 + 0 + 11) / 3 = 15 / 3 = 5 unit

 

Problem-05:

 

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

 

Process IdArrival timeBurst time
P1020
P21525
P33010
P44515

 

If the CPU scheduling policy is SRTF, calculate the waiting time of process P2.

 

Solution-

 

Gantt Chart-

 

 

Now, we know-

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

 

Thus,

  • Turn Around Time of process P2 = 55 – 15 = 40 unit
  • Waiting time of process P2 = 40 – 25 = 15 unit

 

Implementation of Algorithm-

 

  • Practically, the algorithm can not be implemented but theoretically it can be implemented.
  • Among all the available processes, the process with smallest burst time has to be selected.
  • Min heap is a suitable data structure where root element contains the process with least burst time.
  • In min heap, each process will be added and deleted exactly once.
  • Adding an element takes log(n) time and deleting an element takes log(n) time.
  • Thus, for n processes, time complexity = n x 2log(n) = nlog(n)

 

To gain better understanding about SJF Scheduling,

Watch this Video Lecture

 

Next Article- Techniques to Predict Burst Time

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

First Come First Serve | CPU Scheduling

FCFS Scheduling-

 

In FCFS Scheduling,

  • The process which arrives first in the ready queue is firstly assigned the CPU.
  • In case of a tie, process with smaller process id is executed first.
  • It is always non-preemptive in nature.

 

Advantages-

 

  • It is simple and easy to understand.
  • It can be easily implemented using queue data structure.
  • It does not lead to starvation.

 

Disadvantages-

 

  • It does not consider the priority or burst time of the processes.
  • It suffers from convoy effect.

 

Convoy Effect

In convoy effect,

  • Consider processes with higher burst time arrived before the processes with smaller burst time.
  • Then, smaller processes have to wait for a long time for longer processes to release the CPU.

 

PRACTICE PROBLEMS BASED ON FCFS SCHEDULING-

 

Problem-01:

 

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

 

Process IdArrival timeBurst time
P134
P253
P302
P451
P543

 

If the CPU scheduling policy is FCFS, calculate the average waiting time and average turn around time.

 

Solution-

 

Gantt Chart-

 

 

Here, black box represents the idle time of CPU.

 

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
P177 – 3 = 44 – 4 = 0
P21313 – 5 = 88 – 3 = 5
P322 – 0 = 22 – 2 = 0
P41414 – 5 = 99 – 1 = 8
P51010 – 4 = 66 – 3 = 3

 

Now,

  • Average Turn Around time = (4 + 8 + 2 + 9 + 6) / 5 = 29 / 5 = 5.8 unit
  • Average waiting time = (0 + 5 + 0 + 8 + 3) / 5 = 16 / 5 = 3.2 unit

 

Problem-02:

 

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

 

Process IdArrival timeBurst time
P102
P231
P356

 

If the CPU scheduling policy is FCFS, calculate the average waiting time and average turn around time.

 

Solution-

 

Gantt Chart-

 

 

Here, black box represents the idle time of CPU.

 

Now, we know-

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

 

Process IdExit timeTurn Around timeWaiting time
P122 – 0 = 22 – 2 = 0
P244 – 3 = 11 – 1 = 0
P31111- 5 = 66 – 6 = 0

 

Now,

  • Average Turn Around time = (2 + 1 + 6) / 3 = 9 / 3 = 3 unit
  • Average waiting time = (0 + 0 + 0) / 3 = 0 / 3 = 0 unit

 

Problem-03:

 

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

 

Process IdArrival timeBurst time
P103
P212
P321
P434
P545
P652

 

If the CPU scheduling policy is FCFS and there is 1 unit of overhead in scheduling the processes, find the efficiency of the algorithm.

 

Solution-

 

Gantt Chart-

 

 

Here, δ denotes the context switching overhead.

 

Now,

  • Useless time / Wasted time = 6 x δ = 6 x 1 = 6 unit
  • Total time = 23 unit
  • Useful time = 23 unit – 6 unit = 17 unit

 

Efficiency (η)

= Useful time  / Total Total

= 17 unit / 23 unit

= 0.7391

= 73.91%

 

To gain better understanding about FCFS Scheduling,

Watch this Video

 

Next Article- SJF Scheduling | SRTF Scheduling

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Turn Around Time | Response Time | Waiting Time

Various Times Related To Process-

 

Before you go through this article, make sure that you have gone through the previous article on Process States.

 

Various times related to process are-

 

 

  1. Arrival time
  2. Waiting time
  3. Response time
  4. Burst time
  5. Completion time
  6. Turn Around Time

 

1. Arrival Time-

 

  • Arrival time is the point of time at which a process enters the ready queue.

 

2. Waiting Time-

 

  • Waiting time is the amount of time spent by a process waiting in the ready queue for getting the CPU.

 

Waiting time = Turn Around time – Burst time

 

3. Response Time-

 

  • Response time is the amount of time after which a process gets the CPU for the first time after entering the ready queue.

 

Response Time = Time at which process first gets the CPU – Arrival time

 

4. Burst Time-

 

  • Burst time is the amount of time required by a process for executing on CPU.
  • It is also called as execution time or running time.
  • Burst time of a process can not be known in advance before executing the process.
  • It can be known only after the process has executed.

 

5. Completion Time-

 

  • Completion time is the point of time at which a process completes its execution on the CPU and takes exit from the system.
  • It is also called as exit time.

 

6. Turn Around Time-

 

  • Turn Around time is the total amount of time spent by a process in the system.
  • When present in the system, a process is either waiting in the ready queue for getting the CPU or it is executing on the CPU.

 

Turn Around time = Burst time + Waiting time

OR

Turn Around time = Completion time – Arrival time

 

Important Note-

 

While discussing the above definitions,

  • We have considered that the process does not require an I/O operation.
  • When process is present in the system, it will be either waiting for the CPU in the ready state or it will be executing on the CPU.

 

To gain better understanding about various times of process,

Watch this Video Lecture

 

Next Article- FCFS Algorithm | CPU Scheduling

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.