Implementation of Shortest Job First (SJF) Scheduling in Python
Shortest Job First (SJF) scheduling is a non-preemptive CPU scheduling algorithm where the process with the smallest burst time is selected for execution from the ready queue. The objective is to minimize the average waiting time of processes.
Example 1:
Consider the following processes with their burst times:
| Process | Burst Time |
|---|---|
| P1 | 6 |
| P2 | 8 |
| P3 | 7 |
| P4 | 3 |
Output:
Average Waiting Time: 7.0
| Process | Burst Time | Waiting time |
|---|---|---|
| P4 | 3 |
0 |
| P1 | 6 |
3 |
| P3 | 7 |
9 |
| P2 | 8 |
16 |
Example 2:
Consider another set of processes:
| Process | Burst Time |
|---|---|
| P1 | 5 |
| P2 | 3 |
| P3 | 1 |
| P4 | 4 |
Output:
Average Waiting Time: 3.25
| Process | Burst Time | Waiting time |
|---|---|---|
| P3 | 1 |
0 |
| P2 | 3 |
1 |
| P4 | 4 |
4 |
| P1 | 5 |
8 |
Shortest Job First (SJF) Scheduling Algorithm
Sort the processes based on their burst time in ascending order.
- Sort the processes based on their burst time.
- Calculate waiting time for each process.
- Compute the average waiting time.
Implementation of Shortest Job First (SJF) Scheduling in Python:
class Process:
def __init__(self, pid, burst_time):
self.pid = pid
self.burst_time = burst_time
def sjf_scheduling(processes):
processes.sort(key=lambda x: x.burst_time) # Sort processes by burst time
total_processes = len(processes)
current_time = 0
waiting_time = 0
print("Process ID\tBurst Time\tWaiting Time")
for p in processes:
print(f"{p.pid}\t\t{p.burst_time}\t\t{waiting_time}")
waiting_time += current_time
current_time += p.burst_time
average_waiting_time = waiting_time / total_processes
print("\nAverage Waiting Time:", average_waiting_time)
# Example usage
if __name__ == "__main__":
processes = [Process(1, 6), Process(2, 8), Process(3, 7), Process(4, 3)]
sjf_scheduling(processes)
Output
Process ID Burst Time Waiting Time 4 3 0 1 6 0 3 7 3 2 8 12 Average Waiting Time: 7.0
Complexity Analysis:
- Time Complexity: Sorting the processes takes O(nlogn) time. The loop to calculate waiting time takes O(n) time. Therefore, the overall time complexity is O(nlogn).
- Space Complexity: The space complexity is O(n) for storing the processes
Contact Us