Subject: Operating System

Topic: PROCESS MANAGEMENT

Difficulty: Medium

A Process Scheduler schedules different processes to be assigned to the CPU based on particular scheduling algorithms. These algorithms are either non-preemptive or preemptive. Non-preemptive algorithms are designed so that once a process enters the running state, it cannot be preempted until it completes its allotted time, whereas the preemptive scheduling is based on priority where a scheduler may preempt a low priority running process anytime when a high priority process enters into a ready state.

First Come First Serve (FCFS)

• Jobs are executed on first come, first serve basis.

• It is a non-preemptive scheduling algorithm.

• Easy to understand and implement.

• Its implementation is based on FIFO queue.

• Poor in performance as average wait time is high.

Wait time of each process is as follows −

Waiting Time : Service Time - Arrival Time

Waiting Time for P0 = 0 - 0 = 0

Waiting Time for P1 = 5 - 1 = 4

Waiting Time for P2 = 8 - 2 = 6

Waiting Time for P3 = 16 - 3 = 13

Average Waiting Time = (0+4+6+13) / 4 = 5.75

Shortest Job Next (SJN)

• This is also known as shortest job first, or SJF

• This is a non-preemptive scheduling algorithm.

• Best approach to minimize waiting time.

• Easy to implement in Batch systems where required CPU time is known in advance.

• Impossible to implement in interactive systems where required CPU time is not known.

• The processer should know in advance how much time process will take.

Waiting time of each process is as follows −

Waiting Time : Service Time - Arrival Time

Waiting Time for P0 = 3 - 0 = 3

Waiting Time for P1 = 0 - 0 = 0

Waiting Time for P2 = 16 - 2 = 14

Waiting Time for P3 = 8 - 3 = 5

Average Waiting Time= (3+0+14+5) / 4 = 5.50