Overview

In this reading we’ll continue our exploration of potential synchronization problems by looking at two common problems: races and deadlock.

Required Reading

Sections 12.7.4 - 12.7.5 (pp. 1025-1029) 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. Given a sequence of semaphore operations for two threads, draw a progress graph that has forbidden regions for each semaphore clearly labeled.
2. Given a progress graph with labeled forbidden regions, identify all existing deadlock regions and determine if a given trajectory will lead to deadlock.
3. Explain how and in what situations the mutex lock ordering rule can avoid deadlocks.

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 multithreaded C program, determine if there are any races present.
2. Given a multithreaded C program, determine whether deadlock is possible.

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. Problem 12.28 from the course textbook (p. 1033).