Semaphores

In the days before radio, when two ships wished to communicate with each other to decide who was going first to traverse a channel wide enough only for one, they used multicolored flags called semaphores. Computer scientists, being great lovers of anachronistic terms, adopted the term and meaning of the word semaphore to create a way for processes to communicate when accessing shared information.

GNO/ME, like other multitasking systems, provides applications with semaphore routines. Semaphores sequentialize access to data by concurrently executing processes. You should use semaphores whenever two or more processes want to access shared information. For example, suppose there were three processes, each of which accepted input from user terminals and stored this input into a buffer in memory. Suppose also that there is another process which reads the information out of the buffer and stores it on disk. If one of the processes putting information in the buffer (writer process) was in the middle of storing information in the buffer when a context switch occurred, and one of the other processes then accessed the buffer, things would get really confused. Code that accesses the buffer should not be interrupted by another process that manipulates the buffer; this code is called a critical section; in order to operate properly, this code must not be interrupted by any other attempts to access the buffer.

To prevent the buffer from becoming corrupted, a semaphore would be employed. As part of it's startup, the application that started up the other processes would also create a semaphore using the screate(2) system call with a parameter of 1. This number means (among other things) that only one process at a time can enter the critical section, and is called the count.

When a process wishes to access the buffer, it makes a swait(2), giving as argument the semaphore number returned by screate(2). When it's done with the buffer, it makes an ssignal(2) call to indicate this fact.

This is what happens when swait is called: the kernel first decrements the count. If the count is then less than zero, the kernel suspends the process, because a count of less than zero indicates that another process is already inside a critical section. This suspended state is called 'waiting' (hence the name of swait). Every process that tries to call swait with count < 0 will be suspended; a queue of all the processes currently waiting on the semaphore is associated with the semaphore.

Now, when the process inside the critical section leaves and executes ssignal, the kernel increments the count. If there are processes waiting for the semaphore, the kernel chooses one arbitrarily and restarts it. When the process resumes execution at its next time slice, its swait call will finish executing and it will have exclusive control of the critical section. This cycle continues until there are no processes waiting on the semaphore, at which point its count will have returned to 1.

When the semaphore is no longer needed, you should dispose of it with the sdelete(2) call. This call frees any processes that might be waiting on the semaphore and returns the semaphore to the semaphore pool.

One must be careful in use of semaphores or deadlock can occur.

There are (believe it or not) many situations in everyday programming when you may need semaphores, moreso than real UNIX systems due to the Apple IIgs's lack of virtual memory. The most common of these is your C or Pascal compiler's stdio library; these are routines like printf(3) and writeln(3). In many cases, these libraries use global variables and buffers. If you write a program which forks a child process that shares program code with the parent process (i.e. doesn't execve(2) to another executable), and that child and the parent both use non-reentrant library calls, the library will become confused. In the case of text output routines, this usually results in garbaged output.

Other library routines can have more disastrous results. For example, if a parent's free(3) or dispose(3) memory management call is interrupted, and the child makes a similar call during this time, the linked lists that the library maintains to keep track of allocated memory could become corrupted, resulting most likely in a program crash.

GNO/ME provides mutual exclusion (i.e., lets a maximum of one process at a time execute the code) automatically around all Toolbox and GS/OS calls as described in Chapter 3, and also uses semaphores internally in many other places. Any budding GNO/ME programmer is well advised to experiment with semaphores to get a feel for when and where they should be used. Examples of semaphore use can be found in the sample source code, notably dp.c (Dining Philosophers demo) and pipe*.c (a sample implementation of pipes written entirely in C).