Efficient Concurrency: Leveraging Locking Mechanism in Linux
Learning-Linux-OS v0.1
This post provides a solid introduction to concurrency and locking mechanism in computing, with a focus on their application in Linux.
Over the years it has become common for Operating Systems to run multiple processes at the same time, especially with the advent of SMP (Symmetric Multiprocessing). SMP on a high level allows multiple CPUs to share access to main memory. Although concurrency significantly improves the performance and scalability of a system, it comes with the challenges of managing concurrent tasks. The Linux Programmer must take this into account in his/her design.
Concurrency can lead to a situation such as Race Condition, where two of more processes may access the same resource at the same time. Suppose Process A and Process B are running concurrently and both try to write to a Memory X at the same offset, this can cause an overwrite of data by the second process that writes to the memory.
So what’s the solution ? Typically the obvious solution to this is to avoid sharing resources. However, that is not feasible in todays super-fast computing. A common approach involves using locks and ensuring mutual exclusion, i.e. the shared resource can be manipulated only by a single thread. Additionally, we must make sure that the shared object exist until no outside reference exist to it.
Semaphores are a synchronization primitive used to manage access to shared resources in computing, similar to analogous to real-world mechanisms like restroom locks. Imagine a restroom with a single stall and a lock on the door. When the stall is vacant, the lock indicates "VACANT" and anyone can enter. Once inside, the person locks the door, changing the indicator to "IN-USE." This prevents others from entering while the stall is in use and have to wait. Similarly, in computing, a semaphore controls access to a resource. When a process needs to use a shared resource, it checks the semaphore. If the semaphore indicates the resource is available, the process can use the resource and the semaphore is updated to reflect that the resource is now in use. If the semaphore indicates the resource is already in use, the process must wait until the resource becomes available again.
Spinlock is another interesting primitive provided in Linux . Just like semaphores it is also a lock but the difference is that, the thread trying to acquire the lock will not sleep if the lock is not available. Threads trying to acquire semaphore locks will go into sleep if not available at that moment. However, in the case of spinlock, the thread continuously polls till it can acquire the lock. When optimally employed, spinlocks can enhance performance compared to a semaphore in general, because of there is no context switch. It is important to remember is that spinlocks cannot be used in Uniprocessors where preemption is not allowed, in which case if a thread starts spinning on a lock, it will spin forever.
Although these primitives provides a safe way to share resources for concurrent processes to access, it is challenging to implement correctly. To make it manageable it is important to understand how locking could go wrong.
If a function acquires a lock and calls another function which also attempts to acquire the lock there could be a deadlock situation. Therefore prior planning and prioritizing locking in design is vital.
Systems might be using multiple locks, in which case it is important to have a specific order in which locks are acquired and released. For example, if there are two locks, Lock1 (spinlock) and Lock2(semaphore) it is better to acquire the the semaphore first and then the spinlock because if the thread sleeps after acquiring spinlock it could lead to dangerous situation.
Using smaller fragmented locks instead of one big lock. Having fine grained locks are better as threads can wait on different locks as per the resource they are accessing instead of all the threads waiting on single big lock to access the different resources. The Linux kernel uses this mechanism by having multiple locks assigned to different resources such as network, block I/O or CPU.
These rules make it easier to use locks but still it is preferable to minimize reliance on locks using alternatives such as: a) lock free algorithms such as circular buffers that are used in network adapter to exchange packets with the CPU. b) Atomic variables that are much cheaper and provides better performance. Other alternatives include Bit Operations, Sequential locks and Read-Copy Update scheme.
if you are interested in the application and usage of locking primitives such as semaphores and spinlocks checkout the simple kernel module code here :
https://github.com/anvayabn/LearningLinux
Connect with me on LinkedIn : anvayabn
Checkout other projects on my GitHub : https://github.com/anvayabn