SGG 5

5.1 Background

  • 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?

5.2 The Critical Section Problem

We will discuss this topic in Wednesday (9/18)

  • What is the Critical Section Problem? (The Critical Section Problem is also known as Critical Region Problem (CR))
  • What does the entry section do?
  • What does the exit section do?
  • What does the remainder section mean?
  • Can we have a section of code before the entry section, just like the remainder section?
  • A solution to a CR problem must meet three criteria
    1. Mutual exclusion
    2. Progress
    3. Bounded waiting

    What does each mean? Why do we need all three conditions for a CR solution? What if one of the criteria is not met?

5.3 Peterson’s Solution

  • How does Peterson’s solution work?
  • Under what condition(s) does Peterson’s solution work? (or not work?)
  • Can Peterson’s solution be extended to more than two parties?

5.4 Synchronization Hardware

  • One of key sources of the synchronization problem is that the data access often is not mutual exclusive when needed to be.
  • Hardware could help us resolve this problem. The solutions discussed in this section rely on hardware to guarantee atomic operations on shared data.
  • How does test_and_set work? Why would it help solving the synchronization problem?
  • How does compare_and_swap work? Why would it help solving the synchronization problem?
  • Compare algorithms in Figure 5.1, 5.2, 5.4, and 5.6. What are the differences? What are the common elements?
  • Why do not hardware solutions such as test_and_set or compare_and_swap meet all three CR solution criteria?
  • Why does the solution in Figure 5.7 meet all three CR solution criteria?

5.5 Mutex Locks

  • What is a mutex lock?
  • How does mutex lock help solving the synchronization problem?
  • How is mutex lock different from the solutions in previous section (test_and_set or compare_and_swap)? Are there any common elements between the two sets of solutions (mutex lock vs test_and_set or compare_and_swap)?
  • The textbook authors claimed that solutions using busy-waiting such as mutex locks or test_and_wait have an advantage that they don’t require context switch. Why don’t they require context-switch? Why context switch is a problem?

5.6 Semaphores

  • What is a semaphmore? Which two operations can be applied to a semaphore?
  • How does a semaphore help solving the synchronization problem?
  • How is a semaphore implemented?
  • What are the differences and similarities between semaphores and other previous solutions, if any?
  • Under what condition(s) do semaphores cause deadlock, which can lead to starvation?
  • Do semaphores along meet the three criteria for a synchronization problem solution? Why? Why not?

5.7 Classic Problems of Synchronization

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. Solutions to these problems are critical to many computer science areas.

For each classic problem listed below, we should know how the problem is formulated; what general category of problems it represents; how the solution works; the limitations the solution has, if any; alternate solutions, if any; and relations among these classic problems, if any.

  • The Bounded-Buffer Problem
  • The Readers-Writers Problem
  • The Dinning-Philosophers Problem

5.8 Monitors

  • Why can’t solutions such as semaphores, locks, test_and_set, and compare_and_swap solve synchronization problems completely on their own? (Hint: check the three criteria for synchronization problem solutions)
  • Another high level language structure called monitor is developed to resolve these issues.
  • What is a monitor? How does it work? What are the two operations applied to a monitor?
  • What are the differences and similarities between monitors and other previous solutions?
  • Try to work out a solution for each of the classic synchronization problem using monitor(s).
  • Implementing a monitor using semaphores.
Print Friendly