Inter-process communication

Why it exists

Two processes have separate address spaces on purpose: a bug or a crash in one cannot damage the other. The price is that they cannot simply share a variable. Yet processes often have to cooperate: to share information (a file or a database being used by several programs), to speed a computation up by dividing it, to keep a system modular (a web server, a database, a logger). Inter-process communication (IPC) is the set of mechanisms the operating system provides to let separate processes exchange data and coordinate, and the official syllabus names it as a topic of its own.

Prerequisites

You need the process model (address space, fork, process states) and system calls. The part on shared memory uses the ideas of race conditions, and the producer-consumer problem appears again in the classic synchronization problems.

Precise definitions

Independent and cooperating processes. A process is cooperating if it can affect or be affected by other processes.

The two basic models.

• Shared memory. The kernel maps a region into the address spaces of two or more processes. After the set-up, reading and writing it are ordinary memory accesses, with no system call and no kernel involvement; the processes themselves must make sure that they do not interfere (synchronization).
• Message passing. The kernel moves messages between processes. Two operations, send(message) and receive(message). Every message costs system calls and a copy, but the kernel does the synchronization.

Naming (message passing).

• Direct communication: each process names the other: send(P, m), receive(Q, m). A link belongs to exactly one pair.
• Indirect communication: messages go to and come from a mailbox (also called a port) that has an identity; several processes can use one mailbox: send(A, m), receive(A, m).

Synchronization of send and receive.

• Blocking (synchronous): send waits until the message is received (or, with a buffer, until it is accepted into the buffer); receive waits until a message is available.
• Non-blocking (asynchronous): send returns at once; receive returns a message or an indication that there is none.
• If both are blocking and there is no buffer, the exchange is a rendezvous.

Buffering. The queue of messages of a link has one of three capacities: zero (no buffer, the sender must wait for the receiver: a rendezvous), bounded (a finite capacity; the sender blocks when the queue is full), unbounded (the sender never blocks).

Pipes. An ordinary (anonymous) pipe is a one-way channel with a read end and a write end, created with pipe(), and usually shared by fork: parent and child. For two-way communication two pipes are needed. A named pipe (FIFO) has a name in the file system, so unrelated processes can use it; on UNIX it is one-way as well.

Signals. A small asynchronous notification sent to a process (a number and nothing else). Sockets. The two ends of a communication channel, usable between processes of one machine (UNIX domain sockets) or across a network (see the socket API).

How it works

Message passing: blocking send and receive

A producer makes messages, a consumer processes them, the mailbox holds at most two. While the mailbox has room the producer runs ahead of the consumer; when it is full, send does not return and the producer is blocked: the operating system puts it to sleep, and it uses no CPU. The consumer blocks in receive when the mailbox is empty (at tick 0, nothing has been produced yet). A mailbox is therefore also a means of synchronization: blocking operations make the processes wait for each other without a lock or a semaphore in the user's program.

What the capacity changes

With a slow consumer, a larger mailbox lets the producer finish earlier and block less, but the time at which everything is done does not move: it is 25 ticks for every capacity, set by the slow side. With a rendezvous (capacity 0) the producer is blocked most of the time, it must wait for the consumer at every message. With a slow producer the consumer waits for the same 17 ticks whatever the capacity, and no queue ever builds up in the mailbox (the consumer takes each message out at once). A buffer smooths out short-term differences in speed; it cannot help when one side is always slower.

Pipes

A pipe is a buffer inside the kernel, written through one descriptor and read through another. The program writes a message through a pipe from a parent to its child. The child reads until read returns 0.

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>
 
int main(void) {
    int fd[2];
    if (pipe(fd) != 0) return 1;
    pid_t pid = fork();
    if (pid < 0) return 1;
    if (pid == 0) {                          /* child: the reader */
        close(fd[1]);                        /* it never writes, so it closes the write end */
        char buf[16];
        ssize_t n, total = 0;
        while ((n = read(fd[0], buf, sizeof buf)) > 0) total += n;
        printf("child: read %zd bytes, then read returned %zd (end of file)\n", total, n);
        close(fd[0]);
        return 0;
    }
    close(fd[0]);                            /* parent: the writer */
    const char *msg = "hello through the pipe";
    if (write(fd[1], msg, strlen(msg)) < 0) return 1;
    close(fd[1]);                            /* the last write end is closed: the reader will see end of file */
    waitpid(pid, NULL, 0);
    printf("parent: wrote %zu bytes\n", strlen(msg));
    return 0;
}

child: read 22 bytes, then read returned 0 (end of file)
parent: wrote 22 bytes

The rules that follow from this:

• read on an empty pipe blocks as long as some process still has a write end open; it returns 0 (end of file) only when all write ends are closed. This is why the child above closes its copy of the write end: if it did not, it would hold the pipe open itself and wait for ever.
• write to a pipe whose read ends are all closed raises the signal SIGPIPE (the call fails with the error EPIPE if the signal is ignored).
• write to a full pipe blocks. POSIX guarantees that a write of at most PIPE_BUF bytes (at least 512, 4096 on Linux) is not interleaved with writes of other processes.
• A pipe carries a stream of bytes: the boundaries between writes are not kept.

Shared memory

After fork, the child has a copy of every ordinary variable: a change in one process is not seen by the other. A page mapped with MAP_SHARED is the same physical memory in both:

#define _DEFAULT_SOURCE 1
#include <stdio.h>
#include <sys/mman.h>
#include <sys/wait.h>
#include <unistd.h>
 
#ifndef MAP_ANONYMOUS
#define MAP_ANONYMOUS MAP_ANON
#endif
 
int ordinary = 1;
 
int main(void) {
    int *shared = mmap(NULL, sizeof *shared, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANONYMOUS, -1, 0);
    if (shared == MAP_FAILED) return 1;
    *shared = 1;
    pid_t pid = fork();
    if (pid < 0) return 1;
    if (pid == 0) {
        ordinary = 100;                      /* changes the child's own copy */
        *shared = 100;                       /* changes the page both processes see */
        return 0;
    }
    waitpid(pid, NULL, 0);
    printf("ordinary variable: %d\nshared page: %d\n", ordinary, *shared);
    munmap(shared, sizeof *shared);
    return 0;
}

ordinary variable: 1
shared page: 100

Shared memory is the fastest mechanism once it is set up, because data are not copied through the kernel; but nothing coordinates the processes, so they have to do it themselves. The classic use is the bounded buffer: a ring of $N$ slots, an index in where the producer writes and an index out from which the consumer reads. With only these two variables the buffer is full when $(in + 1) \bmod N = out$ and empty when $in = out$, so it holds at most $N - 1$ items (one slot stays free to tell "full" from "empty"). Many textbooks add a shared counter count to use all $N$ slots; the exhaustive check shows what that costs:

For one producer and one consumer, the version with only in and out is correct over all interleavings (and never holds more than $N - 1$ items). With the counter, a violation is reachable, and so is a stuck state. The reason is the lost update: count++ and count-- are each three instructions (load, add, store); if the two interleave, one update overwrites the other. This is the shortest interleaving that ends in a failure:

(The in/out solution assumes that memory operations become visible in program order. Real processors can reorder them, so real code uses atomic operations or memory barriers; the model here assumes sequential consistency.) With more than one producer or consumer even the in/out version needs mutual exclusion; the semaphore solution of the bounded buffer uses three semaphores for that.

Signals

A signal is the cheapest form of IPC and carries almost no information: the number of the signal. The process installs a handler; the kernel runs it when the signal arrives. In this program the parent sends a signal to its child, which waits for it with sigsuspend. The signal is blocked before the fork, so it cannot arrive before the child is ready:

#define _POSIX_C_SOURCE 200809L
#include <signal.h>
#include <stdio.h>
#include <string.h>
#include <sys/wait.h>
#include <unistd.h>
 
static volatile sig_atomic_t got = 0;
static void handler(int sig) { (void)sig; got = 1; }
 
int main(void) {
    sigset_t block, old;
    sigemptyset(&block);
    sigaddset(&block, SIGUSR1);
    sigprocmask(SIG_BLOCK, &block, &old);    /* blocked in the parent and inherited by the child */
    struct sigaction sa;
    memset(&sa, 0, sizeof sa);
    sa.sa_handler = handler;
    sigemptyset(&sa.sa_mask);
    sigaction(SIGUSR1, &sa, NULL);
    pid_t pid = fork();
    if (pid < 0) return 1;
    if (pid == 0) {
        while (!got) sigsuspend(&old);       /* unblocks the signal and sleeps, in one atomic step */
        printf("child: the signal arrived\n");
        return 0;
    }
    kill(pid, SIGUSR1);                      /* may be sent before the child sleeps: it stays pending */
    waitpid(pid, NULL, 0);
    printf("parent: child has finished\n");
    return 0;
}

child: the signal arrived
parent: child has finished

Sockets and the two-way channel

A pipe is one-way. A connected pair of UNIX-domain sockets is two-way: either end can read and write. The same idea, with network addresses instead of a local pair, is the socket API.

#define _POSIX_C_SOURCE 200809L
#include <stdio.h>
#include <sys/socket.h>
#include <sys/wait.h>
#include <unistd.h>
 
static int read_all(int fd, char *buf, int n) {
    int got = 0;
    while (got < n) {
        ssize_t r = read(fd, buf + got, (size_t)(n - got));
        if (r <= 0) return -1;
        got += (int)r;
    }
    return got;
}
 
int main(void) {
    int sv[2];
    if (socketpair(AF_UNIX, SOCK_STREAM, 0, sv) != 0) return 1;
    pid_t pid = fork();
    if (pid < 0) return 1;
    if (pid == 0) {                          /* child: answers "ping" with "pong" */
        close(sv[0]);
        char buf[4];
        if (read_all(sv[1], buf, 4) < 0) return 1;
        if (write(sv[1], "pong", 4) != 4) return 1;
        close(sv[1]);
        return 0;
    }
    close(sv[1]);
    if (write(sv[0], "ping", 4) != 4) return 1;
    char reply[5] = {0};
    if (read_all(sv[0], reply, 4) < 0) return 1;
    waitpid(pid, NULL, 0);
    printf("parent got: %s\n", reply);
    return 0;
}

parent got: pong

The mechanisms compared (quoted from the textbooks, not computed)

Worked examples

Cheat box

Traps and GATE patterns

Connections

IPC between processes is the counterpart of the sharing that threads get for free: threads share an address space, so they communicate through variables and need critical sections; processes must ask the kernel. The blocking behaviour of send, receive and pipes is the same idea as the semaphore: the process is moved to the waiting state of the process life cycle until the other side acts. The buffering of I/O between a device and a program is the same producer-consumer structure.

PYQs

Self-check

Revision card

References