Matt Weisfeld is currently a Program Engineer at the Allen-Bradley Company in Cleveland, Ohio. H is specifically interested in software testing and many of his articles are based upon techniques developed during test efforts. Matt is currently pursuing a Ph.D. in computer engineering at Case Western Reserve University and can be reached via the internet at maw@cle.ab.com.
With the proliferation of windowing systems, multiprocessing, client/server technologies and other multi-user environments, it is a good idea to have some synchronization techniques in your programming toolkit. One of the most popular methods of performing synchronization is with the use of semaphores and critical-sections. In the vast majority of operating systems books, semaphores and critical-sections are discussed in the context of multiple processes on a single platform. In this discussion, the approach taken is of a broader scope. The techniques presented here are applicable to any number, or type, of platforms. In other words, processes of several platforms (perhaps some mixture of UNIX, PC, and Alpha platforms) can be synchronized over a network or shared file system.
This article presents a C++ class that performs synchronization using semaphores and critical-sections. It is based on an algorithm described in Silberschatz, et al. [1]. Some of the material presented here appeared earlier in The C Users Journal in October, 1992 [2]. This article expands on the C code presented in the earlier work in a number of ways — specifically in terms of using the shared file system with processors of different vendors.
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 ensure that this is the case, a process must request permission to enter its critical section. A strict program structure controls these permissions. This structure contains four separate sections: 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:
- Mutual exclusion — only one process at a time may execute in its critical section.
- Progress — only those processes actively interested in entering their critical sections may participate in determining which process enters its critical section next. That is, if no process is executing in its critical section, but some processes want to enter their critical sections, then only those processes that are not executing in their remainder-section can decide who goes next.
- Bounded waiting — a process cannot be locked out of its critical section forever. That is, there must be a limit on the number of times that a process can enter its critical section, preempting a previous request made by another process to enter its critical section.
The Implementation
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 include 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.Figure 1 contains the critical section algorithm in pseudo code, as published by Silberschatz, et al. This algorithm satisfies the requirements previously stated. 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 assignment, j:=turn+l mod n, assures that a turn is given to each requesting process within n-1 turns. Since C/C++ does not have an until command, a do-while loop is used. 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. Despite the somewhat non-descriptive variable names presented in the book (such as i and j), I have kept them as they are to maintain consistency with the algorithm.
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 use only three processes in this example. These processes are running on two UNIX platforms (Sun SPARCstation 5) and one PC (486). On the SPARCstations, the g++ v2.4 compiler is used, and on the PC, the Borland 4.0 compiler is used.
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 the master wait until all other processes take a turn and then proceed. To do this, each slave sets a flag to indicate that it has completed its task. When the master reaches the starting point, it checks the flags of both slaves to see if they are ready. If neither of the slaves is ready, the master will continue to check the flags until both are set. At this point the master clears the flags and continues on its way. It is important to note that these flags are not part of the critical section algorithm; however, access to them is regulated by the critical sections.
In the algorithm, an array is utilized 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 zero and n-1. The other variable, called the turn variable, is a single data item that 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.
Figure 2 illustrates what the file looks like and how it is used. The file resides on a networked file system which all platforms can access. In this example, the synchronization file resides on a disk shared by the UNIX processes and mounted by the DOS application as its G: drive.
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, P0 is at offset zero, P1 is at offset 1, and P2 is at offset 2. The turn flag is at offset PROCESSES+0, and since PROCESSES = 3, the turn flag is at offset 3. The status flag for NODE1 and NODE2 are at PROCESSES+1 and PROCESSES+2 respectively.
The Synchronization Class
The synchronization class, named semaphore, is presented in the file sema.h (Listing 1) . The private data members are explained by the comments found in the code. Note that the status of the process and location flags are contained in the two arrays NODE and LOC. The name of the shared data file is held in the character array filename. The public member functions are explained one at a time in the discussion of the code. A file called defines.h (Listing 2) contains all the constants necessary to compile the code. Again the comments are self explanatory. All the executable code is found in the file sema.cpp (Listing 3) .The constructor semaphore() initializes the data members. One parameter is passed to indicate how many processes there are to synchronize. The data member PROCESSES is then set. In this implementation, the name of the shared synchronization file is set in the constructor. There are obviously other places where PROCESSES can be set (for example, a second parameter can be used to allow for a run-time definition). Finally, the NODE and LOC arrays are initialized to the appropriate values. Note that each NODE is set to its corresponding process value while each LOC is set to PROCESSES + i. The destructor is simply a place holder at this point — it may be needed for future enhancements.
The algorithm to control access to the critical section is found in the method perform. This code follows the algorithm as closely as possible. The only difference relates to the synchronization file access. To keep the algorithm as clean as possible, routines are provided to handle all the file I/O. These routines are called cs_read and cs_write. Note the use of fseek to position inside the file to access the proper flag.
The critical-section code itself is found in the method critical_section. This is what the processes execute while they are in their respective critical section. In many cases the critical sections of different processes will not be identical. For this synchronization example, they all are the same — except that they access different flags. Thus, by using a for loop, all processes can utilize the same critical section. If the node is the master (NODE0), it checks if all the slaves are ready. If they are, then the master clears all the flags and returns a status of STOP. If at least one slave has not completed its task, the master returns NORMAL and tries again. As for the slaves, they simply set their flag to READ and then return STOP.
To encapsulate the critical section algorithm from the user, the method synchronize is provided. This method does all the initialization work for each synchronization and enters a loop until the process has successfully completed its critical section. To synchronize a process, the only code necessary is:
// process is the current process number synchronize(process);There are two supporting methods in this class. The first, called intro, simply identifies the node number of the process. For example, the master would print NODE0 to the screen. The second, called initialize, builds and initializes the shared synchronization file.
The Test Program
A simple test program, found in the file tsema.cpp (Listing 4) , is provided to demonstrate how to use the semaphore class. Aside from checking for proper argument values and the return statement, there are only two lines of executable code in this program:
semaphore S(PROC_NUM); S.synchronize(argv[1]);The constant PROC_NUM defines the total number of process involved in the synchronization — in this case there are three. The parameter passed to synchronize, representing the current process number, is taken directly from the argument passed to the test program (argv [1]). For example, to use this program (compiled with the name test), the master process (NODE0) would execute the following command at the operating system prompt:
test 0The first slave (NODE1) would execute the following (the remaining slaves do the same until PROCESSES - 1 is reached):
test 1 test 2 ... // if there are more than 3 processes test processes-1The matter of building and initializing the file is a special case and is performed by executing the method initialization (when the parameter i is recognized, the initialization routine is called and the program exits):
test iAs an example, Listing 5 contains a short UNIX Korn shell script that is used to test the complete program. Each UNIX process runs this script, and the PC application runs one that is similar in nature.
Conclusion
There are many other means of synchronizing processes and sharing resources. In fact, this is just one example of how to use semaphores and critical sections. Since the code for the actual critical section algorithm is contained in the perform method, it is fairly straightforward to tailor this code for specific applications. In most cases, the routine synchronize and the calling mechanism, are all that need to change.
References
[1] A. Silberschatz, A.J. Peterson, and P. Galvin. Operating System Concepts, 3d ed. (Addison-Wesley, 1991).[2] Matt A. Weisfeld. "Synchronizing Processes Using Critical Sections," The C Users Journal October, 1992.