CS 321 Spring 2012  >  Lecture Notes for Monday, February 13, 2012

CS 321 Spring 2012
Lecture Notes for Monday, February 13, 2012

Shared-Memory IPC

Basics

We we deal with shared resources, we often need to implement mutual exclusion: only one process/thread gets to access a variable at once. Portion of code that accesses a shared resource is a critical region. We generally want no two threads in a critical region at the same time. We also want no thread to have to wait forever to enter a critical region.

Implementing Mutual Exclusion

We can do mutual exclusion using busy waiting: a thread continually checks whether it is acceptable to perform some action (in this case, enter a critical region). We want to avoid this, since a thread that is essentially doing nothing, still takes up processor time.

Another option is disabling interrupts when a thread enters a critical region, so that no other thread can execute. This has a number of problems. It requires user-level code to be given too much power (the power to disable interrupts). It does not allow any other processes to execute—even if they do not access the shared resource. It can fail on multi-processor architectures.

A successful solution for implementing mutual exclusion involves lock variables, usually called simply locks.

At its simplest, we can think of a lock as an int variable. The variable is 1 if a resource is being used, and 0 if not. Consider the following (faulty!) code.

int lock = 0;

void enter_region()  // Call when entering a critical region
{
    while (lock == 1) ;
    // An interrupt here would be BAD
    lock = 1;
}

void leave_region()  // Call when leaving a critical region
{
    lock = 0;
}

Above, when we enter a critical region, we wait for the lock to become 0. If the lock is 1, then this looks like an infinite loop. But remember that we are dealing with multiple threads. When the thread holding the lock exits its critical region, it will call leave_region setting the lock to 0. Then the thread that is waiting for the lock will exit its while loop. It will set the lock to 1, indicating that it has the lock. It does whatever it needs to, then sets the lock back to 0, when the critical region is complete, thus releasing the lock and letting some other thread acquire it.

But this code has a serious problem. What if two threads are waiting for the lock. And what if there is an interrupt just after one exits its while loop, but before it sets the lock variable to 1. Then we can have two threads acquiring the lock at the same time. Mutual exclusion has failed.

Note: Another problem with the above code, is that is does a busy-wait. However, that is not the issue we are addressing at the moment.

Semi-satisfactory solutions to this:

Better hardware-based solution: TSL instruction. TSL = Test & Set Lock. This instruction would be given an register and a memory location (the location of a lock variable). It reads the contents of the memory location into the register. The in stores a non-zero value into the memory location. Further, the instruction is atomic: it either all happens or all does not happen, with no other operation intervening.

If we have a TSL available, then we can make the above code behave correctly. Our leave_region function is unchanged. Our enter_region function can test the lock by executing TSL. If we get a non-zero value, then some other thread has the lock, and we continue looping. If we get a zero value, then the lock was available, and we have acquired it.

Shared-Memory IPC will be continued next time.


CS 321 Spring 2012: Lecture Notes for Monday, February 13, 2012 / Updated: 2 May 2012 / Glenn G. Chappell / ggchappell@alaska.edu