Lab 5: ioPending in bufferCache
Craig Varrichio
a heap of trouble. However, then we run the risk of filling up the
bufferCache with ioPending pages that can't be removed and introduce the new
possibility of it being impossible to read something into the bufferCache.
Right now we just have the process go to sleep until a page is available for
removeable, but we have no idea if that is correct.
Nitya Oberoi
Nitya
Emmett Witchel
No you can't remove it (remember the exam question?). If you run out of
pages, just block the process and run init until an interrupt returns
and you can make further progress.
Emmett
Yiu Fai Sit
Sit
Craig Varrichio
to block this. We are at this point actually blocking - that is, we are
calling wait(). But it sounds like you want us to block using the system.
But how could this possibly work? If we call sched.process_block, this
doesn't actually block the process. The current syscall should complete.
Usually, when this happens in a callback, the process is blocked and the
syscall is allowed to terminate. The syscall is not executed again, but is
instead resurrected by the disk later on. My point is, if we allow the
syscall to terminate and block the process in this situation, I don't think
it's within our power to ressurrect the process later. We can't just put
the event back on the callBackManager directly and we can't change it to an
interrupt and then put it back on the manager. There are lots of hacks
around this but they are all messy and seem to not be what was intended.
If you're still reading after all that nonsense I just said, how are we
supposed to do this?
"Emmett Witchel" <wit...@cs.utexas.edu> wrote in message
news:d5k5m8$d2$2...@geraldo.cc.utexas.edu...
Adrian Kubala
> That's what I thought. But I'm a little confused about how we are
> they are all messy and seem to not be what was intended.
I'm trying to handle this by attaching a queue of continuations (i.e.
OSEvents) to each page, and the read interrupt handler runs each of
these in order. So if you have 5 processes trying to read the same page,
they'll all get blocked, and then when the page is done reading they'll
all get unblocked and have ReadCheck.write called and so forth.
I can't tell how the sample code expects us to handle this case either,
so I ended up redesigning almost everything and I agree it seems like
something else was intended.
Eric Tschetter
> pages, just block the process and run init until an interrupt returns and
> you can make further progress.
Above, in "Lab 5: File size greater than Memory" the following discourse
took place:
Sit said:
for this lab, let's just assume we have enough memory so that these
situations do not happen...
In response to Syed Kamil Fareed:
> On a similar note, what should we return from removeLRU() if we cant
> remove any of the blocks if all of them have their io_pending boolean to
> true?
>
This makes it seem like we can simply assume that we will not run into the
case where the only pages that exist in memory when we need to call
removeLRU() are pages that are either pinned = true or io_pending = true.
That is, can we always assume enough memory for io_pending jobs to complete
their io before their cached page is needed?
I am currently wrestling the same demon as Craig and Adrian, unless I am
mistaken there is no way in our simulator to block a process in a fashion
similar to a normal system. What I mean is, there is no way for us to just
halt a process's activity, pack up what it is currently doing, and make it
just wait (like blocking on a Monitor.wait()). The system seems to force us
to complete the current call stack on a process before it "blocks." Being
forced to complete the current call stack causes problems when RemoveLRU()
is called because we cannot be certain about which page to return (something
that removeLRU "guarantees").
Or, are we supposed to use the strict ordering of io to simply assign pages
assuming that as long as we take the oldest one, its io access will finish
before ours?
--Eric
Emmett Witchel
>>No you can't remove it (remember the exam question?). If you run out of
>>pages, just block the process and run init until an interrupt returns and
>>you can make further progress.
>
>
> Above, in "Lab 5: File size greater than Memory" the following discourse
> took place:
>
> Sit said:
>
> for this lab, let's just assume we have enough memory so that these
> situations do not happen...
>
> In response to Syed Kamil Fareed:
>
>>On a similar note, what should we return from removeLRU() if we cant
>>remove any of the blocks if all of them have their io_pending boolean to
>>true?
>>
>
>
> This makes it seem like we can simply assume that we will not run into the
> case where the only pages that exist in memory when we need to call
> removeLRU() are pages that are either pinned = true or io_pending = true.
> That is, can we always assume enough memory for io_pending jobs to complete
> their io before their cached page is needed?
Yes, I believe this is true. We will not test this case.
> I am currently wrestling the same demon as Craig and Adrian, unless I am
> mistaken there is no way in our simulator to block a process in a fashion
> similar to a normal system. What I mean is, there is no way for us to just
> halt a process's activity, pack up what it is currently doing, and make it
> just wait (like blocking on a Monitor.wait()). The system seems to force us
> to complete the current call stack on a process before it "blocks." Being
> forced to complete the current call stack causes problems when RemoveLRU()
> is called because we cannot be certain about which page to return (something
> that removeLRU "guarantees").
>
> Or, are we supposed to use the strict ordering of io to simply assign pages
> assuming that as long as we take the oldest one, its io access will finish
> before ours?
I believe we use the strict ordering of I/O. This is not ideal, but it is ok for this lab and keeps things simple. Sit can confirm.
Emmett
Adrian Kubala
> I am currently wrestling the same demon as Craig and Adrian, unless I am
> mistaken there is no way in our simulator to block a process in a fashion
> similar to a normal system. What I mean is, there is no way for us to just
> halt a process's activity, pack up what it is currently doing, and make it
> just wait (like blocking on a Monitor.wait()).
Maybe this will confuse more people than it helps, but I have to share
this revelation I had. The whole deal with OSEvents is actually a wacky
form of continuation passing style[1]. You can think of event_number +
state as a function pointer, and when you pass this into a blocking
function like read, it does its IO and then "calls" the continuation to
let the process continue doing whatever it was when it blocked.
Thinking in CPS terms, you're turning your code "inside out" around the
possible blocking points, so that everything after the blocking point
goes into a continuation passed into the blocking method.
Of course, as you noticed nothing actually "blocks"; the blocking call
returns immediately and you are expected to unwind the call stack all
the way back to ProcessTrace.run, which will pick up and run the
continuation for you. This is called trampolining; it's a way of getting
around the fact that Java doesn't do tail-call elimination. If you never
returned you'd eventually run out of stack space, so you smuggle your
return values into the continuation and unwind to the top level which
starts the continuation on your behalf.
Since Java has primitive closures (local inner classes), you can make
OSEvent do *anything* you want, not just limited to the methods and
states already in the code. So you could do a read like this:
sched.proc_block(pid);
bufferTableEntry.lockForIo();
blockDriver.read(devNum, new OSEvent(baseEvent) {
public void happen() {
baseEvent.happen();
bufferTableEntry.unlockForIo();
sched.proc_unblock(pid);
bufferTableEntry.notifyWaiters();
}
});
Actually that won't work literally with the code we have, but hopefully
you get the idea -- it's starting to look like *real* CPS. Personally I
find this a lot easier to understand than the hard-coded function
pointers used in the lab, but not everybody agrees with me.
Yiu Fai Sit
yes, this is true.
Sit
Craig Varrichio
> >> pages assuming that as long as we take the oldest one, its io access
> >> will finish before ours?
> >
> >
> > I believe we use the strict ordering of I/O. This is not ideal, but it
> > is ok for this lab and keeps things simple. Sit can confirm.
> >
>
> yes, this is true.
So what does this mean? We assign it the memPage that it would normally
receive, and just hope that the pending IO will complete first? Wouldn't
that mean that the IOPending flag does nothing?