Jun 27, 2024 | thursday 9:19 pm
Next, I will be going over some of the puzzles I thought were interesting from some classic concurrency problems I solved from here. Try to solve them first before looking at my (or the book’s) solution!
IMPORTANT: All of these puzzles mainly use semaphores to solve the concurrency problems. A semaphore is basically an integer that can only be incremented or decremented. When a thread decrements a semaphore, if the result is negative, the thread blocks itself until another thread increments the semaphore.
context: Two threads A and B must both complete statement x before either starts on statement y.
Thread A Thread B
--------- ---------
statement x statement x
--- Both must arrive before either can proceed ---
statement y statement y
my solution:
Global
---------
arrivedA = Semaphore(0)
arrivedB = Semaphore(0)
Thread A Thread B
--------- ---------
statement x statement x
arrivedA.signal() arrivedB.signal()
arrivedB.wait() arrivedA.wait()
--- Both must arrive before either can proceed ---
statement y statement y
justification: Considering there are two possible scenarios (either A or B finishes statement x first), I use to semaphores to keep track of whichever one occurs, the faster thread must wait on the other before proceeding.
context: A generalization of a mutex, or mutual exclusion, only allows one thread in the critical region at a time. This generalization allows n threads in the critical region at the same time. Iconically it can be compared to a busy nightclub, where security enforces a maximum number of people allowed inside.
my solution:
Global
---------
n = ?
mutex = Semaphore(n)
Thread 1 ,..., Thread X
------------------------
mutex.wait()
〵(^ o ^)/ (dancing)
mutex.signal()
justification When one person enters the nightclub, the capacity goes up until the limit n. When someone leaves, the capacity goes down and security can let +1 person back in.
context: A generalization of rendezvous, n threads must finish running the rendezvous section before moving on.
my solution:
Global
---------
n = # of threads
mutex = Semaphore(n)
barrier = Semaphore(0)
Thread 1 ,..., Thread X
------------------------
rendezvous
mutex.wait()
count++
mutex.signal()
if count == n: barrier.signal()
barrier.wait()
barrier.signal()
〵(^ o ^)/ (More dancing)
justification Once count has reached n, one waiting thread is unblocked, allowing it to pass the barrier and signal another barrier. Thus, all threads are able to move through the barrier and dance!