02158 Concurrent Programming

02158 Concurrent Programming - Course Material

Technical University of Denmark DTU

02158 Concurrent Programming Fall 2024

Course Material

Home Plan Material

Main Texts and Material

[Andrews] Gregory R. Andrews: Foundations of Multithreaded, Parallel, and Distributed Programming
Addison-Wesley 2000. ISBN 0-201-35752-6 / 9780201357523

This is the main text of the course. The course will cover Parts I and II. Remember to consult the errata list.
Can be obtained in the campus bookstore, Polyteknisk Boghandel, (e.g. via this link) for about 450 kr. (students' price).
The main text is supplemented by a number of course notes:

[Basic] Hans Henrik Løvengreen: Basic Concurrency Theory, Version 1.2
Course note, DTU Compute, 2018

The note can be downloaded from DTU Learn, but is not to be distributed.
You are encouraged to print the note (double-sided printing is recommended).

[Aux] Auxiliary Exercises. Exercise compendium, 22 pages

[Proc] Hans Henrik Løvengreen: Concurrent Programming Practice: Processes, Threads and Tasks, vers. 2.0 (preliminary v.3).
Course note, 24 pages.

[Spin] Hans Henrik Løvengreen: Introduction to SPIN, version 1.4
Course note, 14 pages.

[Sync] Hans Henrik Løvengreen: Concurrent Programming Practice 2: Synchronization Mechanisms, vers. 1.5.
Course note, 20 pages.

[Deadlocks] A. Silberschatz, P.B. Galvin and Greg Gagne: Deadlocks
Chapter 7 of Operating System Concepts (8th ed.)
John Wiley & Sons 2010, ISBN:987-0-470-23399-3.
Available on DTU Learn.

Old Exam Problems

To give you some idea of the kinds of problems that you might encounter for the exam, a number of old exam papers and suggested solutions are presented below.

You are recommended to reserve at least one exam set for a real-time test.

Beware that the exam duration this year is 4 hours. Therefore, you should expect more elaborate exam problems than present in the 2 hours exams.

The weekly exercises as well as the other 4 hours exams may give an idea about the expected level.

Note that texts in brackets [...] are supplementary explanations which are usually not required for a proper exam hand-in.

Exam Solutions Duration

E23(pdf) (pdf) 4 Hours

E22(pdf) (pdf) 4 Hours

E21(pdf) (pdf) 4 Hours

E20(pdf) (pdf) 4 Hours

E19(pdf) (pdf) 2 Hours

E18(pdf) (pdf) 2 Hours

Program examples

Various examples in concrete programming/modelling languages presented at the lectures.

[SpinEx] Promela models of mutual exclusion algorithms:
Safety of Peterson's: peterson2.pml, peterson2g.pml, peterson3.pml
Liveness of Peterson's: peterson4_ltl.pml
Other algorithms: testandset_ltl.pml, ticket_ltl.pml

[Linux] The source files for Linux may generally be browsed online on elixir.bootlin.com.

Especially, the traditional Linux Spin-locks discussed at the lecture can be found in these files (for kernel version 2.6.22.6):
Lock types: spinlock_types.h
Lock code: spinlock.h
See the definitions of __raw_spin_lock(), and ___raw_spin_unlock().
If you want to study the the newer, fair (ticket-based) spin-locks yourself, they are now in arch/x86/include/asm/spinlock.h.
A discussion of the idea can be found in this Linux Weekly News article.
Recent kernel versions use much more complicated solutions suitable for virtualization, but still ensuring fairness.

[GoProg] Examples in the Go programming language:
"Uncle Donald" (fork/join): Donald.go
Simple message passing - vote collection: simple_msg_3.go
Basic message passing using time.After: simple_msg_2.go
Server-based bounded buffer: buffer.go
Monitor-based barrier: barrier.go

[Loom] Resources for Virtual Threads in Java (aka project Loom):
Project page
Description of Vitual Threads
Installation Guide (test program: HelloVirtual.java)

[Python] Some references for concurrency in Python (some require free account):
The Threading library
Introduction to Python concurrency notions
Introduction to threading
The Glocal Interpreter Lock

Supplementary material

If you would like to deepen your understanding of selected topics, you may consult the references given here.

[JSpin] Moti Ben-Ari: jSpin - Java GUI for SPIN vers. 5.0
Note, 22 pages.

[Holzmann] Gerard J. Holzmann: The SPIN Model Checker - Primer and reference manual
Addison-Wesley 2004. ISBN 0-321-22862-6.
The standard modern reference on SPIN by the developer himself. Covers both the theory on which SPIN is based as well as some applications. A must for large scale use of SPIN.

[Reek] Kenneth A Reek: Design Patterns for Semaphores
Article, 2004, 5 pages. Can be found at ACM Library or on DTU Learn
Discusses passing-the-baton versus a technique called I'll-do-it-for-you.

[Downey] Allan B Downey: The Little Book of Semaphores
Book, 2005, 279 pages(!). Freely available from www.greenteapress.com/semaphores
Gives a plethora of semaphore based solutions for various synchronization problems.

[LockDoc] Lochmann et. al.: LockDoc: Trace-Based Analsysis opf Locking in the Linux Kernel
Article, 2019. Can be retrieved from the authors here
Gives a status of locking rules in Linux and describes the LockDoc analysis tool.

[NonBlock] Links to non-blocking data structure resources:
Paper by Maged M. Michael and Michael L. Scott: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms (pdf).
Basis for implemenation of the class ConcurrentLinkedQueue.

[Herlihy] Maurice Herlihy and Nir Shavit: The Art of Multiprocessor Programming
Morgan Kaufmann 2008. ISBN 978-0-12-370591-4.
A presentation of concurrent programming with shared variables with emphasis on using non-blocking synchronization techniques written by two of the pioneers within this area.
Recommended after this course for those interested in more advanced synchronization techniques.

[Raynal] Michel Raynal: Concurrent Programming: Algorithms, Principles and Foundations
Springer 2013. ISBN 978-3-642-32026-2.
A newer book presenting numerous concurrent algorithms with focus on wait-free synchronization techniques using a fairly rigid approach.

Hans Henrik Løvengreen, Dec 4, 2024

[Andrews]	Gregory R. Andrews: Foundations of Multithreaded, Parallel, and Distributed Programming Addison-Wesley 2000. ISBN 0-201-35752-6 / 9780201357523 This is the main text of the course. The course will cover Parts I and II. Remember to consult the errata list. Can be obtained in the campus bookstore, Polyteknisk Boghandel, (e.g. via this link) for about 450 kr. (students' price). The main text is supplemented by a number of course notes:
[Basic]	Hans Henrik Løvengreen: Basic Concurrency Theory, Version 1.2 Course note, DTU Compute, 2018 The note can be downloaded from DTU Learn, but is not to be distributed. You are encouraged to print the note (double-sided printing is recommended).
[Aux]	Auxiliary Exercises. Exercise compendium, 22 pages
[Proc]	Hans Henrik Løvengreen: Concurrent Programming Practice: Processes, Threads and Tasks, vers. 2.0 (preliminary v.3). Course note, 24 pages.
[Spin]	Hans Henrik Løvengreen: Introduction to SPIN, version 1.4 Course note, 14 pages.
[Sync]	Hans Henrik Løvengreen: Concurrent Programming Practice 2: Synchronization Mechanisms, vers. 1.5. Course note, 20 pages.
[Deadlocks]	A. Silberschatz, P.B. Galvin and Greg Gagne: Deadlocks Chapter 7 of Operating System Concepts (8th ed.) John Wiley & Sons 2010, ISBN:987-0-470-23399-3. Available on DTU Learn.

Exam	Solutions	Duration
E23(pdf)	(pdf)	4 Hours
E22(pdf)	(pdf)	4 Hours
E21(pdf)	(pdf)	4 Hours
E20(pdf)	(pdf)	4 Hours
E19(pdf)	(pdf)	2 Hours
E18(pdf)	(pdf)	2 Hours

[SpinEx]	Promela models of mutual exclusion algorithms: Safety of Peterson's: `peterson2.pml`, `peterson2g.pml`, `peterson3.pml` Liveness of Peterson's: `peterson4_ltl.pml` Other algorithms: `testandset_ltl.pml`, `ticket_ltl.pml`
[Linux]	The source files for Linux may generally be browsed online on `elixir.bootlin.com`. Especially, the traditional Linux Spin-locks discussed at the lecture can be found in these files (for kernel version 2.6.22.6): Lock types: `spinlock_types.h` Lock code: `spinlock.h` See the definitions of `__raw_spin_lock()`, and `___raw_spin_unlock()`. If you want to study the the newer, fair (ticket-based) spin-locks yourself, they are now in `arch/x86/include/asm/spinlock.h`. A discussion of the idea can be found in this Linux Weekly News article. Recent kernel versions use much more complicated solutions suitable for virtualization, but still ensuring fairness.
[GoProg]	Examples in the Go programming language: "Uncle Donald" (fork/join): `Donald.go` Simple message passing - vote collection: `simple_msg_3.go` Basic message passing using time.After: `simple_msg_2.go` Server-based bounded buffer: `buffer.go` Monitor-based barrier: `barrier.go`
[Loom]	Resources for Virtual Threads in Java (aka project Loom): Project page Description of Vitual Threads Installation Guide (test program: `HelloVirtual.java`)
[Python]	Some references for concurrency in Python (some require free account): The Threading library Introduction to Python concurrency notions Introduction to threading The Glocal Interpreter Lock

[JSpin]	Moti Ben-Ari: jSpin - Java GUI for SPIN vers. 5.0 Note, 22 pages.
[Holzmann]	Gerard J. Holzmann: The SPIN Model Checker - Primer and reference manual Addison-Wesley 2004. ISBN 0-321-22862-6. The standard modern reference on SPIN by the developer himself. Covers both the theory on which SPIN is based as well as some applications. A must for large scale use of SPIN.
[Reek]	Kenneth A Reek: Design Patterns for Semaphores Article, 2004, 5 pages. Can be found at ACM Library or on DTU Learn Discusses passing-the-baton versus a technique called I'll-do-it-for-you.
[Downey]	Allan B Downey: The Little Book of Semaphores Book, 2005, 279 pages(!). Freely available from `www.greenteapress.com/semaphores` Gives a plethora of semaphore based solutions for various synchronization problems.
[LockDoc]	Lochmann et. al.: LockDoc: Trace-Based Analsysis opf Locking in the Linux Kernel Article, 2019. Can be retrieved from the authors here Gives a status of locking rules in Linux and describes the LockDoc analysis tool.
[NonBlock]	Links to non-blocking data structure resources: Paper by Maged M. Michael and Michael L. Scott: Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms (pdf). Basis for implemenation of the class `ConcurrentLinkedQueue`.
[Herlihy]	Maurice Herlihy and Nir Shavit: The Art of Multiprocessor Programming Morgan Kaufmann 2008. ISBN 978-0-12-370591-4. A presentation of concurrent programming with shared variables with emphasis on using non-blocking synchronization techniques written by two of the pioneers within this area. Recommended after this course for those interested in more advanced synchronization techniques.
[Raynal]	Michel Raynal: Concurrent Programming: Algorithms, Principles and Foundations Springer 2013. ISBN 978-3-642-32026-2. A newer book presenting numerous concurrent algorithms with focus on wait-free synchronization techniques using a fairly rigid approach.