Incorporating I/O
Let's have a look at how you will incorporate I/O in the scheduling policies.
We'll cover the following
First, we will relax assumption 4 — of course, all programs perform I/O. Imagine a program that didn’t take any input: it would produce the same output each time. Imagine one without output: it is the proverbial tree falling in the forest, with no one to see it; it doesn’t matter that it ran.
A scheduler clearly has a decision to make when a job initiates an I/O request, because the currently-running job won’t be using the CPU during the I/O; it is blocked waiting for I/O completion. If the I/O is sent to a hard disk drive, the process might be blocked for a few milliseconds or longer, depending on the current I/O load of the drive. Thus, the scheduler should probably schedule another job on the CPU at that time.
The scheduler also has to make a decision when the I/O completes. When that occurs, an interrupt is raised, and the OS runs and moves the process that issued the I/O from blocked back to the ready state. Of course, it could even decide to run the job at that point. How should the OS treat each job? To understand this issue better, let us assume we have two jobs, and , which each need 50 ms of CPU time. However, there is one obvious difference: runs for 10 ms and then issues an I/O request (assume here that I/Os each take 10 ms), whereas simply uses the CPU for 50 ms and performs no I/O. The scheduler runs first, then after (see the figure below).
Assume we are trying to build a STCF scheduler. How should such a scheduler account for the fact that is broken up into 5 10-ms sub-jobs, whereas is just a single 50-ms CPU demand? Clearly, just running one job and then the other without considering how to take I/O into account makes little sense.
Treating jobs as independent
A common approach is to treat each 10-ms sub-job of as an independent job. Thus, when the system starts, its choice is whether to schedule a 10-ms or a 50-ms . With STCF, the choice is clear: choose the shorter one, in this case, . Then, when the first sub-job of has completed, only is left, and it begins running. Then a new sub-job of is submitted, and it preempts and runs for 10 ms. Doing so allows for overlap, with the CPU being used by one process while waiting for the I/O of another process to complete; the system is thus better utilized (see the figure below). And thus we see how a scheduler might incorporate I/O. By treating each CPU burst as a job, the scheduler makes sure processes that are “interactive” get run frequently. While those interactive jobs are performing I/O, other CPU-intensive jobs run, thus better utilizing the processor.
No more Oracle
With a basic approach to I/O in place, we come to our final assumption: that the scheduler knows the length of each job. As we said before, this is likely the worst assumption we could make. In fact, in a general-purpose OS (like the ones we care about), the OS usually knows very little about the length of each job. So, how can we build an approach that behaves like SJF/STCF without such a priori knowledge? Further, how can we incorporate some of the ideas we have seen with the RR scheduler so that response time is also quite good?
Get hands-on with 1400+ tech skills courses.