13 - Semaphores

Class: CSCE-313

Notes:

What is the full producer-consumer problem?

• The producer-consumer problem is a problem in which producers generate data and consumers retrieve and use the data concurrently.
• The producers and consumers share the same fixed-sized memory buffer.
• Earlier we looked at a version of the producer-consumer problem in which the producer never waits
  • Can we extend it to the case when both need to wait?

Semaphores (counting)

A semaphore is a non-negative integer variable, shared among multiple processes. They are used for access control to a common resource in a concurrent environment.

A Semaphore supports the following two atomic operations:

• wait(): Waits until value $>0$, then decrements it by 1
  • Think of this as the wait() operation, or the lock() operation
• post(): Increments value by 1
  • May wake up a waiting thread
  • Analogous to the signal() function, or the unlock() operation.

Notes:

• What is a Semaphore? A semaphore is essentially a thread-safe, non-negative integer variable shared among processes. It is used to control access to a common resource.
• The Two Atomic Operations: Semaphores are manipulated using exactly two fundamental operations, both of which are strictly atomic to prevent race conditions:
  • wait(): If the semaphore's value is greater than 0, it decrements the value by 1 and the thread continues executing. If the value is exactly 0, the thread is completely blocked and goes to sleep until the value goes up.
  • post(): Increments the semaphore's value by 1. If there are threads currently sleeping (because they called wait() when the value was 0), this operation automatically wakes one of them up.
• The "Room Capacity" Analogy: Imagine a room that holds exactly 100 people. You initialize the semaphore to 100. Every time a thread enters the room, it calls wait() (decrementing the counter). Once 100 threads are inside, the counter hits 0. The 101st thread that calls wait() will be blocked at the door. When a thread leaves the room, it calls post(), which increments the counter and allows one waiting thread to enter.
• Strict Atomicity: The hardware/OS guarantees that two simultaneous wait() calls will never accidentally push the counter below zero, and a thread going to sleep will never miss a simultaneous post() wake-up.

Question on midterm

Someone that din't want to use swapcontext

// Switch context from CurrentThread to next_thread
void thread_switch (thread_t *next_thread) {
    getcontext (&CurrentThread->ctx);
    CurrentThread = next_thread;
    setcontext (&CurrentThread->ctx);
    return;
}

• Later when you are going to be restored, you are going to return from the getcontext() call, so you will once again switch to that of next_thread.
• The problem is that you need to be able to figure out that this is the first time you are actually setting context.

Correct answer:

// Switch context from CurrentThread to next_thread
void thread_switch (thread_t *next_thread) {
    volatile bool first_time = true;
    getcontext (&CurrentThread->ctx);
    if(first_time) {
        first_time = false;
        CurrentThread = next_thread;
        setcontext (&CurrentThread->ctx);
        return;
    }
}

• Now before you switch to the other guy, you set the first_time variable to false
• Now when you return from getcontext() you will find that first_time is false so you won't change to it.
• If you mark first_time as volatile, then it is not loaded into a registers, it is kept in memory only

Counting Semaphores

• -1 on entry
• entangled. +1 on exit

These are entangled versions of the same counter but they are atomic. The semaphore allows you to be able to control the number of people in the theater. Once this value becomes 0, they will block.

Semaphores

A semaphore is like a key hat allows a task to carry out some operation or to access a resource.

The only operations allowed are wait() and post().

Operations must be atomic

• Two wait()s together cannot decrement the value below zero.
• Similarly, a thread going to sleep in wait() won't miss wakeup from post, even if they both happen at the "same" time.

Semaphore Implementation

class Semaphore{
private:
    int value;
    mutex m;
    condition_variable cv;
public:
    Semaphore (int _v):value(_v){}
    
    void wait(){
        unique lock<mutex> l(m);
        // wait until the value is positive
        cv.wait(l, [this]{return value > 0;});
        value--;
    }
    
    void post(){
        unique_lock<mutex>
        value++;
        cv.notify_one();
    }
};

• Wait until value>0, so it can be decremented. Then decrement it.
• Always notify on the way out, notify_all() is correct, but would lead to spurious wake ups

Notes:

• When you do notify_one() you are guaranteed that any waiter that is picked up, will be able to complete the task

Semaphores: the signal pattern

Notes:

• Scheduling Constraints: While semaphores can be used for mutual exclusion (like a standard lock), they are also fantastic for enforcing execution order (e.g., forcing Thread 2 to wait for Thread 1 to finish a task).
• The Setup: To use a semaphore for signaling, you initialize its value to 0.
• The Execution Flow:
  • If Thread 2 (the consumer/waiter) executes first, it calls wait() on the 0 value and instantly goes to sleep. When Thread 1 finishes its work, it calls post(), incrementing the counter to 1 and waking up Thread 2.
• The "No Lost Signal" Advantage (Crucial Concept): Earlier, we saw that using a raw condition variable signal() without a state variable is dangerous because if the sender signals before the receiver is asleep, the signal is permanently lost. Semaphores fix this inherently because they store state (the integer). If Thread 1 finishes early and calls post(), the semaphore becomes 1. When Thread 2 finally runs and calls wait(), it simply sees the 1, decrements it to 0, and proceeds immediately without ever blocking.
• Semaphores vs. Condition Variables: Semaphores often make code cleaner and easier to reason about, but they do not add any new theoretical capabilities. Everything you can do with a semaphore can be recreated using a combination of condition variables and mutexes.

Code Semaphores: the signal pattern

sem_t sem;

void *thread (void *arg) {
	printf("Child working...");
	fflush(stdout);
	sleep(4);
	printf("finished.\n");
	sleep(1);
	sem_post(&sem);
}

int main () {
	sem_init(&sem, 0, 0);
	pthread_t t1;
	pthread_create(&t1, NULL, thread, NULL);
	sem_wait(&sem);
	printf("Parent received signal from child.\n");
	pthread_join(t1, NULL);
	sem_destroy(&sem);
	return 0;
}

Two Uses of Semaphores

1. For mutual exclusion (initial value = 1). Also called "Binary Semaphore".

semaphore.wait();
// Critical section goes here
semaphore.post();

2. For scheduling constraints (initial value $=0$ ). Allow thread 1 to wait for a signal from thread 2 , i.e., thread 2 schedules thread 1 when a given constraint is satisfied.

Ex: Suppose you had to implement ThreadJoin which must wait for a thread to terminate:

// Initial value of semaphore = 0
ThreadJoin { // the joiner calls this
    semaphore.wait();
}
ThreadFinish { // the joinee calls this
    semaphore.post();
}

Notes:

• Use 1: Mutual Exclusion (Binary Semaphore): By initializing a semaphore's value to exactly 1, you create a "binary semaphore" that acts identically to a mutex. The first thread calls wait() (decrementing it to 0) and enters the critical section. Any other thread that calls wait() blocks until the first thread calls post().
• Use 2: Scheduling / Execution Ordering: By initializing a semaphore's value to 0, you can enforce strict execution ordering. For example, if you are building a custom ThreadJoin, the joining thread instantly blocks when it calls wait() on the 0 value. It will safely sleep until the finishing thread calls post(), successfully scheduling the joiner to wake up.
• The Big Difference (Ownership): A traditional mutex has strict ownership rules: only the specific thread that acquired the mutex is legally allowed to release it. A semaphore has no ownership rules. Any thread can call post() on a semaphore at any time. This makes semaphores extremely flexible for complex signaling, but it also requires you to be very careful, as a bug in one thread could accidentally post and unlock a completely different thread prematurely.

Producer-consumer with a bounded buffer

Problem Definition

1. A producer puts data into a shared buffer
2. A consumer takes them out
3. We need synchronization to coordinate between producer/consumer

We do not want the producer and consumer to have to work in lockstep (buffer size 1), so we put a fixed-size buffer between them.

1. We need to synchronize access to this buffer
2. The producer needs to wait if buffer is full (e.g refill a vending machine)
3. The consumer needs to wait if buffer is empty (e.g. customer waits if the machine is empty)

Notes:

• The Goal (Avoiding Lockstep): If we only had a buffer size of 1, the producer and consumer would be forced to work in perfect "lockstep"—the producer makes one item and waits, the consumer takes one item and waits. To make the system faster and more concurrent, we place a fixed-size buffer (like an array or queue) between them.
• The Vending Machine Analogy: Think of the buffer like a vending machine.
  1. The Producer (restocker) must wait if the machine is completely full.
  2. The Consumer (customer) must wait if the machine is completely empty.
• Encoding State: We can elegantly manage this by using counting semaphores to directly encode the number of free slots and filled slots.

Correctness constraints

Correctness Constraints

1. Consumer must wait for producer to fill slots, if empty (scheduling constraint)
2. Producer must wait for consumer to make room in buffer, if full (scheduling constraint)
3. Only one thread can manipulate the buffer queue at a time (mutual exclusion using lock)

Rate (flow) control

• Consumer is limited by Production Rate
• Producer is limited by buffer size and consequently Consumption Rate

Applications: Networks, Inter Process Communication etc.

Semaphores on bounded buffer

1. The producer decreases the number of empty slots and increases the number of occupied slots:
   • emptySlots.wait(), fullSlots.post()
2. The consumer decreases the number of occupied slots and increases the number of empty slots:
   • fullSlots.wait(), emptySlots.post()

One thread is creating space, the other one is filling space.

Notes:

• When a producer is adding an item, they need an index
• Sync is just a thing for accessing this index

Full Solution to Bounded Buffer

Semaphore fullSlots = 0;        // Initially, no coke
Semaphore emptySlots = bufSize; //Initially all empty
Semaphore sync = 1;             // No one is using machine

Producer(item) {
    emptySlots.wait();    // Once acquired, never violated
    sync.wait();          // Wait until machine is free
    enqueue(item);
    sync.post();
    fullSlots.post();     // Notify there is more coke
}
Consumer() {
    fullSlots.wait();     // Check if there's a coke
    sync.wait();          // Wait until machine free
    item = dequeue();
    sync.post();
    emptySlots.post();    // tell producer to produce more
    return item;
}

Notes:

• The 3-Semaphore Architecture: The perfect solution requires exactly three semaphores:
  1. emptySlots: Initialized to the maximum buffer size. Tracks how much space is left.
  2. fullSlots: Initialized to 0. Tracks how many items are ready to be consumed.
  3. sync: Initialized to 1. Acts as a standard binary semaphore (mutex) to provide mutual exclusion so threads don't corrupt the actual array/queue while reading or writing.
• The Magic of "Ownership": When the producer successfully passes emptySlots.wait(), it has effectively "reserved" or "owns" one empty slot in the buffer. Because atomic semaphores guarantee correctness, the producer knows with 100% certainty that there is room for its item. The condition will not magically change.
• The Execution Flow:
  • Producer: Wait for an empty slot → lock the buffer (sync) → insert item → unlock the buffer → post to fullSlots (waking up any sleeping consumers).
  • Consumer: Wait for a full slot → lock the buffer (sync) → remove item → unlock the buffer → post to emptySlots (waking up any sleeping producers).

More Thoughts

Is order of wait’s important?

Yes. because of deadlocks

Notes:

• If you were waiting for a slot to become empty, then you may never actually get it because you own the mutual exclusion semaphore, and your consumer will never be able to have it

Is order of posts important? No, except that it might affect scheduling efficiency.

What if we have 2 producers or 2 consumers? Do we need to change anything?
No.

Producer(item) {
	emptySlots.wait();
	sync.wait();
	Enqueue(item);
	sync.post();
	fullSlots.post();
}

Consumer() {
	fullSlots.wait();
	sync.wait();
	item = Dequeue();
	sync.post();
	emptySlots.post();
	return item;
}

The rendezvous pattern

Generalize the "signal" pattern so that it works both ways. Thread A has to wait for Thread B and vice versa. In other words, given this code

We want to guarantee that $a_1$ happens before $b_2$ and $b_1$ happens before $a_2$.

Notes:

• The Concept (Two-Way Signaling): The rendezvous pattern (which translates to a meeting at an agreed time and place) is an extension of the basic semaphore "signal" pattern. Instead of just one thread waiting for another, both threads must wait for each other to reach a specific point before either is allowed to proceed.
• The Goal (The Barrier): Imagine Thread A executes a1​ then a2​, and Thread B executes b1​ then b2​. You want to build a "barrier" in the middle so that a1​ is guaranteed to finish before b2​ starts, and b1​ is guaranteed to finish before a2​ starts.
• The Implementation: To achieve this mutual waiting, you must use two separate semaphores (both initialized to 0) so the threads can signal each other.
• The Execution Flow:
  • Thread A finishes a1​, calls post() on Thread B's semaphore (sending the "I have arrived" signal), and then immediately calls wait() on its own semaphore.
  • Thread B finishes b1​, calls post() on Thread A's semaphore, and then calls wait() on its own semaphore.
  • Because they both post before they wait, whichever thread gets to the barrier first will sleep until the second thread arrives and wakes it up. Once both have arrived, they both cross the barrier and proceed to a2​ and b2​.