CS644 Thursday, Apr. 15
We were looking at send and receive Xinu syscalls, central to hw4:
· status = send(pid, msg): drop off msg to process pid or fail if there’s a msg there already (no blocking)
· msg = receive(): block until a msg is available for this process, return it.
Look at the sample programs sendtest.c and porttest.c, available in $xuex.
Even without looking at the implementation, we can understand the mutex needs for these functions. Consider two senders (i.e. two processes) who both want to send a message to a certain third process of id pid, which does not yet have a message available.
The two senders can’t both succeed, so we see that one should succeed and the other fail.
Need for mutex in send: what can happen without it.
However, without mutex, the following can happen (send here is user or kernel code):
1. sender1 (executing send) sees the fact that process pid has no msg yet, decides it can put its message there.
2. <process switch>
3. sender2 (also executing send) sees the fact that process pid has no msg yet, decides it can put its message there.
4. sender2 puts the msg for process pid, and returns success.
5. <process switch>
6. sender1 executes again with same local var’s as before, in same code, acting on its prior decision, puts its own message in the spot for pid, and returns success.
But this is wrong: one send call should fail here!
Details on <process switch> above: essential to timesharing is the ability of the OS to take control periodically (via preemption) at the timer ticks (and other interrupts) and switch processes if one has run out of its quantum. So if interrupts are enabled, this can happen between any two instructions, in user code or kernel code. Kernel code with IF=1 is kernel code without kernel mutex held, in Xinu.
Preemption
Taking the CPU
away from a process that can still use it is called preemption. It is
implemented by a process switch called from an interrupt handler. The
interrupted process was running, executing user or kernel code (with IF=1) and
bang (in an interrupt), it is switched to be only ready, not running, and some
other process is running instead. Preemption of user execution is needed to
prevent endless user execution hanging the system. Preemption of kernel code is
perhaps less essential, but still is a good thing because it helps ensure that
the highest priority process is running as much as possible. Both current UNIX
and Linux kernels allow kernel code preemption at times when kernel mutex is
not in effect.
The above sequence (1. – 6.) could be in kernel code or user code that is implementing the same functionality (kmessage.c vs. umessage.c in hw4).
Thus we see that we need mutex to get send to do its job properly. Specifically, mutex is needed here to ensure that the global variables underlying send/receive are used properly: a sender needs to see the flag that says there is a message or not for pid and act on it without interference from other activities that use the same global variables. Use of the mutex binds together the test of the flag and the setting of the message into one atomic action.
Add mutex to send, kernel case. Put disable/restore around code in send. Try out same scenario.
1. sender1 (executing send) does disable(ps)
2. sender1 sees the fact that process pid has no msg yet, decides it can put its message there.
3. <process switch> CAN’T HAPPEN: IF=0, no interrupts can happen!
4. sender1 puts the msg for process pid, restore(ps), and returns success.
5. <process switch>
6. sender2 (also executing send) does disable(ps)
7. sender 2 sees the fact that process pid has a msg, restore(ps), returns failure
Now it works!
Add mutex to send, user-level case (usend of hw4). Try out same scenario. For user-level code, we use a semaphore with initial count 1 for mutex.
1. sender1 does wait(mutex), which returns immediately
2. sender1 (executing usend) sees the fact that process pid has no msg yet, decides it can put its message there.
3. <process switch> Yes, this is possible: IF=1 in user code
4. sender2 does wait(mutex), which blocks
5. <process switch>
6. sender1 puts the msg for process pid, signal(mutex), and returns success. signal unblocks sender2
7. <process switch>
8. sender2 returns from wait, sees the fact that process pid has a msg, signal(mutex), returns failure
Now it works!
The case of blocking under mutex: be careful!
In the above scenario, we could use the user-level mutex exactly the same way as the kernel mutex, and that is commonly the case, but not always. The exception to this simple rule is when the code that we need mutex for itself needs to block. Both kernel and user codes need to block for various reasons:
· Blocking kernel code: set pstate for currpid to wait state, call resched().
· Blocking in user code: call a blocking system call.
In receive, the receiver needs to block if there’s no message yet for this pid.
So we need to consider these two cases for kernel and user code (ureceive of hw4).
Kernel case: (for example in book, see syscall wait)
disable(ps)
...
set pstate to wait state
resched()
...
restore(ps)
As we have discussed before, this gives us mutex from the disable to into the resched, then again from the returning resched until the restore. But right at the call to resched(), other processes are running with IF=1, so the mutex does not hold across the call to resched. There are two code sequences separately made atomic here. That’s OK, we just have to realize this fact.
If we copy this pattern to user code we would have:
wait(mutex)
...
call blocking syscall, say wait(another sem)
...
signal(mutex)
However, this is a disaster! If process A blocks in this code, then it is holding the mutex and blocked. No other process can execute this or other functions of this service, because they all will use the same mutex. The system deadlocks, i.e., freezes up.
Luckily, this is easy to fix. We can just delimit the two separate mutex regions that we get so easily with kernel mutex:
wait(mutex)
...
signal(mutex)
call blocking syscall, say wait(another sem)
wait(mutex)
...
signal(mutex)
Note: this discussion has all been about Xinu, but the semaphore mutex cases are much more general. When you do user-level thread programming under a real OS, you have the same memory sharing of global variables and the same kind of mutex needs and capabilities. In Java, we have synchronized methods with built-in mutex in the class object, and support for blocking via Object.wait(), which releases the built-in mutex for the wait, and re-obtains it when it unblocks.
hw4 Implementation Notes
user-level usend/ureceive/uinit
It’s probably best to use an array of structs, one for each process, say struct umessage umsg[MAXPROC]; where MAXPROC is #defined to 50.
Use a semaphore for each process actively using usend/ureceive, for receive to block on. Also you need a single mutex semaphore for the whole system.
kernel-level ksend/kreceive/kinit: again use an array of structs, but now you can use [NPROC], since NPROC is a kernel symbol. Again use a semaphore for each process actively using ksend/kreceive, for receive to block on, but of course don’t use a mutex semaphore here.
Since these mainly differ by the mutex calls, you should be able to do the user-level implementation, and then just fix up a copy to be the kernel version, or vice versa.