Transcript Document

CS533 Concepts of Operating Systems
Class 4
RCU – Scalable Synchronization on
Modern Shared Memory Multiprocessors
Questions


Why have synchronization instructions become more
expensive (relatively) as processors have become
faster?
Why does their cost limit scalability, even in the
absence of lock contention?
CS533 - Concepts of Operating Systems
2
Questions


Why doesn’t global reader-writer locking scale on
modern SMMP machines?
What is per-CPU reader-writer locking (brlock)?
o
o

Why does this improve scalability?
Why is it still far from ideal?
How does the hazard pointer approach improve
performance further?
o
What is its main source of overhead for readers?
CS533 - Concepts of Operating Systems
3
Questions



How does RCU prevent writers from corrupting the
state read by readers?
Why does RCU defer the destruction of old
versions?
When is it safe to reclaim the storage used by an old
version?
o
o
How can you know this?
How can you know it without requiring readers to use
expensive synchronization primitives?
CS533 - Concepts of Operating Systems
4
Questions

In what way is RCU’s distribution of synchronization
overhead asymmetrical?
o

When is this asymmetry beneficial?
How does RCU distribute synchronization overhead
between readers and writers?
o
o
What do readers do?
What do writers do?
CS533 - Concepts of Operating Systems
5
Questions

How does RCU use programming conventions to
piggyback reader-completion signals on naturally
occurring system states?
o
o

How can grace periods be inferred by counting
context switches in non-preemptive kernels?
o

What is a quiescent state?
What is a grace period?
What could you count if the kernel was preemptive?
What are the advantages and disadvantages of long
grace periods?
CS533 - Concepts of Operating Systems
6
Reminder

Class 5 presenters
o
o
Discuss your presentation plans with me ahead of time
Mail me the final version of your slides BEFORE the class
CS533 - Concepts of Operating Systems
7