Saturday, July 30, 2011

Something about Interrupt, Mutex and Semaphore

The details of interrupt and mutex are not that simple. Be aware of the following bullets:

  1. Disable/Enable interrupt can be used to implement mutex. It is simple but flawed.
  2. For multi-processors, disable interrupt may not be useful, unless you disable interrupt on all processors, which will be prohibitively expensive.
  3. Atomic instruction, such as test-and-set, can be used to implement mutex. test-and-set is an atomic instruction which writes 1 to a memory location and fetch the old value of that location. For example, a spin-lock implementation is given as follow:
  4. while (test_and_set(lock)==1);
  5. Besides,  other atomic instructions such as exchange, compare&swap, load linked and conditional store can also be used.
  6. For the example given in 3), we will busy wait. To minimize the waiting time, we can do the following (add a guard variable):
  7. while (test_and_set(guard)==1);
    
    if(lock_value == 1)
    {
       put the thread in the waiting queue for the lock;
       go to sleep;
       guard = 0;
    }
    else
    { 
       lock_value = 1;
       guard = 0
    }
  8. Spin lock can sometimes delay releasing the lock. For example, thread A get switched out right after grabbing the lock. Thread B kicks in and try to grab the lock, but the lock has already been grabbed. Thread B has to be busy waiting, which will delay the switching back to thread A.
  9. Semaphore represents the number of resources that are still available to simultaneous users (e.g. there are still 4 available slots)..   
  10. Besides, we can also use implement some lock-free data structure in pursuit of better performance. These structures usually leverage some atomic instructions or atomic variables (the read/write to the variable is atomic, e.g. pointer type.). Some data structures are weak enough to be implemented without special atomic primitives, e.g., FIFO queue.

No comments:

Post a Comment