Reading Assignment

• Operating Systems Concepts: Chapter 6.

Lecture Slides

• Thread Synchronization

Homework Assignment

Due Date: 3/27/08


• Operating Systems Concepts: #6.9, #6.16, #6.17, #6.27.
• In class we discussed how mutual exclusion could be implemented using a TSL instruction. It is also possible to implement mutual exclusion with a SWAP instruction. Assume that the SWAP instruction is indivisible (i.e. atomic) and that it swaps the values of two variables. For example: SWAP A B will swap the values in the variables A and B. Show how the SWAP instruction could be used to implement mutual exclusion. Also, give an argument, similar to the one given in class, that your SWAP based mutual exclusion works.
• Consider the three threads shown below. Using pseudo-code similar to that used in class, show how it is possible to ensure that section a2 will run before section b2 and that section b2 will run before section c2.

  Thread A		Thread B		Thread C
  1. section a1 2. section a2		1. section b1 2. section b2		1. section c1 2. section c2

• In class we saw a solution to the Readers-Writers problem. Unfortunately, in our solution it was possible for a continuous stream of readers to cause the writers to starve. Augment our solution from class to ensure that writers do not starve. You solution should guarantee that each time writer arrives, the current readers may finish, but any new readers must block until at least one writer has had the chance to write. Hint: Think about using a turnstile that both readers and writers go through. The turnstile should locks when a writer arrives and unlock when a writer completes.

Related Web Sites

Synchronizing Threads

A set of pages from the Java Tutorial that discuss how to synchronize threads. Some of this goes well beyond what we'll be doing in this class, but the inroductory material is good.

Sample Code

• SheepTracker1.java
• SheepTracker2.java
• SheepTracker3.java
• ThreadSynchExample1.java - Example of two threads that contain a mutual exclusion problem.
• ThreadSynchExample2.java - Example of two threads that contain a serialization problem.
  
  
• Semaphore.java - An implementation of a semaphore in Java.

Project Assignment

Due Date: 4/3/08 4/7/08


• Project #3 - Thread Synchronization Problems

Acknowledgment: this content is essentially identical to that developed by Professor Grant Braught for the Spring 2006 Operating Systems course, and I'm grateful for his permission to use it.