Search This Blog

Friday, September 30, 2011



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.


Course Overview slides:
[ppt] [pdf]
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.

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.

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.

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).

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.

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.

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.

Synchronization 7: RCU Implementations
An in depth look at how various versions of RCU are implemented in the Linux kernel.

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.

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.

Synchronization 10: Software Transactional Memory
Comparison of various software implementations of Transactional Memory.

Synchronization 11: Practical Issues for Transactional Memory
Discussion of transactional memory properties and performance.

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.

Review: A Comparison of Synchronization Technologies
Comparison of relative merits of transactional memory and other synchronization techniques.

Scalability 1: Spin Lock Performance Considerations.
Implementation strategies for spin locks, with emphasis on contention issues and design strategies that improve performance.

Scalability 2: Locality Issues in Scalable Kernel Design
Locality issues, object distribution and replication, scalable locking and interaction with memory management.

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.

Scalability 4: Scalable Kernel Design Based on Message Passing
Message passing as a foundation for scalable multiprocessor kernels.

Presenter: Mark Smith
Slides: [.ppt] [.pdf]
Scalability 5: Local Research
Discussion of local research on scalable OS architectures.

No comments:

Post a Comment