CS 385 Lab 14, Spring 2009

Due date: Monday, May 11, 1:00 PM

Reading

In preparation for this lab, you should read the following article:

Adl-Tabatabai, Kozyrakis, and Saha, "Unlocking concurrency," ACM Queue, December 2006. [http://queue.acm.org/detail.cfm?id=1189288]

This article describes transactional memory (TM), an alternative to managing synchronization with locks.

• Read the introduction and conclusion. Note how the authors make the case that an alternative to locks would be useful, and note the advantages and limitations of transactional memory.
• Read the section on programming with transactions. Understand the programming examples and the graph. This section describes the guarantees that a TM system makes to the programmer, and the benefits to correctness and performance.
• Read the "Transactions under the hood" section. The main implementation decisions concern versioning, conflict detection, and nesting. Try to understand each of these issues and the possible design options.
• Read either the section on software transactional memory or the section on hardware transactional memory. For your chosen section, notice how it handles the issues above.

Writeup

You will turn in your writeup electronically, as a text file. To get a good grade on the writeup, your answers should be in your own words and should show that you have worked to understand the article and that you are prepared for discussion.

Answer all of the questions in the following list:

1. What are data races and deadlocks, and how can they occur with locks? Explain. Why would TM avoid these problems? What's the downside?
2. Explain in your own words why versioning is needed and the difference between eager and lazy versioning.
3. Explain in your own words why conflict detection is needed and the difference between pessimistic and optimistic conflict detection.
4. For either hardware transactional memory or software transactional memory, explain how versioning and conflict detection are handled.

Answer two of the questions in the following list:

1. The terms "scalability" and "composition" are used throughout the article; explain them in your own words.
2. Explain the analogy between transactional memory and database transactions.
3. Explain Figure 2: what does it show, and why does that result occur?
4. Explain the challenges that nested transactions present for a TM system.

Submitting your writeup

Make sure that your writeup is named yourlastnameL14.txt, and then copy it to ~srivoire/cs385/submit. Wait 2 minutes, and then check that it was correctly submitted by visiting http://rivoire.cs.sonoma.edu/cs385/lab14sub.txt.