Algorithm One
This algorithm demonstrates the main idea. Consider the simplest case, which involves two processes (or threads; for the purposes of this article, I'll use "processes" and "threads" interchageably). I'll call them Writer and Reader. Writer is transmitting one non-zero processor word of data to Reader and gets confirmation that data has been delivered successfully. This is done by writing this word and confirmation into shared memory.
In our case, it is important that shared memory which is used to transmit data between processes is aligned by the size of the processor word. Aligning guarantees that read/write operations to the main memory will be atomic. Atomic in this case is assumed to mean that if a value of a word initially was V1, and a process writes another value V2, then any other process or thread even without any synchronisation will read either the old value V1 or the new value V2.
The algorithm itself is the following:
- Initially the word in the shared memory has zero value.
- When Writer needs to transmit a non-zero processor word to Reader, it writes this word into shared memory.
- Reader continuously reads a processor word from the shared memory and compares it with zero. When it reads a non-zero value it means that data has arrived.
- Reader writes back to the same place in the shared memory a zero value to confirm that data has arrived.
- Writer reads shared memory words until it reads zero. This means that Writer has got confirmation from Reader that data was transmitted successfully.
This algorithm does not guarantee how fast data will be delivered from one process to another, or how fast confirmation will be delivered back. This is similar to sending a network packet from one computer to another and receiving a confirmation.