The Synergy Between Non-Blocking Synchronization and Operating System Structure

Cache Kernel (OSDI ‘94)

Synergy between OS Structure & Non-Blocking Synchronization (NBS)

Example: Deletion from linked list

Double Compare and Swap

Type-stable memory management (TSM)

TSM is good OS structuring

TSM aids Non-Blocking Synchronization

NBS is good for OS structure: non-blocking signals

Contention Minimizing Data Structures(CMDS)

CMDS Benefits

NBS is good for OS structure: Synch.subordinate to scheduling

Minimizing the (W of I) Window of Inconsistency

Minimizing the window of inconsistency

NBS is good for OS structure:

Implementing non-blocking Synchronization

Implementing non-blocking Synchronization (cont.)

Results: Complexity & Correctness

Performance of NBS No Preemption

Performance of NBS With Preemption

Conclusions

Conclusions (2)

Advantages of Non-blocking Synchronization

Obstacles to deployment