C Program for Shortest Job First (SJF) Scheduling Algorithm | Scaler Topics
FREE
Overview
Shortest Job First (SJF) is a CPU scheduling algorithm that runs the ready process with the smallest burst time next. Its non-preemptive form runs each process to completion; its preemptive form, Shortest Remaining Time First, switches whenever a newly arrived process needs less time than the one running.
The operating system is responsible for scheduling a job for the processor. There are various types of algorithms used for scheduling a job to the CPU for executing these processes. How the CPU scheduler picks the next process depends on the scheduling algorithm being used. Shortest Job First (SJF) is a type of CPU scheduling algorithm in the operating system in which the processor executes the job first that has the smallest execution time. In the shortest Job First algorithm, the processes are scheduled according to the burst time of these processes.
Introduction to Shortest Job First
The operating system maintains a ready queue of processes waiting for CPU execution. SJF scheduling selects the process with the shortest burst time among the processes currently available in the ready queue. The selected process is then allocated the CPU for execution.
Burst time can be defined as the time required by the process to get executed in a millisecond. The process that has the lowest burst time of all the currently available processes will get scheduled by the SJF algorithm and it will get executed first. Also, it is not an easy task to predict the burst of a process, so the implementation of the SJF algorithm is also not easy.
CPU scheduling determines which ready process gets the CPU, while disk scheduling algorithms like SSTF and SCAN determine which disk request is serviced next.
Burst time can be defined as the time required by the process to get executed in a millisecond. The process that has the lowest burst time of all the currently available processes, will get scheduled by the SJF algorithm and it will get executed first. Also, it is not an easy task to predict the burst of a process so, the implementation of the SJF algorithm is also not easy.
Characteristics of SJF Scheduling
Following are the characteristics of (Shortest Job First) SJF scheduling program in C.
- This algorithm is related to each job as a unit of time for completion.
- This algorithm is helpful for those types of processing of jobs in which the completion time of a job can be calculated easily like Batch-type processing.
- This algorithm can improve the CPU processing as it executes the shorter jobs first which leads to a short turnaround time.
Algorithm
The algorithm of Shortest Job First is as follows:
- First, identify the processes that have already arrived and are available in the ready queue.
- At each decision point, select the process with the smallest burst time among the processes that have already arrived.
- Execute the selected process and, after it completes, check the ready queue again. Select the process with the smallest burst time from the processes that have arrived by that time.
Build an AI-First Career, Master the Complete Skillset
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
AI Forward Deployed Engineer Program
Full-stack engineering, production AI and client-facing consulting
+1000 moreTypes of SJF
(Shortest Job First) SJF scheduling program in C is of two types. The first one is Pre-emptive SJF and the second one is Non-Preemptive SJF. Let us see them in detail.
Pre-emptive SJF
Pre-emptive SJF is a type of scheduling algorithm in which processes are inserted into the ready queue as soon as they arrive. Pre-emptive SJF is also called Shortest Remaining Time First (SRTF). The scheduler compares the remaining burst time of the processes in the ready queue. If a newly arrived process has a shorter remaining time than the process currently running, the current process is pre-empted and the newly arrived process gets the CPU. Suppose there are five processes in a queue and their burst time and arrival time are given below in the table.
| Process Queue | Burst Time | Arrival Time |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
The processes will get executed in the following steps:
- job P4 arrives at time t=0, and gets executed
- after that at time=1, the process P3 comes. Since the burst time of P4 has a short burst time so it will get executed.
- all the jobs at each instance of time, a new job arrives and it is then compared to the burst time of other jobs. And the jobs having the shortest burst time will get executed.
- at time=15, when the process P1 gets executed, there is only job P3 left. So, it will get executed.
- at time=23, the process P3 will finish.
Now, the average waiting time will be calculated as:
Non-Preemptive SJF
In this type of scheduling algorithm, if one process is allocated for the CPU, the process sticks to the CPU until the process becomes in a waiting state or gets executed. Suppose there are 5 processes shown in the below table and they have their own burst time and average time.
| Process Queue | Burst Time | Arrival Time |
|---|---|---|
| P1 | 6 | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Given below are the steps through which the processes get executed:
- At time= 0, the CPU gets allocated to the process P4.
- At time= 1, Process P3 comes, but here process P4 is already in between the execution. So, the process will continue to execute here.
- At time= 2, the process P1 comes but it is added to the waiting queue and process P4 will still be in the execution process.
- Atc time= 3, P4 will finish. Here the burst time of processes P3 and P1 will be compared. Here the burst time of P1 is the shortest so it will get executed first.
- This will continue at each instance of time and lastly, process P5 will get executed and at time= 23, process P23 will get executed.
Now the average waiting time will be calculated as follows:
3 factors to consider while solving SJF
There are some factors that are responsible for calculating the SJF algorithm. Let us see them in brief.
BURST Time
The burst time is defined as the difference between the completion time and the waiting time for a particular process.
Average waiting time
The waiting time is defined as the difference between the turnaround time and burst time of a process.
Average turnaround time
The Turn around time is defined as the time taken by a process to complete after the arrival time. Or simply we can say that turnaround time is the difference between the arrival and completion time of a process.
Code for Non-Preemptive SJF Scheduling
Let's see an implementation of Non-Preemptive SJF Scheduling in C language:
Output:
SJF vs SRTF: What Is the Difference?
SJF and SRTF mainly differ in what the scheduler considers when selecting the next process. SJF compares the burst time, while SRTF compares the remaining burst time of the processes that have already arrived.
Before comparing the two, you can also look at how round robin scheduling handles process selection and preemption.
| Aspect | SJF | SRTF |
|---|---|---|
| Selection criterion | Smallest burst time | Smallest remaining burst time |
| Preemption points | No preemption. Once a process starts, it runs until completion. | A running process can be preempted when a newly arrived process has a shorter remaining time. |
| Context switches | Fewer context switches | More context switches because processes can be preempted |
| Average waiting time on this dataset | 5.2 ms | 4.6 ms |
| Starvation risk | A long process may wait if shorter processes keep arriving. | A long process may also wait if shorter processes keep arriving. |
| Typical use | Used when processes can run to completion and their burst times can be estimated. | Used when the scheduler needs to respond to newly arrived processes with shorter remaining times. |
The main difference is that SJF does not interrupt a process once it starts executing. SRTF can interrupt the current process when a newly arrived process has a shorter remaining burst time. This is also why the average waiting time is different for the two algorithms in the example above.
How Scaler Transformed Careers in Different Fields
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreThe Three Values You Calculate In Every SJF Problem
There are some factors that are responsible for calculating the SJF algorithm. Let us see what the OS tracks in a process control block in brief.
BURST Time
Burst time is the amount of CPU time a process needs to finish. It is given to you in the question; every other value on this page is derived from it.
Average waiting time
The waiting time is defined as the difference between the turnaround time and burst time of a process.
Average turnaround time
The Turn around time is defined as the time taken by a process to complete after the arrival time. Or simply we can say that turnaround time is the difference between the arrival and completion time of a process.
Code for Pre-emptive SJF Scheduling
Let's see an implementation of Pre-emptive SJF Scheduling in C language:
Output:
Advantages of SJF
The following are the advantages of SJF scheduling:
- This algorithm comes into use when there is long-term scheduling.
- This algorithm reduces the average waiting time.
- This algorithm is useful if there is a batch-type processor.
- This algorithm can be considered an optimal algorithm because, in this algorithm, the average waiting time is minimum.
Turn Learning into Career Growth
Disadvantages of SJF
The following are the disadvantages of the SJF algorithm:
- There are chances that this algorithm will face starvation if there are too many processes that have shorter burst times then it will cause longer processes to wait in the queue will lead to Starvation.
- This algorithm can lead to a long turnaround time.
- It is not an easy task to get knowledge about the length of future jobs.
To learn more about various scheduling algorithm in operating system click here Scheduling Algorithm in OS
Conclusion
- The SJF scheduling algorithm executed that process first that has the smallest execution time.
- The SJF algorithm considers the time as a unit for a job to execute a process.
- Used in Batch-type processing because, in this type of system, it is easy to wait for one job to get executed first.
- There are two types of SJF scheduling algorithms that are:-
- Non-preemptive SJF
- Preemptive SJF
- In non-preemptive SJF, one process gets executed in a single CPU cycle and the process sticks to the CPU until it gets executed.
- SJF is generally used when there is long-term scheduling.
- Waiting time of this algorithm is reduced when compared to the FIFO (First in First Out) algorithm.
FAQ
Is SJF preemptive or non-preemptive?
SJF can be implemented in both forms. In non-preemptive SJF, the selected process continues until it finishes. The preemptive form is called Shortest Remaining Time First (SRTF), where the scheduler compares the remaining burst time and can switch to another process when a shorter job arrives.
What is the difference between SJF and SRTF?
SJF selects the process with the shortest burst time and does not interrupt it once execution starts. SRTF uses the remaining burst time instead. If a new process arrives with a shorter remaining time than the process currently running, SRTF can preempt the current process.
Why is SJF called optimal?
SJF is called optimal because, when all processes are available at the same time, choosing the shortest burst first gives the minimum possible average waiting time. This condition matters. With processes arriving at different times, as in the example on this page, SRTF can produce a lower average waiting time than non-preemptive SJF.
Can SJF cause starvation?
Yes. A process with a long burst time can keep waiting if shorter processes continue to arrive and are selected first. The same issue can occur with SRTF when shorter remaining jobs keep getting preference. This means a process may remain in the ready queue for a long time before getting CPU time.
How do you break a tie in SJF?
If two processes that are already in the ready queue have the same burst time, the process that arrived earlier can be selected first. The same tie-breaking rule can be applied when two processes have equal remaining times in SRTF. Different tie-breaking rules can produce different but valid Gantt charts.
What is the time complexity of this program?
Both SJF implementations have a time complexity of O(n²) for n processes. The SRTF version repeatedly checks the process list at each time unit to find the process with the shortest remaining time, so the same process list can be scanned many times during execution.
