Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 17

Resource Counting with Unnamed Semaphores

Recommended resources

Hello! Welcome to your next lesson.

In our previous session, we explored how pthread_rwlock_t optimizes performance for read-heavy workloads by allowing concurrent reads. This was a powerful step up from the all-or-nothing exclusivity of a standard mutex.

Today, we shift our focus to a different kind of synchronization challenge. Instead of managing access based on read vs. write operations, we'll learn to manage access to a finite number of resources. Your learning outcome for this lesson is to initialize and use unnamed semaphores (sem_t) for resource counting. You will discover that a semaphore is not a lock, but a more generalized signaling mechanism that is perfect for this task.

1. What is a Semaphore?

At its core, a semaphore is a non-negative integer counter that supports two fundamental, atomic operations:

  • sem_wait(): This operation decrements the semaphore's value. If the value is already zero, the calling thread blocks until another thread increments it.
  • sem_post(): This operation increments the semaphore's value, potentially unblocking a thread that is waiting in sem_wait().

Unlike a mutex, a semaphore doesn't have a concept of an "owner". Any thread can call sem_post() at any time, whereas with a mutex, only the thread that locked it can unlock it. This makes semaphores a tool for signaling and counting, not for enforcing exclusive access to a critical section in the same way a mutex does.

Counting Semaphores: Concept and Resource Management
This diagram illustrates the concept of a counting semaphore. The integer value tracks the number of available resources (like free buffers in a pool), and the `Pend()` (wait) and `Post()` operations allow tasks to safely acquire and release these resources.

Let's watch a short video that introduces the basic API and demonstrates the core concept.

Introduction to semaphores in C

The video "Introduction to semaphores in C" by CodeVault provides a practical walkthrough of the essential POSIX semaphore functions and their behavior.

Please watch from the beginning up to 08:42. The video will cover: Initialization: sem_init() and sem_destroy(). Core Operations: sem_wait() and sem_post() and how they compare to mutex locks. Internal Counter: A clear explanation of how the semaphore's internal integer value changes and causes threads to block or proceed.

As the video explained, if you initialize a semaphore with the value 1, it behaves much like a mutex. This is often called a binary semaphore. However, the real power for our purposes comes from using it as a counting semaphore.

2. Semaphores for Resource Counting

The central idea of a counting semaphore is to initialize its value to N, where N is the number of available resources.

  • A thread wishing to use a resource calls sem_wait(). If a resource is available (value > 0), the call succeeds, the counter is decremented, and the thread proceeds.
  • When the thread is finished with the resource, it calls sem_post(), incrementing the counter and signaling that the resource is available again.

If N threads all call sem_wait(), they will all succeed, and the semaphore's value will become 0. The (N+1)-th thread to call sem_wait() will block until one of the other threads calls sem_post().

Let's see this in action.

Introduction to semaphores in C

We'll continue with the same CodeVault video, which now demonstrates exactly how changing the initial value allows multiple threads to proceed.

Please watch from 08:42 to the end (11:32). Notice how initializing the semaphore to 2 allows two threads to enter the critical section concurrently, and initializing it to 4 allows all four threads in the example to run in parallel.

This demonstrates a simple but powerful application: throttling. Imagine you have a task that is memory-intensive. If 100 threads perform this task simultaneously, you might exhaust system memory. By using a semaphore initialized to a smaller number (say, 8), you can guarantee that no more than 8 threads will execute that memory-intensive code block at once.

This brings us to a general rule for initialization.

Semaphores

The textbook "Operating Systems: Three Easy Pieces" (OSTEP) provides a useful heuristic for setting a semaphore's initial value. This perspective is key to using them correctly for resource management.

Please read the short aside titled "ASIDE: SETTING THE VALUE OF A SEMAPHORE". It provides a simple, effective rule of thumb.

The rule is simple: Initialize a semaphore to the number of resources you are willing to give away immediately. For a lock, that's 1. For throttling 8 threads, it's 8. For a resource that is not yet available, it's 0.

3. Case Study: The Producer-Consumer Problem

The most classic application of counting semaphores is solving the producer-consumer problem. In this scenario:

  • One or more producer threads generate data and place it into a shared, fixed-size buffer.
  • One or more consumer threads retrieve data from the buffer and process it.

We face two synchronization challenges:

  1. Producers must wait if the buffer is full.
  2. Consumers must wait if the buffer is empty.

This is a resource counting problem! We have two types of resources to track:

  1. The number of full slots (items available to be consumed).
  2. The number of empty slots (spaces available for production).

We can solve this elegantly with two semaphores.

Producer - Consumer Problem in Multi-Threading

This CodeVault video, "Producer - Consumer Problem in Multi-Threading", builds the entire solution from the ground up. It starts by showing the problems with a naive approach and then implements a robust solution using semaphores.

Please watch from 15:01 to 18:56. This section focuses on the core semaphore logic: Initialization: It creates two semaphores, sem_empty and sem_full, and initializes them based on the buffer size (sem_empty starts at BUFFER_SIZE, sem_full starts at 0). Synchronization: It shows how the producer waits on sem_empty and posts on sem_full, and how the consumer does the opposite.

This is the canonical pattern. Let's formalize the logic:

  • sem_empty: Initialized to buffer size N. Producers wait() on it before adding an item. Consumers post() to it after removing an item.
  • sem_full: Initialized to 0. Consumers wait() on it before removing an item. Producers post() to it after adding an item.
Test your understanding!

You are implementing a thread-safe object pool that manages 10 reusable database connection objects. The functions are db_connection_t* acquire_connection() and void release_connection(db_connection_t* conn).

You decide to use a single semaphore, sem_t available_connections;, to manage the pool.

  1. What should its initial value be?
  2. Which semaphore operation (sem_wait or sem_post) belongs in acquire_connection()?
  3. Which semaphore operation belongs in release_connection()?
Show answer
  1. Initial Value: The semaphore should be initialized to 10, the number of resources available at the start. sem_init(&available_connections, 0, 10);
  2. acquire_connection(): This function must call sem_wait(&available_connections);. If the count is greater than zero, it will succeed, and the thread gets a connection. If the count is zero, the thread blocks until a connection is released.
  3. release_connection(): This function must call sem_post(&available_connections);. This increments the counter, signaling that a connection has been returned to the pool and potentially waking up a waiting thread.

4. Semaphores and Mutexes: A Necessary Partnership

Watching the producer-consumer video, you may have noticed something. The semaphore logic prevents a producer from running when the buffer is full, but it doesn't prevent two producers from running at the same time when there is space. If two producers try to write to buffer[count] simultaneously, you still have a race condition.

Semaphores manage the high-level signaling ("is there space?"), but they don't provide mutual exclusion for the critical section where the shared data structure is actually modified. For that, you still need a mutex.

The complete, correct producer-consumer pattern uses two semaphores and one mutex.

Semaphores & Synchronization

The OSTEP chapter on Semaphores and the Illinois CS341 course page both provide excellent, detailed explanations of the complete producer-consumer solution, including the crucial role of the mutex.

First, in the OSTEP PDF ("Semaphores"), read section 31.4, "The Producer/Consumer (Bounded Buffer) Problem". Pay close attention to the evolution of the solution: from a semaphore-only version that has a race condition, to a version that incorrectly adds a mutex and causes deadlock, and finally to the correct implementation. This analysis is invaluable.

Synchronization

Next, this resource from the University of Illinois provides another take on a similar problem (a thread-safe stack) that reinforces the same pattern.

In the "Synchronization" web page, read the section "Using Semaphores". It walks through several incorrect sketches before arriving at the correct solution that combines semaphores for counting with a mutex for the critical section. This repetition from a different perspective will solidify your understanding.

The key takeaway from both resources is the final, correct pattern:

  • Producer:

    1. sem_wait(&sem_empty); // Wait for an empty slot.
    2. pthread_mutex_lock(&mutex); // Lock for exclusive access to the buffer.
    3. ... modify buffer ...
    4. pthread_mutex_unlock(&mutex);
    5. sem_post(&sem_full); // Signal that a slot is now full.

  • Consumer:

    1. sem_wait(&sem_full); // Wait for a full slot.
    2. pthread_mutex_lock(&mutex); // Lock for exclusive access to the buffer.
    3. ... modify buffer ...
    4. pthread_mutex_unlock(&mutex);
    5. sem_post(&sem_empty); // Signal that a slot is now empty.

Note the order: you acquire the resource semaphore before the mutex. The OSTEP chapter clearly explained why reversing this order leads to deadlock.

Conclusion

Today you've added a versatile new tool to your concurrency toolkit. You've learned that semaphores are fundamentally different from mutexes; they are counters used for signaling and managing access to a finite number of resources.

Key Takeaways:

  • A semaphore is a counter that can be atomically decremented (sem_wait) and incremented (sem_post).
  • sem_wait blocks if the semaphore's value is zero, providing a mechanism for threads to wait for a condition or resource.
  • The initial value of a semaphore is set with sem_init() and represents the number of resources available at startup.
  • The producer-consumer pattern is a classic use case, employing two semaphores to count empty and full slots in a buffer.
  • Semaphores handle the high-level coordination (waiting for resources), but a mutex is still required to protect the critical sections where shared data is directly manipulated.

Preview of the Next Lesson:
You've now mastered the theory and seen the canonical example. In our next lesson, you will put this knowledge into practice to implement a simple resource pool protected by a semaphore. This will involve building a reusable component that could manage a pool of database connections, worker threads, or any other finite resource, solidifying the concepts from today's lesson.