6.1 Background

• Create a scenario that shows in practice what a race condition is.
• Consider the code for the Consumer/Producer problem given in the textbook. Explain why the value of the counter variable may turn out to be incorrect.
• The classic Consumer/Producer Problem (a.k.a. Bounded-Buffer Problem)
• Why the counter value may be inconsistent (or incorrect) in the example given in the textbook?
• What is a race condition?

6.2 The Critical Section Problem

• Describe the general idea behind the Critical Section Problem (CSP).
• Show the general structure of a program with multiple processes or threads that models the CSP.
• Discuss how this structure might relate to the construction of solutions to the CSP.
• Describe the function of the entry section, the exit section, and the remainder section in the model of solution to the CSP presented in the textbook.
• Describe the importance of the three criteria that any solution to a CSP problem must meet:
  1. Mutual exclusion
  2. Progress
  3. Bounded waiting
• Explain why nonpreemptive kernels cannot encounter race conditions.

6.3 Peterson’s Solution

• Given the model of program for solving the CSP (in section 5.2), implement Peterson’s solution.
• Explain the shortcomings of Peterson’s solution.

5.4 Hardware Support for Synchronization

• Explain the concept of atomic operation and how it may help one to develop constructs that solve the CSP.
• Solve the CSP using the following instructions: test_and_set , swap, and compare_and_swap. Discuss whether a proposed solution meets the three criteria for CSP solutions.
• Compare algorithms in Figure 5.1, 5.2, 5.4, and 5.6. What are the differences? What are the common elements?
• Why does the solution in Figure 5.7 meet all three CSP solution criteria?

6.5 Mutex Locks

• Compare a mutex lock to a binary semaphore.
• Show how one can use a mutex lock to solve the basic mutual exclusion problem, in which an arbitrary number threads/processes try to modify the state of one shared data structure.
• Describe how the operations init, wait, and signal modify the state of a mutex lock.
• Should the system allow the operations on a mutex lock to be interrupted by the short-term scheduler? (That is, would it be ok for the scheduler to interrupt one of these operations and switch the CPU to a different process or thread?)
• Mutual exclusion problems can also be solved by spinlocks. Compare blocking mutex locks to spinlocks and identify the advantage(s) and disadvantage(s) of each.
• Propose a scenario in which a mutual exclusion problem is better solved by spinlocks.
• Propose a scenario in which a mutual exclusion problem is better solved by a blocking mutex lock.

6.6 Semaphores

• Describe the data structure of a semaphore and how the operations init, wait, and signal modify its state.
• Should the system allow the operations on a semaphore to be interrupted by the short-term scheduler? (That is, would it be ok for the scheduler to interrupt one of these operations and switch the CPU to a different process or thread?)
• Describe the differences between binary semaphores and counting semaphores. Propose a scenario where one type of construct is more useful than the other.
• Propose a scenario in which one or more processes experience starvation.
• Construct a scenario with a small number of processes (2 or 3) that illustrates deadlock.
• Discuss whether a counting semaphore can be used to solve a mutual exclusion problem.

6.7 Monitors

• Describe the concept of monitor and what kinds of problems this construct might address.
• What are the types of problems that can be solved with monitors?
• Construct a solution to the bounded-buffer problem using a monitor and any other synchronization construct you might want.
• From the perspectives of abstraction and usability, how do monitors compare against semaphores and mutex locks?

6.8 Liveness

• Read about deadlock and priority inversion, two situations that can lead to liveness failure.

6.9 Evaluation 

• Under what contention load should compare-and-swap (CAS) be used instead of the traditional mutual exclusion locking using test-and-set? Why?

7.1 Synchronization Examples – Classic Problems

There are a number of well known, classic synchronization problems. Each represents a category of general problems. These classic problems illustrate the essence and challenges presented in synchronizing processes that access shared data. These problems tend to appear in commonly in concurrent and parallel computing.

Use the synchronization constructs we studied to propose solutions to the following problems:

• The Bounded-Buffer Problem
• The Sleeping Barber Problem
• The Dining Philosophers Problem

7.2 Synchronization Within the Kernel

7.2 POSIX Synchronization

The POSIX standard defines useful mutex, semaphore, and condition variable structures for your multithreaded synchronization efforts. This section provides useful code snippets.