|
|
|
|
|
|
|
primitives are categorized as either acquire (lock) or release (unlock). In release consistency, the third constraint of weak consistency is removedthe acquire and release operations need not be sequentially consistent. Accesses to synchronization primitives that require consistency are called special accesses and must be processor consistent. |
|
|
|
|
|
|
|
|
The actual mechanism of synchronization includes as a basic element a read-modify-write function on a location in memory. The simplest type of synchronization is a single synchronization variable. Before access can be made to a shared variable, a particular location is referenced. If this location is (say) zero, then a write may be made to a shared variable, and the contents of the synchronization primitive is changed to one, indicating that the location containing the shared variable is full. Similarly, if an access is made to the synchronization primitive for a read, this is only allowed if the synchronization primitive is set at one, indicating that the shared variable is full and hence available. |
|
|
|
|
|
|
|
|
For example, suppose process A is producing data to be used by process B (a consumer). They share a memory location (b) which they use to indicate the state of a separate data space in memory. Originally the bit is empty (say, b = 0), while the producer process creates and fills the data space. Any access by the consumer reveals that b = 0 and the data space is not yet ready. When the producer process A completes, it sets b = 1 (full). Now the consumer process B can access the data space, and, when finished, reset the bit to b = 0 (empty), indicating that the producer can resume storing into the data space. If there were multiple consumers, we would need additional bits to coordinate the consumers. Now we would designate certain bit combinations as giving exclusive rights to the producer or either one of the consumers; e.g., the following pattern might satisfy the requirements: |
|
|
|
|
| | | | | |
|
|
|
|
Producer working on data, consumers locked out. |
|
|
|
| | | |
|
|
|
|
Data available to any consumer, producer locked out. |
|
|
|
| | | |
|
|
|
|
A consumer has acquired data, producer and other consumers locked out. |
|
|
|
| | | |
|
|
|
|
Buffer empty, consumers locked out, buffer available to the producer. |
|
|
|
|
|
|
|
|
|
|
Certain bit patterns lock and unlock access to this store regionthese bits are referred to as semaphores. |
|
|
|
|
|
|
|
|
A similar type of mechanism is the test and set instruction, which tests a bit in memory. The bit is tested as if it were a condition code. The test and set instruction tests a value in memory, and then sets that value to one. The processor acts on the original value of the tested bit. If a test-and-set instruction is executed and processing cannot proceed because the tested bit indicates that a shared variable is not yet available, then the accessing process could enter a loop in which it continues to access the primitive until it gets the indication that the shared variable is set. This process of looping on a shared variable with a test-and-set type of instruction is called a spin lock. The spin lock idea can be incorporated into a single instruction, or can simply be programmed using the test and set instruction. |
|
|
|
|
|