In my last two blog posts, I presented the idea of an Application Locking Mechanism and I also presented a prototype.  I would now like to present the full implementation of this facility.  This is the final post in this series.

//
//  The magic number is used to help detect data corruption in the lock
//  structure.
//

#define LOCK_MAGIC              314157

In my last blog post, I presented the idea of an Application Locking Mechanism.  The features that we want to support are:

1)  Multiple readers.

2)  Zero or one writers.

3)  Multiple readers and writers without data corruption.

4)  Wait fairness.

5)  Ensure lock/unlock sanity.

In previous blog posts, I have described how the operating system solves locking problems.  Now a days, Linux is popular and it is a good idea to try to solve problems in
user code.  This makes application code much easier to port and goes a long way in making it platform independent.  So I would now like to describe a Locking Mechanism that is completely implemented in user space.  So what features do we want to support:

1)  Multiple readers.
If there is no writer, then there can be multiple readers.

I’m wrapping up a nine-part series on Symmetric Multi Processors (SMP). Following up on #8 the Random Back-off Problem which focused on a solution to isolating locks so that a cache line can only hold a single lock, I’ll conclude with another solution that completely solves the Thundering Herd problem in an optimal manner: Queued Locks.

I’ve shown you how a 32 bit cpu commonly uses an 8-word cache line.  And we only want a single lock (or word) on a cache line.  We can use the rest of the cache line to implement a Queued Lock.