Synchronization cont. #

Since these could output in any order, we can setup semaphores to ensure the run order.

Bounded buffer problem #

• full and empty are counting semaphores.
  • full notifies consumers how many items are there
  • empty notifies producers how many empty slots available
• mutex is a binary semaphore.

• mutex starts at 1, “unlocked”, so the first process can have mutual exclusion
• full is set to 0, and empty is set to n, because all slots are available

• The first wait(empty) checks if there is an empty slot
• wait(mutex) checks if there is a process accessing the shared buffer
• wait(full) checks if there is any items to consume

Consider switching the order of the first to wait functions, to:

wait(mutex);
wait(empty);

This would have the consequences of being able to get mutual exclusion first, then all other processes would be prevented from running. But then if the buffer is already full it won’t ever get past the wait(empty). So, the order cannot be swapped.

Next, consider switching the order of the signal functions:

signal(full);
signal(mutex);

This is actually okay because the order of the unlock does not matter as much. The other process is waiting for both locks to continue.

The readers writers problem #

This is a slight difference in the producer consumer problem, because readers actually don’t change the shared buffer (just read it). Also, any number of readers can access data simultaneously.

• multiple readers are reading database
• new readers may join
• new writer must waiting

• new readers must wait
• new writers must wait

• if a new writer arrives at \( t = 1 \) , it waits
• if a new reader arrives at \( t=2 \) , there are 2 variations:
  • skip the line and join the other readers, prioritizing readers
  • wait behind the writer, prioritizing writers

Why ensure mutual exclusion for updating readcount? We need to make sure that the readcount variable is being updated atomically.

Note: The solution to the second readers writers problem (prioritizing writers) is more complex. It requires five variables.

The dining philosophers problem #

• you can only use your adjacent chopsticks
• you can only pick up one chopstick each turn
• you can eat when you have both chopsticks
• the goal is to order the picking up and placing of chopsticks without deadlock or starvation

So if everyone starts by picking up the left chopstick, then the right chopstick, it will end up in deadlock.

We can treat each philosopher as a process, and the chopstick as a competing resource.

• wait(fork[i]) waits for the left chopstick
• wait(fork[i+1 % 5]); waits for the right chopstick
• then they may eat
• then they put the chopsticks back down right then left using the signal functions
• however, this current state results in deadlock

Note: fork here is the chopstick, for brevity.