COMS W4118 Operating Systems I

Interprocess communication in UNIX

Pipes

Unnamed Pipe

#include <unistd.h>

int pipe(int fd[2]);
    // Returns: 0 if OK, –1 on error

After calling pipe():

Figure 15.2, APUE

fd[0] is opened for reading, fd[1] is opening for writing

After calling pipe() and then fork():

Figure 15.3, APUE

Recall from L03-file-io: when forking, all open file descriptors are “dup’d”. Child gets a reference to the read and write ends of the pipe.

Diagram is slightly misleading: pipes are only half-duplex (one-way communication). You can only do one of the following:

You can’t use pipe as a full-duplex (two-way communication) channel, e.g.:

Since pipe is only half-duplex, close() unused ends of pipe after forking depending on who you want to read/write. e.g., where child reads and parent writes:

int fd[2];
pipe(fd);

if (fork() == 0) {
    close(fd[1]);  // close unused write end
    // ...
    read(fd[0], ...);
} else {
    close(fd[0]);  // close unused read end
    // ...
    write(fd[1], ...)
}

Note dependence on fork() for sharing ends of pipe via dup’d file descriptors. This form of IPC only works for related processes (e.g. parent-child)

connect2 demo: how shell stitches together two processes when you run a pipeline: p1 | p2.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/wait.h>

int main(int argc, char **argv)
{
    int fd[2];
    pid_t pid1, pid2;

    // Split arguments ["cmd1", ..., "--", "cmd2", ...] into
    //                 ["cmd1", ...] and ["cmd2", ...]

    char **argv1 = argv + 1; // argv for the first command
    char **argv2;            // argv for the second command

    for (argv2 = argv1; *argv2; argv2++) {
        if (strcmp(*argv2, "--") == 0) {
            *argv2++ = NULL;
            break;
        }
    }
    if (*argv1 == NULL || *argv2 == NULL) {
        fprintf(stderr, "%s\n", "separate two commands with --");
        exit(1);
    }

    pipe(fd);

    if ((pid1 = fork()) == 0) {
        close(fd[0]);   // Close read end of pipe
        dup2(fd[1], 1); // Redirect stdout to write end of pipe
        close(fd[1]);   // stdout already writes to pipe, close spare fd
        execvp(*argv1, argv1);
        // Unreachable
    }

    if ((pid2 = fork()) == 0) {
        close(fd[1]);   // Close write end of pipe
        dup2(fd[0], 0); // Redirect stdin from read end of pipe
        close(fd[0]);   // stdin already reads from pipe, close spare fd
        execvp(*argv2, argv2);
        // Unreachable
    }

    // Parent does not need either end of the pipe
    close(fd[0]);
    close(fd[1]); 

    waitpid(pid1, NULL, 0);
    waitpid(pid2, NULL, 0);
    return 0;
}

Named pipe (FIFO)

#include <sys/stat.h>

int mkfifo(const char *path, mode_t mode);
    // Returns: 0 if OK, –1 on error

mkfifo(): create a new named pipe on the filesystem

Afterwards, use file I/O syscalls to interact with special pipe file. Shares semantics with unnamed pipe – still half-duplex.

Unlike unnamed pipe, FIFO can be used for IPC between unrelated processes because they can use the filesystem as a rendezvous point. Both processes just need to know the path to the FIFO.

POSIX Semaphores

Semaphore Theory

Semaphore: fundamentally, just an integer value mainly manipulated by two methods.

Increment: increase the integer

Decrement: wait until value > 0, then decrease the integer value

Initial value affects semaphore semantics!

Binary semaphore (a.k.a. lock): initial value is 1. Protects one resource.

  1. Before acquiring resource, run sem_wait(). Value decremented to 0.
  2. Use resource
  3. Run sem_post() to release the resource. Value incremented to 1.

Resource is limited to 1 user at a time. Concurrent access while resource is locked sees value of 0, blocks, and is woken up when value is incremented back to 1.

Counting semaphore: initial value is N > 1. Protects N resources.

  1. Before acquiring resource, run sem_wait(). Value is decremented by 1.
  2. Use resource
  3. Run sem_post() to release the resource. Value incremented by 1.

Since there are N resources, concurrent access is only blocked after N concurrent accesses (i.e. when the value hits 0). N + 1th concurrent access sees value of 0, blocks, is woken up when the value becomes positive again (i.e. some users posted the semaphore).

Ordering semaphore: take advantage of blocking semantic to implement “events”. e.g.:

sem = 0  // initial value is 0

P1: 1 -> 2 -> sem_wait() -> 4 -> 5

P2: A -> B -> C -> D -> sem_post()

P1 completes tasks 1-2 then blocks until P2 completes tasks A-D before moving on to tasks 4 and 5. P1 has to wait until P2 increments the semaphore value.

POSIX API

Initializing and destroying unnamed POSIX semaphores:

#include <semaphore.h>

int sem_init(sem_t *sem, int pshared, unsigned int value);
        // Returns: 0 if OK, –1 on error

int sem_destroy(sem_t *sem);
        // Returns: 0 if OK, –1 on error

sem_t *sem: pointer to shared semaphore object. Declared by user and initialized/destroyed by API.

int pshared: If semaphore is meant to be shared by processes, pass in non-zero value. Otherwise, (e.g. threads), pass in 0.

unsigned int value: Initial value for the semaphore

If unnammed semaphore is to be shared by related processes, where should semaphore be declared?

Creating, opening, closing, and removing named POSIX semaphores:

#include <semaphore.h>

sem_t *sem_open(const char *name, int oflag, ...
                /* mode_t mode, unsigned int value  */ );
        // Returns: Pointer to semaphore if OK, SEM_FAILED on error

int sem_close(sem_t *sem);
        // Returns: 0 if OK, –1 on error

int sem_unlink(const char *name);
        // Returns: 0 if OK, –1 on error

Similar semantics to file API syscalls (recall L03-file-io).

Named semaphores meant to be used by unrelated processes – use semaphore name as “redezvous” point.

Decrement the value of semaphores:

#include <semaphore.h>
#include <time.h>

int sem_trywait(sem_t *sem);
int sem_wait(sem_t *sem);
        // Both return: 0 if OK, –1 on error

int sem_timedwait(sem_t *restrict sem,
                    const struct timespec *restrict tsptr);
        // Returns: 0 if OK, –1 on error

Blocking semantics:

Increment the value of semaphores:

#include <semaphore.h>

int sem_post(sem_t *sem);
        // Returns: 0 if OK, –1 on error

Memory-mapped I/O

Mapping a file into memory

Using the file I/O syscalls can be annoying. Consider the example of opening a file with O_RDWR:

Alternative: map region of file into your virtual address space! Figure 14.26, APUE

Memory-mapped region is backed by disk. That is, updates to the memory-mapped region go to memory first, then (eventually) flushed to disk

Furthermore, mappings can be private or shared.

#include <sys/mman.h>

void *mmap(void *addr, size_t len, int prot, int flag, int fd, off_t off);
        // Returns: starting address of mapped region if OK, MAP_FAILED on error

Note-worthy parameters:

Mapping a file with MAP_SHARED is a form of IPC for unrelated processes

Anonymous memory mappings and sharing mappings

Sometimes we want to map memory that is not backed by a file (kinda like malloc()):

However, mapping visibility makes this more powerful than malloc()! Consider a process that creates an anonymous memory and then fork()s. We know that child will inherit all of the parent’s memory mappings, but…

Mapping some anonymous memory with MAP_SHARED is a form of IPC for related processes

Example: counter.c – note that unnamed semaphore is placed in shared memory so both parent and child have access to it.

#include <stdio.h>
#include <unistd.h>
#include <assert.h>
#include <semaphore.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/wait.h>

#define LOOPS 2059

struct counter {
    sem_t sem;
    int cnt;
};

static struct counter *counter = NULL;

static void inc_loop() {
    for (int i = 0; i < LOOPS; i++) {
        sem_wait(&counter->sem);

        // Not an atomic operation, needs lock!
        // 1) Load counter->cnt into tmp
        // 2) Increment tmp
        // 3) Store tmp into counter->cnt
        counter->cnt++;

        sem_post(&counter->sem);
    }
}

int main(int argc, char **argv) {
    // Create a shared anonymous memory mapping, set global pointer to it
    counter = mmap(/*addr=*/NULL, sizeof(struct counter),
                   // Region is readable and writable
                   PROT_READ | PROT_WRITE,
                   // Want to share anonymous mapping with forked child
                   MAP_SHARED | MAP_ANON,
                   /*fd=*/-1,  // No associated file
                   /*offset=*/0);
    assert(counter != MAP_FAILED);

    // Mapping is already zero-initialized.
    assert(counter->cnt == 0);

    sem_init(&counter->sem, /*pshared=*/1, /*value=*/1);

    pid_t pid;
    if ((pid = fork()) == 0) {
        inc_loop();
        return 0;
    }

    inc_loop();
    waitpid(pid, NULL, 0);

    printf("Total count: %d, Expected: %d\n", counter->cnt, LOOPS * 2);

    sem_destroy(&counter->sem);
    assert(munmap(counter, sizeof(struct counter)) == 0);
    return 0;
}

XSI IPC

Skim briefly just to appreciate how great POSIX IPC is :^)

They share common naming and interface scheme:

And they all suck…

  1. Hard to clean-up because there is no reference counting

    • pipes get automatically removed when last process terminates
    • data left in a FIFO is removed when last process terminates

  2. Hard to use

    • complex and inelegant interfaces that don’t fit into UNIX file system paradigm
    • stupid naming scheme: IPC identifiers, keys, and project IDs – are you serious?

They have been widely used for lack of alternatives. Fortunately we do have alternatives these days:

Last updated: 2023-02-02