CST 334 - Week 6

Semaphores

This week we learned about semaphores, a data type consisting of a lock/condition variable combo and an integer. Semaphores can be used like mutex locks if they are initialized to 1. This is known as a binary semaphore. When sem_wait() is called, the value of the semaphore is decreased by 1. If the result is negative, the calling thread is blocked and placed in a waiting list. When sem_post() is called, the semaphore's value is increased by 1 and a thread in the waiting list is allowed to continue. While this may replace the standard mutex, semaphores can be used in even more intricate ways to enable synchronization of concurrent threads (see the producer-consumer problem or reader-writer locks). 

Problems with Concurrency

Two of the most common concurrency bugs come from atomicity violations and order violations. Atomicity violations can be avoided by correctly locking critical code sections, and order violations can be avoided by either using locks (with condition variables) or semaphores to guarantee threads run in a particular order. Another serious, but less common, concurrency issue results from deadlock. Deadlock occurs when a thread holds a resource exclusively while waiting to obtain a resource from another thread, which is in-turn waiting (either directly or in some circular fashion) for the first thread's resource. 

There are many ways to prevent deadlock: through the total ordering or partial ordering of lock acquisition; by acquiring all locks upfront (using a mutex to ensure atomicity); by calling the pthread's trylock() function (which may still result in livelock, where threads get stuck in infinite loops trying to obtain each other's locks); or by using a special hardware compare-and-swap instruction (such as CMPXCHG on x86).