1.0 Problem

Suppose there are n concurrent peer processes, where n > 1. All these processes have a checkpoint, which is an important point in the execution trace of the process. These processes need to be synchronized such that no process crosses its checkpoint before the others have reached their individual checkpoints. For example, a software system might have multiple processes and it might be desirable they all finish their initialization routines before transaction processing can begin.

Figure 1: Concurrent Processes P0 – P4. Each process Pn has a checkpoint at time tn. No process should proceed beyond checkpoint until all processes have reached their individual checkpoints.

2.0 Solution

The problem is easily solved using counting semaphores. Suppose there are n processes, where n > 1. There is a semaphore for each process with initial value 0. Once a process reaches a checkpoint it does a V operation on its semaphore (n – 1) times. That is, the value of its semaphore becomes (n – 1). Then, it does a P operation on semaphores of other (n – 1) processes. When this completes, all processes have passed their respective checkpoints and have been synchronized.

3.0 Example Program

We have an example program that demonstrates the above solution for three processes. The same program is run as three processes, viz., Process 0, Process 1 and Process 2. Each process does some work and reaches its checkpoint. It, then, synchronizes with other processes. After synchronization, the processes do some arbitrary work.

/*
 *
 *   process.c: program to demonstrate process synchronization
 *         
 */

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <fcntl.h>
#include <sys/stat.h>
#include <semaphore.h>
#include <unistd.h>
#include <time.h>

#define NUM_PROCESSES 3
#define MAX_SLEEP_TIME 5     // seconds
#define PRIME_MOD 937

sem_t *sem [NUM_PROCESSES];
char buf [128];

int main (int argc, char **argv)
{
    int i, my_process_id;

    if (argc != 2) {
	fprintf (stderr, "Usage: process-id\n");
	exit (EXIT_FAILURE);
    }
    sscanf (argv [1], "%d", &my_process_id);
    
    fprintf (stderr, "(%d): Hello, World!\n", my_process_id);
    if (my_process_id < 0 || my_process_id >= NUM_PROCESSES) {
        fprintf (stderr, "process id = %d. Out of range\n", my_process_id);
	exit (EXIT_FAILURE);
    }

    // create/open semaphores
    for (i = 0; i < NUM_PROCESSES; i++) {
	sprintf (buf, "/sem-%d", i);
        if ((sem [i] = sem_open (buf, O_CREAT, 0660, 0)) == SEM_FAILED) {
            perror ("sem_open"); exit (EXIT_FAILURE);
        }
    } 

    time_t now = time (NULL);
    srand ((unsigned int) (now % PRIME_MOD));

    unsigned int sleep_time;
    // sleep for random time
    sleep_time = rand () % MAX_SLEEP_TIME;
    (void) sleep (sleep_time);

    // checkpoint; synchronize
    fprintf (stderr, "(%d): Checkpoint, synchronizing ...\n", my_process_id);
    //V (sem-id); (n - 1) times
    for (i = 0; i < (NUM_PROCESSES - 1); i++) {
        if (sem_post (sem [my_process_id]) == -1) {
            perror ("sem_post"); exit (EXIT_FAILURE);
        }
    }

    for (i = 0; i < NUM_PROCESSES; i++) {
        if (i != my_process_id) {
	    // P (sem-id)
	    if (sem_wait (sem [i]) == -1) {
	        perror ("sem_wait"); exit (EXIT_FAILURE);
            }
	}
    }

    fprintf (stderr, "(%d): synchronized. Will do rest of the work.\n", my_process_id);
    
    // sleep for random time
    sleep_time = rand () % MAX_SLEEP_TIME;
    (void) sleep (sleep_time);

    // Remove semaphore
    sprintf (buf, "/sem-%d", my_process_id);
    if (sem_unlink (buf) == -1) {
        perror ("sem_unlink"); exit (EXIT_FAILURE);
    }
    
    fprintf (stderr, "(%d): Bye.\n", my_process_id);
    exit (0);
}

We can compile the above program and run it as three processes, as below.

$ ./process 0 & ./process 1 & ./process 2 & ps
[1] 19907
[2] 19908
[3] 19909
(1): Hello, World!
(0): Hello, World!
(2): Hello, World!
    PID TTY          TIME CMD
  19374 pts/2    00:00:00 bash
  19907 pts/2    00:00:00 process
  19908 pts/2    00:00:00 process
  19909 pts/2    00:00:00 process
  19910 pts/2    00:00:00 ps
$ (0): Checkpoint, synchronizing ...
(1): Checkpoint, synchronizing ...
(2): Checkpoint, synchronizing ...
(2): synchronized. Will do rest of the work.
(0): synchronized. Will do rest of the work.
(1): synchronized. Will do rest of the work.
(0): Bye.
(2): Bye.
(1): Bye.

[1]   Done                    ./process 0
[2]-  Done                    ./process 1
[3]+  Done                    ./process 2
$ 

4.0 See also

POSIX Semaphores In Linux