Much of the discussion surrounding processes so far has been focused entirely on low-level execution: how do we switch between contexts? How do we run processes? How do we run restricted operations? However, there has been a general lack of conversation surrounding which processes should even run.
To best understand processes, we'll first start with a series of assumptions to get a base understanding. Then, we'll remove certain assumptions and build toward a more robust idea of how modern OSs implement scheduling.
We'll also need some metrics to determine how efficient a scheduling system is. The first will be turnaround time, which is defined as the time a job completes minus the time at which the job arrived in a system. There's also fairness, which we'll discuss later.
So, operating under these assumptions, we can build a rather simple image of how scheduling should go. There's FIFO (first in, first out) or FCFS (first come, first serve).
Now that we have unequal run times, the FIFO system starts to become a problem. Now, it makes much more sense to run the shortest jobs first (to maximize turnaround). SJF (shortest job first) drastically decreases turnaround time in systems where there are unequal processes.
Now we get rid of the second assumption and it leaves us with an issue. What if a longer process arrives before a shorter process? This gives us a rather tragic situation—with shorter processes now being forced to wait for a longer process to finish.
Now that we can have jobs pause in the middle of their execution, we can use the STCF (shortest time to completion first) or PSJF (preemptive shortest job first) mechanism to optimize turnaround. Now, any time a job enters a system, the scheduler determines which job should run based on time to complete. But what about response time? Now we can introduce this idea of fairness. Response time is the time it takes from when a job first arrives at a system to when it is first scheduled.
This new scheduling algorithm (RR) provides a potential fix to the problem of response time. RR runs a job for a time slice (or scheduling quantum) which is a multiple of the timer interrupt interval. RR improves response time. But what about turnaround time?
RR is actually incredibly bad for turnaround time. Think about it. You split up the processes and continually cycle through them. Now, instead of a short job finishing quickly, it has to wait through multiple cycles to complete. Fairness and turnaround is a tradeoff across scheduling.
Naturally, there must be some I/O in our processes. Otherwise we would have quite a poor user experience! In this case, we can split processes into essentially subprocesses. Say a process executes, then waits a bit for I/O. During that waiting time, we can run parts of other processes. This is overlapping processes, which is very powerful when it comes to scheduling with I/O.
In almost all systems, we don't know how long a process will run. Many algorithms that we currently use depend on knowledge of the run time. So, we find ourselves in a bit of a crossroads here.