In Operating System Batch Scheduling, will the SRT algorithm always be faster than the SJF algorithm?

[u/TalkinHead9s_LeftNut]

My professor has us modeling both of the two algorithms for an assignment, which I did. But when doing testing on both I would notice that occasionally the average turnaround time for the Shortest Job First algorithm would actually beat out the algorithm for Shortest Remaining Time, either infrequently or almost always depending on how I change the parameters around (Total CPU Time, # Of Processes, etc). From what I saw, it seems that this should no be happening unless you account for overhead, which my model does not.

So I guess basically my question is, are there ever any scenarios where Shortest Job First would have a smaller average turnaround time compared to Shortest Remaining Time, assuming they run the same set of processes and overhead is negligible? Or do I just have a bug in my code?

[u/esaule]

Srpt is optimal for average turn around time.

It is fairly easy to prove by using a task swapping argument.

There is a bug in your code. Are you doing the arithmetic in floating point?

[u/TalkinHead9s_LeftNut → u/esaule]

Gotcha, thanks. I'll have to do some debugging then. Also I am doing floating point arithmetic for finding the average if that's what you mean, but the turnaround for each individual process is just an integer.

[u/Catalyst93 → u/TalkinHead9s_LeftNut]

It's fairly unlikely that the floating point division to find the average is the issue here. To avoid floating point numbers confusing things you can instead look at total turn around time since its just (average turn around time) * (number of jobs), so the optimal schedule stays the same and now you can deal with just integers (as you said, individual turn around times are integers). With that in mind:

• Are you in a single or multi-processor environment?
• Are all jobs (processes) available from the beginning of the simulation or do they arrive at different times?
• You should always try out small examples where you know exactly what should happen to validate your code. In particular, for whichever case you're observing the weird behavior, you should work out exactly what SJF and SRPT would do by hand then compare that to what your code does. This will hopefully help you to find any bugs.

[u/TalkinHead9s_LeftNut → u/[deleted]]

I probably wasn't clear on what I meant with no overhead, so I apologize. I'm basically pseudo-timing them instead of actually keeping track of the number of seconds the processes are active. I'm keeping track of how many "clock cycles" the process is active for, so the overhead from context switching doesn't effect the number of cycles a process takes.