Tag: Priority Scheduling Algorithm

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.

Priority Scheduling | CPU Scheduling | Examples

Priority Scheduling-

 

In Priority Scheduling,

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

 

 

  • Priority Scheduling can be used in both preemptive and non-preemptive mode.

 

Advantages-

 

  • It considers the priority of the processes and allows the important processes to run first.
  • Priority scheduling in preemptive mode is best suited for real time operating system.

 

Disadvantages-

 

  • Processes with lesser priority may starve for CPU.
  • There is no idea of response time and waiting time.

 

Important Notes-

 

Note-01:

 

  • The waiting time for the process having the highest priority will always be zero in preemptive mode.
  • The waiting time for the process having the highest priority may not be zero in non-preemptive mode.

 

Note-02:

 

Priority scheduling in preemptive and non-preemptive mode behaves exactly same under following conditions-

  • The arrival time of all the processes is same
  • All the processes become available

 

PRACTICE PROBLEMS BASED ON PRIORITY SCHEDULING-

 

Problem-01:

 

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

 

Process IdArrival timeBurst time Priority
P1042
P2133
P3214
P4355
P5425

 

If the CPU scheduling policy is priority non-preemptive, calculate the average waiting time and average turn around time. (Higher number represents higher priority)

 

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
P144 – 0 = 44 – 4 = 0
P21515 – 1 = 1414 – 3 = 11
P31212 – 2 = 1010 – 1 = 9
P499 – 3 = 66 – 5 = 1
P51111 – 4 = 77 – 2 = 5

 

Now,

  • Average Turn Around time = (4 + 14 + 10 + 6 + 7) / 5 = 41 / 5 = 8.2 unit
  • Average waiting time = (0 + 11 + 9 + 1 + 5) / 5 = 26 / 5 = 5.2 unit

 

Problem-02:

 

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

 

Process IdArrival timeBurst time Priority
P1042
P2133
P3214
P4355
P5425

 

If the CPU scheduling policy is priority preemptive, calculate the average waiting time and average turn around time. (Higher number represents higher priority)

 

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
P11515 – 0 = 1515 – 4 = 11
P21212 – 1 = 1111 – 3 = 8
P333 – 2 = 11 – 1 = 0
P488 – 3 = 55 – 5 = 0
P51010 – 4 = 66 – 2 = 4

 

Now,

  • Average Turn Around time = (15 + 11 + 1 + 5 + 6) / 5 = 38 / 5 = 7.6 unit
  • Average waiting time = (11 + 8 + 0 + 0 + 4) / 5 = 23 / 5 = 4.6 unit

 

To gain better understanding about Priority Scheduling,

Watch this Video Lecture

 

Next Article- Practice Problems On CPU Scheduling Algorithms

 

Get more notes and other study material of Operating System.

Watch video lectures by visiting our YouTube channel LearnVidFun.