Tag: FCFS Scheduling

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.

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.