[CSE]  Advanced Operating Systems 
 COMP9242 2002/S2 
UNSW

PRINTER 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 ReferenceMIPS R4000 User Manual 
- Network Driver
- GT64111
 
Related Info
- Aurema OS Prize
- OS Hall of Fame
 
History
- 2000
- 1999
- 1998
 
Staff
- Gernot Heiser (LiC)

 
Valid HTML 4.0!
next up previous
Next: Dangers of Locking: Priority Up: 10-smp Previous: Mutual Exclusion Techniques

Subsections

Spin locks

void lock (volatile lock_t *l) {
   while (test_and_set(l)) ;
}
void unlock (volatile lock_t *l) {
   *l = 0;
}

Busy waits. Good idea?

Spin lock busy-waits until lock is released:

  • Stupid on uniprocessors, as nothing will change while spinning.
    • Should release (yield) CPU immediately.
  • Maybe ok on SMPs: locker may execute on other CPU.
    • Minimal overhead.
    • Still, should only spin for short time.
Generally restrict spin locking to:
  • short critical sections,
  • unlikely to be contended by the same CPU.
  • local contention can be prevented
    • by design
    • by turning off interrupts

Alternative: Conditional lock

bool cond_lock (volatile lock_t *l) {
   if (test_and_set(l))
      return FALSE; //couldn't lock
   else
      return TRUE;  //acquired lock
}



  • Can do useful work if fail to aquire lock.
  • But may not have much else to do.
  • Starvation: May never get lock!

More appropriate mutex primitive:

void mutex_lock (volatile lock_t *l) {
   while (1) {
      for (int i=0; i<MUTEX_N; i++)
         if (!test_and_set(l))
            return;
      yield();
   }
}

  • Spins for limited time only
    • assumes enough for other CPU to exit critical section
  • Useful if critical section is shorther than N iterations.
  • Starvation possible.

Multiprocessor spin lock:

void mp_spinlock (volatile lock_t *l) {
   cli();    // prevent local contention
   while (test_and_set(l)) ;   // lock
}
void mp_unlock (volatile lock_t *l) {
   *l = 0;
   sti();
}
  • only good for short critical sections

Multireader locks:

void rw_rdlock (volatile lock_ *l);
void rw_wrlock (volatile lock_ *l);
  • Allow mutliple readers into the critical section concurrently.
  • Write access is exclusive.
  • Too much overhead for really short critical sections.
  • Used in UNIX SysVR4.


next up previous
Next: Dangers of Locking: Priority Up: 10-smp Previous: Mutual Exclusion Techniques
Gernot Heiser 2002-10-11