pipe(); semaphore in distributed systems

Why do we need pipe()?

pipe() is a UNIX system call that creates a unidirectional communication channel (a kernel buffer) between processes. It is needed for inter-process communication: it lets the output of one process become the input of another (as in ls | wc), usually between a parent and its child created by fork. It also synchronizes the processes, since a reader blocks on an empty pipe and a writer blocks on a full one.

int fd[2];
pipe(fd);                 /* fd[0] = read end, fd[1] = write end */
if (fork() == 0) { close(fd[0]); write(fd[1], "hello", 6); }
else             { close(fd[1]); read(fd[0], buf, 6); }

Semaphore and its operations

A semaphore is an integer variable (introduced by Dijkstra) that can be accessed only through two atomic operations, down (P / wait) and up (V / signal). It is used for mutual exclusion and for synchronization of processes.

down(S):  if (S > 0) S = S - 1;
          else block the calling process (put it on S's queue);
up(S):    if (some process is blocked on S) wake up one of them;
          else S = S + 1;

Both operations are indivisible: once started, no other process can access S until the operation finishes or blocks.

Initialised to 1 it acts as a mutex; initialised to n it counts n identical resources. Typical uses are mutual exclusion (down(mutex) ... up(mutex)) and synchronization (down(full), up(empty) in producer-consumer).

Can semaphores be used in a distributed system?

Not directly, but they can be emulated. A normal semaphore is a shared variable whose down and up are made atomic by the OS of a single machine (by disabling interrupts, TSL or kernel locking). In a distributed system the computers have no shared memory and no common clock, and communicate only by messages with delays and failures, so there is no single place where atomic access can be guaranteed.

They can be implemented in two ways:

• Central semaphore server: one process owns the semaphore, and other machines send down/up request messages and wait for the reply. It is simple, but the server is a single point of failure and a bottleneck.
• Distributed algorithms (message-based mutual exclusion, e.g. Ricart-Agrawala, token ring or Lamport's algorithm based on logical clocks) that give the same effect.

So other mechanisms such as message passing, RPC and distributed mutual exclusion algorithms are used in practice.