Coordination of Action

We coordinate many actions in life with the help of a clock. We set times for such events meetings, classes, train and airplane departures, and radio and TV broadcasts, and our morning alarm clocks. We set up signaling systems to prevent trains from colliding on a section of track or cars colliding in an intersection. Whether we use clocks or signals, our real purpose is to coordinate actions with other people and with machines. For example, arriving late to a meeting means we miss the opportunity to coordinate with the others who attended the meeting; arriving late for a train means we miss the train, and then the opportunity to meet with other people at our destination. A malfunctioning railroad semaphore or traffic light can spell a train wreck or car crash. The cost of a failed synchronization may be an inconvenience, a loss of business, or an accident. Synchronization -- meaning to perform actions together -- is a fundamental aspect of coordination.

Computers must be carefully designed so that synchronizations required by their human masters do not fail. To synchronize events to a clock, the designer creates a clock-monitor program that constantly compares the time to a list of scheduled events; when one of the events comes due, the clock monitor signals another program to perform the requisite action. Thus, from the standpoint of a computer designer, an action synchronized to a clock is no different from an action triggered by a signal from another program: all can be formulated as the exchange of signals.

Semaphores as Synchronizers

The semaphore provides everything needed to accomplish the signaling needed for every kind of synchronization. A semaphore is a special object used to exchange signals. It contains a count of the number of signals sent, but not yet received; and if the count is in deficit, it also contains a list of the processes that are stopped to wait for a signal. We call these two components of a semaphore the count and the queue.

We need a way to send a signal via a semaphore and a way to receive a signal from a semaphore. To send a signal to a semaphore sem, we use the operation SIGNAL(sem), which adds one to the count and releases one process from the queue if any are in the queue. To receive a signal, we use the operation WAIT(sem), which subtracts one from the count and stops to wait in the queue if the count is a deficit.

The only requirement for the correct operation of WAIT and SIGNAL is that the system not allow two processes attempting SIGNAL or WAIT operations to carry them out at the same time. This is the familiar mutual exclusion requirement. Without it, the system can lose a signal or drop someone from the queue, leading to potentially major failures of synchronization. The beauty of semaphores is that the system designer needs to solve the problem of mutual exclusion just once -- for the implementation of semaphores -- and then everyone else can make any set of operations mutually exclusive as they desire.

Common Examples of Synchronization

A very common synchronization requirement encountered by computer programmers is the strict order of two tasks. Task A must be completed before Task B can start. We cannot board the train until we have bought a ticket. We cannot enter the intersection until the traffic light is green. We cannot get money from an ATM until after we have entered our PIN.

This requirement is easy to implement with semaphores. We create a semaphore AB with initial count 0. Then we simply put the SIGNAL at the end of A and the corresponding wait at the start of B:

  A:  Program of A; SIGNAL(AB)
  B:  WAIT(AB); Program of B

Semaphores can be used when one process (on one machine) requests another process (on another machine) to do a task for it. We call this a remote procedure call. The calling (client) process must stop and wait until it receives a signal from the service process indicating that the task is done. This can be done with two semphores, call and return both with initial counts of 0:

  Client: repeat { some computation; SIGNAL(call);
                   WAIT(return); more computation }
  Server: repeat { WAIT(call); computation; SIGNAL(return) }

Semaphores are a powerful tool for designers of signaling systems. Here is an example of a simple traffic light controller for an intersection between and east-west road and a north-south road:

  Clock:  repeat { wait 30 seconds; SIGNAL(switch);
                   wait  5 seconds; SIGNAL(switch) }
  Lights: repeat { WAIT(switch); set E-W to green, N-S to red;
                   WAIT(switch); set E-W to yellow;
                   WAIT(switch); set E-W to red, N-S to green;
                   WAIT(switch); set N-S to yellow }

Variations

There are many variations on semaphores. One common variation is to simplify the semaphore by restricting count to two values (0 and 1) and eliminating the queue by tying the semaphore to a particular process. Time sharing systems (discussed in another section) use this simplification extensively to implement low-level synchronizations. A process that needs to stop and wait for a signal can use a SLEEP instruction and another process can issue a WAKEUP instruction to restart it. In this case the count is a bit that tells whether or not a WAKEUP signal has already been sent, and the queue is unnecessary because the bit is uniquely associated with a process.

Network protocols give another example of synchronization with simplified semaphores. The program that listens to the network to must stop and wait until the next packet arrives; the network interface unit can send the WAKEUP signal to the listener process whenever a packet arrives.

Next section: Deadlocks