2023-10-30

# In the last few lectures, we looked at

• Condition variables (CVs)
• wait() and signal()
• Solution to the sequencing problem (parent and child)
• Producer-consumer problem
• using locks and CVs
• Semaphores
• sem_init, sem_wait and sem_post
• Using semaphores as locks
• Using semaphores as CVs
• Yesterday’s solution works but a writer may starve
• Think: How to prevent starvation?

# Producer-consumer problem using semaphores

• Check the handout
• Does Solution 1 work?
• If $$max=1$$, it works
• What about $$max>1$$ and multiple producers/consumes?
• Race condition
• Producers $$Pa$$ and $$Pb$$
• $$Pa$$ do_fill’s first buffer entry
• Before fillptr increments, $$Pb$$ runs
• $$Pb$$ overwrites first buffer entry

# Solution 2

• Check the handout
• Does Solution 1 work?
• No, a deadlock may occur
• Scenario:
• Two threads: $$P$$ and $$C$$
• $$C$$ acquires mutex, calls wait(full), sleeps
• $$P$$ calls wait(mutex) and is now stuck waitin

# Working Solution

• Fill in a fix to Solution 2 so that producer consumer problem is solved without deadlock
• Solution 2 problem: $$C$$ holds mutex and is waiting for the someone to signal full. $$P$$ could signal full but is waiting for the mutex
• Fix: reduce the lock scope

# Working solution

void *producer(void *arg)
{
int i;
for (i = 0; i < loops; i++) {
Sem_wait(&empty);
Sem_wait(&mutex);
do_fill(i);
Sem_post(&mutex);
Sem_post(&full);
}
}

void *consumer(void *arg)
{
int tmp = 0;
while (tmp != -1) {
Sem_wait(&full);
Sem_wait(&mutex);
tmp = do_get();
Sem_post(&mutex);
Sem_post(&empty);
printf("%d\n", tmp);
}
}

# The Dining Philosophers

• Five philosophers
• Between each pair of philosophers is a single fork
• The philosophers each have times where they think, and don’t need any forks, and times where they eat
• In order to eat, a philosopher needs two forks: the left and the right ones
• The contention is for these forks

# The Dining Philosophers (Cont.)

## Referring to the left and the right

int left(int p) {  return  p; }

int right(int p) { return (p + 1) % 5;}

## What philosophers do

while (1) {
think();
get_forks(p);
eat();
put_forks(p);
}

# Solution 1

void getforks() {
sem_wait(forks[left(p)]);
sem_wait(forks[right(p)]);
}

void putforks() {
sem_post(forks[left(p)]);
sem_post(forks[right(p)]);
}

# Solution 2

void getforks() {
if (p == 4) {
sem_wait(forks[right(p)]);
sem_wait(forks[left(p)]);
}
else {
sem_wait(forks[left(p)]);
sem_wait(forks[right(p)]);
}
}

# Implementing semaphores using CV and locks

typedef struct __Zem_t {
int             value;
pthread_cond_t  cond; // cond_signal(c), cond_wait(c, m)
} Zem_t;

// can assume only called by one thread
void
Zem_init(Zem_t *z, int value) {
z->value = value;
// init lock and cond
}

void Zem_wait(Zem_t *z) {
// use semaphore definition as your guide
}

void Zem_post(Zem_t *z) {
// use semaphore definition as your guide
}

# Solution

void Zem_wait(Zem_t *z) {
Mutex_lock(&z->lock);
while (z->value <= 0)
Cond_wait(&z->cond, &z->lock);
z->value--;
Mutex_unlock(&z->lock);
}

void Zem_post(Zem_t *z) {
Mutex_lock(&z->lock);
z->value++;
Cond_signal(&z->cond);
Mutex_unlock(&z->lock);
}