previous | contents | next



KEYWORDS: Arbiter, producer, consumer, polling, synchronization, parallelism.

The purpose of the K(arbiter) module is to arbitrate multiple requests for use of a common set of facilities. A polling structure which examines such requests in turn, e.g. as described in the M(queue) problem (later in this chapter), solves the same type problem as the K(arbiter), but the K(arbiter) saves hardware and makes the solution of timing and synchronization problems quite apparent. These synchronization problems arise from the need (desire) to achieve a high degree of parallelism in digital systems.

The K(arbiter) module is similar to a parallel merge in that it waits for a specific condition to occur before proceeding, but unlike the parallel merge, its use is not predicated on lock-step parallelism. The form of parallelism it addresses is referred to as concurrency; in essence two or more processes are active concurrently, and, at some time, must share a common set of facilities (resources). In the M(queue) problem, the three control subprocesses each access a common data part, hence only one control part is allowed to be active at a given time. On the other hand, in the histogram recorder problem, a record updating process and display process could run concurrently except when, both required access to the shared memory.

The basic structure of this latter type of system is shown in Figure ARB-1. There is no coordination required by the two processes except that they cannot access the common memory (essentially a queue) at the same time. The producer process generates data and makes calls to store the data in the common memory while the consumer process makes calls to fetch data, to use in the process, from the memory. The producer and consumer processes call the common memory buffer process at different rates and neither is synchronized with it or with each other. A common process controls access to the central memory in such a way that only one process (producer or consumer) can use it at a time, thereby protecting the two processes from one another. Without such protection, the processes might incorrectly change a controlling variable in the central process, thereby causing erroneous action by either the producer or consumer.

Suppose that there is a flag that indicates whether the common facility is in use or not. Each process can examine the flag, and if' the memory is free, then that process can set the flag to indicate that the memory is in use at that time, thereby inhibiting the other process from gaining access to it. When the process has finished using the memory, it can reset the flag to indicate that the facility is not in use, thereby allowing the waiting process to access the memory. An implementation based on such a flag is shown in Figure ARB-2. There is a slight' flaw in the design, however, that could make the system operate incorrectly. When examining the flag, both the producer and consumer might at the same



previous | contents | next