Concurrency & Multithreading 2016-2017
week 44-50: Monday 11.00-12.45 in room M639
week 44-50: Wednesday 13.30-15.15 in room M639
lecturer: Wan Fokkink
week 44-50: Tuesday 11.00-12.45 in room M623
week 44-50: Thursday 9.00-10.45 in room M639
teaching assistant: Chris Ouwehand
To obtain a good understanding of concurrency concepts and multicore computing
- Fundamental insight into multicore computing: mutual exclusion,
locks, read-modify-write operations, lost wakeups, ABA problem,
consensus, construction of atomic multi-reader-multi-writer registers
Algorithms for multicore computing: mutual exclusion algorithms,
spin locks, monitors, barriers, AtomicStampedReference class in Java, transactional memory
Analyzing multicore algorithms: functionality, linearizability,
starvation- and wait-freeness, Amdahl's law, determine efficiency gain of parallelism
Concurrent datastructuren: lists, queues, stacks
Multicore programming: hands-on programming experience, perform experiments with multicore programs, thread pools in Java
For the BSc variant of this course there is a programming assignment that counts for 25% of the final mark.
For the MSc variant of this course there is a programming assignment that counts for 35% of the final mark.
You can make these assignments either alone or in a team of two persons.
A resit for the programming assignment is only offered if initially you
achieved at least a 3.0 for this assignment. The maximum mark for such a
revised program is a 6.0.
Assignment: Concurrent Data Structures
Referenced paper: Non-blocking Binary Search Trees (MSc only)
Framework: Java skeleton with Ant build script (Note: requires Java JDK and Ant).
Note that there are intermediate deadlines in the assignment! For Bachelor students, the first deadline is on
Sunday November 20 at 23:59, for Master students, the first deadline is already on Sunday November 13 at 23:59.
Deadlines are strict! If you are unable to finish the assignment in time, at least submit your unfinished work before the deadline.
See the assignment for further details.
The programming assignment is coordinated by Ceriel Jacobs. Teaching assistant is Evangelos Chatzikalymnios.
Register your team of two persons, or that you want to do the assignment alone, at the coordinator.
Please mention the following in your registration mail:
- your name, email address, and student number
- whether you are a master or bachelor student
- if you work in a team or alone; if in a team, name, email address and student number of your partner
- whether you already have a DAS4 account; if not, a temporary one will be provided
DAS4 accounts should be requested from the coordinator. Do NOT request them yourselves from the DAS4 administrators!
NEW! Revised copies of the slides for the regular lectures
Slides for the guest lecture by Pieter Hijma
The lectures are based on Maurice Herlihy and Nir Shavit, The Art of Multiprocessor Programming, Morgan Kauffmann, 2008 (or revised 1st edition, 2012)
Have a look at the list of errata from the authors and my own errata
Schedule per lecture:
- H 1.1-1.3, 1.5-1.6, Appendix B: Introduction: SMP and NUMA architectures, flag protocol for mutual exclusion, can protocol for producers-consumers, Amdahl's law;
H 3.7: Progress properties.
- H 2.1-2.6, 2.8: Mutual Exclusion: Critical sections, locks in Java, Peterson lock, Filter lock, volatile variables, Bakery algorithm, lower bound on the number of locations, Fischer's algorithm.
- H 3.1-3.2, 3.4-3.6, 3.8: Concurrent Objects: Pre- and postconditions, linearizability, wait-free bounded queue, sequential consistency;
H 4.1, 4.2.4-4.2.6: Foundations of Shared Memory: From regular SRSW to atomic SRSW, from atomic SRSW to atomic MRSW, from atomic MRSW to atomic MRMW.
- H 5.1-5.4, 5.6-5.8: The Relative Power of Primitive Synchronization Operations: Consensus, impossibility of consensus with atomic registers, 2-thread consensus with a queue, impossibility of 3-thread consensus with a queue, read-modify-write registers, n-thread consensus with compareAndSet;
H 6.1-6.4: Universality of Consensus: A wait-free universal construction.
- H 7.1-7.6: Spin Locks and Contention: TAS and TTAS locks, exponential back-off, Anderson lock, CLH lock, MCS lock, CLH lock with timeout.
- H 8.1-8.4: Monitors and Blocking Synchronization: Monitors, conditions, bounded queue with locks and conditions, the lost-wakeup problem, readers-writers lock, reentrant lock, semaphore, synchronized method;
H 17.1-17.5, exercises 202,207: Barriers: Sense-reversing barrier, combining tree barrier, tournament barrier, dissemination barrier.
- Multithreaded Programming: Pieter Hijma discusses some example multithreaded programs in detail.
- H 9.1-9.9: Linked Lists: The Role of Locking: Optimistic, lazy and lock-free synchronization for list-based sets, AtomicMarkableReference class.
- H 10.1-10.6 (not 10.6.1), 11.1-11.4: Concurrent Queues and Stacks: Fine-grained bounded and unbounded queue, unbounded lock-free queue, the ABA problem, unbounded lock-free stack, elimination array.
- H 16.1-16.2, 16.4-16.5.1, 17.6: Work Distribution, Futures and Scheduling: Work-stealing bounded queue, termination detecting barrier, parallelization of matrix operations, thread pools in Java, measuring parallelism.
- H 18.1-18.3.7, 18.4: Transactional Memory: What is wrong with locking and compareAndSet, transactions, MESI cache coherence protocol, hardware transactional memory, software transactional memory.
- no lecture
- no lecture
- question hour
- 1 2 4 5 6 7
- 10 11 12 13 14 15 16
- 24 27 28 32 33 36 40 41 42 46
- 52 53 54 55 57 76 77 80 83
- 85 86 91 92 extra exercises I and II
- 93 95 96 98 199 202 204 207 208
- no exercise class
- 100 101 102 103 104 105 106 108 109 112 113 114 115 117 118
- 120 121 122 123 124 125 126 127 128 129
- 185 186 188 190 191 192 193(1) 196 210
- extra exercises III, IV, V, VI, VII, VIII 211 213 223
- no exercise class
- no exercise class
- exam from 2014 is discussed + question hour
The written exam will count for BSc students for 75% and for MSc students for 65% of the final mark. For the material you need to study for this exam, see the "schedule per lecture" and the slides; you should also study appendices A and B. Material from the textbook that is not covered during the lectures (e.g., several correctness proofs) does not have to be studied for the exam! At the exam, you may use the textbook of Herlihy and Shavit. Answers can be given in English or Dutch. (You are not allowed to use the slides, or a laptop.)
To pass the course, at least a 5.0 must be achieved for the two individual parts (programming assignment and written exam), as well as an overall average mark of at least 5.5.