CS 134

Arrival Time and I/O Wait

  • Cat speaking

    I think a few things from last lesson weren't very realistic. For example, all the processes arrived at the same time. That's not very likely.

  • Duck speaking

    And they never had to wait for any I/O, they were always ready to just run.

  • PinkRobot speaking

    True. Let's remedy that.

Our Work

We'll stick with the processes we had last week, but this time, we've added an arrival time for each process.

Process Arrival Time Required Time

It's also the case that while most of the procesess are compute-bound (i.e., they are spending most of their time—in this case, all of their time—doing computation), one process is different:

  • Drew regularly does I/O, with each I/O request taking 3 time units. In fact, I/O dominates Drew's execution, so we would call Drew I/O-bound.

We'll see how this change affects the scheduling. Take a look at the chart below (which returns to simple FCFS scheduling) and the statistics table.

Schedule

In the schedule below, time spent waiting for I/O to complete is shown in a dark teal color (whereas, just as in last week's lesson, time spent ready-to-run is shown in a light blue).

Timeline of processes running with Round Robin scheduling

Chronology

Although the chart above shows the processes running, it isn't always easy to see exactly why a given process was scheduled next. This scrollable table shows another view of what was going on.

Time Running Ready Blocked

Statistics

Here are all the statistics for the processes in this run:

Process Response Time Turnaround Time Wait Time Context Switches

Your Thoughts

Looking at this schedule, what do you think about it? What new things do you notice compared to when we looked at FCFS last week? (i.e., things due to the I/O happening, rather than specific to FCFS)

If you observe any issues, do you have a suggestion for what might help address them?

  • Hedgehog speaking

    Poor Drew! Arrives right at the beginning, and yet is last to finish. After their first I/O, Drew is ready to go again at step 4, but no, Alice, Eve, and Bob are all too important. They want to toil away. If they just let Drew back for a moment, they'd barely notice the difference, but it'd make such a difference to Drew.

  • Cat speaking

    I'm pretty sure round robin will help with that. It's not perfect, but it's got to be better than FCFS.

  • PinkRobot speaking

    Let's see… Fun fact, we were actually already using round robin here, but with a large quantum so it acted like FCFS. If we make the quantum smaller, we'll see Drew get more chances to run.

Click the button below to enable to add controls that allow you to adjust the quantum for the round-robin scheduling algorithm and change the random seed to get different times for the processes to explore different scenarios.

  • Scroll back up to the chart where you'll see the enabled controls, and experiment with different quantum values. Initially leave the seed at its default, 9876573.
  • Then, try out different random seeds to see how the schedule changes. For example, try the seed 12345 where round-robin doesn't do as well.
  • Note that even if setting the quantum really small seems to give better results, we usually wouldn't want it to be as small as possible as that generates too much context-switch overhead. So explore how well we do when the quantum is set to 3.

Starting with the scenario-generation seed is 12345 and the quantum is set to 3, notice that at time 15, Drew is ready to run, but doesn't actually get to run until time 18. Explain, being as specific as you can, why Drew had to wait. (Hint: Look at the chronology table rather than the schedule chart.)

Does this example give you any ideas for a change we could make to the scheduling algorithm to help Drew?

  • Cat speaking

    I see why Drew doesn't get to go at time 15. B is at the front of the ready queue, and so B gets to run next. That's what we always do. It's fair. Whoever has waited the longest gets to run next.

  • Hedgehog speaking

    But Drew doesn't need much CPU. Can't we find a way to give Drew a bit of a break?

Boosting I/O-bound Processes

Besides getting all the work completed sooner, there are some other compelling reasons to give I/O-bound processes a bit of a boost…

Setting aside our running examples for a moment, can you think of a reason (perhaps one that relates to your own computer usage) why, if the machine is busy with compute-bound processes, it might be a good idea to give an I/O-bound process a bit of a boost?

  • Dog speaking

    If I'm using my computer, I don't want to have to wait around for it to finish something else. I want it to be responsive to me. Interaction with the user is I/O, and as the user, I'm supposed to be the center of attention.

  • Goat speaking

    Meh. You wish.

  • Horse speaking

    Hay! I've an idea! Going back to our example, what if we put Drew at the front of the ready queue when Drew wakes up? Then Drew would get to run next.

  • PinkRobot speaking

    Let's try that!

Wake at Front

Adding newly woken threads to the front of the ready queue is a common optimization for round-robin scheduling. It helps to reduce the wait time for threads that don't need much CPU time.

You can experiment with this optimization by clicking the button below. It will enable the checkbox to put newly woken threads at the front of the ready queue. It also automatically scrolls back up to the chart so you can change the setting and observe the new schedule.

Go back and set the scenario seed to 12345, the quantum to 3, and enable wake-at-front. We can see that Drew often gets to run right after an I/O operation. But at step 10, Drew has to wait for two steps before running.

Explain why Drew had to wait (i.e., is there a rule you can infer?).

Could the system have been designed differently so that Drew got to run right away? What are the pros and cons of doing that?

  • Pig speaking

    I just realized something. Wake at front could lead to STARVATION! If we always put the newly woken threads at the front of the ready queue, then the threads that are already running might never get to run again. That's not good.

  • PinkRobot speaking

    Yes, we're going to have to think about some of the ways that programs might manipulate the system to get more than they deserve and figure out how to prevent that.

(When logged in, completion status appears here.)