Advanced Operating Systems   COMP9242 2002/S2

UNSW

Printer-Friendly Version Administration                - Notices - Course Intro - Consultations # On-line Survey (closed) - Survey Results   Work - Lectures - Milestone 0 - Project Admin - Project Spec - Project FAQ - Exam   Documentation - ASysT Lab - L4 source browser - Sulima ISA Simulator - R4x00 ISA Summary  - MIPS R4700 Reference - MIPS R4000 User Manual  - Network Driver - GT64111   Related Info - Aurema OS Prize - OS Hall of Fame   History - 2000 - 1999 - 1998   Staff - Gernot Heiser (LiC)

Dangers of Locking: Priority Inversion Assume , all running on same CPU. prevents higher-priority process from executing. Solution: Avoid preempting processes holding a kernel lock. How? Solution: Priority inheritance Blocked high-prio process helps locker by donating time slices. Also called wait-free locking[CSL$^+$87]. Everything needs to be prioritised. Need to record holder of lock. No good if holds lock too long. Wait-free synch. of long critical sections: Multiprocessor priority-inheritance protocol [HH01] cross-CPU helping: holds lock, helps remote helping: migrates to 's CPU only works if becomes highest-prio on 's CPU need global ``end-to-end'' prio scheme otherwise not wait-free race condition: migrates to , migrates away... local helping: execute's 's code on own CPU 's state must migrate to 's CPU totally wait-free: highest-prio always makes progress Alternative: Lock-free synchronisation: Ensure all data is always consistent Perform changes on shadow copies When completed, perform atomic swap eg swap pointers with atomic compare-and-swap instruction use mp_spinlock if no such instruction practically limited to simple data structures (linked lists) Best to avoid long critical sections in kernel! What to lock? Giant lock: lock whole kernel. Only one process can execute in kernel. Similar to dedicated OS processor. Coarse-grain locks: lock whole subsystems. E.g., all TCBs, file system. Marginal improvement over giant lock, not scalable. Fine-grain locks: lock as little as possible at a time. Potential for large amount of parallelism. Only suitable approach for large numbers of CPUs. All but giant locks can lead to deadlocks! Usual deadlock-avoidance schemes apply (numbering locks). May not always know in advance which locks are needed. Release lock temporarily to obtain lower-numbered one. Must leave DS consistent when releasing. Must recheck state after reacquiring.