Shortest Job First
Let's see if we can improve on FCFS to try to reduce the average wait time for processes…
Our Work
We'll stick with the same set of processes from the previous page.
| Process | Required Time |
|---|
(We've set the seed to 123456 from the end of the previous page, but, as usual, you can change the seed to get different times for the processes.)
Shortest-Job First Scheduling
Shortest-Job First (SJF) scheduling is a scheduling algorithm that selects the process with the smallest execution time to execute next. It's like waiting in line at the grocery store, but the cashier always picks the person with the fewest items to check out next.
That doesn't seem fair to me. I usually have MORE items than anyone else!
Well, it's not all about you. It's about getting everyone through the line as quickly as possible. Half the time I'm waiting in line with one bottle of Advil, and this seems like a great idea to me.
The chart below shows our timeline as usual:
Statistics
Here are all the statistics for the processes in this run:
| Process | Response Time | Turnaround Time | Wait Time |
|---|
Here's the random seed we used for this run, which you can change to get different times for the processes and see how the chart and statistics change.
Prof. Melissa ran the simulation one million times and found the response time (and wait time) averaged out to be 8.5, and the turnaround time averaged out to be 14.5. The standard deviation for each of these times was about 7.42 for the response and wait times, and about 9.85 for the turnaround time.
That's an improvement over what we saw for FCFS, where the response time was 12 and the turnaround time was 18.
-
Looks good to me!
-
I don't like it. In fact, I'm worried it could cause starvation!!!! What if I have a long job and a bunch of short jobs keep coming in? I might never get to run!
There is something I find strange, too. It seems to require foreknowledge of the future. How can we know how long a process will run before it starts?
-
Good points.
To summarize:
- SJF scheduling is an improvement over FCFS in terms of response time and turnaround time.
- SJF can cause starvation if a long job is waiting behind a bunch of short jobs and more short jobs keep coming in.
- SJF seems to require foreknowledge of how long each process will run, which is not always available.
- Sometimes, however, we can make a good guess based on past behavior.
-
I think we need something better. Something with better response time.
Meh. Now that you're running last, that's suddenly important to you. Typical.
-
Hey! I'm just saying…
(When logged in, completion status appears here.)