7.4. Semaphores¶

7.4.1. Semaphores as Signaling¶

Semaphores can be used to send general signals to other threads that some application-specific event has occurred. Note that this use of semaphores is different from the pre-defined signals such as SIGKILL. Events with semaphores have no pre-defined meaning and are simply indications that something has occurred.

To illustrate signaling, consider the two threads shown in Code Listing 7.7. One thread (keyboard_listener()) reads a line of input from STDIN into a shared buffer. Once the input has been received, the thread posts to the semaphore to alert the second thread that the event (receiving input) has occurred. The second thread (keyboard_echo()) starts by waiting on the semaphore before trying to read the input from the buffer. The semaphore ensures that the echo thread cannot try to read from the buffer until the listener has finished writing to the buffer.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/* Code Listing 7.7:
   Two threads cooperating to echo input text
 */

/* Struct instance will contain pointers to semaphore and buffer */
struct args {
  sem_t *semaphore;
  char *buffer;
};

#define MAX_LENGTH 40

/* Listener thread gets input, then ups the semaphore */
void *
keyboard_listener (void * _args)
{
  /* Cast the args to a usable struct type */
  struct args *args = (struct args *) _args;
  printf ("Enter your name here: ");
  assert (fgets (args->buffer, MAX_LENGTH, stdin) != NULL);

  /* After receiving input, up the semaphore and exit */
  sem_post (args->semaphore);
  pthread_exit (NULL);
}

void *
keyboard_echo (void * _args)
{
  /* Cast the args to a usable struct type */
  struct args *args = (struct args *) _args;

  /* Wait on the signal from the semaphore */
  sem_wait (args->semaphore);

  /* Trim off at the newline character */
  char *newline = strchr (args->buffer, '\n');
  if (newline != NULL) *newline = '\0';

  /* Echo back the name and exit */
  printf ("Hello, %s\n", args->buffer);
  pthread_exit (NULL);
}

The key with signaling is that the semaphore must be created and initialized with an initial value of 0 as shown in Code Listing 7.8. By using this initial value, the semaphore eliminates the issue of nondeterministic thread scheduling. Specifically, if the keyboard_echo() thread runs first, it must wait until the keyboard_listener() reads the input and ups the semaphore. However, if keyboard_listener() runs first and ups the semaphore before keyboard_echo() gets scheduled, then the semaphore will have a value of 1 and the thread will not be blocked.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/* Code Listing 7.8:
   Initializing a semaphore and passing it to threads
 */

/* Allocate the buffer and open the named semaphore */
char buffer[MAX_LENGTH+1];
memset (buffer, 0, sizeof (buffer));

/* For signaling, initialize the semaphore to 0 */
sem_t *sem = sem_open ("/OpenCSF_Sema", O_CREAT | O_EXCL,
                       S_IRUSR | S_IWUSR, 0);
assert (sem != SEM_FAILED);

/* Set up struct instance with both pointers; pass it to threads */
struct args args = { sem, buffer };
assert (pthread_create (&threads[0], NULL, keyboard_listener,
                        &args) == 0);
assert (pthread_create (&threads[1], NULL, keyboard_echo, &args)
        == 0);

/* Wait for both threads to finish, then unlink the semaphore */
pthread_join (threads[0], NULL);
pthread_join (threads[1], NULL);
sem_unlink ("/OpenCSF_Sema");

Bug Warning

---

In this basic signaling pattern, it is possible to have the two threads repeatedly post to or wait on a single semaphore. This approach is a common technique for handling repeated events. However, it is fraught with peril. In this example, there is only one buffer. So if the keyboard_listener() repeatedly reads input (posting each time), the buffer would be repeatedly overwritten, and there is no guarantee that the keyboard_echo() thread would read any of the input.

Another complication arises if there are multiple threads repeatedly waiting on the same semaphore. In the default implementation of POSIX semaphores, the order in which threads are unblocked with sem_post() is unspecified. As such, it is possible that one thread might be repeatedly unblocked while the other waiting thread is never unblocked.

7.4.2. Mutual Exclusion with Semaphores¶

Semaphores can also be used to ensure mutually exclusive access to a shared variable or resource. Consider the two threads, shown in Code Listing 7.9, that atomically increment or decrement an int counter variable. Each change to the shared variable is preceded by a call to sem_wait() and followed by a call to sem_post(). This wrapping is analogous to the mutual exclusion style used with locks.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

/* Code Listing 7.9:
   Two threads that synchronize modifications to a shared variable
 */

/* Struct containing the semaphore and integer */
struct args {
  sem_t *semaphore;
  int value;
};

/* Adder thread that repeatedly adds 10 */
void *
add (void * _args)
{
  /* Cast the args to a usable struct type */
  struct args *args = (struct args *) _args;
  int i;

  /* Atomically add 10 to value 100000 times */
  for (i = 0; i < 100000; i++)
    {
      sem_wait (args->semaphore);
      args->value += 10;
      sem_post (args->semaphore);
    }
  pthread_exit (NULL);
}

/* Subtracter thread that repeatedly subtracts 10 */
void *
subtract (void * _args)
{
  /* Cast the args to a usable struct type */
  struct args *args = (struct args *) _args;
  int i;

  /* Atomically subtract 10 from value 100000 times */
  for (i = 0; i < 100000; i++)
    {
      sem_wait (args->semaphore);
      args->value -= 10;
      sem_post (args->semaphore);
    }
  pthread_exit (NULL);
}

As shown in Code Listing 7.10, the difference between signaling and mutual exclusion is the initial value of the semaphore. For mutual exclusion, the semaphore is initialized to 1.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

/* Code Listing 7.10:
   Initializing a semaphore for mutual exclusion instead of signaling
 */

/* For mutual exclusion, initialize the semaphore to 1 */
sem_t *sem = sem_open ("/OpenCSF_Sema", O_CREAT | O_EXCL,
                       S_IRUSR | S_IWUSR, 1);
assert (sem != SEM_FAILED);

/* Set up a struct instance with semaphore and initial value 0 */
struct args args = { sem, 0 };
assert (pthread_create (&threads[0], NULL, add, &args) == 0);
assert (pthread_create (&threads[1], NULL, subtract, &args) == 0);

As illustrated in Code Listing 7.9, semaphores can be used identically to mutex locks as shown previously. In fact, Code Listing 7.11 shows that we can use semaphores as a foundation to create locks. Acquiring the lock involves waiting on the semaphore and setting oneself as the lock owner. Releasing the lock clears the ownership field and posts to the semaphore. If multiple threads try to acquire the lock, they all end up trying to down the semaphore, and only one is successful. Once that thread releases the lock, the semaphore is upped and a single thread is unblocked; that thread then sets itself as the owner.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/* Code Listing 7.11:
   Creating locks from semaphores
 */

/* We can create a lock with a semaphore and owner field */
typedef struct lock {
  sem_t *semaphore;
  pthread_t owner;
} lock_t;

/* To acquire the lock, wait on semaphore and set self as owner */
int
mutex_lock (lock_t *lock)
{
  int retvalue = sem_wait (lock->semaphore);
  lock->owner = pthread_self ();
  return retvalue;
}

/* To release, clear the owner field and post to the semaphore */
int
mutex_unlock (lock_t *lock)
{
  /* Only the owner can release the lock */
  if (lock->owner != pthread_self ())
    return -1;
  lock->owner = 0;
  return sem_post (lock->semaphore);
}

The key difference between locks and semaphores is that a semaphore must be explicitly initialized to the integer value 1, whereas the initialization for a lock is opaque. Or, put a different way, mutex locks are preferred because they adhere to the principles of encapsulation and information hiding. The notion of acquiring a lock is more concrete than waiting on a semaphore, and is a more appropriate abstraction for mutual exclusion.

7.4.3. Multiplexing with Semaphores¶

Both locks and semaphores can be used for mutual exclusion, though locks are typically the preferred abstraction. However, the mutual exclusion style of semaphores can be extended to allow for multiple but limited shared accesses. This concept is known as multiplexing. That is, while a lock can only be used to grant access to a single thread at a time, a semaphore can be set to allow 5, 10, or any other number of concurrent accesses. Once this limited number has been reached, any additional threads would become blocked, just as they would if trying to acquire a locked mutex.

As a real-world example of multiplexing, consider a popular restaurant or club. Building safety codes specify that there is a maximum occupancy, say 100 people. As patrons start arriving when the place opens, they are allowed in one at a time. However, once the 100th person has been allowed in, the management must make sure that no one else enters (or risk legal trouble and fines). At that point, a line forms out front. Once a single person leaves, the next patron is allowed in. In this case, the employee enforcing this restriction at the entrance is acting like a multiplexing semaphore with an initial value of 100.

Within the context of computing, multiplexing has many uses. One example is to limit the number of concurrent accesses to a pool of resources where more than one is required for each operation. For example, consider a networking hub that has 10 incoming ports and 10 outgoing ports that can be locked independently. Consider the scenario where 9 threads have already locked both an incoming and an outgoing port. Two new threads arrive; one of them acquires an incoming port and the second acquires an outgoing port. At this point, no ports of either kind are available. If these last two threads then try to acquire the missing port, they cannot. As a result, there are two ports (one incoming and one outgoing) that are both locked but not in use. This waste of resources could be prevented with the structure in Code Listing 7.12.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

/* Code Listing 7.12:
   Using a semaphore to multiplex access to a thread pool
 */

/* Acquire access to the pool of resources */
sem_wait (pool_semaphore);

/* Try to acquire incoming port. If taken, move on to the next. */
for (i = 0; i < 10; i++)
  if (pthread_mutex_trylock (incoming_mutex[i]))
    {
      in = i;
      break;
    }

/* Work with incoming port, even if no outgoing port is needed */

/* Once an outgoing port is needed, acquire it in the same way. */
for (i = 0; i < 10; i++)
  if (pthread_mutex_trylock (outgoing_mutex[i]))
    {
      out = i;
      break;
    }

/* To finish, release both locks and up the semaphore */
pthread_mutex_unlock (incoming_mutex[in]);
pthread_mutex_unlock (outgoing_mutex[out]);
sem_post (pool_semaphore);

Assuming the pool_semaphore was initialized to 10, every thread granted access to the pool of resources (ports in this example) will have access to one of each type. Moreover, this structure makes it possible for the incoming and outgoing ports to be acquired in any order; this flexibility is commonly associated with the problem of deadlock, but multiplexing in this manner avoids that issue.