Quartz 4

1. Introduction

3 min read

1. What is a Semaphore?

A semaphore is a primitive used to provide synchronization between different processes or threads. Unlike a mutex, which is designed effectively as a lock, a semaphore is more like a counter or a signal tracker.

The text classifies semaphores into three categories, though this chapter focuses on the first two (Posix):

  1. Posix Named Semaphores: Identified by a name (like a filename) and can be used by unrelated processes.
  2. Posix Memory-Based Semaphores: Stored in shared memory and used by threads or related processes.
  3. System V Semaphores: Maintained by the kernel (covered later in Chapter 11).
2. Core Operations

Stevens defines three fundamental operations that must be atomic (performed without interruption):

  • Create: Initialize the semaphore to a specific value.
  • Wait (P operation): * Tests the value of the semaphore.
    • If the value is 0, the process blocks (waits).
    • If the value is , it decrements the value and proceeds.
  • Post (V operation): * Increments the value of the semaphore.
    • If any processes are blocked waiting for this semaphore, one is woken up.
3. Binary vs. Counting Semaphores
  • Binary Semaphore: Can only have the value 0 or 1. It functions very similarly to a Mutex (Mutual Exclusion).
  • Counting Semaphore: Can have any non-negative integer value. These are often used to track resources (e.g., the number of empty slots in a buffer).
4. Semaphores vs. Mutexes & Condition Variables

This is a critical distinction made in this section. While they can look similar, they behave differently in two key ways: A. Ownership

  • Mutex: Must be unlocked by the same thread that locked it.
  • Semaphore: Can be “posted” (incremented/unlocked) by a different thread or process than the one that waited (decremented/locked) it.
    • Example: A producer puts data in a buffer and posts a semaphore. The consumer waits on that semaphore to know data is ready. They are different threads interacting with the same lock. B. State Persistence
  • Condition Variable: If you signal a condition variable and no one is waiting, the signal is lost.
  • Semaphore: If you post to a semaphore, the value increments (state is saved). If a thread arrives later and waits, it sees that stored positive value and proceeds immediately without blocking.
5. The Producer-Consumer Logic (Figure 10.5)

The text provides pseudocode to illustrate how semaphores solve the producer-consumer problem without needing a separate mutex and condition variable.

Here is a summary of that logic:

// Producer Thread
sem_wait(&put);      // Wait for space (put semaphore)
place_data();        // Add data to buffer
sem_post(&get);      // Signal that data is available (increment get)
 
// Consumer Thread
sem_wait(&get);      // Wait for data (get semaphore)
process_data();      // Remove/use data from buffer
sem_post(&put);      // Signal that space is available (increment put)

Note: In this model, put counts empty slots (initialized to buffer size), and get counts filled slots (initialized to 0).

Graph View