Screen Version

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

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.