Week 6 – CST– 334 Operating System

Module 6 – Concurrency Continued (Semaphores)

This week we continued with concurrency and covered semaphores. Semaphores were invented by Edsger Dijkstra and colleagues. A semaphore is a synchronization primitive. It is an object with an integer value that can be manipulated by two routines, sem_wait() and sem_post. The semaphore must first be initialized to determine the behavior. A binary semaphore is a lock. By initializing the semaphore value to 1 it can behave like a lock. For example, thread1 will call sem_wait() and decrement the value to 0 which will allow the thread to enter the critical section. If thread2 calls sem_wait() while thread1 is still in the critical section, it will decrement the semaphore value to -1 and thread2 will go to sleep. Once thread1 is done with the critical section, it will call sem_post() incrementing the value to 0 and waking thread2 so it can acquire the lock to the critical section which will in turn decrement the value back to -1.

Chapter 31 uses a problem called the bounded buffer to demonstrate how to use semaphores to solve concurrency problems. In the problem, producers produce something, and consumers consume what the producers produce. They use two semaphores, empty and full. When the buffer is full, the producers signal the consumers to consume. When the buffer is empty, the consumers signal the producers to produce. In other words, the producers wait for empty and signal when full and the consumers wait for full and signal when empty. Lastly, to avoid deadlock, we must put the mutex lock just around the critical sections, which in this case is put() and get().

Chapter 32 covered common concurrency problems. They break down the bugs to non-deadlock and deadlock bugs. Non-deadlock bugs include atomicity-violation bugs and order-violation bugs. Atomicity -violation bugs occur when the code is intended to be atomic, but atomicity is not enforced. Most of the time, the solution is to simply add locks around the shared variable references to ensure any thread that wants to access the critical section must acquire the lock and only one thread can have the lock at a time. Order-violation bugs occur when the execution of threads is not done in proper order. For example, A should always be executed before B, but the order is not enforced. To fix this type of bug you must use locks, condition variables, and state variables to enforce the order of execution.

Deadlock bugs occur when thread1 is holding lock1 and waiting for lock2 and thread2 has lock2 and is waiting for lock1to be released. In this situation both threads are waiting for each other and cannot run. For a deadlock to occur, four conditions must take place; mutual exclusion, hold-and-wait, no preemption, and circular wait. Therefore, to prevent deadlock, you must prevent one of these four conditions from happening.