7 Synchronization

Semaphore

Integer value manipulated by two methods

1. Increment (aka V, up, sem_post())
2. Decrement: wait until value > 0, then decrease value (aka P, down, sem_wait())
   • Blocks until value is not 0.

• Binary semaphore: protect one resource (like mutex)
  • sem_wait() until resource available. Use resource, and sem_post() to release
  • Different threads can sem_wait() and sem_post(), unlike mutex.
• Counting semaphore: protect N resources
• Ordering semaphore: used to trigger events
  • Initialize sem = 0.
    • Process 1: X -> sem_wait() -> Y
    • Process 2: A -> sem_post()
  • P1 has to wait for P2 to complete A. Y must happen after A.

POSIX sem API

Unnamed

Initialize as a global variable

#include <semaphore.h>
int sem_init(sem_t *sem, int pshared, unsigned int value);
int sem_destroy(sem_t *sem);

Returns: 0 if OK, –1 on error

• sem_t *sem: Pointer to semaphore object.
• int pshared: If semaphore is meant to be shared with child processes, pass in non-zero value. Otherwise (i.e., shared among threads), pass in 0.
  • If shared among multiple processes, where to declare sem?

  • [[#^f7a1df

    Shared anonymous mapping]] with child using mmap() and then fork()

  • For unrelated processes, you may do (pseudo) file-based mapping, but clumsy
• unsigned int value: Initial value for the semaphore.

Named

More sharable across unrelated processes

sem_t *sem_open(char *name, int oflag, ... /* mode_t mode, unsigned int value*/ );
int sem_close(sem_t *sem);
int sem_unlink(char *name);

• sem_open() makes a fake file so processes can communicate
  • Returns: Pointer to semaphore if OK, SEM_FAILED on error

Operations

int sem_post(sem_t *sem);
int sem_wait(sem_t *sem);
int sem_trywait(sem_t *sem);
int sem_timedwait(sem_t *restrict sem,
                    const struct timespec *restrict tsptr);

• sem_post() never blocks
• sem_wait() blocks until semaphore value is positive
  • Sets errno to EINTR if interrupted by a signal
• sem_trywait() does NOT block, fails immediately if semaphore value is 0
  • Sets errno to EAGAIN if the semaphore is unavailable
• sem_timedwait() is the same as sem_wait() but with a timeout value
  • Sets errno to ETIMEDOUT if sem_timedwait() returns due to the timeout

Producer-Consumer Problem

Ring buffer (last element wraps to the beginning)

• Must track indices of first (consumer) and last (consumer) elements
• Use modulus for index

Semaphore

uint32_t buffer[N];

sem_t empty; // Number of empty slots
sem_t full;  // Number of filled slots
sem_t guard; // Mutex for ring buffer access

uint32_t pi = 0; // Producer index
uint32_t ci = 0; // Consumer index

int main() {
    sem_init(&empty, 0, N); 
    sem_init(&full,  0, 0);
    sem_init(&guard, 0, 1); // binary sem
}

void enqueue(uint32_t piece) {   // empty--, full++
    sem_wait(&empty);
    sem_wait(&guard);

    buffer[pi] = piece;
    pi = (pi + 1) % N;
    
    sem_post(&guard);
    sem_post(&full);
}

uint32_t dequeue() {   // empty++, full--
    uint32_t piece;
    sem_wait(&full);
    sem_wait(&guard);

    piece = buffer[ci];
    ci = (ci + 1) % N;
    
    sem_post(&guard);
    sem_post(&empty);
    return piece;    // or pointer to some bigger structure
}

Application: producer-consumer.c

• mutex lock needed for printing
• Terminating conditions
• Main focus is producer-consumer

Condition Variable

HW2 related

// condition variables, not associated with numbers
// Need separate counters
pthread_cond_t  empty_cond;   // producer wait for consumer signal
pthread_cond_t  full_cond;
pthread_mutex_t mutex;

void enqueue(uint32_t piece) {
    pthread_mutex_lock(&mutex);

    // Wait until there's space in the ring buffer
    while (is_full())
        pthread_cond_wait(&empty_cond, &mutex);
    // ...
    
    pthread_cond_signal(&full_cond);
    pthread_mutex_unlock(&mutex);
}

Java

Keyword synchronized: will be mutually excluded (locks around)