Homework — Pipes & FIFOs

All the sources are available in the part-3 tarball.

The C files are located in directory part-3/homework-pipe-fifo/material/.

The general specifications of the POSIX functions are available at OpenGroup website.

Overview

In this homework, we study pipes and fifos.

After a short course and few exercises to learn how to handle pipes and fifos, we extend the fork-join model described in process lab.

Pipes and FIFOs

Pipes are Unix implementations of shared data based on the producer/consumer model. This model was described in the synchonisation TD and the synchronisation homework.

Access to a file declared as a "pipe" is managed by Unix according to the producer/consumer model. read and write on this file are similar to consume and produce respectively, but read operations are destructive. A read byte is removed from the tube. As for a consume operation, a read operation is blocking if the tube is empty. As for a produce operation, a write operation is blocking if the tube is full.

Pipe

pipe() creates a pipe, a unidirectional data channel that can be used for interprocess communication.

int pipe(int pipefd[2]);

The array pipefd is used to return two file descriptors referring to the ends of the pipe. pipefd[0] refers to the read end of the pipe. pipefd[1] refers to the write end of the pipe. 

int p[2];
int rv = pipe(p[2]);
assert(rv == 0);
while (read(p[0], ..., ...)>0){};

FIFO

A FIFO or a named pipe is similar to a pipe, except that it has a filename entered into the filesystem instead of being an anonymous communications channel. With this filename, any process can open the FIFO for reading or writing. mkfifo() creates a FIFO file with a mode access permissions.

int mkfifo(const char *pathname, mode_t mode);

Then, processes have to use open() in read or write mode to perform reading or writing operations respectively.

int rv = mkfifo("fifo", 0666);
assert(rv == 0);
int fd = open("fifo", O_RDONLY);
assert(0 <= fd);
while (read(fd, ..., ...)>0){};

Pipe in Shell

The symbol "|" designates a tube into which the output of the process on its left arrives, and from which the process on its right takes its input. Try the following shell commands :

who
who | grep $USERNAME
ls -rt
ls -rt | sort
ps aux
ps aux | wc -l
  • who displays who is logged in.
  • grep searches for lines that match one or more patterns.
  • sort sorts text files by lines.
  • wc displays the number of lines (-l), words (-w), and bytes (-c).

To illustrate that the pipe implements the producer / consumer model. Try the following :

for i in 1 2 3 4; do
ls
sleep 2
done | grep c

The output of ls is filtered four times by grep each time after 2 seconds of delay.

Pipes in C

In this exercise, we want to implement a ping pong mechanism.

  1. Complete the pipe-ping-pong.c file. The parent process creates two pipes, ping and pong. The parent writes a value into ping, and the child reads it from ping, it doubles this value and adds 1 and then writes it into pong. The parent reads the new value from pong, it doubles it and adds 1 and then sends it again to child. This is done for 3 times by the parent.
  2. Compiles and run it. You should get something like:
> ./pipe-ping-pong
15017 send ping 7
15018 recv ping 7
15018 send pong 15
15017 recv pong 15
15017 send ping 31
15018 recv ping 31
15018 send pong 63
15017 recv pong 63
15017 send ping 127
15018 recv ping 127
15018 send pong 255
15017 recv pong 255

Model fork-join with communication

[tp-proc][tp-proc-thread.md]

This part assumes that you have worked on the fork-join execution model presented in the [processor lab][tp-proc]. The general idea of this model is to solve a problem by dividing it into smaller, identical sub-problems (Fork part), then solve the smallest version of the problem in parallel, and finally combine the results (Join part). In the [processor lab][tp-proc], the child received the data to be processed (its identifier) as stored in its parent's copy of memory. Here, we want to communicate the data to be processed via pipes.

We give the code for pipe-fork-join.c, a modified version of processor-fork-join.c that deals specifically with inter-process communication. In this code, the parent process, called the master, creates max_slaves child processes, called slaves. The master sends each slave R, a specific quantity of resources (an integer value). With its R resources, a slave produces G, a quantity of goods, according to the following formula G = R - 1, and sends the master G, the quantity of goods produced. When a slave produces 0 goods, it completes.

After creating max_slaves slave processes, the master creates max_slaves input pipes to send resources and max_slaves output pipes to receive goods. Slaves use the other end of the input pipes to receive resources and the other end of the output pipes to send goods.

Not so parallel fork-join execution

We use the macros FD_CLR, FD_ISSET, FD_SET and FD_ZERO to manipulate the fd_set file descriptor bit-set.

  • FD_CLR(fd, &fdset)
    • Clears the bit for the file descriptor fd in the file descriptor set fdset.
  • FD_ISSET(fd, &fdset)
    • Returns a non-zero value if the bit for the file descriptor fd is set in the file descriptor set pointed to by fdset, and 0 otherwise.
  • FD_SET(fd, &fdset)
    • Sets the bit for the file descriptor fd in the file descriptor set fdset.
  • FD_ZERO(&fdset)
    • Initialises the file descriptor set fdset to have zero bits for all file descriptors.
  1. Complete the code of pipe-fork-join.c to enforce the communication process described above.
  2. Run and test your program. You should obtain the following display:
> ./pipe-fork-join 4
[ 0] master sending 4 resources to slave 0
[ 0] master sending 3 resources to slave 1
[ 0] master sending 2 resources to slave 2
[ 0] master sending 1 resources to slave 3
[ 0] master polling ...
[ 2] slave 3 produce 0 goods in 2 seconds
[ 4] slave 2 produce 1 goods in 4 seconds
[ 6] slave 1 produce 2 goods in 6 seconds
[ 8] slave 0 produce 3 goods in 8 seconds
[ 8] master receive 3 goods from slave 0
[ 8] master sending 3 resources to slave 0
[ 8] master receive 2 goods from slave 1
[ 8] master sending 2 resources to slave 1
[ 8] master receive 1 goods from slave 2
[ 8] master sending 1 resources to slave 2
[ 8] master receive 0 goods from slave 3
[ 8] master sending 0 resources to slave 3
[ 8] master polling ...
[10] slave 2 produce 0 goods in 2 seconds
[12] slave 1 produce 1 goods in 4 seconds
[14] slave 0 produce 2 goods in 6 seconds
[14] master receive 2 goods from slave 0
[14] master sending 2 resources to slave 0
[14] master receive 1 goods from slave 1
[14] master sending 1 resources to slave 1
[14] master receive 0 goods from slave 2
[14] master sending 0 resources to slave 2
[14] master polling ...
[16] slave 1 produce 0 goods in 2 seconds
[18] slave 0 produce 1 goods in 4 seconds
[18] master receive 1 goods from slave 0
[18] master sending 1 resources to slave 0
[18] master receive 0 goods from slave 1
[18] master sending 0 resources to slave 1
[18] master polling ...
[20] slave 0 produce 0 goods in 2 seconds
[20] master receive 0 goods from slave 0
[20] master sending 0 resources to slave 0
[20] master polling ...

Note that slaves 2 and 1 produce at times 4 and 6 respectively, but the master only takes their outputs into account at time 8, when slave 3's output is received. In some way, the system is sequential, since the master "scans" the output pipes in sequential rather than global order.

A more parallel fork-join execution

In order to "scan" all the pipes simultaneously, we want to take advantage of the system call, select().

#include <sys/time.h>
int select(int nfds,
    fd_set *readfds,
    fd_set *writefds,
    fd_set *errorfds,
    struct timeval *timeout);
void FD_CLR(int fd, fd_set *fdset);
int FD_ISSET(int fd, fd_set *fdset);
void FD_SET(int fd, fd_set *fdset);
void FD_ZERO(fd_set *fdset);

The select() function indicates which of the specified file descriptors is ready for reading (readfs), ready for writing (writefds), or has an error condition pending (errorfds). If the specified condition is false for all of the specified file descriptors, select() blocks, up to the specified timeout interval, until the specified condition is true for at least one of the specified file descriptors.

The nfds argument specifies the range of file descriptors to be tested. The select() function tests file descriptors in the range of 0 to nfds-1.

If the fd set argument is not a null pointer, it points to an object of type fd_set (a bit-set) that on input specifies the file descriptors to be checked for a given operation (read and write), and on output indicates which file descriptors are ready for the operation.

The macros FD_CLR, FD_ISSET, FD_SET and FD_ZERO are there to help manipulating the fd_set bit-set.

  1. Complete the code of pipe-fork-join.c and use select() to detect the pipes that have data to read.
  2. Run and test your program. You should obtain the following display and notice that now the master receives the goods as soon as they are available :
> ./pipe-fork-join 4
[ 0] master sending 4 resources to slave 0
[ 0] master sending 3 resources to slave 1
[ 0] master sending 2 resources to slave 2
[ 0] master sending 1 resources to slave 3
[ 0] master polling ...
[ 2] slave 3 produce 0 goods in 2 seconds
[ 2] master receive 0 goods from slave 3
[ 2] master sending 0 resources to slave 3
[ 2] master polling ...
[ 4] slave 2 produce 1 goods in 4 seconds
[ 4] master receive 1 goods from slave 2
[ 4] master sending 1 resources to slave 2
[ 4] master polling ...
[ 6] slave 1 produce 2 goods in 6 seconds
[ 6] master receive 2 goods from slave 1
[ 6] master sending 2 resources to slave 1
[ 6] master polling ...
[ 6] slave 2 produce 0 goods in 2 seconds
[ 6] master receive 0 goods from slave 2
[ 6] master sending 0 resources to slave 2
[ 6] master polling ...
[ 8] slave 0 produce 3 goods in 8 seconds
[ 8] master receive 3 goods from slave 0
[ 8] master sending 3 resources to slave 0
[ 8] master polling ...
[10] slave 1 produce 1 goods in 4 seconds
[10] master receive 1 goods from slave 1
[10] master sending 1 resources to slave 1
[10] master polling ...
[12] slave 1 produce 0 goods in 2 seconds
[12] master receive 0 goods from slave 1
[12] master sending 0 resources to slave 1
[12] master polling ...
[14] slave 0 produce 2 goods in 6 seconds
[14] master receive 2 goods from slave 0
[14] master sending 2 resources to slave 0
[14] master polling ...
[18] slave 0 produce 1 goods in 4 seconds
[18] master receive 1 goods from slave 0
[18] master sending 1 resources to slave 0
[18] master polling ...
[20] slave 0 produce 0 goods in 2 seconds
[20] master receive 0 goods from slave 0
[20] master sending 0 resources to slave 0
[20] master polling ...