Practical Concurrent and Parallel Programming (PCPP) (PRCPP)

• This MSc course is about how to write correct and efficient concurrent and parallel software, primarily using Java, on standard shared-memory multicore hardware. It covers basic mechanisms such as threads, locks and shared memory as well as more advanced mechanisms such as transactional memory, message passing, and compare-and-swap. It covers concepts such as atomicity, safety, liveness and deadlock. It covers how to measure and understand performance and scalability of parallel programs. It covers tools and methods to find bugs in concurrent programs.
• For exercises, quizzes, and much more information, see the course LearnIT site (restricted access).
• For formal rules, see the official course description.
• The course is designed and taught by Peter Sestoft and Claus Brabrand at the IT University of Copenhagen.
• Exam questions January 2015 and supporting code. Post-exam versions: exam questions with some corrections and supporting code with some corrections.

Course week	ISO week	Date	Who	Subject	Materials	Exercises
1	35	29 Aug	PS	Concurrent and parallel programming, why, what is so hard. Threads and locks in Java, shared mutable memory, mutual exclusion, Java inner classes.	Goetz chapters 1, 2; Sutter paper; McKenney chapter 2; Bloch item 66; Slides week 1; Exercises week 1; Example code: pcpp-week01.zip	Exercises week 1
2	36	5 Sep	PS	Threads and Locks: Threads for performance, sharing objects, visibility, volatile fields, atomic operations, avoiding sharing (thread confinement, stack confinement), immutability, final, safe publication	Goetz chapters 2, 3; Bloch item 15; Slides week 2; Mandatory exercises week 2; Example code: pcpp-week02.zip	Mandatory handin 1
3	37	12 Sep	PS	Threads and Locks: Designing thread-safe classes. Monitor pattern. Concurrent collections. Documenting thread-safety.	Goetz chapters 4, 5; Slides week 3; Exercises week 3; Example code: pcpp-week03.zip	Exercises week 3
4	38	19 Sep	PS	Performance measurements.	Sestoft: Microbenchmarks; Slides week 4; Exercises week 4; Example code: pcpp-week04.zip; Optional: McKenney chapter 3	Mandatory handin 2
5	39	26 Sep	PS	Threads and Locks: Tasks and the Java executor framework. Concurrent pipelines, wait() and notifyAll().	Goetz chapters 6, 8; Bloch items 68, 69; Slides week 5; Exercises week 5; Example code: pcpp-week05.zip	Exercises week 5
6	40	3 Oct	PS	Threads and Locks: Safety and liveness, absence of deadlock and livelock. The ThreadSafe tool.	Goetz chapter 10, 13.1, appendix A; Bloch item 67; Slides week 6; Exercises week 6; Example code: pcpp-week06.zip	Mandatory handin 3
7	41	10 Oct	PS	Threads and Locks: Performance and scalability	Goetz chapter 11, 13.5; Slides week 7; Exercises week 7; Example code: pcpp-week07.zip	Exercises week 7
	42	17 Oct	Fall break
8	43	24 Oct	PS	Threads and Locks: GUI applications	Goetz chapter 9; Slides week 8; Exercises week 8; Example code: pcpp-week08.zip	Mandatory handin 4
9	44	31 Oct	PS	Threads and Locks: Testing concurrent programs.	Goetz chapter 12; Herlihy and Shavit chapter 3; Slides week 9; Exercises week 9; Example code: pcpp-week09.zip	Exercises week 9
10	45	7 Nov	PS	Transactional memory, Multiverse library	Harris et al 2008 paper; Herlihy and Shavit sections 18.1-18.2; Cascaval et al 2008 paper; Slides week 10; Exercises week 10; Example code: pcpp-week10.zip	Mandatory handin 5
11	46	14 Nov	PS	Optimistic concurrency, lock-free data structures, Treiber stack, compare-and-swap	Herlihy and Shavit chapter 11; Goetz chapter 15; Slides week 11; Exercises week 11; Example code: pcpp-week11.zip	Exercises week 11
12	47	21 Nov	PS	The Michael and Scott queue, progress concepts, Java memory model	Goetz chapter 15 and 16; Michael and Scott paper; Optional: Java Language Specification section 17.4; Slides week 12; Exercises week 12; Example code: pcpp-week12.zip	Exercises week 12
13	48	28 Nov	CB	Introduction to message passing concurrency (no mutable shared memory), Introduction to Erlang, Introduction to Java+Akka.	Erlang chapter 1, 2, 5; Slides week 13; Exercises week 13; Example code: pcpp-week13.zip	Mandatory handin 6
14	49	5 Dec	CB	Message passing (no mutable shared memory), Erlang, Java+Akka.	Slides week 14; Example code: pcpp-week14.zip; or see materials at Claus's page	No new exercises

Mandatory course materials

• Goetz et al: Java Concurrency in Practice, Addison-Wesley 2006. The Academic Bookstore will sell it at ITU at start of term. Also at Amazon.co.uk. Example code at http://jcip.net/.
• Herlihy and Shavit: The Art of Multiprocessor Programming. Revised first edition, Morgan Kaufmann 2012. Chapters 1 and 3 (safety and liveness concepts) and 11 (concurrent stacks) and 18.1, 18.2 (compositionality, transactional memory). At Amazon.co.uk
• Sestoft: Microbenchmarks in Java and C#. Free at http://www.itu.dk/people/sestoft/papers/benchmarking.pdf with the corresponding Java example code.
• Harris, Marlow, Peyton-Jones, Herlihy: Composable memory transactions. Communications of the ACM 51, 8 (August 2008) 91-100, see also LearnIT.
• Cascaval et al: Software Transactional Memory: Why Is It Only a Research Toy? ACM Queue 2008. Free at http://queue.acm.org/detail.cfm?id=1454466
• Michael and Scott: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. PODC 1996. Free at http://www.research.ibm.com/people/m/michael/podc-1996.pdf
• The Multiverse Software Transactional Memory library for Java, and the source for a book about it.
• Armstrong, Virding, Williams: Concurrent Programming in Erlang. Part 1 free at http://www.erlang.org/download/erlang-book-part1.pdf.

• Bloch: Effective Java. Second edition, Addison-Wesley 2008. Item 15 on immutability and items 66-73 on concurrency. At Amazon.co.uk. Contains much other wisdom for Java (and .NET) developers; you should own this book and use it.
• Sestoft: Java Precisely. Second edition, MIT Press 2005. Especially chapters 9 and 10 on classes, inner classes and anonymous classes, and chapter 16 on threads. At Amazon.co.uk
• Sutter: The free lunch is over. Free at http://www.gotw.ca/publications/concurrency-ddj.htm
• If you want a deep understanding of how modern multicore cache and memory hardware design affects concurrency performance, these seem to be good overviews, although far too detailed for this course: McKenney: Memory barriers, a hardware view for software hackers (IBM, 2010) and Drepper: What every programmer should know about memory (Redhat, 2007).
• Budd, Lipton, Sayward, DeMillo: The design of a prototype mutation system for software testing, 1978. Free at http://www.computer.org/csdl/proceedings/afips/1978/5086/00/50860623.pdf.
• On transactional memory: Peyton Jones: Beautiful concurrency, 2007; and Larus and Kozyrakis: Transactional memory, 2008 (free access within ITU); and Dan Grossman's very enlightening analogy between transactional memory and garbage collection; and hardware support via the Intel Transaction Synchronization Extensions (2012) and also pages 8-1 through 8-24 of the Instruction Set Extensions Programming Reference; Robert Ennals: Software transactional memory should not be obstruction-free, 2006, PDF; and a response to Cascaval's critique of STM by Dragojevic et al: Why STM can be more than a research toy CACM, April 2011. (PDF accessible for free from within ITU's network).
• On memory models: see Java Language Specification below; and Ostrovsky: The C# Memory Model in Theory and Practice, in MSDN Magazine, part 1 (December 2012) and part 2 (January 2013); and The C# Language Specification (standard Ecma-334), especially section 10.10 and 17.4.3, and Joseph Albahari's Threading in C# Part 4: Advanced Threading.
• Akka+Java Actor Snapshot
• The Akka+Java documentation
• Video Talk on Akka by Viktor Klang (on YouTube)
• Video Talk on Akka by Jonas Boner (on YouTube)
  • Slides for the Video Talk on Akka (from GOTO conference, Aarhus, Denmark).

• Nancy Leveson's 1995 report on the Therac-25 accidents, caused by incompetent concurrent programming.
• Per Brinch Hansen on Java's insecure parallelism, 1999.
• Hoare's paper on monitors, CACM 17, 10 (October 1974) 549-557.
• The CERT Oracle Secure Coding Standard for Java especially sections 08 on Locking, 09-11 on Threads, and 07 on Visibility and Atomicity.
• McKenney (ed.): Is Parallel Programming Hard, And, If So, What Can You Do About It? IBM 10 March 2014. Free at https://www.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html. Chapters 2 and 3.
• A good book about .NET parallel programming is Campbell, Johnson, Miller, Toub: Parallel Programming with Microsoft .NET, Design Patterns for Decomposition and Coordination on Multicore Architectures. Microsoft Press 2010. There is an online version and also a printed version at Amazon.com.
• M. Herlihy: Wait-free synchronization. ACM Toplas 11, 1 (January 1991) 124-149. Free PDF at Herlihy's homepage.
• N. Shavit: Data structures in the multicore age. Communications of the ACM 54, 3 (March 2011) 76-84. Free inside ITU from the ACM Digital Library.

Java resources

• Java concurrency tutorial. Free at http://docs.oracle.com/javase/tutorial/essential/concurrency/.
• Java streams tutorial, parallelism section. Free at http://docs.oracle.com/javase/tutorial/collections/streams/parallelism.html.
• Java Swing GUI Toolkit tutorial, concurrency lesson at http://docs.oracle.com/javase/tutorial/uiswing/concurrency/index.html.
• Java 8 class library documentation online.
• Java 8 development kit download
• Java 8 language specification in PDF and online as HTML; especially 17.1 synchronization and 8.3.1.4 volatile fields and 17.5 final field semantics and the somewhat complicated 17.4 memory model.
• Brian Goetz about the design of the Java 1.5 memory model: part 1 and part 2, IBM 2004.
• JSR 305 thread-safety annotations jar file for @GuardedBy and similar. Download the jar file, put it someplace such as ~/lib/jsr305-3.0.0.jar, add import javax.annotation.concurrent.GuardedBy; to your Java source files, and mention the jar file on the classpath when compiling Java files, as in javac -cp ~/lib/jsr305-3.0.0.jar *.java
• Akka homepage. http://akka.io/ (Documentation, FAQ, Download, ...).
• Akka+Java API