Concurrency & Multithreading 2018-2019


Lecturer

Wan Fokkink

Teaching assistants

Ruben Helsloot, Hans-Dieter Hiep


Learning objective

To obtain a good understanding of concurrency concepts and multicore computing

Programming assignment

The programming assignment as well as practical information regarding this assignment can be found here.


Slides

NEW! Revised version (after the 3rd lecture) of the slides for the regular lectures

Slides for the guest lecture by Pieter Hijma


Book

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:

  1. 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.
  2. 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.
  3. 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: Foundations of Shared Memory: From safe MRSW to atomic MRMW registers;
  4. 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.
  5. 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.
  6. 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.
  7. Multithreaded Programming: Pieter Hijma discusses some example multithreaded programs in detail.
  8. H 9.1-9.9: Linked Lists: The Role of Locking: Optimistic, lazy and lock-free synchronization for list-based sets, AtomicMarkableReference class.
  9. 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.
  10. 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.
  11. no lecture
  12. 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.
  13. no lecture
  14. question hour


Exercise classes

  1. 1 2 4 5 6 7
  2. 10 11 12 13 14 15 16 17
  3. 24 27 28 32 33 36 39 40 41 42 46
  4. 52 53 54 55 57 64 67 76 77 78 80 81 83
  5. 85 86 91 92 extra exercises I and II
  6. no exercise class
  7. 93 95 96 98 199 202 204 207 208
  8. 100 101 102 103 104 105 106 108 109 112 113 114 115 117 118
  9. 120 121 122 123 124 125 126 127 128 129
  10. no exercise class
  11. 185 186 188 190 191 192 193(1) 196 210
  12. no exercise class
  13. extra exercises III, IV, V, VI, VII, VIII 211 213 223
  14. no exercise class



Written exam

The written exam will count for 75% 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.


Video lectures

Video lectures by Maurice Herlihy

A lecture on hardware transactional memory by Michael Neuling