Internal & External Synchronization

If concurrent processes are going to constructively interact, they must be able to synchronize with each other. Process synchronization takes place on two levels: internally (between processors) using semaphores and externally (between a processor and external hardware) using interrupts or polling.

A semaphore is a processor synchronization device used for limiting the number of processors which access certain data simultaneously. Normally only one processor is allowed to access the data at any given time. The semaphore is implemented as a mutually agreed upon bit in the computer's memory. When a processor wants to claim or wait for the semaphore, it both tests and sets the bit in one atomic operation, usually implemented as a single machine instruction so that it can't be interrupted4. If (and only if the bit) was already set, then the processor waits until it is cleared. (The bit signifies that the data the semaphore represents is in use.) Out of courtesy, a processor must likewise clear the bit when it is through, to release the semaphore and signal any waiting processors.

Semaphores provide the necessary processor synchronization but are fairly primitive. With them, higher-level control structures be built. The monitor, for example, monitors data by limiting its access to a set of procedures, only one of which can run at any given time.

Interrupts and polling, on the other hand, allow a processor to synchronize itself with its external hardware devices. To synchronize, a processor may poll its devices, waiting for them to reach a certain state (as ``ready to receive data''). The advantage of polling is that the processor may wait for any set of conditions of its choosing. The disadvantage, of course, is the processor may waste a lot of time polling, and must remember to poll amid is regular processing. For this reason, most processors have built into them circuitry for automatically polling a set of hardware interrupts between each of their instructions. When an interrupt is signaled, the current process is interrupted and an interrupt handler routine is run to handle the interrupt. Complications set in when the interrupt handler itself is interrupted, and most processors allow interrupts to be disabled or prioritized.

Figure: Internal and External Processor Syncronization Devices
\begin{figure}
\begin{verbatim}
EXTERNAL HARDWARE
/=============------...
...===================================================/\end{verbatim}
\end{figure}

As semaphores are systematically claimed and released, so are interrupts disabled and enabled. When accessing data, a process must disable all interrupts which may also modify the data. For this reason, you'll typically, you'll typically hear the buzz words: non-pre-emptive code (not interruptable while executing) and non-re-entrant functions (not recallable while evaluating).