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
$
