Perhaps most fundamental to multitasking, even more than the context
switch, is the need for autonomous actions. It is not surprising
that they are among the first topics covered in texts on concurrent
operating systems and multitasking.4 An atonomous
action is an operation which must be completed in one indivisible step.
The action cannot be interrupted or partially completed. Some things in
life require atomicity. When changing clothes, you don't want to be
caught with your pants down, and the same is true for computers!
There are two basic approaches which we can take to achieve atomicity.
One approach is to wait until you can guarantee you can do what
you've got to do in ``one action''. To avoid the wait, a more
sophisticated approach is to go ahead and do what you've got to do
atomicly, and if you're interrupted, to undo what you've done.
However, this approach is more complicated, requiring that you
remember everything you've done so far. More importantly, all we've
really done is break up one big ``atomic'' action into smaller
actions, which, if you think about it, must also be atomic. In other
words, we're going in circles. Thus at some point, we will have to
have an action which must wait until it can guarantee to
complete. To insure we are not interrupted, we need to
synchronize ourselves with all parts of our environment which may
interrupt us, namely other processors and independent hardware the
computer may have. We need the synchronicity of signals and
semaphores...
- A Signal
- , or, in lower-level constructs, an interrupt, is a
common means used to synchronize a processor with external (and
asynchronous) hardware (such as I/O drivers). A processor supporting
interrupts automatically checks for any pending interrupt signals between
each instruction. If an interrupt is pending, the processor suspends what
it is doing and calls an interrupt handler routine, such as a procedure
to read in the character when one has arrived at the keyboard. When the
handler returns, the processor (usually) continues as if nothing had
happened.
Interrupts help the programmer by automatically polling in
hardware if specific events have occurred, allowing more timely (faster)
interaction with the outside world. However, their handlers must make
some change to the computer's environment to have an effect. At certain
points, though, we don't want them to make any changes; for example, we
may not want to be interrupted while servicing an interrupt, nor would we
like to be interrupted when working on data an interrupt may modify. In
other words, when working with a piece of data, we need to mask or
block all interrupts which may directly or indirectly modify that
data. If we are only going to be working with the data a short time,
perhaps the safest and easiest strategy is just to block all interrupts.
This is what the mpsig.h code does by modifying the IFflag
(MS-DOS version) or calling the
setsigmask (UNIX version). For
convenience (and to emphasize the temporary nature of signal blocking), I
have included a
mpsig
macro to disable interrupts around a
specified block of code.
- A Semaphore
- As signals synchronize the processor with other
hardware, semaphores synchronize it with other processors. A semaphore is
like a gate which will only let a certain number of people (processors)
through, usually just one. We can limit the simultaneous access of
certain data or the simultaneous evaluation of certain code by
associating a semaphore with it and requiring each process claim the
semaphore before it proceeds, and release it when it's through.
Though a simple idea, implementing semaphores is somewhat tricky. At some
point we must have some indivisible operation which either exchanges
data between a processor's local (register) memory and global shared
memory, or something which essentially increments or decrements the global
memory location. Though the former is most efficient, the latter happens
to be available in ``C'' and takes no low-level assembly programming. The
mpsem.h code attempts to accomplish this in ``C'' via the + + var
pre-increment operator on a volatile integer. On most machines, this
should compile to a single machine instruction. (The problem of this
scheme is that it requires to be efficient a back-off strategy (a delay)
when several processes are grabbing for the same semaphore (NOT IN CURRENT
IMPLEMENTATION)). For convenience (and to emphasize the temporary nature
of signal blocking), I have included a
mpsig macro to claim a
semaphore and (then) disable interrupts around a specified block of code.
These synchronization tools, signals and semaphores, are necessary to
build an efficient and correct multiprocessing scheduler. However, they
are intended only for these low-level system utilities. For
simplicity, instead of signals, higher-level task I/O should more
straight-forward constructs as streams. And for efficiency, instead
of semaphores, higher-level task synchronization should use more
controllable constructs as conditional waits. (More on a
nifty abstraction to implement these ideas in a subsequent article.)