Overview

While parallelism and concurrency can greatly improve the performance of our applications, they also introduce unique problems. In this reading we’ll examine how sharing data can lead to incorrect results for something as basic as incrementing a variable. We’ll see how progress graphs can help identify problematic thread interleavings and get a quick introduction to semaphores, one basic mechanism for helping deal with synchronization errors.

Required Reading

Sections 12.5.0 - 12.5.2 (pp. 995-1002) from the course textbook.

Learning Objectives

BASIC Learning Objectives

Each student will be responsible for learning and demonstrating proficiency in the following objectives PRIOR to the class meeting. The reading quiz will test these objectives.

1. Relate the multi-step process of accessing a shared variable to the potential for incorrect results when modifying such a variable.
2. Explain the relationship between critical sections and mutual exclusion.
3. Given a sample trajectory through a progress graph, determine instruction ordering.
4. Given an progress graph with a labeled unsafe region, provide an example trajectory that is safe and one that is unsafe.
5. Describe the operation of the P and V operations on a semaphore, relating those to the sem_wait and sem_post functions.
6. Describe what is meant by the semaphore invariant.

ADVANCED Learning Objectives

The following objectives should be mastered by each student DURING and FOLLOWING the class session through active work and practice.

1. Given a multi-threaded C program, identify where the critical sections are located.
2. Given a multi-threaded C program with unprotected shared variables, identify all of the possible final values for the shared variables.
3. Write, read, and trace code that uses the following POSIX semaphore library functions: sem_init, sem_wait, and sem_post.

Pre-class Exercises

These exercises are geared towards mastering the BASIC learning objectives listed above. You are expected to submit them before class and it is highly recommended that you complete them before attempting the reading quiz.

1. Part A: In your own words: What is a critical section?

   Part B: How can we avoid problems relating to critical sections?

2. What is the instruction ordering for the progress graph trajectory given below.

   

3. For Figure 12.21 in your book, provide one additional safe trajectory and one additional unsafe trajectory.

4. What is the semaphore invariant?