Shortest Job First CPU Scheduling in Operating System

 

Shortest Job First (SJF) is a CPU scheduling algorithm that allocates the CPU to the process with the shortest burst time. The burst time is the time required by a process to complete its execution. This algorithm is also known as the shortest process next (SPN) algorithm.

The SJF algorithm operates in two modes:

1. Preemptive SJF: In this mode, if a new process arrives with a burst time shorter than the current running process, the CPU is immediately switched to the new process.

2. Non-preemptive SJF: In this mode, once the CPU is allocated to a process, it cannot be taken away until the process completes its execution.

SJF is a deterministic algorithm, meaning that the same set of inputs will always produce the same output. This algorithm is also a optimal algorithm in terms of average waiting time and average turn around time, as it allocates the CPU to the process with the shortest burst time, resulting in a minimum waiting time for all processes.

Example 1:

Consider the following processes with the arrival time and burst time as shown below:

Process ID  Arrival Time  Burst Time 
    P1                   0                     10
    P2                   2                       5
    P3                    4           8

    P4                    6                       7

Using the non-preemptive SJF algorithm, we can allocate the CPU to the processes as follows:

1. The first process to arrive is P1 with a burst time of 10. The CPU is allocated to P1.
2. The next process to arrive is P2 with a burst time of 5. The CPU is not allocated to P2 as P1 is still executing.
3. P3 arrives with a burst time of 8. The CPU is still not allocated to P3 as P1 is still executing.
4. P4 arrives with a burst time of 7. The CPU is still not allocated to P4 as P1 is still executing.
5. Once P1 completes its execution, the CPU is allocated to P2 as it has the shortest burst time among the waiting processes.
6. P3 and P4 are still waiting for their turn.
7. Once P2 completes its execution, the CPU is allocated to P3.
8. P4 is still waiting for its turn.
9. Once P3 completes its execution, the CPU is allocated to P4.
10. P4 completes its execution and all processes are now completed.

The waiting time and turn around time for each process can be calculated as follows:

Process ID  Arrival Time  Burst Time  Waiting Time  Turn Around Time

    P1                   0                     10                  0                    10

    P2                    2                       5                   10                    15

    P3                    4            8                   15                    23

    P4                     6            7                   23                    30

Example 2:

Consider the following processes with the arrival time and burst time as shown below:

Process ID  Arrival Time  Burst Time
      P1                   0                     8

      P2                   1                      4

      P3                   2                      9

      P4                   3                      5

Using the preemptive SJF algorithm, we can allocate the CPU to the processes as follows:

1. The first process to arrive is P1 with a burst time of 8. The CPU is allocated to P1.
2. P2 arrives with a burst time of 4. As P2 has a shorter burst time than P1, the CPU is switched to P2.
3. P3 arrives with a burst time of 9. The CPU remains with P2 as its burst time is shorter.
4. P4 arrives with a burst time of 5. The CPU remains with P2 as its burst time is shorter.
5. Once P2 completes its execution, the CPU is allocated to P1.
6. P3 and P4 are still waiting for their turn.
7. Once P1 completes its execution, the CPU is allocated to P3.
8. P4 is still waiting for its turn.
9. Once P3 completes its execution, the CPU is allocated to P4.
10. P4 completes its execution and all processes are now completed.

The waiting time and turn around time for each process can be calculated as follows:

Process ID  Arrival Time  Burst Time  Waiting Time  Turn Around Time

     P1                   0                     8                       4                    12

     P2                   1                     4                       0                    4

     P3                   2                     9              5                    14

     P4                   3                     5              9                    14

It can be seen from the above examples that the SJF algorithm reduces the waiting time and turn around time for the processes, leading to an overall improvement in the performance of the operating system.

However, the major disadvantage of the SJF algorithm is that it requires knowledge of the burst time of each process in advance, which is often not possible in real-world systems. As a result, the SJF algorithm is often used in conjunction with other CPU scheduling algorithms, such as the Round Robin algorithm, to overcome this limitation.

In conclusion, the Shortest Job First (SJF) algorithm is an effective CPU scheduling algorithm that allocates the CPU to the process with the shortest burst time, leading to a minimum waiting time and turn around time for all processes. Although it requires knowledge of the burst time in advance, the SJF algorithm is still widely used in operating systems for its efficiency and performance benefits.