Features

Synchronizing Processes Using Critical Sections

Matt Weisfeld

Matt Weisfeld is currently employed by the Allen-Bradley Company as a Senior System Test Engineer and is responsible for the development of test software on VAX/VMS, UNIX, DOS and other platforms. The author holds an M.S. in Computer Science, an M.B.A., and has taught computer programming and software design at two universities. Matt can be reached at maw@mailhost.da.hh.ab.com.

Synchronizing multiple processes on one computer can be accomplished using shared synchronization flags, since all processes share the same memory. However, when processes running on different computers need to be synchronized there is no local memory to share. To allow the computer platforms to communicate, they must be connected by a network.

The same approaches used to synchronize processes on a single computer platform can be used to synchronize processes across multiple platforms. Critical sections are one of the many strategies available. This article describes an implementation of a critical-section algorithm using C. The algorithm referenced in this article is from the book Operating System Concepts (Silberschatz, et al. 1991).

Critical-Section Program Structure

A critical section is a segment of code that allows a process to access shared data. Each process has one critical section. Only one process at a time can execute in its critical section. To assure that this is the case, a process must request permission to enter its critical section.

A strict program structure controls these permissions. The code contains four separate sections of code: entry, critical, exit, and remainder. In the entry section, a process requests permission to enter its critical section. The critical section itself is the only code where a process can change common data. When a process no longer needs to be in its critical section it enters an exit section. Here a process relinquishes control and allows other processes a chance to enter their critical sections. Finally, in the remainder section a process performs tasks that do not affect the common data.

The program structure must satisfy three requirements:

The Implementation

Figure 1 contains the critical-section algorithm in pseudocode, as published by Silberschatz, Peterson, and Galvin. This algorithm satisfies the requirements previously mentioned. First, a process is granted permission to enter its critical section only if all status flags are not IN_CS (mutual exclusion). Second, the turn variable can only be modified when a process enters or leaves its critical section (progress). Third, when a process leaves its critical section, it must choose a successor from the first process in the cycle (bounded waiting). The line of code,

j:=turn+1 mod n;
assures that a turn is given to each requesting process within n-1 turns. Listing 2 contains the implementation of the algorithm in C. I attempt to keep the code true to the algorithm. Since C does not have an until command, I used a do-while loop. The only difference in logic is to not the expression in the do-while loop. In this way, the flow of the logic remains as close to the algorithm as possible.

The algorithm in Figure 1 is valid for any number of processes (P0, P1,..., Pn-1). However, to keep the discussion as simple as possible, I used only three processes in this example. These processes are running on three VAXstations (of various models), running VMS and connected by DECnet. Each VAXstation has one process running that will participate in this synchronization. The processes are running in a master/slave relationship. The master is NODE0, and the slaves are NODE1 and NODE2. The intent is to have all processes start at approximately the same time. To do this, each slave sets a flag when it is ready to start. Then it waits. When the master reaches the starting point, it checks the flags of both slaves to see if they are ready. If either one of the slaves is not ready, the master will continue to check the flags until both are set. At this point the master sends a signal for both slaves to proceed, clears the flags, and continues on its way. It is important to note that these flags are not part of the criticalsection algorithm, however, their access is regulated by the critical sections.

Two common data structures maintain process synchronization. These variables are called status and turn. Each process has its own status variable that indicates its current state. Possible states are IDLE (when the process has no interest in entering its critical section), WANT_IN (when the process is requesting permission to enter the critical section), or IN_CS (when the process is currently in its critical section). All elements are initially idle. Listing 1, enet_cs.h, contains the definitions of these states.

The algorithm utilizes an array to hold all the status variables. In this implementation, the status variables are located in a shared data file. Instead of using an offset into an array, it uses an offset into a file. This offset is represented by the process number, which is always between 0 and n--1. The other variable, called the turn variable, is a single data item. It indicates which process is next in line for permission to enter its critical section. Again, the number for turn is identified by the process number n.

One of the systems, not necessarily one with competing processes, owns the data file where the shared data resides. The file consists of the status variables (an offset represented by the process number). Thus, for three processes, P1 is at offset 0, P2 is at offset 1, and P3 is at offset 2. The turn flag is at offset PROCESSES+0, and since PROCESSES = 3, the turn flag is at offset 3. The signal flags for NODE1 and NODE2 are at PROCESSES+1 and PROCESSES+2 respectively. (See Listing 1. )

To access this file the programs use DECnet. The following code opens the files:

FILE *fp;
char filename[100] =
"node\"account password\":: [directory] filename";
fp = fopen(filename, "a+");
The filename variable must contain a valid DECnet command. The backslashes are needed to spare the quotes from the C preprocessor. Notice that the password is needed to obtain access to a foreign node. After this command is executed, the variable fp contains all the information necessary to access the file. No further reference to the foreign node is needed. This implementation uses DECnet; however, any other compiler/system that allows a process to open a file residing on another host will suffice.

To keep the critical-section code as clear as possible, library routines were developed to deal with the DECnet activity. For example, to obtain the information in a specific file location (ie., TURN LOC), the code

turn_num = cs_read(TURN_LOC);
is executed.

Listing 3 contains the code for the DECnet libraries. The main point of interest with the DECnet libraries relates to how the code handles the situation when it is denied access to the file. This will happen if another process has opened the file. The message that VMS deposits in errno (defined by Standard C) when a file is controlled by another process is 65,535 (hex ffff). So as long as this is the message received, the code simply loops until successful. However, if any other error message is encountered, the process terminates. One other point of interest is the mode by which the file is opened. Since VMS maintains versions of all files, every time a file is opened, it creates a new version. This is not desirable in the implementation of the critical-section problem. Thus, the file must be opened in append mode. In this way, no new version of the file is created.

Listing 4 contains the code for all critical sections. Actually, the contents of the critical section has no bearing on the algorithm itself. None of the shared synchronization flags are ever updated in a critical section. In this example, only the flags that indicate if the slaves are ready are updated. Notice that one routine, called critical-section, handles all nodes. The process number causes the switch statement to execute the appropriate critical section.

To initiate the program enter the following command at the prompt:

$ ENET_CS node
The value of node specifies the process value for the specific instance of the code. In this way, the same executable can be used on all systems. Notice that the slaves, NODE1 and NODE2, set their proper flags and then return from their critical section with the value STOP. The master, NODEO, checks to see if the slaves are ready, if they are, then the master clears them and returns with the value STOP, since it has completed its mission. If one or both of the slaves are not ready, then the master simply returns with the value NORMAL, signaling that it has not found what it was looking for. In this case, the master will continue to request permission to enter its critical section until it finds that both slaves are ready. Note that the master never loops in the critical section. No process should ever loop in the critical section.

Conclusion

There are other means of synchronizing processes and sharing resources. The chief advantage of the method described here is the ability to synchronize processes running on multiple computer platforms. As a result, the method makes it possible to make the platforms more transparent to the processes. For programmers, this represents a small but significant increase in the ability of code to migrate to future computer platforms.

References

Silberschatz, A., A. J. Peterson, and P. Galvin. 1991. Operating System Concepts, 3d ed. Reading, MA: Addison-Wesley Publishing Company.