CST334 - Week 29

This week we learned about semaphores and common concurrency problems.

A semaphore is an object with an integer value that is used with two calls, sem_wait() and sem_post(). One must initialize the value of the semaphore and this value is very important as it determines its behavior. Sem_wait() will either decrement the value of the semaphore and return right away or, if the value is negative, it will wait for the sem_post(). Sem_post() will increment the value of the semaphore by one, and wake a waiting thread if there is one in the queue. Binary semaphores are used as locks for critical sections of code with the initial value of one. Semaphores are also useful as ordering primitives to order events in a concurrent program and can aid in the solution of the bounded buffer producer/consumer problem. Some data structures might have different kinds of entry points that require different kinds of locks. For example, a data structure can have a method that writes in the data structure, which would require locks to ensure atomic and secure updates of the data but also may need to just be read from, which can be done by many processes or threads concurrently. Semaphores can be used here when acquiring read and write locks. Semaphores can also be used to help solve numerous other problems such as the dining philosophers problem.

Non-deadlock bugs are the most common and make up the majority of bugs in terms of concurrency. Two of the main types are atomicity violation bugs and order violation bugs. Atomicity violation is when a specific part of code should be run atomically, but this atomicity is not enforced when the code executes. Locks can be used in this case to ensure atomicity. Order violation bugs occur when there is a desired order in the code, but it is also not enforced when the code executes. Using condition variables with corresponding locks are one solution to this problem.

Deadlock bugs are also common in concurrency and can occur when the following four conditions exist:

1. Mutual exclusion exists; each thread has exclusive control of a lock it acquires.

2. Threads hold-and-wait, meaning that a thread will hold a lock it acquires and waits until it can acquire another lock that is currently held.

3. There is no preemption; locks cannot be taken from the threads that have acquired them by force.

4. There exists a circular wait among the threads; there is a chain of threads in which a thread holds a lock that the next thread in the chain is waiting to acquire. 

There are a few different ways to tackle the problem of deadlock. Prevention aims to prevent one of these conditions from being true, thereby making it impossible for deadlock to occur. These solutions can target a specific condition such as ensuring a total ordering for acquiring locks to combat the circular wait condition or require that all locks be acquired atomically and all at once to prevent a hold-and-wait situation. Another way is through avoidance. A scheduler can schedule threads in a way that deadlock cannot occur. For example, if a few threads all need to acquire the same few locks, they can be scheduled one after the other, but concurrently with other threads that don't require any or all of those locks. This solution can be effective, but limits concurrency and slows performance.

The last solution is the detect and recover method. This method allows deadlocks to occur and implements an action to take when a deadlock is detected. This solution is only a good idea if the deadlock occurs so rarely that this "non-solution" can be used. For example, a deadlock may require a rebooting of the system, but if this happens so infrequently, it wouldn't be such an issue.