General
News
24.5.2011 — Assignment 11 and its solution are online.
24.5.2011 — Slides for lecture 13 are online.
23.5.2011 — Solution for assignment 10 is online.
17.5.2011 — Assignment 10 and the solution for assignment 9 are online.
10.5.2011 — Assignment 9 and the solution for assignment 8 are online.
3.5.2011 — Assignment 8 and the solution for assignment 7 are online.
18.4.2011 — Assignment 7 is online.
11.4.2011 — Solution for assignment 6 is online.
11.4.2011 — Slides for lecture 8 are online.
4.4.2011 — Solution for assignment 5 is online.
4.4.2011 — Slides for lecture 7 are online.
28.3.2011 — Assignment 6 is online.
28.3.2011 — Slides for lecture 6 are online.
21.3.2011 — Added notes on tools.
21.3.2011 — Assignment 5 is online.
21.3.2011 — Solution for assignment 4 is online.
21.3.2011 — Solution for assignment 3 is online.
17.3.2011 — Assignment 4 is online.
17.3.2011 — Slides for lecture 5 are online.
17.3.2011 — The project assignment is online.
14.3.2011 — Solution for assignment 2 is online.
11.3.2011 — Assignment 3 is online.
11.3.2011 — Slides for lecture 4 are online.
7.3.2011 — Solution for assignment 1 is online.
7.3.2011 — Slides for lecture 3 are online.
3.3.2011 — Assignment 2 is online.
1.3.2011 — Updated reading materials and schedule.
25.2.2011 — Assignment 1 is online.
10.1.2011 — The initial version of this page is up.
Course description
252-0268-00 Concepts of Concurrent Computation
Abstract: Concurrent programming is one of the major challenges in software development. The "Concepts of Concurrent Computation" course explores important models of concurrency, with a special emphasis on concurrent object-oriented programming and process calculi.
Objective: After completing this course, students will understand the principles and techniques of concurrent programming, supporting theories (CSP, CCS) allowing formal reasoning about concurrent systems, advances in concurrent object-oriented programming, and applications to multithreading, distribution, Web services and real-time.
Content:
-
Overview
- Concurrent and parallel programming
- Distributed programming
- Client-server programming
- Internet, Web Services
- Specific issues of embedded and real-time concurrency
-
Approaches to concurrent programming
- Notion of process, thread and application domain
- Message passing versus variable sharing
- Data consistency issues
- Enforcing synchronization: semaphores, monitors, barriers, etc.
- Java and .NET multithreading
-
Formal models of concurrency
- Computation versus observation
- Interesting properties of concurrent programs
- Concurrent calculi: CSP and Ada, CCS, the Pi-calculus, ...
-
Concurrency and Object-Orientation
- Language issues
- Processes versus objects
- Synchronizing objects
- Language examples, including C-omega (Polyphonic C#), Actors and others.
-
Concurrent object-oriented programming: the SCOOP model
- Processors; handling an object
- Synchronous and asynchronous feature calls
- Design by Contract in a concurrent context
- Separate objects and entities
- Accessing separate objects; validity rules
- Synchronization: waiting, reserving, preconditions as wait conditions, Wait by Necessity
- Avoiding deadlock: The Business Card principle
- Interrupting a reservation: duels and priorities
- Mapping the processors to physical resources
- Examples and applications
-
Extensions and open problems
- Real-time and embedded extensions
- Timing contracts
- Proofs of concurrent programs
Prerequisites: The course includes a significant component of active participation on the part of the students: exercises, both theoretical (in particular on process calculi) and implementation-oriented, implying the construction of solutions to concurrency problems.
Grading: No Testat is delivered for the course. The assessment consists of a project (50%) and a written semester end exam (50%) for which no supporting material is allowed. The only way to get a grade is to take the written exam and submit the project. This applies regardless of your department or status. The performance assessment is only offered at the end after the course unit. Repetition only possible after re-enrolling.
Course book
Bertrand Meyer, Sebastian Nanz: Concepts of Concurrent Computation (draft) Electronic version
Helping and getting help
Talk to the assistants or use the VIS forum.
Tools
For the development of SCOOP programs, we ask you to use the most recent version of EiffelStudio. Note that this is not necessarily the version that is marked as the latest version. Once you installed EiffelStudio, change the project setting Concurrency to scoop, to turn on SCOOP in your project. For the development of Java programs, you can use a Java development environment of your choice. For example, you can use Eclipse.
Further reading
- Piotr Nienaltowski. Practical framework for contract-based concurrent object-oriented programming. Phd Dissertation, ETH Zurich, 2007. [paper pdf]
- Bertrand Meyer. Object-Oriented Software Construction, Second Edition, Chapter 30, Prentice Hall, 1997, ISBN 0-13-629155-4. [chapter 30 html]
- Maurice Herlihy and Nir Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008, ISBN 978-0123705914.
- Gregory R. Andrews. Foundations of Multithreaded, Parallel, and Distributed Programming. Pearson Addison Wesley, 1999, ISBN 978-0201357523.
- Mordechai Ben-Ari. Principles of Concurrent and Distributed Programming. Prentice Hall, 1990, ISBN 978-0321312839.
- Howard Bowman and John Derrick (Editors). Formal methods for distributed processing: a survey of object-oriented approaches. Cambridge University Press, 2001.
- Bertrand Meyer. Eiffel: The Essentials. [paper pdf]
- Marcel Kessler. DO IT WITH STYLE - A Guide to the Eiffel Style. [paper pdf]
- EiffelSoftware. Eiffel and EiffelStudio Documentation. [website html]
- Allen B. Downey. The Little Book of Semaphores Second Edition. Green Tea Press, 2005. [paper pdf]
Lecture
Schedule
| Day | Time | Location |
|---|---|---|
| Tuesday | 10:15-12:00 | RZ F 21 |
Slides
| Date | Lecture | Title | Slides | Readings |
|---|---|---|---|---|
| Tuesday 22.2.2011 | 1 | Welcome and introduction |
pdf
|
|
| Tuesday 1.3.2011 | 2 | Challenges of concurrency |
pdf
|
Chapter 2 |
| Tuesday 8.3.2011 | 3 | Synchronization algorithms |
pdf
|
Chapter 3 |
| Tuesday 15.3.2011 | 4 | Semaphores |
pdf
|
Chapter 4 |
| Tuesday 22.3.2011 | 5 | Monitors |
pdf
|
Chapter 5 |
| Tuesday 29.3.2011 | 6 | SCOOP principles |
pdf
|
Chapter 9 |
| Tuesday 5.4.2011 | 7 | SCOOP type system |
pdf
|
Chapter 9 |
| Tuesday 12.4.2011 | 8 | SCOOP advanced concepts |
pdf
|
Chapter 9 |
| Tuesday 19.4.2011 | 9 | Review of concurrent languages |
pdf
|
|
| Tuesday 26.4.2011 | no lecture | Easter break | ||
| Tuesday 3.5.2011 | 10 | Lock-free approaches |
pdf
|
|
| Tuesday 10.5.2011 | 11 | CCS |
pdf
|
Chapter 7 |
| Tuesday 17.5.2011 | 12 | CCS advanced concepts |
pdf
|
Chapter 7 |
| Tuesday 24.5.2011 | 13 | CSP |
pdf
|
Chapter 6 |
| Tuesday 31.5.2011 | Exam |
= Temporary version
= Final version
Exercises
Schedule
| Day | Time | Location |
|---|---|---|
| Tuesday | 12:15-13:00 | RZ F 21 |
Assignments
| Date | Title | Material |
|---|---|---|
| Tuesday 1.3.2011 | Introduction and challenges of concurrency | assignment |
| Tuesday 8.3.2011 | Synchronization and satisfaction | assignment |
| Tuesday 15.3.2011 | Semaphores | assignment |
| Tuesday 22.3.2011 | Monitors | assignment |
| Tuesday 29.3.2011 | SCOOP principles | assignment |
| Tuesday 5.4.2011 | SCOOP type system | assignment |
| Tuesday 19.4.2011 | Review of concurrent languages | assignment |
| Tuesday 3.5.2011 | Lock-free approaches | assignment |
| Tuesday 10.5.2011 | CCS | assignment |
| Tuesday 17.5.2011 | CCS advanced concepts | assignment |
| Tuesday 24.5.2011 | CSP | assignment |
Assistants
Project
Please read the project assignment.Additionally, a small example script is available as a starting point for testing.