TP — Multiprocessing & multithreading

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

The C files are located in directory part-3/tp-proc-thread/material/.

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

Overview

The aim of this lab is to learn how to use Unix system calls to manage processes.

To illustrate this, we shall design a simple Unix shell. A Unix shell is a command-line interpreter or shell that provides a command line user interface for Unix-like operating systems. This application is probably the most typical example of the use of the four basic functions for process management, fork(), exec(), exit() and wait().

Then, we shall study one of the most typical concurrency design patterns, the fork-join model. In parallel computing, the fork-join model is a way of executing a program in parallel, so that the execution splits (fork) in several subtasks to execute them in parallel, only to merge (join) at a later point and resume sequential execution.

The sources for the labs are in the archive you downloaded at the beginning of the course.

Processes

This section is a short course about UNIX processes.

Unix is a multi-tasking system, meaning it can run several programs at the same time. A process is an instance of a running program. Each process has a process id which designates an entry in the system process table, a data structure in the computer memory. Each entry holds the context of the process such as its state (active, running, blocked), its registers (stack pointer, program counter...), pointers to the program code and the memory address space...

fork() is a system call that the parent process uses to clone itself into another identical process, called the child process. After calling fork(), the child process is an exact copy of the parent process, except for the return value of the fork() call. This exact copy includes open files, register status and all memory allocations, including the program's executable code.

The new process is a child of the parent process and has a new process identifier (PID). The fork() function returns the child's PID to the parent process. The fork() function returns 0 to the child process. This distinguishes the two processes, even if they are executing the same code.

When the parent process modifies its memory space, since the child process only has an earlier copy of its parent's space, this modification is not reflected in the child process' space.

In some cases, both processes continue to execute the same code, but often one of them (usually the child process) switches to executing another executable code using the exec() system call. When the child process calls exec(), with a new program to run as a parameter, all data in the original program is lost and replaced by a running copy of the new program.

The parent process can either continue execution or wait for the child process to finish. If the parent process chooses to wait() for the child process to complete, it will receive the exit status of the program the child has executed. To do this, the child process uses the exit() system call. The integer parameter of exit() specifies the state of the terminating child process. If a program terminates without exit(), the system terminates with a default status of 0, this value indicating an error-free termination.

When a child terminates, its address space is deallocated, leaving only its entry in the process table. The child becomes a zombie process. In other words, the child is dead, except for its entry in the process table to preserve its status for its parent. The parent must call wait() on its children, either periodically, or when it receives the SIGCHLD signal (cf. upcoming homework assignment), which indicates that a child process has terminated. In this case, the child's termination status can be transmitted and its entry in the process table completely deallocated. If the parent terminates before its child or without calling wait() on a zombie child, the child becomes orphan. The first process started by the system adopts any orphan process, i.e., a process whose parent has terminated before its child becomes a child of this first process, and call wait() for this process. Note that getpid() returns the process id of the current process and getppid() the process id of the current process' parent

Programming processes in C

We first review functions of process management from the POSIX API and propose simple exercises.

Function fork()

int fork();
  • This function will create a process. The returned value rv of this function indicates:
    • rv > 0 We are in the parent process and rv is the child process id,
    • rv == 0 We are in the child process,
    • rv == -1 fork failed, no process created. This situation occurs when there are not enough resources (memory for instance) to duplicate the parent process.
int getpid();
  • This function returns the process id of the current process.
int getppid();
  • This function returns the process id of the parent process.
  1. Complete the fork-single.c file to create a process. Compile and run it.
    • Understand the code to answer the next questions.
    • Why are there five lines displayed when there are only three printf calls in the program?
  2. Run the program several times.
    • Why is it very likely (e.g. on a single processor) that the parent process will continue to run after the call to fork()?- Give a scenario, even if unlikely, such that the child process continues to run after the call to fork()?

We now want several fork() system calls to have parent, child and grandchild processes.

  1. Complete the fork-multiple.c file to create several processes. Compile and run it.
    • After execution, note down the process ids.
    • Define the execution order of the printf instructions so as to find the execution order of the processes.
  2. Represent these processes as a process tree (one node per process, one arc between each process and its parent).
  3. After the last call to fork() but before the last call to printf():
    • Make the grandchild process execute the sleep system call for 1 second.
    • What do you observe ? Explain why.

Functions wait() and exit()

We recall some function specifications.

void exit(int status);
  • Ends a process, status is a byte (0 to 255) returned as an int to the parent process.
pid_t wait(int *status);
  • The current process waits for the termination of one of its children, changing its own state to blocked. When a process terminates, it signals its completion to its parent. This causes the parent process to switch from the blocked state to the ready state. The parent process thus leaves the wait() function.
  • The return value of wait() is the id of the child process that has just terminated. When there are no children to wait for, the wait() function returns -1. Each time a child terminates, the parent process returns from wait() and can inspect the returned parameter status to obtain information on the child that has just terminated.
  • status is a pointer to a two-byte word: the most significant byte contains the value returned by the child (status from the exit() function), the least significant byte contains 0 in the general case. Otherwise, it contains information on the abnormal termination of the child process.
  1. Complete the fork-wait.c file to force the parent process to wait for the child process. Compile and run it.
  2. Check that the display is consistent in terms of status and returned value.

Function execvp()

The exec family of functions shall replace the current process image (code + data) with a new process image. One form of this family is execvp():

int execvp(const char *file, char *const argv[]);
  • execvp() replaces the current process image with a new process image.
  • file is the process image file that will be loaded into the code area of the process calling execvp. If this file is not in the current directory, or if it is not accessible via the list of directories referenced by the PATH variable, you must specify the path to the file (relative or absolute).
  • The argv argument is an array of null-terminated strings that is used to provide a value for the argv argument to the main function of the program to be executed. The last element of this array must be a null pointer. By convention, the first element of this array is the file name of the program. For example, if you want to load a file called prog, which is located in the current directory and uses two arguments passed on the command line: execvp("prog", (char *[]){"prog", "x", "y", NULL}).
  • The returned value is -1 when an error occurs (for instance when the the process image file does not exist).
  1. Complete the fork-exec.c file to execute the rest of the command line in a new process. Compile and run it.
    • Note that the argument list to be passed to execvp() does not start at argv[0] but at argv[1].
  2. To check that it's working properly, we'll have to invoke exec on a very simple program. You can then run the fork-exec program by passing it various commands as arguments, such as:
$ fork-exec fork-exec
$ fork-exec /bin/ps
$ fork-exec ls -l

Programming processes in Shell

The following exercises focus on the use of few shell commands that allow you to view the list of processes, launch them with or without blocking the execution of the shell, and finally replace the code of the shell process with that of another process.

Command ps

To see the list of processes and the different properties concerning them, try the following sequence of commands:

$ ps -l              # list of processes attached to the terminal
$ ps -edf            # list of processes present on the system
$ ps -axl            # same with more details
$ ps -ael            # or depending on the system used
$ ps -axjf --forest  # same with parent process identifier and tree representation

Note the very first process with pid 1 (process id) and its tree of processes (a parent process and its child processes). The process 1 is the parent of all processes. It adopts any orphan process, i.e. a process whose parent has terminated before its child becomes a child of process 1.

Command in background

In this exercise, we illustrate the use of '&' option when launching a process from the shell.

  1. Compile the program fork-nothing. Run fork-nothing program.
$ ./fork-nothing

You can't type any more commands until you've closed or stopped it.

  1. Stop it with Ctrl-C.

  2. Now launch the same program with the '&' option:

$ ./fork-nothing &

This time, the fork-nothing program is launched, but you can continue to type new commands.

Let's take another example using sleep n which pauses the process executing this command for n seconds.

  1. Send the following sequence and observe the process filiation:
$ ps -l # list of processes attached to the current terminal
$ sleep 20& # process sleeping for 20s in the background
$ sleep 30& # process sleeping for 30s in the background
$ ps -l

This last command let you view the new process configuration.

  • Note that that the process running the shell has several child processes, each running the sleep command.

Command exec

We will now see the effect of the exec command, which like the system call of the same name, replaces the code and data of the process that executes it with the code of a binary file referenced when launching 'exec'. 

exec ps

What is happening and why ?

For exec, as for some other commands (built-in commands such as cd, echo, exit, kill, ...) the shell does not create a new process, i.e. it does not use a fork for the command, but executes it directly in the shell code.

To validate this mechanism, open a new terminal window, Now enter the command zsh. Note the pid of the process that runs this new current shell (by making ps -l), then run 'exec ps -l'. Retrieve the pid of the process that runs this program ps -l. What is its value and why?

Fork-join execution model

In this exercise, we aim at implementing the Fork-Join execution model which is essentially a parallel divide-and-conquer model of computation. The general idea for this model is to solve a problem by breaking it up into identical sub-problems with smaller size (Fork part), then solve the smaller version of the problem in parallel, then combine the results (Join part). Do not get confused by the different meanings of the word "fork".

Implementation with processes

We first implement this model with processes. Write a program whose operation is as follows:

  • The parent process

    • Reads from the command line (use argc and argv) N the number of processes to create.
    • Creates N child processes by making N calls to fork (beware of doing this iteratively and not recursively, otherwise you risk creating \( 2^N \) processes!).
    • Waits for the completion of these N child processes and displays their identity.

  • The i-th child process

    • Displays its pid (getpid()) and that of its father (getppid()),
    • Sleeps for 2 * i seconds and displays its completion,
    • Ends by providing to its parent its index i.
  1. Complete the process-fork-join.c file. Take example from the previous implementations.
  2. After checking that the program is running correctly, cause one of the child processes to terminate abnormally (e.g., by doing an integer division by zero, or by dereferencing a NULL pointer) and note that the system does not return zero as a low-order state, but provides an error flag instead.

Implementation with threads

(Optional exercise, to go further in the understanding of the course topics.)

Instead of using fork(), wait() and exit(), we use the thread interface with pthread_create(), pthread_join() and pthread_exit().

int pthread_create(pthread_t *thread, const pthread_attr_t *attr, void *(*main)(void*), void *arg);
  • Create a new thread and let this thread execute main as a main subprogram.
    • thread is a pointer to the created thread.
    • attr allows to configure some thread attributes but we will not use this parameter in this exercise, so just use NULL for this.
    • main is the routine executed by the thread with arg as its sole argument.
    • arg is the sole parameter passed to the thread main procedure main.
int pthread_join(pthread_t thread, void **value_ptr);
  • Wait for a thread to complete
    • thread is the thread we are waiting for (different from wait() for processes)
void pthread_exit(void *value_ptr);
  • End the thread
    • Provide its exit information in value_ptr. Note that using exit() instead would not only terminate the thread, but the process itself with all its threads.
pid_t gettid(void);
  • Get the tid of the current thread
    • Return the tid of the thread as getpid() would do for the process id.

We aim at implementing the fork-join model not using the process interface, but instead using the pthread interface.

  • The main thread (executing the process):

    • Reads from the command line (use argc and argv) N the number of threads to create.
    • Creates N threads by making N calls to pthread_create.
    • Waits for the completion of these N threads and displays their index and their thread.

  • The i-th thread

    • Displays its index and its thread id.
    • Sleeps for 2 * i seconds and displays its completion.
  1. Complete the thread-fork-join.c file.
    • Note that the second parameter of join() is a pointer to be modified, so a pointer of pointer.

Implementation of a simple shell

(Optional exercise, to go further in the understanding of the course topics.)

A (simple) shell implementation

The shell is as a typical application of the four system calls fork, exec, wait and exit. To understand the behaviour differences between a given command line and the same command line with '&', let's give a pseudo code describing the implementation of the shell. 

forever
    print $prompt$
    $command$ = read the command line

    create process $child$ using fork()

    # both child and parent processes execute the next instructions

    if ($current_process$ is $child$)
        launch $command$ using exec()
        # the child process does not return from exec() (if $command$ exists)

    if ($current_process$ is $parent$) and ($command$ does not end with '&')
        wait for $child$ completion using wait()

When we previously launched the fork-nothing program on the command line, $command$ was 'fork-nothing'. The shell creates a new process, and this child process runs 'exec fork-nothing'. The shell or the parent process waits for its child process completion. But when we launch the fork-nothing program with '&', the shell does not wait for its child process completion.

  1. Use the fork-shell.c file which provides a code to convert a string (or a command line) into a structure argc/argv.
  2. Implement a shell that executes simple commands and check with several calls such as "ls -l" or "ps -a". Check that the result occurs before the new prompt. You can also reuse what you implemented in the fork-exec.c file.
    • Use strcmp() to detect strings such as "&" or "exit".
  3. Extend your shell to execute simple commands and check with several calls such as "ls -l &" or "ps -a &". Check that the result occurs after the new prompt. You can use the strcmp() function to compare two strings.

A (simple) shell implementation with builtins

For built-in commands (cd, echo, exit, kill, ...) the shell does not create a new process, i.e. it does not use a fork for the command, but executes it directly in the shell code. For instance, exit must not create a new process, otherwise it would exit the child process and not the main process!

To illustrate this difference, we detail a bit more our initial shell implementation. 

forever
    print $prompt$
    $command$ = read the command line

    if ($command$ in builtins)
        execute code of $command$
        # if $command$ = exit, leave forever loop

    else
        create process $child$ using *fork()*
        if ($current_process$ is $child$)
            launch $command$ using exec()

        if ($current_process$ is $parent$) and ($command$ does not end with '&')
            wait for $child$ completion using wait()
  1. Use the simple shell you implemented in the previous exercise.
  2. Extend your shell to execute simple builtin commands (exit and exec at least) and check with several calls such as "exit" or "exec ps".