Semester 2 G52CON Concepts of Concurrency

This module introduces the basic principles of concurrent programming and their use in designing programs. The aims and objectives of the module can be found in the module description.

Outline Syllabus

The module focuses on four main themes

1. Introduction to concurrency: what concurrency is, hardware support for concurrency, the core problems of mutual exclusion and conditional synchronisation, concurrency primitives for shared memory and distributed concurrent programming including semaphores, monitors, RPC and rendezvous
2. Design of simple concurrent algorithms in Java: the use of threads, synchronized methods, and monitors.
3. Correctness of concurrent algorithms: safety and liveness properties of concurrent algorithms, proving properties using assertional reasoning and model checking.
4. Design patterns for common concurrency problems: the lectures and exercises also illustrate the use of concurrency primitives and algorithms to solve some common problems in concurrent programming, e.g., the producer-consumer problem, the readers and writers problem, client server problems etc.

Lectures

Lectures are on Tuesdays at 1pm in A25 (NBS) and Thursdays at 1pm in LT3 (CTF).

Assessment

Assessment is by means of a two hour exam and a coursework which involves writing a small concurrent program. The exam accounts for 75% of the assessment and the coursework 25%.

Coursework Description

The coursework involves writing a concurrent binary search tree. Full details can be found in the coursework description. Coursework submissions are due at 3:30pm on Friday the 14th of March.

There are three model solutions to the coursework:

• a basic fully-synchronized version which only allows one method to run at a time;
• a read-write version, which allows either one destructive operation (i.e., inserting or deleting an item) or multiple non-destructive operations (i.e., searching for an item) to run at the same time; and
• a fine(r)-grained version which allows multiple destructive operations (i.e., inserting or deleting an item) and multiple non destructive operations (i.e., searching for an item) to run at the same time, by synchronising at the node level.

Reading List

Recommended Reading

• Andrews (2000), Foundations of Multithreaded, Parallel and Distributed Programming, Addison Wesley.
  The errata page contains a list of typos and a couple of major errors.
• Lea (2000), Concurrent Programming in Java: Design Principles and Patterns, (2nd Edition), Addison Wesley.
  There is an online supplement to the book and the errata page again lists a number of typos and errors, though less serious than in Andrews.

• Ben-Ari (1982), Principles of Concurrent Programming, Prentice Hall.
• Andrews (1991), Concurrent Programming: Principles & Practice, Addison Wesley.
• Burns & Davies (1993), Concurrent Programming, Addison Wesley.
• Hartley (1998), Concurrent Programming: The Java Programming Language, Oxford.
• Magee & Kramer (1999), Concurrency: State Models and Java Programs, John Wiley.
• Bishop (2000), Java Gently, 3rd Edition, Addison-Wesley.
• Huth & Ryan (2000), Logic in computer science: modelling and reasoning about systems, Cambridge University Press.

Note that there is also a version of the reading list with links to the University Library catalogue.

Suggested Reading

Note that the following list of suggested reading is provisional, as it may necessary to change the order in which topics are presented.

• Lecture 1: Introduction. Andrews (2000), chapter 1, sections 1.1-1.2; Ben-Ari (1982), chapter 1.
• Lecture 2: Processes and Threads. Bishop (2000), chapter 13; Lea (2000), chapter 1; Java Tutorial, Threads.
• Lecture 3: Synchronisation. Andrews (2000), chapter 2, section 2.1, chapter 3, section 3.1; Ben-Ari (1982), chapter 2.
• Lecture 4: Atomic Actions. Andrews (2000), chapter 2, sections 2.1 and 2.4, chapter 3, section 3.2; Ben-Ari (1982), chapter 2.
• Lecture 5: Mutual Exclusion Algorithms I. Andrews (2000), chapter 3, sections 3.1--3.2; Ben-Ari (1982), chapter 2; Andrews (1991), chapter 3, section 3.1.
• Lecture 6: Mutual Exclusion Algorithms II. Ben-Ari (1982), chapter 3; Burns & Davies (1993), chapter 3, section 3.4.
  for the Java Memory Model. Lea (2000), chapter 2; Java Language Specification, chapter 17.
• Lecture 7: Semaphores I. Andrews (2000), chapter 4, sections 4.1--4.2; Ben-Ari (1982), chapter 4; Burns & Davies (1993), chapter 6.
• Lecture 8: Semaphores II. Andrews (2000), chapter 4, sections 4.1--4.2; Ben-Ari (1982), chapter 4; Burns & Davies (1993), chapter 6.
  for Producer-Consumer Problems. Andrews (2000), chapter 1, section 1.6; Ben-Ari (1982), chapter 4.
• Lecture 9: Monitors I. Andrews (2000), chapter 5; Ben-Ari (1982), chapter 5; Burns & Davies (1993), chapter 7, sections 7.4-7.9.
• Lecture 10: Monitors II. Andrews (2000), chapter 5; Ben-Ari (1982), chapter 5; Burns & Davies (1993), chapter 7, sections 7.4-7.9.
  for Readers and Writers Problems. Andrews (2000), chapter 4, section 4.4, chapter 5, section 5.4; Ben-Ari (1982), chapter 5, section 5.4; Burns & Davies (1993), chapter 6, section 6.8;
• Lecture 11: Synchronisation in Java I. Lea (2000), chapter 2; Java Tutorial, Synchronizing Threads.
• Lecture 12: Synchronisation in Java II. Lea (2000), chapter 3.
• Lecture 13: Message Passing. Andrews (2000), chapter 7; Burns & Davies (1993), chapter 4; Andrews (1991), chapters 7 & 8.
  for Client-Sever problems. Andrews (2000), chapters 7 & 8.
• Lecture 14: Remote Inovcation. Andrews (2000), chapter 8; Ben-Ari (1982), chapter 6; Burns & Davies (1993), chapter 5; Andrews (1991), chapter 9.
• Lecture 15: Distributed Processing in Java I. Andrews (2000), chapter 8; Java Tutorial, Sockets.
• Lecture 16: Distributed Processing in Java II. Andrews (2000), chapter 8; Java Tutorial RMI.
• Lecture 17: Proving Correctness. Andrews (2000), chapter 2, sections 2.6--2.8; Ben-Ari (1982), chapter 3.
• Lectures 18 & 19: Model Checking. Huth & Ryan (2000), chapter 3.

Exercises

There will be a number of (unassessed) exercises covering some of the programming constructs and proof techniques introduced in the module. Model answers will be given in the lectures.

• Exercise 1: Interference. Model solution to the exercise.
• Exercise 2: Semaphores. Model solution to the exercise.
• Exercise 3: Monitors. Model solution to the exercise.
• Exercise 4: Monitors in Java. Model solution to the exercise.
• Exercise 5: Dining Philosophers Problem. A solution using semaphores can be found in lecture 13. The semaphore solution is a particular instance of using resource ordering for deadlock avoidance (also explained in the lecture).
• Exercise 6: Proving Correctness.
• Exercise 7: CTL. Model solution to the exercise.

Lecture Slides

Warning: the slides are not `lecture notes': they are there to help present the material, not to act as a reference to the main points covered in the lecture. Simply reading the slides won't necessarily give you a good grasp of the syllabus. They are specifically not a substitute for taking your own notes or reading the suggested reading for the lecture.

In some cases, an abridged version of the lecture slides will be made available before the lecture. These will be replaced by the unabridged version after the lecture.

• Lecture 1: Introduction Slides Slides (2 per page)
  
• Lecture 2: Processes and Threads Slides Slides (2 per page), and the ParticleApplet example
  
• Lecture 3: Synchronisation Slides Slides (2 per page) and the Ornamental Gardens applet (from Magee & Kramer (1999))
  
• Lecture 4: Atomic Actions Slides Slides (2 per page)
  
• Lecture 5: Mutex Algorithms I Slides Slides (2 per page)
  
• Lecture 6: Mutex Algorithms II Slides and Slides (2 per page)
  
• Lecture 7: Semaphores I Slides and Slides (2 per page)
  
• Lecture 8: Semaphores II Slides, Slides (2 per page); and the Producer-Consumer/Bounded Buffer applet (from Magee & Kramer (1999))
  
• Lecture 9: Monitors I Slides and Slides (2 per page)
  
• Lecture 10: Monitors II Slides and Slides (2 per page)
  
• Lecture 11: Synchronisation in Java I Slides and Slides (2 per page)
  
• Lecture 12: Synchronisation in Java II Slides and Slides (2 per page)
  
• Lecture 13: Message Passing Slides and Slides (2 per page)
  
• Lecture 14: Remote Invocation Slides and Slides (2 per page)
  
• Lecture 15: Distributed Processing in Java I Slides, Slides (2 per page) the KnockKnockServer example and the ChatServer example
  
• Lecture 16: Distributed Processing in Java II Slides and Slides (2 per page)
  
• Lecture 17: Proving Correctness Slides and Slides (2 per page), the Ornamental Gardens applet (from Magee & Kramer (1999)), and the the "Proof Garden" applet
  
• Lecture 18: Model Checking I Slides and Slides (2 per page)
  
• Lecture 19: Model Checking II Slides and Slides (2 per page)
  
• Lecture 20: Revision Slides and Slides (2 per page)
  

Past Papers

Past papers are available from the Examinations office. Note that for copyright reasons, past papers can only be accessed from machines connected to the local network.

You may find the feedback on the G52CON 2006/2007 and the G52CON 2007/2008 exams helpful.