Intro to Os

Non-Preemptive Scheduling Algorithms

Formulas

• Completion Time = Time at which Process terminates (see Gantt chart)
• Turnaround Time = Completion time- Arrival time    OR    waiting time+ Burst Time
• Waiting Time = Turnaround time – Burst Time
• Response Time = In Non-Preemptive Response Time= Waiting time
• Response Ratio = (waiting_time + service_time) / service_time
• Avg. Turnaround Time = Sum of turnaround time of all processes/ total processes

Let’s explain non-preemptive scheduling algorithms with examples,

In every example, the Given Fields are

• Process No
• Burst Time
• Burst Time

We have to find the following fields:

• Completion Time
• Turnaround Time
• Waiting Time
• Response Time
• Average Turnaround Time

1. First Come First Serve (FCFS)

• It Depends on the Arrival Time of the process

2. Shortest Job First (SJF)

It depends on the Burst Time of the process.

Note: If burst time is the same for two processes then check their the arrival time. if arrival time is also same then check their the process ID. Any process having less burst time or arrival time or process ID is executed first.

3. Largest Job First (LJF)

It can also be treated as the same concept of Shortest Job First (SJF) except the Burst time.IF Burst time is higher in LJF, then that process will execute first. But in SJF, if the process has less Burst Time, the process will execute first.

4. Highest Priority (0 is the highest priority)

• A low value (0) can be considered as the Highest Priority or lower Priority in choosing a process for execution. In this example, we will consider Zero as the Highest Priority.

5. Highest response ratio Next (HRRN)

• The highest Response Ratio Processes are executed First

Explanation

As

• Response Ratio = (waiting_time + service_time) / service_time
• Waiting time: Time at which the Process gets the CPU the first time- Arrival time
• Service Time: Service time is the Burst Time

P1 is executed first because at 0 time, no other process arrives except P1. Only P2 arrives with the execution of P1.

While execution of P2 Processes P3, P4 and P5 are arrived. So, Check the Response Ratio at time point 9 in the Gantt chart of Processes P3, P4, and P5

• P3 Responce Ratio = (5+4)/4= 2.25
• P4 Responce Ratio = (3+5)/5= 1.6
• P5 Responce Ratio = (1+2)/2= 1.5

As P3 Has the Highest Response ratio. So, it will execute first.

As P3 completes its execution at time 13. No other process arrived at this time. So, Check the Response Ratio at time 13 in Gantt. Chart for remaining processes P4 and P5.

• Responce Ratio of P4 = (7+5)/5= 2.4
• Responce Ratio of P5 = (5+2)/2= 3.5

As P5 has the highest Response Ratio. So, P5 was executed first. In the end, P4 is executed because no other process remains to compare for HRRN. In this way, all the processes are executed successfully through the Highest Response ratio.

Note: The waiting time of A is 5 at time 9 in Gantt Chart because it comes at time 4 and gets CPU at 9, so waiting time = 9-4=5

All Preemptive scheduling algorithms are explained in the next lecture.