Section 7: Pipes #

Pipes are a shared memory buffer provided by the operating system that allow for multiple processes to communicate (share data) with each other. Pipes are implemented using file descriptors and allow for multiple processes to read and write data to this shared buffer.

Pipes are actually implemented using file descriptors! Interacting with pipes and files on disk use the same interface in file descriptors. For example, you can read from and write to pipes and files on disk the same way (using the same functions).

One way pipes differ from file descriptors is the location of their reads and writes. Reads and writes to a file interact with that file on hard disk. Reads and writes to a pipe interact with that pipe's memory buffer in the kernel, which is located in RAM and not the hard disk. In addition, some operations on file descriptors are not supported for pipes, such as the seek operation.

The writes in Mario's code occur when the child process writes the grandchildren PIDs to the pipe. The reads in Mario's code occur when the parent process reads the grandchild processes' PIDs from the shared pipe. Only the child process writes (so its read end of the pipe is closed), and only the parent process reads (so its write end of the pipe is closed).

These writing and reading operations could occur in any order, because there is no defined order of execution between multiple processes (even if they are parent and child processes).

Note that calls to read from an empty pipe will block until more data is written and calls to write to a full pipe will block until data is read. This blocking may influence the order of execution for reading and writing operations.

For future problems, we use the following order of reads and writes to the pipe:

• Child writes granchild 1 PID
• Child writes granchild 2 PID
• Child writes granchild 3 PID
• Child writes granchild 4 PID
• Child writes granchild 5 PID
• Parent reads PID
• Parent reads PID
• Parent reads PID
• Parent reads PID
• Parent reads PID

First the child writes (grand)child 1 PID to the pipe.

Then the child writes (grand)child 2 PID to the pipe.

Then the child writes (grand)child 3 PID to the pipe. Afterwards,

The child attempts to write the (grand)child 4 PID into the pipe, but the pipe is full, so this call to write will block until data is read from the pipe.

Since the child process is blocked, the next operation is the parent process reading data from the pipe. It reads the PID of (grand)child 1.

The parent process continues reading and reads the PID of (grand)child 2.

The parent process continues reading and reads the PID of (grand)child 3.

The parent process attempts to read again, but the pipe is empty. Since there is still another process (namely the child) that has a write end of the pipe open, the parent process' read call will block until more data is written to the pipe. It does not return 0 since it is possible another process could write data to the pipe.

At this point, the child has become unblocked and can write the (grand)child 4 PID to the pipe.

Finally, the child writes the (grand)child 5 PID to the pipe. Afterwards, the child closes its write end of the pipe.

Since more data has been written to the pipe, the parent process can unblock and begin reading the data. It starts by reading the PID of Child 4.

Next, the parent process reads the PID of Child 5.

The parent process attempts to read one more time. Since there is no data in the pipe and all write ends of the pipe have closed (the child process closed its write end), the call to read will return 0. No more reads and writes occur to the pipe.

Luigi will need a total of 6 pipes to allow for each of his three processes to communicate with each other using unidirectional pipes. Each process needs to be able to write to each of the other two processes, so 3 processes will each need 2 pipes. This setup will also allow each process to read from each other process.

The pipes needed are as follows:

• Pipe 1: Process 1 writes to Process 2
• Pipe 2: Process 1 writes to Process 3
• Pipe 3: Process 2 writes to Process 1
• Pipe 4: Process 2 writes to Process 3
• Pipe 5: Process 3 writes to Process 1
• Pipe 6: Process 3 writes to Process 2

To achieve this pipe setup, each process should close the following file descriptors:

• Process 1 closes the read end of Pipe 1 and Pipe 2, the write end of Pipe 3 and Pipe 5, and both read and write ends of Pipe 4 and Pipe 6
• Process 2 closes the read end of Pipe 3 and Pipe 4, the write end of Pipe 1 and Pipe 6, and both read and write ends of Pipe 2 and Pipe 5
• Process 3 closes the read end of Pipe 5 and Pipe 6, the write end of Pipe 2 and Pipe 4, and both read and write ends of Pipe 1 and Pipe 3

Luigi will need to drastically increase the number of pipes compared to the number of processes. If Luigi wants to use 4 processes, he will need a total of 12 pipes. If he uses an arbitrary number (such as n) child processes, there are $\dbinom{n}{2}$ ways to choose a pair of processes, and 2 pipes per pair (as each pipe is unidirectional), for a total of $2\cdot\dbinom{n}{2}=n(n-1)$ pipes. Luigi will need to close the vast majority of file descriptors; each process should only have access to n - 1 read ends (to read from each of the other pipes) and n - 1 write ends (to write to each of the other pipes). Determining which file descriptors to close can be done using a similar enumeration strategy to QUESTION 2A.