SMP Mutex Lock

A mutex (short for mutual exclusion), is a lock that waits for a field to be released before proceeding. In its simplist incantation, a mutex constantly checks the field in question. This type of lock thus uses the following alorithm:

mutex (void *addr)  {
while (test_and_set(addr) == 1) ;
}

For this algorithm to work, there must be an atomic operation: test_and_set(void *ptr). This operation writes a 1 into the given word address. If the value was previously 0, then test_and_set() returns 0. Otherwise this operation returns 1.

It is important to note that a mutex does not voluntarily give up the cpu. In the kernel, this means never. In user space, the schedular can run another process if it has higher priority.

SMP Semaphore Lock

A semaphore is a lock in which the cpu is released if the field is not free. In its simplist incantation, a semaphore uses a mutex to try to set the lock. If the lock is not set, then the semaphore gives up the cpu and tries later. This type of lock thus uses the following alorithm:

semaphore (void *addr)
{
while (test_and_set(addr) == 1)
sleep(0);
}

The call to sleep with a seconds value of 0, simply results in a call to sched(). And sched() will preempt the semaphore if there is another process ready to run.

So why is mutex used at all? Why not always use a semaphore? The reason is that the kernel has to use a mutex, it cannot use a semaphore, since there is only a single copy of the kernel that can run on a given cpu. But in user mode, semaphores allow other processes to run, thus improving system efficiency.