Features

Using Files As Semaphores

Lyle Frost

Lyle Frost is the owner of Citadel, a consulting and software development firm. He can be contacted at 241 E. Eleventh St., Brookville, IN 47012 or on the Citadel BBS at (317) 647-2403.

Multitasking operating systems allow a single application to execute as a group of concurrent processes. These processes must usually share access to common resources, such as data files or shared memory. In the case of a multi-user database system, for example, each user would access the same set of data files through separate processes. Concurrent access to a shared resource requires some synchronization to prevent the processes from interfering with one another. The semaphore is one of the primary constructs for achieving this synchronization. Implementing semaphores is in general a difficult task. However, files may serve as a very simple implementation.

Mutual Exclusion

A program segment that accesses a shared resource is called a critical section. While in a critical section, a process must prevent other processes from entering critical sections requiring the same resource. This type of synchronization is called mutual exclusion.

For example, consider two concurrent processes A and B which simultaneously modify the same record. Two distinct accesses are needed to modify a record; the original record must first be read from its storage area, then after being modified, must be written back. Without mutual exclusion, the timing of the individual accesses by process A relative to those by process B is unpredictable. If, for instance, the write by process A occurred during the interval between the read and write by process B, the modification made by process A would be lost (Figure 1a) . Only if the two critical sections happened not to overlap would the correct result be obtained (Figure 1c) .

Mutual exclusion ensures that conflicting critical sections do not overlap. The basic principle of mutual exclusion is not complicated: before entering a critical section, a process must somehow allocate the required resource for its exclusive use. If the process fails to obtain the resource because it is currently allocated by another process, execution of the critical section must be postponed until the resource can be acquired. The critical section may be executed only after successfully allocating the resource, which must be freed at the conclusion of the critical section. Figure 2 shows two processes attempting to modify the same record simultaneously, but using mutual exclusion.

Since an allocated resource impedes the execution of other processes needing the same resource, critical sections should execute as quickly as possible, and contain only the code necessary to complete the operations on the resource. For instance, a critical section should not contain code to read user input (unless, of course, the resource is a keyboard).

Semaphores

Semaphores are used to enforce mutually exclusive access to shared resources. A semaphore is simply a flag that indicates to other processes that a specific resource has been allocated. A process lowers a semaphore to indicate that a resource is in use, then raises the semaphore when it has finished with the resource. Successfully lowering a semaphore and entering the critical section is also referred to as "passing the semaphore". The terminology derives from the device used on railroads to show when a section of track is occupied. The railroad semaphore is historically a mechanical arm that lowered a flag when the section of track it marked was in use, then raised it when the track became free.

The following pseudocode outlines the semaphore lower and raise operations. Traditionally, a value of 0 is used for a lowered semaphore and a value of 1 for a raised semaphore.

semlower(semaphore s)
{
     if s == 1 /* if semaphore is raised, */
         then s = 0 /* lower semaphore */
     else
         s not available
}

semraise(semaphore s)
{
     s = 1 /* raise semaphore */
}

At first glance, these two routines may seem trivial to implement — and they would be, except that semlower itself has a critical section; it must first perform a test operation to check if s is raised, followed by a set operation to lower s. Suppose two processes simultaneously attempted to lower the same semaphore. If the timing was such that the test and set operations of the two processes interleaved, each process would believe it had lowered the semaphore. The semaphore is not in itself a solution to the root problem of implementing mutual exclusion. Introducing the semaphore merely confines the general concurrency problem to a single critical section. Once mutual exclusion has been effected for the critical section in semlower, semaphores can then provide mutual exclusion for all other critical sections.

There are two fundamental requirements for a semaphore implementation:

• The semaphore must be visible to all processes which manipulate it.
• Mutual exclusion must be effected for the critical section in semlower.

Assuming that a shared memory facility is available, the first requirement can be met without great difficulty. The second, however, is a problem. While mutual exclusion algorithms have been devised, they are all quite complex. However, by using files as semaphores, the complex algorithms, as well as the need for shared memory capabilities, can be avoided.

Files clearly fulfill the visibility requirement, but how they provide mutual exclusion is not so obvious.

Access to the file system is controlled by the operating system and requires special functions referred to as system calls. In UNIX, for example, open, close, and unlink are file-related system calls. Though invoked exactly like a regular function, a system call causes code within the operating system to be executed. (Note that while the stdio library functions which access the file system are regular functions, they must be written using system calls — fopen would call open, remove would call unlink, etc.)

When called to delete a file, the operating system must first check that the file exists, then delete it. This is a test and set sequence and as such, requires mutual exclusion. Since the operating system has complete control over process scheduling, it can easily force a test and set to execute consecutively. Because the operating system ensures this mutual exclusion, files can be used as semaphores. Deleting and creating a file correspond to lowering and raising a semaphore, respectively.

Listing 1 and Listing 2 show the salient parts of the source code for an implementation of semaphores using files. Listing 1 (semaphor.h) should be included by programs using these routines so that all semaphore files needed by an application may be created as a "set" in a dedicated directory. The semaphore set control structure semset_t defined in semaphor.h contains the two values defining a semaphore set: the name of the directory containing the semaphore files and the number of semaphores in the set.

A semaphore set is opened using the semopen function.

semset_t *semopen(char *semdir,
               int flags, int semc);

semdir is the name of the directory containing the semaphore files. flags values are constructed by bitwise OR-ing command and permission flags. If the SEM_CREAT flag is set, the set will be created if it does not exist. If SEM_EXCL is also set, semopen will fail (returning -1) if the semaphore set already exists. The operating system dependent permission flags determine access to the semaphore set and are usually defined in <sys/stat.h> as macros of the form S_I*. If the semaphore set must be created, it will include semc semaphores; otherwise, semc is ignored. The macro semcount counts the number of semaphores in an open set. semopen returns a semaphore set pointer which is used by other semaphore functions.

An individual semaphore can be lowered using the semlower function.

int semlower(semset_t *ssp, isemno);

ssp is a semaphore set pointer obtained from a previous call to semopen, and semno is the number of the semaphore in that set to be lowered. If the semaphore is already lowered, semlower fails and sets errno to EAGAIN. The following code fragment illustrates the use of semlower.

for (n = 0; n < MAXTRIES; n++){
    if (semlower(ssp, semno) == -1) {
         if (errno == EAGAIN) {
             /*semaphore already
               lowered */
              continue;
         } else  {   /* error */
             break;
         }
    }else { /* semaphore successfully lowered */
         break;
    }
}

A semaphore is raised using the semraise function.

int semraise(semset_t *ssp, int
semno);

ssp and semno are the same as for semlower. The source code for semlower and semraise is shown in Listing 2.

After finishing with a semaphore set, it should be closed using semclose.

int semclose(semset_t *ssp);

All semaphores lowered by a process should be raised before calling semclose.

Finally,

int semremove(char *semdir);

removes all the semaphore files from directory semdir then removes the directory.

Shared Locking

By definition, a semaphore allocates a resource for exclusive use by a single process. But in many applications there are two types of critical sections:

• those sections requiring exclusive access, and
• those which may share access with each other, but not with critical sections of the first type.

Introducing the second type of critical section creates what is usually referred to as the Readers and Writers Problem. A critical section where data will be written to a file usually requires exclusive access to the file, but critical sections which will only read data may share access with each other. (In database terminology exclusive locks are also called write locks, and shared locks are also called read locks.)

Even though semaphores allocate only for exclusive access, they can also be used to implement read and write locking. Each resource lock requires two semaphores and a shared integer variable. The first (write) semaphore prevents any other process from write locking the resource. The second (read) semaphore locks not the resource, but the shared variable. The shared variable is the read count. It contains the number of processes which have the resource read locked.

If wsem is the write semaphore, rsem is the read semaphore, and rc is the read count, then the algorithm to read lock a resource is:

semlower(rsem)    /* allocate read count */
if rc == 0     /* if no other readers, */
    semlower(wsem)  /* allocate resource */
rc++        /* increment read count */
semraise(rsem)    /* free read count */

The shared variable containing the number of readers is first allocated. The first reader lowers the write semaphore to prevent the resource from being write locked. Incrementing the read count informs the next reader that the write semaphore is already lowered.

The algorithm for releasing a read lock is shown below.

semlower(rsem)      /* allocate readcount */
rc-              /* decrement readcount */
if rc == 0       /* if no other readers, */
    semraise(wsem)     /* free resource */
semraise(rsem)       /* free readcount */

When the last reader leaves its critical section, the write semaphore is lowered to allow the resource to be write locked. A write lock is acquired and released by lowering and raising the write semaphore, respectively. If any processes have the resource read locked or write locked, the write semaphore will already be lowered and the attempted write lock will fail.

Listing 3 and Listing 4 show a portion of the implementation of r/w locking using files. The read counts require the same visibility as the semaphores, and so files are also used for read counts. The routines developed above are used to manipulate the semaphores (two for each r/w semaphore). r/w semaphores are also grouped into sets; the read count files (one for each r/w semaphore) and the directory containing the semaphores (twice the number of r/w semaphores) would be isolated within a single directory.

The header rwsem.h, Listing 3, defines the r/w semaphore set control structure rwsset_t. rwsdir contains the files used by the semset_t, and rwsc is the number of r/w semaphores. ssp points to a semaphore set used for the write and read semaphores. lockheld points to an array of lock types containing the type of lock held by the calling process for each r/w semaphore. (The lock type must be remembered because the procedure to remove a read lock is different from that for removing a write lock.)

The r/w semaphore functions

rwsset_t *rwsopen(rwsset_t *rwsp, int flags, int rwsc);
int rwscount(rwsset_t *rwsp);
int rwsclose(rwsset_t *rwsp);
int rwsremove(char *rwsdir);

are exactly analogous to their semaphore counterparts. The single function rwslock controls locking, in place of semlower and semraise.

int rwslock(rwsset_t *rwsp, int rwsno, int ltype);

The first two parameters are the same as for semlower and semraise. The last specifies the type of lock.

RWS_UNLCK   unlock
RWS_RDLCK   read (shared) lock
RWS_WRLCK   write (exclusive) lock

If ltype is RWS_RDLCK and the indicated r/w semaphore is already in a write lock state, or if ltype is RWS_WRLCK and the indicated r/w semaphore is already in a read lock state, rwslock will fail (return -1) and set errno to EAGAIN. As for semlower, a busy wait loop would be used for rwslock when ltype is RWS_RDLCK or RWS_WRLCK. The source for rwslock is shown in Listing 4.

Conclusion

The control of concurrency has been a prominent topic for many years; E. W. Dijkstra's paper introducing semaphores was first published in 1965. But in spite of its relatively long history, it may be new to many microcomputer programmers who are suddenly acquiring multitasking capabilities for the first time. Understanding the implications of concurrency and the techniques for concurrency control will be necessary for the programmer to fully utilize the new multitasking systems now available for microcomputers, particularly those that are also multi-user.

References

Calingaert, P. Operating System Elements. Englewood Cliffs, NJ: Prentice-Hall, 1982.

Deitel, H. An Introduction to Operating Systems. Reading, MA: Addison-Wesley, 1984.