[an error occurred while processing this directive]

Screen Version

School of Computer Science & Engineering
University of New South Wales
 Advanced Operating Systems 
 COMP9242 2002/S2 

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.

[an error occurred while processing this directive]