System Programing | Scheduling Times

Question

I'm trying to understand these scheduling algorithms:

• First-Come-First-Served (FCFS)
• Shortest job first (SJF)
• Shortest remaining time (SRT)
• Round-robin (RR)

So, given some input:

Process Name: A; Arrival Time: 0; Expected CPU Running Time: 3
Process Name: B; Arrival Time: 1; Expected CPU Running Time: 5
Process Name: C; Arrival Time: 3; Expected CPU Running Time: 2
Process Name: D; Arrival Time: 9; Expected CPU Running Time: 5
Process Name: E; Arrival Time: 12; Expected CPU Running Time: 5

FCFS would schedule as AAABBBBBCCDDDDDEEEEE.

I can't seem to figure the rest out. Can someone help explain the difference to me?

I tried Googling but the result I got for SJF is kind confusing.

Answer 1

I'll just give you some hints.

For SJF and SRT you don't really definitions - just think logically about the name.

For SJF, pick the shortest arrived unfinished job. Use the total time of the job, i.e. 3,5,2,5,5 - pay no attention to how much has already been scheduled for that job.

For SRT, pick the arrived unfinished job with the least remaining time. The remaining time is simply defined as the total time minus how much has already been scheduled. So, at time 2, you'd have scheduled AA, thus the remaining time for A would be 3-2 = 1.

For SJF and SRT, conflicts (when there are two jobs with the same times) can probably be resolved by picking the job that arrived first. For SRT, conflicts may also be resolved by picking the longest job. You'll have to confirm this.

Note that there are two variations for these algorithms - preemptive and non-preemptive. In short, preemptive means that, at every time step you pick the job to execute next. For non-preemtive, on the other hand, once you've picked a job, you schedule that job until it's finished, no matter whether or not there's a newly arrived job with a shorter time. See this for a more detailed explanation.

For RR, just pick the one you've picked the longest ago.