Book

Schedule per lecture:

1. H 1.1-1.3, 1.5-1.6: 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.
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.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.
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 queue lock, CLH queue lock, MCS queue lock, CLH queue 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.
7. Multithreaded programming: Pieter Hijma discusses an example multithreaded program in detail.
8. H 17.1-17.6, exercises 202,207: Barriers: Sense-reversing barrier, static tree barrier, combining tree barrier, tournament barrier, dissemination barrier, termination detection barrier.
9. H 9.1-9.9: Linked Lists: The Role of Locking: Coarse-grained synchronization, fine-grained synchronization, optimistic synchronization, lazy synchronization, lock-free synchronization, AtomicMarkableReference class.
10. 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 backoff array.
11. H 16.1-16.2, 16.4-16.5.1: Work Distribution, Futures and Scheduling: Work-stealing bounded queue, parallelization of matrix operations and the Fibonacci numbers, thread pools in Java, measuring parallelism.
12. H 18.1-18.3.7, 18.4: Transactional Memory: What is wrong with locking and compareAndSet, transactions, unbounded and bounded transactional queues, MESI cache coherence protocol, hardware transactional memory, software transactional memory, conflict resolution policies.
13. Question hour

Exercise classes

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

Programming assignments

Written exam

• exam 2010
• resit 2010