Concurrent and System Programming¶
Lecturer: dr hab. inż. Paweł T. Wojciechowski, prof. PP
Web page in e-kursy: https://ekursy.put.poznan.pl/course/view.php?id=35705
Consultation: by e-mail
Over the past decades, Moore’s law has been in force: “the number of transistors in an integrated circuit doubles about every two years”. Each new generation of processors made the programs to work faster. However, this trend is changing. The future computer systems will have more and more CPU multi-core units, but each individual unit will not be faster than the unit from the previous year. Thus, to fully utilize the hardware capabilities, computations must be carried out concurrently.
A major focus of concurrent programming is to correctly and effectively program the parts of the code that require coordination and synchronization, because these parts can substantially affect the correctness and performance of our concurrent program as a whole.
The aim of the course is to introduce concurrency control concepts and their implications for system design and implementation aimed for current computer architectures. A handout for students is available here.
Below is a list of topics (Winter term 2023) (Syllabus in Polish):
Introduction¶
Processes and threads.
Concurrency vs parallelism.
Synchronization¶
A critical section and the need for concurrent coordination, explained solving a real life example. The example has been used to explain basic properties: mutual exclusion, deadlock-freedom, starvation-freedom (or lockout-freedom), and limited waiting.
Two basic synchronization patterns: atomicity and condition synchronization.
Atomicity implemented using a single lock vs fine-grain locking; deadlock on locks.
Condition synchronization illustrated by a bounded buffer.
A synchronization barrier.
Two basic techniques to implement condition synchronization and mutual exclusion (locks): spinning (busy waiting) and blocking (at the thread scheduler).
Correctness: safety (e.g., mutual exclusion, deadlock freedom) and liveness (e.g., starvation freedom, livelock freedom).
Amdahl’s Law.
Deadlock¶
Requirements for deadlock: exclusive use, hold and wait, irrevocability (no preemption), and circularity.
A resource allocation graph (RAG).
Methods to ensure deadlock freedom:
breaking some requirement for deadlock,
preventing deadlock by design,
detecting deadlock and recovery,
avoiding deadlock (i.e., allocating resources safely).
RAG for avoiding deadlock.
Dijkstra’s Banker’s algorithm for avoiding deadlock.
Theory¶
Designing safe concurrent objects.
Sequential consistency and lack of composable orders.
Linearizability and its formal definition (sequential, well formed, legal, and linearizable histories); linearizable objects.
Comparison of sequential consistency and linearizability using examples.
Properties of linearizability: compositionality (locality) and nonblocking, with proofs.
Parallelizing a sorted linked list using hand-over-hand locking (lock coupling) for efficiency.
Transactions, serializability, and strict serializability.
Comparison of ordering properties (sequential consistency, linearizability, serializability, and strict serializability).
Liveness: blocking vs nonblocking.
Variants of nonblocking progress: wait freedom (≡ starvation freedom), lock freedom (≡ livelock freedom), and obstruction freedom.
Fairness (weak vs strong) by examples.
The consensus number to describe the relative “power” of atomic primitives.
Data races and the happens-before relation.
Towards language-level memory models.
Spin Locks¶
Historical algorithms to solve mutual exclusion (implement locks):
Dekker’s algorithm for two threads and its generalization to n-threads,
Peterson’s algorithm for two threads, with a proof sketch,
Lamport’s “bakery” algorithm.
Algorithms using TAS:
test-and-set (TAS) lock,
test-and-test-and-set (TTAS) lock,
a lock with exponential backoff.
Mellor-Crummey and Scott’s ticket lock (with FAI).
Extended interface: timeout, trylocks.
A reentrant lock and its example implementation.
The readers and writers problem (including fairness issues).
Reader-writer lock and its example implementation using CAS and FAA.
Other variants of locks: queued locks and sequence locks.
The Read-copy update (RCU) strategy to avoid some locks; a general scheme for setting grace period in order to reclaim memory safely.
Scheduling, Semaphores, Monitors, and CCRs¶
Thread scheduling: multiplexing concurrent (kernel) threads on a single core (coroutines, context blocks, a ready list, preemption, and routines: reschedule, yield, and transfer).
Dijkstra’s semaphores and its blocking implementation (at the thread scheduler level).
Binary vs counting semaphores.
N-resource allocation with a semaphore.
The producer-consumer problem and a bounded buffer.
A bounded buffer implemented using semaphores.
Monitors and condition variables.
Hoare’s classic monitor and its implementation using semaphores.
A bounded buffer implemented using Hoare’s monitor.
Monitors in Java/C#.
Comparison of the “classic” and Java/C# monitors.
The nested monitor problem.
Conditional critical region (CCR).
A bounded buffer implemented using CCR.
Barriers¶
Example use of flags and barriers.
The sense-reversing centralized algorithm implementing a barrier.
The dissemination barrier.
Fuzzy barriers improving performance of programs with barriers.
Fuzzy variant of the sense-reversing barrier.
Hardware AND barriers and the “Eureka” OR operation.
Series-parallel execution in Cilk (extension of C for parallel computing).
Transactional Memory¶
Transactional memory (TM) and its potential advantages (e.g. scalability, composability, and deadlock prevention).
Conditional synchronization with retry and orElse.
The design of software transactional memory (STM): progress guarantees, buffering of speculative updates (undo logging vs redo logging), conflict resolution (eagerly vs lazily), access tracking (“ownership” records).
Validation in STM and correctness issues (single lock atomicity, opacity).
Inconsistent state due to interaction of STM transactions with nontransactional code (the “publication” and “privatization” examples).
Hardware transactional memory (HTM); extension of the MESI cache coherence protocol.
Advantages and disadvantages of HTM.
Nonblocking Algorithms for Concurrent Data Structures¶
An example of a single-word atomic counter with CAS.
The lock-free Treiber’s stack algorithm (using CAS).
The lock-free Michael and Scott’s M&S queue algorithm (using CAS).
The Harris and Michael’s H&M list – a general idea.
Herlihy’s universal construction of a nonblocking data structure from its sequential specification.