Shortest Job First (or SJF) CPU Scheduling Python Program

In CPUs the scheduling methods chooses the sequence in which the processes will be executed hence managing the waiting time. One of such methods is known as the "shortest job first" (SJF) or "shortest job next". This algorithm gives the process the least execution time to run first. Another method known as Shortest Job Next (SJN), often used as SJN, can also be used.

Characteristics of SJF Scheduling:

Shortest Job First can be implemented using a Greedy Algorithm.

This algorithm's plus point is that it has the lowest average waiting period of all the available CPU scheduling algorithms.

If, however, there is a situation where the processes with shorter execution times continue to be produced, it can cause starvation. This particular issue can be resolved by implementing the idea of aging.

Since the operating system could not be aware of burst timings, it is almost impossible to categorize them. Although the complete execution time of the processes cannot be predicted, it may be determined using various techniques, such as calculating the weighted-average of previous execution periods.

SJF can be employed in specialized settings when precise running time estimations are available.

Algorithm:

We will start by sorting the procedures according to their arrival time.
Then we will choose the particular process which has the shortest arrival time and the shortest burst time.
Then we will create a collection of processes executed by the CPU after the one that has just finished and choose the one from the collection with the shortest burst time after that process.
Completion time is when the process has reached the end of its execution.
Turn Around time is defined as the time passed between the completion timestamp and the arrival timestamp of the process.

Turn Around Time = Completion Time of any particular Process - Arrival Time of any particular Process.

Waiting Time is defined as the difference value of the turnaround time and the burst time of a particular process.

Waiting Time = Turn Around Time of the Process - Burst Time of the Process

Segment Trees are a data structure that may be used to construct the non-preemptive types Shortest Job First method.

There is an assumption to be kept in mind before proceeding. The arrival time is considered to be zero, which means that the turnaround and completion times of processes will be the same.

Implementing SJF Algorithm in Python

Code

# Python program to implement the Shortest Job First algorithm 

# Taking the input of the number of processes
n = int(input("Enter the number of processes: "))

# Creating a matrix for storing the Process Id, Burst Time of each process, Average Waiting Time, and the Average Turn Around Time according to the provided burst times.
mat = [[0 for j in range(4)] for i in range(n)]
t, avg_wttime, avg_tatime = 0, 0, 0
print("Enter the Burst Time of the processes:")

# Taking the input of the burst times of the processes
# Alloting process Ids to each process
for i in range(n): 
  mat[i][1] = int(input(f"P{i + 1}: "))
  mat[i][0] = i + 1

# Sorting the processes that we stored above according to their burst time
for i in range(n): 
  ind = i
  for j in range(i + 1, n):
    if mat[j][1] < mat[ind][1]:
      ind = j
  a = mat[i][1]
  mat[i][1] = mat[ind][1]
  mat[ind][1] = a
  a = mat[i][0]
  mat[i][0] = mat[ind][0]
  mat[ind][0] = a

# Calculating the waiting times of the processes
mat[0][2] = 0 
for i in range(1, n):
  mat[i][2] = 0
  for j in range(i):
    mat[i][2] += mat[j][1]
  t += mat[i][2]
avg_wtime = t / n
t = 0
# Calculating the Turn Around Time for each process

# Printing the data in the table form
print("P B_T W_T TA_T")
for i in range(n):
  mat[i][3] = mat[i][1] + mat[i][2]
  t += mat[i][3]
  print(f"P{mat[i][0]} {mat[i][1]} {mat[i][2]} {mat[i][3]}")
avg_tatime = t / n
print(f"The average Waiting Time of the whole sequence of processes is = {avg_wtime}")
print(f"The average Turn Around Time of the processes is = {avg_tatime}")

Output:

Enter the number of processes: 10
Enter the Burst Time of the processes:
P1: 4
P2: 3
P3: 7
P4: 9
P5: 1
P6: 10
P7: 14
P8: 11
P9: 5
P10: 16
P	B_T	W_T	TA_T
P5	1	0	1
P2	3	1	4
P1	4	4	8
P9	5	8	13
P3	7	13	20
P4	9	20	29
P6	10	29	39
P8	11	39	50
P7	14	50	64
P10	16	64	80
The average Waiting Time for the whole sequence of processes is = 22.8
The average Turn Around Time of the processes is = 30.8

Time Complexity: The time complexity of this SJF algorithm is O(n^2). The time complexity is non-linear because we run a nested loop to sort the burst time and process ids.

Auxiliary Space: This approach takes O(n) extra memory space. We are storing arrays of the process.

Advantages of Shortest Job First Algorithm:

This algorithm manages the processes such that the waiting period is shorter than other algorithms such as the First come, first serve algorithm, also known as FCFS.
This algorithm is typically employed for long-term scheduling.
It is appropriate for jobs running in batches and with known run periods.
SJF is arguably the best option regarding turnaround times on average.

Disadvantages of Shortest Job First Algorithm:

SJF may result in starvation or long turnaround periods.
The SJF requires that time frames for job completion be provided in advance, albeit this can sometimes be challenging.
It is often tough to anticipate how long a forthcoming CPU request will be.
It causes starvation and does not shorten the typical turnaround time.

Shortest Remaining Time First (SRTF)

The preemptive version of the Shortest Job First (SJF) algorithm is called Shortest Remaining Time First (SRTF). This algorithm allocates the CPU to the task that is nearly finished.

This technique cannot be used in an interactive system since it needs a sophisticated understanding of how much CPU time is needed to complete the task. However, the SRT method is utilized in batch systems when it is essential to prioritize small jobs.

However, SRT has additional expenses than SJN since it necessitates regular OS context switching and needs to monitor the CPU time of the processes in the queue.

The SRT method executes more quickly than the SJF algorithm for the same collection of processes. However, in this case, the operational costs, or the time needed to execute context switching, have been disregarded. All of its processing data of the tasks that are considered preemptive must be stored in its corresponding PCB for whenever it is to be resumed, and the data of the other process's PCB, that is, the process to which the Operating System is switching, are written into what is commonly called as memory registers. This is the process of Context Switching.

Advantages:

If we do not take into account the overhead cost in the function of SRTF, it processes jobs more quickly than the SJF algorithm.
This algorithm helps manage library modifications or replacements more easily without recompiling the program.
Because several program instances can access libraries, it allows for cost-effective memory usage.
This algorithm improves the portability because the program can operate on other systems as long as relevant libraries are available during execution.

Disadvantages:

Context switch occurs many times as in the SJF. This alone makes up a significant amount of time required for processing the tasks. This increases the processing time and lessens the benefit of quick processing.
Due to the extra linking procedure, program startup will be a little slower.
The algorithm has to handle library dependencies correctly to guarantee appropriate execution.
Due to libraries being independent entities that are fetched at runtime, troubleshooting can be a little more difficult.

Next TopicZig-Zag Traversal of Binary Tree in Python

← prev next →