CST334 week 6 (30/100)

 Josh Goldberg

CST 334-40_2262

Apr 14, 2026

Journal Entry Week 6

This week we covered how to write proper sync barriers for threads to prevent a variety of locking conditions. We started by reviewing condition variables, which let a thread sleep until a signal is generated by another thread that the sleeping one should wake up. This uses pthread_cond_wait and pthread_cond_signal or pthread_cond_broadcast to wake one or all threads waiting on the CV, respectively. The Anderson-Dhalin method is a recipe to write these code patterns: 1. Design the class as usual, 2. Add locks, 3. lock/unlock around the method, 4. add CVs with names that accurately describe the condition, 5. Signal after the state changes, and 6. Add waits inside a loop. The loop is important to deal with spurious wakeups.

We discussed using semaphores instead of CVs because semaphores hold a value. They are useful for different patterns with the same constructs such as locking (like with CVs), ordering and joining, and n-concurrent access. We reviewed a producer/consumer pattern with semaphores that uses three semaphores to indicate empty, full, and a mutex, and that the empty/full semaphore waits should be outside the mutex or else there can be a deadlock. The dining philosopher problem was reviewed. It describes a circular lock pattern that could result in a deadlock. The solution is to have one of the philosophers grab forks in reverse order from the others. 

Synchronization barriers were discussed, where all thread execute some work then “rendezvous” by waiting at a barrier until all threads are done. A turnstile pattern was discussed where after each thread passes through the barrier it signals for the next waiting thread to proceed such that all threads will move and continue past the barrier. A conditional wait pattern can also be used where an inequality condition is the barrier and the first thread that passes through (the last thread to arrive) signals that the remainder can continue. To be reusable, barriers need to be reset once all threads pass through. The count variable must be decremented, and because it is shared it needs to be locked in a mutex.

We reviewed concurrency bugs and deadlocks. Atomicity violations are found in check-and-set patterns where the state can be modified between the check and the set. The fix is to wrap this in a lock. Order violations are when we assume that one thread always runs before another. Using a semaphore is an easy way to enforce ordering. Deadlocks and livelocks were also discussed. For a deadlock there are four necessary conditions: mutual exclusion, hold and wait, no preemption, and a circular wait. All four must be present for a deadlock to be possible. We discussed methods of preventing each of those conditions. Deadlocks are easy to detect because execution halts. Livelocks spin the cpu and are harder to detect because the threads are actively passing control back and forth in lockstep. Adding some randomized backoff before retrying the lock can break a livelock.

Sharing resources is a critical responsibility of an operating system. This week we looked at the patterns of how sharing can fail and what tools are available to prevent these failures. Last week was an intro to threads and this week is a review in how to make them not fail. Week 7 is about persistence, which introduces slow I/O where some of these locking issues frequently occur because they are shared not just between threads but between processes too. Semaphores can be a construct not just between threads but also between processes, so this will probably come up.