Mutex and spinlocks

Mutex:
Short for mutual exclusion object. Mutex is kind of a key to use any resources in the system. If you have mutex, you can use the resource. Any thread that needs the resource must lock the mutex from other threads while it is using the resource. The mutex is set to unlock when the data is no longer needed or the routine is finished.

In java, this can be implemented by simply using a "synchronized" key word.

Java Class Semaphore
A semaphore maintains a set of permits. Each acquire() blocks if necessary until a permit is available, and then takes it. Each release() adds a permit, Semaphore just keeps a count of the number available and acts accordingly.
A semaphore initialized to one, and which is used such that it only has at most one permit available, can serve as a mutual exclusion lock. It is also known as a binary semaphore, because it only has two states: one permit available, zero not, or vice versa. When used in this way, the binary semaphore has the property that the "lock" can be released by a thread other than the owner.


Spinlock:
Spinlock is a lock which causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking if the lock is available.

In Java, this can be implemented by using a guarded block.

public synchronized String take(){
  //wait for the producer
  //to send the message
  while(empty){
   try{
    System.out.println("Waiting for producer to send the message...");
    wait();
   }catch(InterruptedException e){};
  }
  empty = true;
  //Notify producer that
  //status has changed
  notifyAll();
  return message;
 }

In the above example, while another thread is using the resource, the boolean empty = true, the current thread will wait until the empty is set to false. Then it will reset the empty to true and notify all other threads that it is using the resource after acquiring the resource.
The "synchronized" keyword in the above example allows multiple threads to share the same resource (object), however, if one thread is executing the take() method, all other threads must wait until the current thread finishes executing.

FIFOMutex
The following snippet is hacked from Java doc, which uses a queue to perform a FIFO order for each thread to access the resource. Basically, if you are not on top of the queue, wait for your turn. :)

public class FIFOMutex {
 private final AtomicBoolean locked = new AtomicBoolean(false);
 //The head of the queue is that element that has been on the queue the longest time. 
 //The tail of the queue is that element that has been on the queue the shortest time
 private final Queue waiters = new ConcurrentLinkedQueue();
 
 public void lock(){
  boolean wasInterrupted = false;
  //currentThread(): 
  //Returns a reference to the currently executing thread object.
  Thread current = Thread.currentThread();
  waiters.add(current);
  //if already locked or it is not the first thread in the queue
  while(waiters.peek() != current || !locked.compareAndSet(false, true)){
   //Disables the current thread for 
   //thread scheduling purposes unless the permit is available
   LockSupport.park(this);
   if(Thread.interrupted())//ignore interrupts while waiting
    wasInterrupted = true;
  }
  //remove head, inherent from AbstractQueue
  //throw an exception if queue is empty
  //poll() will return null if empty
  waiters.remove();
  //interrupt the thread that was supposed to be interrupted while waiting
  if(wasInterrupted)
   current.interrupt();
 }
 public void unlock(){
  locked.set(false);
  //Makes available the permit for the given thread, 
  //if it was not already available.
  LockSupport.unpark(waiters.peek());
 }

}

Here is another method stolen from here. I personally don't like this version, since its not as clear as the first one.

/**
 * the following code uses a ReentrantLock to queue up the threads, 
 * the fairness policy is applied so as to implement the FIFO nature
 * If releaseCount is zero, that means all threads on the queue is 
 * waiting for the lock
 * when release() is invoked, increase the releaseCount to release the number 
 * of threads
 * @author shirleyyoung
 *
 */

public class ResourceWaitQueue {
 //if using fairness policy
 //when set true, the lock favors granting access to the longest-waiting thread. 
 //Otherwise this lock does not guarantee any particular access order
 //use fair locks may cause the program to be slower, 
 //often much slower than those using the default setting, 
 //but have smaller variances in times to obtain locks and guarantee lack of starvation
 private final ReentrantLock lock = new ReentrantLock(true);
 //Returns a Condition instance for use with this Lock instance.
 private final Condition goodToGo = lock.newCondition();
 private int releaseCount = 0;
 
 public final void await() throws InterruptedException{
  lock.lock();
  try{
   while(releaseCount == 0)
    //Causes the current thread to wait 
    //until it is signaled or interrupted.
    goodToGo.await();
   if(--releaseCount > 0)
    //Wakes up one waiting thread.
    //If any threads are waiting on this condition 
    //then one is selected for waking up. 
    //That thread must then re-acquire the 
    //lock before returning from await.
    goodToGo.signal();
  } finally {
   lock.unlock();
  }
 }
 public final void release(){
  lock.lock();
  try{
   releaseCount++;
   goodToGo.signal();
  } finally{
   lock.unlock();
  }
 }
 
}