Lindsey Kuper (lindseykuper) wrote,
Lindsey Kuper

Andy Tanenbaum's Orange and Apple Orchard

So, I've been studying for the systems qualifying exam that I have to take in a week and a half or so (eep!). Today I came across a question that really frustrated me. It's on one of the practice exams that I'm working from, and it also seems to show up all over the interwebs in various versions, answers included. But one of the answers didn't make sense to me until a little while ago. I'm going to try to describe it in everyday language -- see if you can figure it out faster than I did. No computer science background should be necessary for the problem I'm about to describe. (Believe me, it didn't help me.)

You work at an orange and apple orchard outside of Amsterdam. You have to complete two tasks: filling a bucket with apples and filling another bucket with oranges. You know that the most efficient thing for you to do would be to fill a whole bucket with one fruit before moving on to the other fruit. But if your boss, Andy, comes along and sees that there are a lot fewer oranges in your orange bucket than there are apples in your apple bucket, he'll get irritated and kick your apple bucket over! A similar thing will happen if you favor the oranges and neglect the apples. Therefore, you want to give the appearance of making incremental progress on both fronts at once.

With that in mind, you've devised a cunning plan: work on the oranges for time Q, then work on the apples for time Q. Andy agrees to this plan, and promises not to kick over your buckets as long as you always trade off after Q amount of time has gone by. (Also, if you finish a bucket and you're still in the middle of a chunk of time Q, you can simply switch right away; you don't have to stand around idle until the end of the time. It seems obvious, but I actually overlooked it on my first attempt at the problem.)

The only thing wrong with your cunning plan is that every time you stop working on one bucket and start on the other, it takes a little while to get reacclimated -- you have to take off your orange-handling gloves and put on your apple-handling gloves again. So, there's a small cost to stopping and starting -- say, an amount of time S. Also, there's the time it takes to get your gloves on just when you're beginning, which we'll say is also S. In a perfect world, where S doesn't exist, it takes time T to fill a bucket. But in the real world, we're going to have to think about the additional time taken up by S.

Now, suppose that the buckets are really small, or that Q is really long. In fact, the buckets are so small or Q is so long that it's possible to finish an entire bucket of fruit during one period of time Q -- in short, Q is greater than T. Great! You still have your start-up cost of S, and you have to switch to working on the other bucket in the middle, which also takes time S, but then you can finish the second bucket within the next chunk of time Q. Overall, you're able to fill two buckets in time 2T + 2S. Not bad -- it only took time T + S per bucket. We say that your efficiency -- the ratio of the time it would ideally take to fill a bucket to the time that it actually takes -- is T/(T+S). This is pretty much as good as it gets. Notice that since you are always able to finish your buckets in less than the Q time limit, then it is as though the time limit doesn't exist for you -- and, indeed, Q doesn't show up in your efficiency calculations at all. T/(T+S) is probably pretty close to 100%, depending on how small S is.

Now, for a more realistic example, let's say that you can't fill a bucket in time Q. That is, the time T is greater than the time Q. Now, our calculations get a little more difficult, but not much more. We're going to have to spread out the time it takes to fill the apple bucket over several periods of length Q. How many will it take? To find out, we just divide T by Q, getting a number T/Q. And those will be interleaved with several periods of length Q in which we were working on the orange bucket. Again, there will be T/Q of those. And every time a new period of length Q starts, we'll have to change our gloves. So, there will be 2T/Q glove changes, each taking up time S, for a total of 2ST/Q time spent changing our gloves.

What's our efficiency? We're spending 2T + 2ST/Q time on our two buckets, or T + ST/Q per bucket. So our efficiency is T/(T + ST/Q). Using trusty ninth-grade algebra1, this turns out to be the same as Q/(Q+S). Pretty good. It's not quite as good as what we had before; remember, we said that T is greater than Q, so, Q/(Q+S) ends up being not quite as good as T/(T+S). (I tried a few examples to convince myself of this.) But it's not bad.

Still with me? Okay, now here's the part where I got confused.

Suppose that Q is equal to S. That's a pretty short amount of time for Q, isn't it? We're saying that in the time Q, all we're going to have time to do is take off our apple-handling gloves and put on our orange-handling gloves, or vice versa. As soon as we've done so -- oops, time's up! We've got to switch to working on apples again. So we change our gloves back -- oops, times's up! And so on. We're doomed to change our gloves forever, with no time to actually do any work. To me, that would suggest 0% efficiency.

The problem is that the math disagrees. If we plug in Q in place of S in our Q/(Q+S) formula from above, then we get Q/(Q+Q), or 50% efficiency.

I was really confused by this. Which was it -- 0% or 50%? Of course, I thought, it would certainly be nice if our system wasn't so awful that it forced us to do nothing but change our gloves forever. If only it were flexible enough to allow us to just grab the next chunk of time Q and use it for whatever purpose we happened to be wearing the appropriate gloves for. We could keep going that way, using two chunks of time Q at a time, first to change our gloves again, and then to do some work. It would be terribly inefficient -- indeed, the efficiency would be just about, oh, fifty percent -- but it would at least let us get something done...

And that's when I realized my mistake! The problem was that I had suddenly decided to count the glove-switching time S as part of the time Q. In my earlier calculations, S hadn't been part of Q; after switching gloves, we still had all of the time Q left to try to get work done. (Suppose we had been including S in Q earlier, in the Q-is-greater-than-T scenario. If we had, then having the time S cut into Q might have pushed us over into not being able to finish an entire bucket during time Q, which would undermine the whole premise. So we really had been relying on having S be its own, separate chunk of time.)

If we understand that S is not included in Q for the S = Q scenario, it makes a lot more sense: the efficiency ends up being 50%, just like we thought. And all is right with the world, and my answers agree with the ones I've seen on the rest of the blagonets. The only difference is that my explanation is a lot more awesome.

By the way, if you've stuck around this long, you've learned about round-robin scheduling (the system you devised to keep Andy from kicking your buckets over)2 and context switching (changing your gloves).

I don't know if it's typical to include the context switch in the quantum or not -- anyone know?

  1.     T             T               T               T             1         Q
    --------  =  -----------  =  -----------  =  -----------  =  -------  =  ---
    T + ST/Q     TQ/Q + ST/Q     (TQ + ST)/Q     T * (Q+S)/Q     (Q+S)/Q     Q+S
  2. The kicking-buckets-over analogy isn't unrealistic; if several things are happening on a computer at once and one of them doesn't appear to be making any progress, the user will often unceremoniously pull the plug on one of the others, forcing it to start all over again. Round-robin scheduling helps guard against that kind of thing, at least in theory. If you find this interesting, you should consider studying computer science.
Tags: signal

  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded