|
|
|
|
|
02158 Concurrent Programming Fall 2023 |
Course Material |
| Home | Plan | Material |
| [Andrews] |
Gregory R. Andrews:
Foundations of Multithreaded, Parallel, and Distributed
Programming Addison-Wesley 2000. ISBN 0-201-35752-6 / 9780201357523
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 New slightly extended version as of Oct. 9 |
| [Proc] |
Hans Henrik Løvengreen: Concurrent Programming Practice:
Processes, Threads and Tasks, vers. 2.0
(preliminary v.2). Course note, 22 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. |
| [Sols] |
Compilation of all solutions for exercise
classes and weekly exercises.
|
To give you some idea of the kinds of problems that you might encounter for the exam, a number of old exam papers are presented below.
More exam papers and solutions will be provided successively - before the exam.
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.
| Exam | Solutions | Duration
|
| E22(pdf) | (pdf) | 4 Hours
|
| E21(pdf) | (pdf) | 4 Hours
|
| E20(pdf) | (pdf) | 4 Hours
|
| Trial E20(pdf) | (pdf) | 4 Hours
|
| E19(pdf) | (pdf) | 2 Hours
|
| E18(pdf) | (pdf) | 2 Hours
|
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.
Lock types:
spinlock_types.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 |
| [Python] |
Some references for concurrency in Python (some require free account):
The
Threading library
|
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. |
| [Lamport] |
Leslie Lamport:
Specyfying Systems: The TLA+ Language and Tools for Hardware
and Software Engineers Addison-Wesley 2003. ISBN 0-321-14306-X.
Describes how both concurrency specificatons and concurrent programs
may be expressed in the extended temporal logic of actions: TLA+.
|
| [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). |
| [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, Nov 30, 2023 |