Systems, Networks & Concurrency 2019
Summary
Uwe R. Zimmer – The Australian National University
10
• Forms of concurrency
• Models and terminology
• Processes and threads
• Basic concepts and notions
• Processstates
• Concurrent programming languages:
• Explicit concurrency: e.g. Ada, Chapel
• Implicit concurrency: functional programming – e.g. Haskell, Caml
Summary
Summary
Concurrency – The Basic Concepts
• Abstractions and perspectives: computer science, physics & engineering
• Observations: non-determinism, atomicity, interaction, interleaving
• Correctness in concurrent systems
© 2019 Uwe R. Zimmer, The Australian National University page 747 of 757 (chapter 10: “Summary” up to page 757)
• Definition of mutual exclusion
• Atomic load and atomic store operations
• … some classical errors
• Decker’s algorithm, Peterson’s algorithm
• Bakeryalgorithm
• Realistic hardware support
• Atomic test-and-set, Atomic exchanges, Memory cell reservations
• Semaphores
• Basic semaphore definition
• Operating systems style semaphores
Summary
Summary
Mutual Exclusion
© 2019 Uwe R. Zimmer, The Australian National University page 748 of 757 (chapter 10: “Summary” up to page 757)
• Guard evaluation times, nested monitor calls, deadlocks, simultaneous reading, queue management.
• Synchronization and object orientation, blocking operations and re-queuing.
• Message based synchronization
• Synchronizationmodels • Addressingmodes
• Messagestructures
• Examples
© 2019 Uwe R. Zimmer, The Australian National University
page 749 of 757 (chapter 10: “Summary” up to page 757)
Summary
Summary
Communication & Synchronization
• Shared memory based synchronization • Flags, condition variables, semaphores,
conditional critical regions, monitors, protected objects.
• Non-determimism by design: • Benefits & considerations
• Non-determinism by interaction: • Selectivesynchronization
• Selectiveaccepts
• Selectivecalls
• Correctness of non-deterministic programs:
• Sources of non-determinism
• Predicates & invariants
© 2019 Uwe R. Zimmer, The Australian National University
page 750 of 757 (chapter 10: “Summary” up to page 757)
Summary
Summary
Non-Determinism
• Data-Parallelism
• Vectorization
• Reduction
• Generaldata-parallelism
• Examples
• Imageprocessing • Cellularautomata
© 2019 Uwe R. Zimmer, The Australian National University
page 751 of 757 (chapter 10: “Summary” up to page 757)
Summary
Summary
Data Parallelism
• Basic performance scheduling
• Motivation & Terms
• Levels of knowledge / assumptions about the task set
• Evaluation of performance and selection of appropriate methods
• Towards predictable scheduling • Motivation & Terms
• Categories & Examples
Summary
Summary
Scheduling
© 2019 Uwe R. Zimmer, The Australian National University page 752 of 757 (chapter 10: “Summary” up to page 757)
• Liveness • Fairness
• Safety
• Deadlockdetection • Deadlockavoidance • Deadlockprevention
• Atomic & Idempotent operations • Definitions & implications
• Failure modes
• Definitions, fault sources and basic fault tolerance
© 2019 Uwe R. Zimmer, The Australian National University
page 753 of 757 (chapter 10: “Summary” up to page 757)
Summary
Summary
Safety & Liveness
• Networks
• OSI,topologies
• Practical network standards
• Time
• Synchronized clocks, virtual (logical) times
• Distributed critical regions (synchronized, logical, token ring)
• Distributed systems • Elections
Summary
Summary
Distributed Systems
• Distributed states, consistent snapshots
• Distributed servers (replicates, distributed processing, distributed commits)
• Transactions (ACID properties, serializable interleavings, transaction schedulers)
© 2019 Uwe R. Zimmer, The Australian National University page 754 of 757 (chapter 10: “Summary” up to page 757)
• Data-Parallelism
• Vectorization, Reduction, General data-parallelism
• Concurrency in languages
• Some examples: Haskell, Occam, Chapel
• Operating systems
• Structures: monolithic, modular, layered, μkernels • UNIX,POSIX
© 2019 Uwe R. Zimmer, The Australian National University
page 755 of 757 (chapter 10: “Summary” up to page 757)
Summary
Summary
Architectures
• Hardware architectures – from simple logic to supercomputers • logic, CPU architecture, pipelines, out-of-order execution, multithreading, …
Summary
Exam preparations
Helpful
• Distinguish central aspects from excursions, examples & implementations.
• Gain full understanding of all central aspects.
• Be able to categorize any given example under a general theme discussed in the lecture.
• Explain to and discuss the topics with other (preferably better) students.
• Try whether you can connect aspects from different parts of the lecture.
Not helpful
• Remembering the slides word by word.
• Learn the Chapel / Unix / Posix / Occam / sockets reference manual page by page.
© 2019 Uwe R. Zimmer, The Australian National University page 756 of 757 (chapter 10: “Summary” up to page 757)
© 2019 Uwe R. Zimmer, The Australian National University
page 757 of 757 (chapter 10: “Summary” up to page 757)
Summary