Unix™ Systems Programming [Electronic resources] : Communication, Concurrency, and Threads نسخه متنی

14.1 Dealing with Critical Sections

Imagine a computer system in which all users share a single printer and can simultaneously print. How would the output appear? If lines of users' jobs were interspersed, the system would be unusable. Shared devices, such as printers, are called exclusive resources because they must be accessed by one process at a time. Processes must execute the code that accesses these shared resources in a mutually exclusive manner.

A critical section is a code segment that must be executed in a mutually exclusive manner, that is, only one thread of execution can be active in its boundaries. For example, code that modifies a shared variable is considered to be part of a critical section, if other threads of execution might possibly access the shared variable during the modification. The critical section problem refers to the problem of executing critical section code in a safe, fair and symmetric manner.

Program 3.1 on page 67 to generate a process chain. It prints its message one character at a time. The program takes an extra command-line argument giving a delay after each character is output to make it more likely that the process quantum will expire in the output loop. The call to wait ensures that the original process does not terminate until all children have completed and prevents the shell prompt from appearing in the middle of the output of one of the children.

Exercise 14.1

Explain why the marked section of code in Program 14.1 is a critical section.

Answer:

After falling out of the forking loop, each process outputs an informative message to standard error one character at a time. Since standard error is shared by all processes in the chain, that part of the code is a critical section and should be executed in a mutually exclusive manner. Unfortunately, the critical section of Program 14.1 is not protected, so output from different processes can interleave in a random manner, different for each run.

Exercise 14.2

Run Program 14.1 with different values of the delay parameter. What happens?

Answer:

When the delay parameter is near 0, each process usually outputs its entire line without losing the CPU. Longer delays make it more likely that a process will lose the CPU before completing the entire message. For large enough values of the delay, each process outputs only one character before losing the CPU. Depending on the speed of the machine, you might need to use values of the delay in excess of 1 million for this last case.

Exercise 14.3

Program 3.1 on page 67 uses a single fprintf to standard error to produce the output. Does this have a critical section?

Answer:

Yes. Although the output is in a single C language statement, the compiled code is a sequence of assembly language instructions and the process can lose the CPU anywhere in this sequence. Although this might be less likely to happen in Program 3.1 than in Program 14.1, it is still possible.

Program 14.1 chaincritical.c

A program to generate a chain of processes that write to standard error.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/wait.h>
#include "restart.h"
#define BUFSIZE 1024
int main(int argc, char *argv[]) {
char buffer[BUFSIZE];
char *c;
pid_t childpid = 0;
int delay;
volatile int dummy = 0;
int i, n;
if (argc != 3){   /* check for valid number of command-line arguments */
fprintf (stderr, "Usage: %s processes delay\n", argv[0]);
return 1;
}
n = atoi(argv[1]);
delay = atoi(argv[2]);
for (i = 1; i < n; i++)
if (childpid = fork())
break;
snprintf(buffer, BUFSIZE,
"i:%d  process ID:%ld  parent ID:%ld  child ID:%ld\n",
i, (long)getpid(), (long)getppid(), (long)childpid);
c = buffer;
/********************** start of critical section **********************/
while (*c != '\0') {
fputc(*c, stderr);
c++;
for (i = 0; i < delay; i++)
dummy++;
}
/********************** end of critical section ************************/
if (r_wait(NULL) == -1)
return 1;
return 0;
}

Each process in Program 8.6 on page 271, the signal handler and the results function compete for access to buf and buflen. The entry section or gatekeeper is the code in results to block SIGUSR1; the exit section is the code to unblock SIGUSR1 and to restore the original signal mask.

Program 2.3 on page 39 illustrates a related problem that can arise with recursive calls to nonreentrant functions such as strtok. Although this example is not strictly a critical section problem by the definition given above, it has the same characteristics because the single thread of execution changes its execution environment when a function call pushes a new activation record on the stack.