How to Solve Non-Preemptive SJF Scheduling

TL;DR

Non-preemptive Shortest Job First scheduling selects the arrived process with the smallest burst time and runs it completely without interruption. For the four-process example, the execution order is P3, P1, P2, and P4 after an initial idle interval, producing an average turnaround time of 6.25 units and an average waiting time of 3 units.

Transcript

Hello Friends, Welcome to Gate Smashers Let's understand the concept of shortest job first scheduling algorithm with a numerical So in the numerical first we have given here Four processes P1, P2, P3, P4 Their arrival time and burst time is given It'll be given to you in almost all numerical What we need to find is completion time, turnaround time,... Read More

Key Insights

• Shortest Job First scheduling selects the available process with the lowest burst time. Arrival eligibility must be checked before burst times are compared, because only processes that have already arrived can be considered for execution at the current point in the schedule.
• Non-preemptive execution means a selected process runs completely without interruption. Once a process receives the CPU, it continues for its full burst time, so the scheduler does not replace it when another process arrives during its execution.
• CPU idle time occurs when no process is available in the ready queue. In the example, none of the four processes has arrived at time 0, so the Gantt chart records an idle interval from time 0 to time 1.
• The execution order is P3, P1, P2, and P4. P3 runs from time 1 to 3, P1 runs from 3 to 6, P2 runs from 6 to 10, and P4 runs from 10 to 14.
• Tie-breaking begins with arrival time when two available processes have equal burst times. P2 and P4 both have burst times of 4, so P2 is selected because it arrived at time 2, earlier than P4 at time 4.
• Process ID can resolve a tie when both burst time and arrival time are equal. Under the rule described in the lesson, the process with the lower process ID is selected when neither burst time nor arrival time distinguishes the candidates.
• Turnaround time is completion time minus arrival time, and waiting time is turnaround time minus burst time. The example produces turnaround times of 5, 8, 2, and 10, with corresponding waiting times of 2, 4, 0, and 6.
• Response time equals waiting time in this non-preemptive example because each process completes after receiving the CPU for the first time. Response time is calculated as the first CPU allocation time minus the process arrival time.

Questions & Answers

Q: How does non-preemptive SJF scheduling select a process?

Non-preemptive Shortest Job First scheduling first identifies every process that has arrived by the current time. It then compares the burst times of those available processes and selects the one with the smallest burst time. After selection, the process runs for its entire burst time without interruption, even if another process arrives while it is executing.

Q: How is the Gantt chart constructed for the SJF example?

The Gantt chart starts at time 0, with the CPU idle until time 1 because no process is available. P3 then runs from 1 to 3, followed by P1 from 3 to 6. P2 executes from 6 to 10, and P4 finishes the schedule by running from time 10 to time 14.

Q: Why is the CPU idle from time 0 to time 1?

The CPU is idle from time 0 to time 1 because none of the four processes has arrived at time 0. A scheduler can select only a process that is already available. The first arrivals are P1 and P3 at time 1, so execution cannot begin before that time and the initial Gantt chart interval is marked idle.

Q: Why does P3 execute before P1 in the SJF example?

P1 and P3 both arrive at time 1, so both are eligible when the CPU becomes available. Their burst times determine the selection: P1 requires 3 units, while P3 requires 2 units. Because P3 has the shorter burst time, SJF selects it first, and non-preemptive execution keeps it on the CPU until time 3.

Q: How are equal burst times resolved in SJF scheduling?

When two available processes have equal burst times, the lesson resolves the conflict by comparing their arrival times. The process that arrived earlier is selected first. P2 and P4 each require 4 units, but P2 arrived at time 2 while P4 arrived at time 4, so P2 runs first. If arrival times are also equal, the lower process ID is selected.

Q: How are completion, turnaround, and waiting times calculated?

Completion time is the time shown at the right boundary of a process in the Gantt chart. Turnaround time is calculated by subtracting arrival time from completion time. Waiting time is then calculated by subtracting burst time from turnaround time. For P1, these calculations give completion time 6, turnaround time 5, and waiting time 2.

Q: Why does response time equal waiting time in non-preemptive SJF?

Response time measures the interval from a process's arrival until it receives the CPU for the first time. In non-preemptive scheduling, a process runs completely once it first receives the CPU, so it has no later execution interval after an interruption. Therefore, the delay before its first CPU allocation is also its entire waiting time in this example.

Q: What are the average turnaround and waiting times in the example?

The turnaround times for P1, P2, P3, and P4 are 5, 8, 2, and 10 units. Their total is 25, which divided by four processes gives an average turnaround time of 6.25 units. The waiting times are 2, 4, 0, and 6, totaling 12, so the average waiting time is 3 units.

Summary & Key Takeaways

• The example begins by listing four processes with their arrival and burst times. Because no process has arrived at time 0, the CPU remains idle until time 1. At that point, P1 and P3 are available, and P3 is selected because its burst time of 2 is shorter than P1's burst time of 3.

• Non-preemptive SJF runs each selected process to completion. P3 executes from time 1 to 3, P1 from 3 to 6, P2 from 6 to 10, and P4 from 10 to 14. P2 is chosen before P4 because their burst times are equal, but P2 has the earlier arrival time.

• Completion time is read from the right boundary of each process in the Gantt chart. Turnaround time equals completion time minus arrival time, while waiting time equals turnaround time minus burst time. The calculated average turnaround time is 6.25 units, and the calculated average waiting time is 3 units for the four processes.