SHORTEST JOB FIRST ALGORITHM
12
PRESENTED BY:--
Shankar.K-1NT21CS161
Shrinivas Shahapur-1NT21CS169
M Yashwanth Reddy -1NT21CS108
Sanchal S Astekar-1NT21CS156
SHORTEST JOB FIRST ALGORITHM
PRESENTED TO :- Dr Chaitra Naveen
(dept of cse)
ADVANTAGES
DISADVANTAGES AND SUMMARY
SHORTEST JOB FIRST ALGORITHM
INTRO
Gives minimum average waiting time for a given set of processes.
Minimizes average turnaround time.
It cannot be implemented at the level of short term CPU scheduling.
Store estimated value in PCB for the current burst, and compare with actual value.
• Exponential averaging is used to estimate the process
burst duration.
SJF (Shortest Job First) is a scheduling algorithm used in computer operating systems that prioritises the execution of tasks based on their burst time.
The aim of SJF :
• minimizes the average waiting time of processes
• reduce turnaround times and efficient CPU utilization.
INTRO
>WHY
1.Minimizes average waiting time
2.Efficient utilization of resources
3.Decreases turnaround time
4.No starvation for short processes.
TYPES OF SJF
SJF AND ITS TYPES
1.Non-Preemptive SJF and
2) Preemptive SJF
• In the non-preemptive type of SJF, once a process is selected to run, it is allowed to complete its execution without interruption.
•The scheduler does not preempt the running process when the new process with shorter burst time is arrived.
• In the preemptive , the running process can be interrupted and preempted by a newly arrived process with a shorter burst time.
• If a new process with a shorter burst time enters the system or the current running process is preempted due to some other reason
• The scheduler will switch to the process with the shortest remaining burst time
NON PREEMPTIVE SJF
NON PREEMPTIVE EXAMPLE,CODE AND ALGORITHM
CODE
The algorithm of non preemptive SJF
• When a process enters the ready queue , the scheduler checks the burst time of all processes in the queue.
• The process with the shortest burst time is selected for execution first.
• The selected process runs until it completes its execution or until it voluntarily releases the CPU
• Once the running process finishes, the scheduler selects the next process with the shortest burst time from the remaining processes in the ready queue.
•The process continues until there are no more processes left in the ready queue
def sjf_non_preemptive(processes):
n = len(processes)
total_waiting_time = 0
total_turnaround_time = 0
processes.sort(key=lambda x: x['burst_time'])
waiting_time = [0] * n
for i in range(1, n):
waiting_time[i] = processes[i-1]['burst_time'] + waiting_time[i-1]
turnaround_time = [0] * n
for i in range(n):
turnaround_time[i] = processes[i]['burst_time'] + waiting_time[i]
for i in range(n):
total_waiting_time += waiting_time[i]
total_turnaround_time += turnaround_time[i]
avg_waiting_time = total_waiting_time / n
avg_turnaround_time = total_turnaround_time / n
print("Process\tBurst Time\tWaiting Time\tTurnaround Time")
for i in range(n):
print(f"P{i + 1}\t\t{processes[i]['burst_time']}\t\t{waiting_time[i]}\t\t{turnaround_time[i]}")
print(f"\nAverage Waiting Time: {avg_waiting_time:.2f}")
print(f"Average Turnaround Time: {avg_turnaround_time:.2f}")
if _name_ == "_main_":
processes = [
{'burst_time': 6},
{'burst_time': 8},
{'burst_time': 3},
{'burst_time': 4},
{'burst_time': 5}
]
sjf_non_preemptive(processes)
PREEMPTIVE SJF
PREEMPTIVE SJF
CODE
The algorithm of preemptive SJF
• When a process enters the ready queue or the running process is preempted for any reason , the scheduler checks the burst time of all processes in the ready queue, including the remaining burst time of the currently running process .
• The process with the shortest remaining burst time is selected for execution.
• If the selected process is running and a new process with an even shorter burst time arrives, the currently running process is preempted, and the CPU is given to the newly arrived process.
• The newly selected process runs for a certain time quantum or until it completes its current burst, whichever occurs first.
• If the process does not finish its burst during the time quantum, it is moved back to the ready queue, and the scheduler selects the next process with the shortest remaining burst time for execution.
• The process continues until there are no more processes in the ready queue
#include <stdio.h>
int main()
{
int arrival_time[10], burst_time[10], temp[10];
int i, smallest, count = 0, time, limit;
double wait_time = 0, turnaround_time = 0, end;
float average_waiting_time, average_turnaround_time;
printf("nEnter the Total Number of Processes:t");
scanf("%d", &limit);
printf("nEnter Details of %d Processesn", limit);
for(i = 0; i < limit; i++)
{
printf("nEnter Arrival Time:t");
scanf("%d", &arrival_time[i]);
printf("Enter Burst Time:t");
scanf("%d", &burst_time[i]);
temp[i] = burst_time[i];
}
burst_time[9] = 9999;
for(time = 0; count != limit; time++)
{
smallest = 9;
for(i = 0; i < limit; i++)
{
if(arrival_time[i] <= time && burst_time[i] < burst_time[smallest] && burst_time[i] > 0)
{
smallest = i;
}
}
burst_time[smallest]--;
if(burst_time[smallest] == 0)
{
count++;
end = time + 1;
wait_time = wait_time + end - arrival_time[smallest] - temp[smallest];
turnaround_time = turnaround_time + end - arrival_time[smallest];
}
}
average_waiting_time = wait_time / limit;
average_turnaround_time = turnaround_time / limit;
printf("nnAverage Waiting Time:t%lfn", average_waiting_time);
printf("Average Turnaround Time:t%lfn", average_turnaround_time);
return 0;
}
SUMMARY
-->SJF is an algorithm in which the process having the smallest execution time is chosen for the next execution.
-->This algorithm method is helpful , where waiting for jobs to complete is not critical.
-->There are basically two types of SJF methods 1) Non-Preemptive SJF and 2) Preemptive SJF
-->In non-preemptive scheduling, once the CPU cycle is allocated to process, the process holds
-->it till it reaches a waiting state or terminated
. In Preemptive SJF Scheduling, jobs are put into the ready queue as they come.
-->Although a process with short burst time begins, the current process is removed or preempted from execution, and the job which is shorter is executed 1st.
Advantages of SJF
1. SJF scheduling minimizes waiting time by prioritizing shorter processes over longer ones.
2. SJF is efficient for batch processing environments, where jobs with different burst times are executed sequentially.
3.In non-preemptive version guarantees a process to run undisturbed until completion, simplifying implementation and management.
4. SJF gives importance to short processes hence quicker execution for shorter jobs and improves system responsiveness.
5. it is optimal for minimizing average turnaround time, that results in faster completion of processes.
Disadvantages of SJF
1.May cause very long turnaround times or starvation.
2.Requires knowledge of how long a process or job will run
3.Leads to the starvation that does not reduce average turnaround time
4.Hard to know the length of the upcoming CPU request