Wednesday, August 03, 2005

What to Lock (Locking Design part IV)

To discuss this, we first need to look at what kind of system architecture is being used. There are two special types of locking primitives, they are described below.

  • Semaphore

    A semaphore is used to denote a locking primitive in which we relinquish the CPU if we do not get the lock. In the examples used in the previous article, down, down_write and down_interruptible are semaphores. The pseudo code for a typical semaphore implementation is given below.

    \begin{algorithm} % latex2html id marker 53\caption{Psuedo code for a semaphor... ... queue} \STATE return with the lock held \ENDIF \end{algorithmic}\end{algorithm}

  • Spinlock

    A spinlock is used in a multiprocessor environment. There might be cases when one cannot go to sleep waiting for a lock. Consider for example an interrupt handler in a Symmetric Multi Processing environment (here after referred to as SMP). All the CPUs may receive an interrupt from any device. If a device interrupted the system twice, lets say one interrupt goes to CPU 1 and the other to CPU 2. Both of them execute the same interrupt handler for the device. They will need mutual exclusion to avoid the kind of races or unexpected results. It would be very bad for a CPU to go to sleep in an interrupt handler, because an interrupt handler is running at a very high priority, preempting everything else, we should deal with it quickly or the system will perform very badly. So what do we do, we spin on the lock being held by the other CPU (assuming that the other CPU will not hold the lock for long). Once we get it, we finish with the interrupt handler and continue (NOTE: The assumption here is that interrupt handlers run fast, otherwise the spinlock will spin for a long time).

    \begin{algorithm} % latex2html id marker 63\caption{Psuedo code for a spinlock... ...TATE return with the lock held \ENDIF \ENDWHILE \end{algorithmic}\end{algorithm}

Now that we have looked at kinds of locking primitives, let us discuss when we need to lock data. First of all remember that we need to lock only global variables and structures, since only they are prone to races. Local variables reside on the stack and since each process on each processor has its own stack, there are no race conditions with local variables. We will consider the following cases


Zaira said...

Nice one!.. Visit me and drop me a line..........

MitzieBitchie said... got me thinkin bout that huh?..catch me in my profile.. gimme some smart kick-ass comments sweetie!..

Balbir Singh said...

I am surprised that you visit so many blogs and leave behind information. It can be a nice way to meet other people.

Good luck with your blogs

Dynamic programming for the binomial coefficient

More fun things, this time with some visualisation of what happens when memoisation is used and what happens when we don't. I don'...