CS 5204 - Fall, 2009
Problem Set 5
Assigned: September 22, 2009
Due: September 29, 2009 (noon) 
Total points: 20

Please submit your answers in PDF format via email.

---

1. (6 points) Describe in prose a "system" of interest to you and define the behavior of this system using the pi calculus. The "system" may be from the "real world" (similar to - but do not use - a vending machine) or a "technical" systems (similar to - but do not use - a producer-consumer process structure). Your system must have a rich enough behavior to require the use of all of the basic pi-calculus operators (sequence, choice, recursion and/or replication, communication, encapsulation, concurrent composition). Your answer will be graded on the basis of the clarity of the prose description, the correctness and appropriateness of the pi-calculus description, and the the use of all of the pi-calculus operators. Your answer should be on the "scale" of the mobile phone example presented in the readings and discussed in class.

2. (5 points) Assume that you have a version of Java whose only synchronization operations are the transactional memory operations BeginTransaction(), EndTransaction(), Validate(), Commit(), and Abort(). All memory operations that occur between the BeginTransaction and the EndTransaction are part of the transaction. The Validate operation returns true if the memory operations performed after the BeginTransaction and prior to the Validate operation are consistent (and returns false otherwise). The Commit operations return true if the transaction was able to commit successfully (and returns false otherwise). Show how you would revise the code shown in Figure 2 in Lee's paper using this version of Java.

3.(6 points) In the paper Transactional Memory: Architectural Support for Lock-Free Data Structures the authors propose (page 5, right column) "a simple “update-and-commit” operation (like STORE_COND) would be useful for single-word updates." Describe how you would implement such an operation. Your description should be similar to those in the paper for the LT, LTX, and ST operations with explicit reference to cache line states, bus cycles, and processor flags.

4. (3 points) State three  insightful questions for discussion in class about hardware and/or software transactional memory based on your reading of the papers available on our web site.