Multiprocessor or multitasking systems need a mechanism to coordinate inter-processor or inter-task communication.  In shared memory architectures the lowest level parts of this mechanism are usually called semaphores.  These can be used to request a resource such as I/O.  Typically this is a memory location that is tested to see if the resource is free and then set to lock out other actors.  Unfortunately an interrupt or separate processor might intervene between the test and set.  Some, but not all, processors have implemented test-and-set instructions that cannot be interrupted.  This protects against other tasks but the test-and-set instruction must also work with dual port memory and cache systems to hold off other processors.  The main problem is allowing multiple actors simultaneous write access to the same memory location.  Various solutions have been tried.  Some years ago, the UNOS operating system developed by Charles River Data Systems implemented eventcounts for low level signaling.  These 32 bit objects could only be incremented, preventing some of the problems with test-and-set semaphores.

For real-time industrial control a much more robust solution is necessary that satisfies a set of requirements.  1. Semaphores must be deterministic without the possibility of race conditions or ambiguity.  2. The solution must not require special processor features to allow portability.  3. Each semaphore is an entire smallest memory object that is written with a single memory cycle, usually an 8 bit byte or alternately 16 bit word for pure 16 bit memories.  4. Semaphores are provided in Query (Q) / Response (R) pairs. 5. Only one client actor may write a Q semaphore and only a single different server actor may write the associated R semaphore.  6. Each resource, be it a memory buffer, I/O, master state machine, or other is under the control of a single actor.  7. Enough distinct Q/R pairs are allocated to each client/server channel to unambiguously control all transactions.  8. At system configuration, and later as needed, semaphore pairs are assigned to client/server channels to establish the required communication channels.  9. Different processors or tasks may be servers for different resources.  10. Query and Response actions are performed in a single memory cycle.

As an example, when a channel is inactive, Qa and Ra are equal.  The specific value is irrelevant.  The client compares Qa and Ra.  If they are equal, the client may place a Query to request access to a resource such as a shared memory buffer by writing the logical complement of Ra into Qa.  When the resource becomes available the server copies Qa into Ra which signals the client that the buffer is available for reading and writing.  When the client finishes its data/control access it sends a query to Qb by writing the complement of Rb to it.  This signals the server that the client is finished with the buffer.  The server copies the Qb to the respective Rb to signal that it has regained control of the resource.  Note that this last is useful as otherwise the client might think the buffer is already requestable since Qa = Ra.  Bidirectional control transmissions may be passed from the server back to the client using additional Qc/Rc, Qn/Rn, … semaphores where Q is the server side.

Alternately, the above transaction could be

Client: [Qa = not Ra] ->

Server: [Qc = not Rc] ->

Client: Access …  -> [Rc = Qc] ->

Server: [Ra = Qa]

Note that in either case, the source of the query always sets the semaphore pair to a different value and the responder to the query always sets the semaphore pair to the same value.  In other words, an actor is not allowed to change its mind.  An abort request must be handled by a separate Q/R pair.  This is absolutely necessary for deterministic behavior.

This strategy works well in main memory for separate tasks and threads, shared memory for multiprocessors, and in hardware for handshaking to control communication buffers.

Please leave any comments using the post in my comments category.