13 - Semaphores

#concurrency #threads

Class: CSCE-313

Notes:

What is the full producer-consumer problem?

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:

image-37.png424

Notes:

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;
}

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;
    }
}

Counting Semaphores

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

image-40.png378x235

Semaphore Implementation

image-41.png562x346

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();
    }
};

Notes:

Semaphores: the signal pattern

image-42.png599x328

Notes:

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();
  1. 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:

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)

image-43.png401x67

Notes:

Correctness constraints

...

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.

image-46.png421

Notes:

Full Solution to Bounded Buffer

image-44.png594x351

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:

More Thoughts

Is order of wait’s important?

Yes. because of deadlocks

image-45.png551

Notes:

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

image-47.png555x273

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

image-48.png382

We want to guarantee that a1 happens before b2 and b1 happens before a2.

Notes: