CS444 class 17

CS444 Class 17

For next time, read Chap. 3 to pg. 194, esp. 189-194

HW3 Setup—does multitasking, so need process switch code, very tricky—

How the System runs with supplied uprog1, uprog2, uprog3

Uprog1: write(TTY1, “aaaaaaaaaa”, 10);…

Uprog2: write(TTY1,”bbbbbbbbbb”, 10);…

Uprog3: <delay loop>, write(TTY1, “ccccccccccc”, 10);…

Here is what we expect to happen with two user programs starting off doing more than 6 chars of output (the output buffer size) to the same TTY device.

As provided in $cs444/hw3, uprog1 runs, then uprog2 runs, then uprog3 runs, with asmswtch executing only when a user program exits:

int sysexit(int exit_code)

{

cli();

curproc->p_exitval = exit_code;

curproc->p_status = ZOMBIE;

number_of_zombie++;

schedule_one(curproc-proctab); /* will switch to process 0 */

/* never returns */

return 0; /* never happens, but avoids warning about no return value */

}

As provided, same old busy loops for input and output in tty.c

But there are comments in tty.c to show you where to edit to call scheduler to sleep, wakeup

As fixed, with a proper round-robin scheduler:

--One user process runs until it has filled the output buffer, then blocks (via call to scheduler, which looks for another process to run),

--another process runs, also blocks, because it wants to output to the same device, and the output queue for it is full

--a third runs, goes into CPU-bound delay loop

-- output drains during loop (no preemption here), as soon as space in output queue, 1 and 2 unblocked

-- output finished, transmitter shuts down,

-- delay loop in uprog3 finishes, uprog3 enqueues 6 c’s, blocks, process switch to 1, blocks, process switch to 2, blocks

-- all user processes blocked, so process 0 is chosen to run. As process 0 runs, output drains at interrupt level, and the user processes are unblocked by a call to the scheduler from the transmitter interrupt handler as soon as one char (a ‘c’) is output. Process 0 calls the scheduler and the scheduler finds a process to run, process 3

--the chosen user process, process 3, runs and refills the output buffer (1 char, another ‘c’), then blocks.

--the other two user processes run in turn and find the full output buffer, and block again.

--process 0 runs again…

…over and over... until the output is done.

hw3’s scheduler

Scheduler setup, kernel global variables:

proctab[], curproc: global, used by tunix.c and sched.c

Recall our discussion of PEntry structs, one for each process in the proctab array. There are 4 spots in the array, one for process 0 and 3 for the user processes 1, 2, and 3.

process 0 derives from the startup execution, i.e., the kernel initialization in tunix.c morphs itself into a process by filling in proctab[0] and curproc. It is always runnable, so the scheduler can always find a process to run.

Once the system is running, all process 0 does is call the scheduler over and over, and allow int’s for a moment between these calls, until is sees that all the user processes are zombies. Then it brings down the system.

Scheduler API (not encapsulated: uses global proctab[], as do other functions in the kernel)

sched.c will contain the scheduler code—here are its major functions.

schedule()—look for a user process to run, else choose process 0, call asmswtch
tsleep(event)—block the calling process by changing p_status to BLOCKED, p_waitcode to event, and then calling schedule().
twakeup(event)—loop through proctab, changing all processes blocked on this event to p_status = RUN.

Sleep and wakeup are the traditional names for the functions: we’re adding t for tiny-UNIX, and to allow “sleep” to name a new system call.

Where are these called from?

tsleep—called from ttywrite (to replace the busy wait)

twakeup—called from the tty output interrupt handler, when a new spot in the output queue becomes available.

schedule—called from process 0 code, to get started, and as an “idle loop” to try to hand off the CPU to a user process. Also from sysexit.

These are all critical code, so should run with interrupts off. If you call wakeup only from int handlers, of course it will get IF=0 automatically, since we never turn ints back on in int handlers. You could put checks in to make sure IF=0 ((get_eflags()>>9)&1 gives IF)

Note that wakeup is a “broadcast” action, so multiple processes may wake up for just one char-spot in the tty output queue, for example. Also note that wakeup doesn’t call schedule, so it doesn’t actually get a process running, it just marks it runnable. Sometime later, another process calls sleep, and that calls schedule, and chooses this one to run. Or process 0 calls schedule, and that does the trick.

The only tricky coding in sched.c is schedule(), because it calls asmswtch, a completely weird function. I’d code it like this:

Decision code, end up setting new curproc, but also knowing oldproc, pointers to proctab entries.
asmswtch(oldproc, curproc)
return

You don’t have to do it this way, but be aware that asmswtch does return after the given process is rescheduled, and then it should return from schedule and go on with its business (unless the process is exiting). Don’t let it fall into inappropriate code because you think it never returns!

Blow by blow:

Process 1 running, ESP pointing into stack1, calls asmswtch (&proctab[1], &proctab[2]) to switch to process 2, a process that has already run

Return from asmswtch: process 2 is now running. ESP points into stack2 area.

…

Later, asmswtch(&proctab[0], &proctab[1]) happens, to switch back to process 1

Return from asmswtch: now process 1 running, ESP points into same spot in stack1 as earlier,

So looking from process 1 lifetime:

Process 1 running, ESP pointing into stack1, calls asmswtch (&proctab[1], &proctab[2])

Return from asmswtch: now process 1 running, ESP points into same spot in stack1 as earlier,

In this view, asmswtch acts like a normal function. As long as its registers and stack are intact, it shouldn’t “notice” that a little delay happened.

Special case: starting process 2:

Process 1 running, ESP pointing into stack1, calls asmswtch (&proctab[1], &proctab[2]) to switch to process 2, a process that has never run

Return from asmswtch: because the “saved PC” is ustart2, process 2 starts running at ustart2 here. ESP points into stack2 area because of the saved ESP value.

The calls into the scheduler are straightforward to code except for the sleep call from ttywrite. There we had a busy loop of attempted enqueues into the output queue, and we need to replace it by blocking the process.

Might try:

if (enqueue(...) == FULLQ)
sleep(OUTPUT);
/* can we enqueue now? Not for sure! */

Suppose two processes, A and B, were unblocked by wakeup. If A gets to run first, it will use up the space in the output queue, but B will still be marked RUN, and will be chosen to run a little while later. It will return from sleep, but there will be no space in the output queue for it to use. It needs to call sleep again. So we really need something like:

while (enqueue(...) == FULLQ)
sleep(OUTPUT);

But what about mutex? We know from hw2 that enqueue needs mutex (cli()) to protect it against concurrent modifications to the queue data structure by itself and the dequeue in the interrupt handler, which can run in the middle of an enqueue unless we turn off interrupts.

Is that enough? Suppose we write guarded_enqueue(), which is just enqueue’s body surrounded by cli and sti (or set_eflags back to original value.), and similarly guarded_sleep(). Then we would have:

while (guarded_enqueue(...) == FULLQ)
guarded_sleep(OUTPUT);

But there’s a sneaky problem here called the lost wakeup problem. It was discussed in Tan, pg. 110 in the context of user-level sleep and wakeup calls. Luckily we are working inside the kernel here, so we are allowed to turn off interrupts as needed.

The problem is this. Suppose that just after guarded_enqueue returns with FULLQ, an interrupt happens that causes a dequeue and a call to wakeup. But this process is not yet blocked, so it is not unblocked. Instead, the wakeup does nothing at all to proctab[] (that’s OK in itself, maybe there’s no more output.) Then this code resumes and calls guarded_sleep, and this process may sleep forever (if it’s the last non-zombie process, for example.)

The solution is to put the cli()—sti() mutex region across more code:

cli();
while (enqueue(...) == FULLQ)
sleep(OUTPUT);
sti();

It’s a little scary to call sleep with interrupts off, but in fact they won’t be off long, because the sleep immediately calls schedule, which finds another process to run, and asmswtch swaps the EFLAGS with the IF in it, and the other process resumes execution, typically with IF=0 inside asmswtch, but it soon restores IF to 1 as it returns to user code. So the mutex (IF=0) is only holding for the execution in this process. The important thing for us here is that an interrupt can no longer occur in that bad spot described above. So even though there is a “mutex hole” at the call to sleep, we have what we need here.

Optional Coverage

More on the mutex hole: Suppose we have a global kernel variable x and we put:

cli();
x = 1;
while (enqueue(...) == FULLQ)
sleep(OUTPUT);
/* is x still = 1 here? Not necessarily, because of the mutex hole at sleep() */
sti();

You can see that the mutex hole allows another process to run in the middle of this sequence, and it could set x to some other value. So the use of cli—sti mutex along with sleep has to be thought out carefully. Basically there are two mutex regions, one before and the other after the call to sleep.