PIDs, fork, _exit, and waitpid

In a POSIX system, fork, _exit, kill, and waitpid are fundamental system calls for creating and managing processes. They all work with process IDs (PIDs) to identify processes.

Process IDs

Every process in a POSIX system has a unique process ID—the PID. The PID is an integer assigned to the process when it is created.

Unlike file descriptors, new PIDs do not use the lowest-available integer. Instead, the kernel keeps track of the highest PID assigned so far, and assigns the next available PID to the next process created. Eventually the next-available PID will wrap around to 1, and the kernel will start reusing PIDs (while taking care not to assign to a PID that is still in use).

By convention, the PID of the first process created in a POSIX system is 1, and is referred to as the “startup” process. Historically, this process was called init, although on Linux these days it is systemd, and on a Mac it is launchd. All subsequent processes are created by forking from existing processes, and will thus be numbered from 2 and up.

Range of PID Values

Human beings often need to refer to processes by their PID, so a 64-bit number like 13532322497857280783 or even a 32-bit value like 3123456789 is going to feel like a bit of a mouthful. In early Unix systems, PIDs were numbers with at most four digits, so they were easy to remember and type; macOS increased the maximum PID to five digits, and in Linux the maximum PID became a kernel-configuration setting that defaults to 4194304.

In each of these cases, however, the range of possible PID values is larger than the number of processes that can be created on the actual system. This decision was made to avoid reusing PIDs too quickly, which could lead to confusion if a process finished and a new process was then created with the same PID, especially in a world where we have system calls such as kill that can target processes by PID—we don't want to accidentally kill the wrong process!

Process Table Design

From these details, we can see that a direct array of struct proc objects indexed by PID is not a good design for a process table. The table would be far too large, and most of the entries would be empty.

For us, with OS/161, the simplest and most basic choice would be to use a fixed-size array indexed by PID and not worry too much about premature reuse of PIDs. But a better solution might be to use tagged indexes again.

Let's take a look at a plausible design for a process table.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

/* Constants */
#define ARRAY_SIZE 128
#define GEN_BITS 6
#define INDEX_BITS 7
#define MAX_PID ((1 << (GEN_BITS + INDEX_BITS)) - 1)

/* Macros to pack and unpack PIDs */
#define PID_TO_INDEX(pid) ((pid) & ((1 << INDEX_BITS) - 1))
#define PID_TO_GEN(pid) ((pid) >> INDEX_BITS)
#define MAKE_PID(gen, index) (((gen) << INDEX_BITS) | (index))

struct procinfo {
        const char *name; /* In reality, we'd store other information here */
};

struct pid_entry {
        /* Information we need to make the table work */
        unsigned short generation;
        bool is_free;

        /* Information we want to store */
        struct procinfo info;
};

struct pid_array {
        struct pid_entry processes[ARRAY_SIZE];
        int last_allocated;
};

/* We only have the one, so it's fine to make it global */
static struct pid_array pid_array;

/* Allocate a PID for a process with the given name. */
unsigned int
pid_alloc(const char *name)
{
        int start = pid_array.last_allocated + 1;
        for (int i = 0; i < ARRAY_SIZE; i++) {
                int index = (start + i) % ARRAY_SIZE;
                if (pid_array.processes[index].is_free) {
                        pid_array.processes[index].is_free = false;
                        unsigned int pid = MAKE_PID(
                            pid_array.processes[index].generation, index);
                        pid_array.last_allocated = index;

                        pid_array.processes[index].info.name = name;
                        return pid;
                }
        }
        return MAX_PID + 1; // Error: no free PIDs
}

/* Free a PID. */
void
pid_free(unsigned int pid)
{
        unsigned int index = PID_TO_INDEX(pid);
        unsigned int generation = PID_TO_GEN(pid);

        if (index < ARRAY_SIZE &&
            pid_array.processes[index].generation == generation &&
            !pid_array.processes[index].is_free) {
                pid_array.processes[index].is_free = true;
                pid_array.processes[index].generation =
                    (generation + 1) & ((1 << GEN_BITS) - 1);
        }
}

/* Get the process information for a PID. */
struct procinfo *
pid_to_info(unsigned int pid)
{
        unsigned int index = PID_TO_INDEX(pid);
        unsigned int generation = PID_TO_GEN(pid);

        if (index < ARRAY_SIZE &&
            pid_array.processes[index].generation == generation &&
            !pid_array.processes[index].is_free) {
                return &pid_array.processes[index].info;
        }
        return NULL;
}

/* Initialize the PID array. */
void
pid_array_bootstrap(void)
{
        for (int i = 0; i < ARRAY_SIZE; i++) {
                pid_array.processes[i].is_free = true;
                pid_array.processes[i].generation = 0;
        }
        pid_array.last_allocated = 0;
}

/* Test the PID allocator. */
int
main(void)
{
        pid_array_bootstrap();

        printf("Allocating three PIDs\n");
        unsigned int pid1 = pid_alloc("Alice");
        unsigned int pid2 = pid_alloc("Betty");
        unsigned int pid3 = pid_alloc("Chloe");

        printf("\nProcess names:\n");
        printf("PID %u: %s\n", pid1, pid_to_info(pid1)->name);
        printf("PID %u: %s\n", pid2, pid_to_info(pid2)->name);
        printf("PID %u: %s\n", pid3, pid_to_info(pid3)->name);

        pid_free(pid2);
        printf("\nFreed PID %u\n", pid2);

        /* Churn through 125 more PIDs to get to where we finally reuse an
         * array slot, but not a PID. */
        printf("\nChurning through more PIDs\n");
        for (int i = 0; i < 125; i++) {
                unsigned int pid = pid_alloc("Zarek");
                pid_free(pid);
        }

        unsigned int pid4 = pid_alloc("Diane");
        printf("Allocated new process with PID: %u\n", pid4);
        printf("PID %u: %s (actually in slot %u)\n", pid4,
               pid_to_info(pid4)->name, PID_TO_INDEX(pid4));

        pid_free(pid1);
        printf("\nFreed PID %u\n", pid1);

        /* Churn through 127+62*128 = 8062 more PIDs, calculated get to where
         * we finally reuse PID 1 */
        printf("\nChurning through *LOTS* more PIDs\n");
        for (int i = 0; i < 8063; i++) {
                unsigned int pid = pid_alloc("Yanni");
                pid_free(pid);
        }

        unsigned int pid5 = pid_alloc("Ellen");
        printf("Allocated new process with PID: %u\n", pid5);
        printf("PID %u: %s\n", pid5, pid_to_info(pid5)->name);

        return 0;
}

This code defines a simple PID allocator that uses a fixed-size array of struct pid_entry objects to keep track of PIDs.

• The pid_alloc function allocates a PID for a process with a given name. It searches for the next free slot in the array, which becomes the index, and then the PID is made by combining the index with the next generation number. The generation number is used to avoid reusing PIDs too quickly.
• The pid_free function frees a PID, marking the slot as free and incrementing the generation.
• The pid_to_info function returns the process information for a given PID.

The main function demonstrates the allocator in action, allocating and freeing PIDs and showing that the allocator can handle reusing PIDs.

• Try this code in Online GDB

In this code, MAX_PID is 8191, which is (one less than) the highest power of two that is still a four-digit number. If we preferred five-digit PIDs, we could set GEN_BITS to 9 and keep INDEX_BITS at 7 for 16 bits total (65536 possible PIDs).

If you run it, you'll see

Allocating three PIDs

Process names:
PID 1: Alice
PID 2: Betty
PID 3: Chloe

Freed PID 2

Churning through more PIDs
Allocated new process with PID: 130
PID 130: Diane (actually in slot 2)

Freed PID 1

Churning through *LOTS* more PIDs
Allocated new process with PID: 1

This output demonstrates that the allocator can handle reusing both slots in the array and, eventually, PIDs themselves.

fork

The fork system call creates a new process that is an exact copy of the calling process. The new process is called the child process, and the calling process is the parent process.

The fork call needs to allocate a new PID (and a new underlying struct proc) and then duplicate the calling process's

• Address space, including all memory mappings and the contents of those mappings.
• File descriptors (but share the underlying open file objects).
• Signal handing state. (Not relevant for OS/161.)
• Current working directory.

and then set the child process's PID to the new PID.

The child process is started in the same state as the parent process, with the same program counter, stack pointer, and so on. The only difference is that the return value of fork is 0 in the child process, and the child process's PID in the parent process.

Fork Fun!

// One process here...
for (int i = 0; i < 10; i++) {
    fork();
}
// ...how many here?

_exit

The _exit system call terminates the calling process and records an exit status. The process's resources are released, and the process is removed from the process table.

After the process has exited, although the process is no longer running, something might still want to know things about it; in particular, its exit status. So the process-table entry has to be kept around until its parent calls waitpid to get the exit status.

waitpid

The waitpid system call waits for a child process to exit and returns the child's exit status. If the child has already exited, waitpid returns immediately. If the child has not exited, waitpid blocks until the child exits (unless the WNOHANG option is used, in which case waitpid returns immediately).

When a process has exited but we've kept the process-table entry around, the process is called a zombie. Zombies are not running (they're “dead”), but they still have an entry in the process table. Because zombie processes consume process-table slots, it's considered bad form to leave zombies around for too long.

In POSIX systems, we can either give waitpid a specific PID to wait for, or we can use the special value -1 to wait for any child process. You are only required to implement the former in OS/161 for the homework.

(When logged in, completion status appears here.)