BKL: One lock to bind them all

Synchronised access by multiple resources is an ability any decent OS kernel must posses. The access is not intended for just the user. In fact the kernel internals are the largest consumers of synchronised access.

The kernel has to micro manage the whole hardware of the machine as such you'd expect it to be intensely intertwined and cutting corners in terms of performance at all stages. Even if performance and efficiency are very much desired, one thing that cannot be compromised is the security and safety of it all. A common backdoor in the safe working of the kernel is often a vulnerability of the concurrency of its functions. So before one considers being clever in infinitely many ways for the purposes of improving the kernel's performance, one must be singularly confidant that the kernel is safely concurrent. A kernel not using the hardware to its full potential is ordinary but a kernel risking reliability by not preventing the hardware from over stepping processes is criminal. It goes without saying that locks are absolutely essential in a kernel.

I know almost nothing about kernels. Thanks to the Linux kernel, that almost wasn't an absolutely. Not long before the present versions of Linux, the famous kernel had an old companion called the big kernel lock. It belongs to the spin lock category. The reason for the use of the article "the" in its name is because of its exclusiveness. It was about the only lock the Linux kernel employed or needed to hold its own at concurrency of operations. The adjective "big" states the obvious that to manage a big piece of software, a big lock is needed. The bigness of a lock in my guess is estimated by the size of the critical section it holds, hence the name the big kernel lock is justified. 

The big kernel lock was a global spin lock responsible for most synchronisation efforts in the Linux kernel back when it was active and acting. Remember what a lock is? If no then this is awkward otherwise following are some interesting features of the big kernel lock:

1. A process can sleep and probably dream while holding the BKL. This means that a process doesn't have to relinquish the lock (which it probably should), but the lock will be released automatically anticipating the process' inactivity.
2. The lock is recursive in nature meaning that a single process can have consecutive and successful attempts at locking the kernel (or at least a big significant chunk of it).
3. Like the ring in the Lord of the rings, you don't want this as it corrupts, eventually.

There has been radical changes in the Linux kernel to remove the lock and although it hasn't completely been removed but its usage has been reduced dramatically after 2011. New code is discouraged from using the now infamous lock_kernel() API.

The BKL does not allow kernel preemption. This is a good thing when it is a good thing. I mean BKL is essential for cases where it remains used in the kernel still but it cannot be used extensively for locking the kernel. Doing so would be like jamming the whole city's traffic even if a small gathering was to happen in a corner of the town. A more fine graded locking mechanism is apt for such purposes. Such fine grading has been gradually applied in the kernel since. BKL is obsolete but it isn't extinct. For more informed and authentic information, read this link.

Locks and Types

Locking is essential for computers for the same reasons door knobs are essential for bathrooms. A lock is meant to ensure only one (or any other number) of contenders access a resource. By access I meant exploit and by contenders I meant entities that need the resource ideally immediately.

I mentioned how the number of entities accessing a lock can be more than one. This is because a resource may have more than one available copy of it self for the greater good of the consumer kind. The multiplicity of same resources is there for the same reasons that explain multiple compartments in a public toilet. In short it is good to build more hoping that no one has to wait much and hence no one has to explode. I was talking about computers if the above metaphors got mixed a little to homogeneously.

The basic idea is that a lock protects access to some kind of shared resource. If someone has the lock, that someone can use the resource. If someone does not have the lock, they have to wait. In order to "have the lock", one needs to wait for their turn in perhaps a queue or a skewed web of priorities (just like life is). Once the turn comes, the following abstract sequence follows:

1. Acquire the lock on the resource.
2. Do your thing, quickly but to your satisfaction.
3. Hope no one important comes and steals your turn in between "the act".
4. Release the lock when done, or release it anyway and wait till your turn comes back again.

The concept of locks is not just to let someone have protected access to a resource but is also to keep others from rushing into a busy process. Such waiting folks are said to have been blocked, temporarily.

Now moving on from what are locks to how they are implemented. Implementing a lock is as simple as counting stuff. You just need to count how many resources are available and how many are free. A lockable resource will have a maximum number of owners or lock holders. If that number has been reached then no one will be allowed to use it further simply because no one can. If and when a resource frees up, the next in line is allowed to access it. Simple. 

Enough for the overly simplified analogies for locks. Let us look at some types of locks:

1. Mutexes: Mutex is short for Mutual Exclusion. The word exclusion is anti to the whole idea of sharing. So mutex are locks that allow exclusive access to a resource to only one process at a time. Unless the degree of mutexness is diluted by excuses like shared mutex, recursive mutex or read/write mutex; a mutex most certainly means no sharing at all.
2. Recursice Mutex: It is the same as a regular mutex but more than one lock can be held on the resource at the same time. So they are nothing like mutex at all. No, but seriously they are, maybe not by intent but by principle. These allow the same process to hold multiple locks over the same resource, recursively. The complete freedom of the resource would mean an completely inverse unwinding of these locks. 
3. Reader/Writer Mutexes: These mutexes add more meaning to the notion of holding a lock over a resource. They classify locks to be of two kinds:
   1. Read locks: Locks given to threads that only wish to read the resource.
   2. Write locks: Locks given to threads that wish to make changes to the resource.
      If some process has a write lock at a resource then no one else is allowed to either change the resource or even read it. But if some process is having a read lock over the resource then other processes can also have a sneak peak and acquire read locks of their own.
4. Spinlocks: A spinlock is a special kind of mutex. Why? Probably since it does not need to be appended by the word mutex to have some respectable identity. In fact there was a spinlock in the Linux kernel that was so fundamental and so fundamentally wrong that they actually had to remove it or Linux would not have been so sophisticated.
   A spinlock does not use OS synchronisation functions when a contending process has to wait for its turn. Instead, it just keeps trying to update the mutex data structure to take the lock in a loop. It is the relentless type. This type of technique resonates with the inpatient types and hence works well when the locks are generally held for a short time and are changed hands frequently. However if some lock is in place and is meant to stay in place for a long time then such consistent looping to get the lock may seem and is a waste of time for the processor.
5. Semaphores: Semaphores are like mutex made rich and diplomatic. They have the powers of a mutex minus the rudeness. They deliberately interact with multiple processes and multiple resources. With each resource there is a number representing how many processes are currently consuming the resource and how many are currently craving it. I have just the post for you if you wish to read more about them. Read more about them.