CONCURRENT SYSTEM PPT
Schedule &
Syllabus
|
Synchronization 1: Review of
Kernel Locking Techniques
A discussion of various forms of lock-based synchronization used in OS kernels. A case study of locking primitives used in the Linux kernel. Reading:
|
Synchronization 2: Lock-Free
(non-blocking) Synchronization
Lock-free synchronization strategies for common kernel data structures, kernel design based on extensive use of lock-free synchronization and other strategies to improve locality. Reading:
|
Synchronization 3: Practical
Blocking & Non-Blocking Queue Algorithms
Practical blocking and non-blocking queue algorithms using Compare and Swap (CAS) which is a readily available instruction on modern CPUs. Effects of preemption on performance of locking and non-blocking synchronization. Reading:
|
Complication 1: Memory Consistency
Models
Review of memory consistency models used by modern CPUs. Algorithms discussed earlier assume sequential consistency, which is not typical of modern CPUs. Safety net techniques, in the form of memory barriers, must be used to make such algorithms safe in the presence of weak consistency models, which are typical. Reading:
|
Complication 2: Compiler
reordering
Discussion of the correctness implications of compiler and architecture-level reordering when concurrency is implemented outside the compiler (i.e. through a thread-library). Reading:
|
Synchronization 4: General Methods
for Non-Blocking Synchronization
A general methodology for converting sequential objects to non-blocking objects. Introduction to simple memory management approaches and issues. Reading:
|
Synchronization 5: Safe Memory
Reclamation for Lock-Free Objects;
Discussion of the implications of non-blocking synchronization on memory management. The use of "hazard pointers" for safe and scalable memory reclamation with lock-free objects. Reading:
|
Synchronization 6: Relativistic
Programming using RCU
Review of the Read-Copy Update (RCU) technique with lock-based writers, lock-free readers, and quiescent state based deferred reclamation, for practical scalable concurrent programming on modern architectures. Reading:
|
Synchronization 7: RCU Implementations
An in depth look at how various versions of RCU are implemented in the Linux kernel. Reading:
|
Synchronization 8: Relativistic
Programming Case Studies
Case study of two examples of relativistic programming. Specifically, a study of relativistic implementations of hash tables and red-black trees. Reading:
|
Synchronization 9: Transactional
Memory
Introduction to the transactional memory abstraction as a means of simplifying concurrent programming. Outline of a hardware implementation of transactional memory. Reading:
|
Synchronization 10: Software
Transactional Memory
Comparison of various software implementations of Transactional Memory. Reading:
|
Synchronization 11: Practical
Issues for Transactional Memory
Discussion of transactional memory properties and performance. Reading:
The following is an interesting
and relevant paper I just came across ...
Understanding Transactional Memory Performance
Donald Porter and Emmett Witchel, In the Proceedings of the 2010 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS '10), White Plains, NY, March 2010 |
Synchronization 12: Case Study of
Transactional Memory Use in an OS
Discussion of performance, I/O and scheduling interactions of transactional memory in an operating system. Reading:
|
Review: A Comparison of
Synchronization Technologies
Comparison of relative merits of transactional memory and other synchronization techniques. Reading:
|
Scalability 1: Spin Lock
Performance Considerations.
Implementation strategies for spin locks, with emphasis on contention issues and design strategies that improve performance. Reading:
|
Scalability 2: Locality Issues in
Scalable Kernel Design
Locality issues, object distribution and replication, scalable locking and interaction with memory management. Reading:
|
Scalability 3: Communication and
Synchronization Strategies for SMMP Kernels;
Implications of interrupt-level vs process-level execution and the use of remote access vs remote invocation for communication across processors in shared memory multiprocessor kernels. Reading:
|
Scalability 4: Scalable Kernel
Design Based on Message Passing
Message passing as a foundation for scalable multiprocessor kernels. Reading:
|
Scalability 5: Local Research
Discussion of local research on scalable OS architectures. |
No comments:
Post a Comment