RSS Feed
Twitter
Orkut
Synchronization / Kernel Locking Techniques in Linux
The Kernel locking is introduced in Linux Kernel to avoid race conditions or concurrency. We need synchronization to achieve multiprocessing. The most important point to note here is we should have hardware level support to achieve synchronization i.e to implement locking in kernel we should have support in hardware along with software(OS).
The hardware should support the "atomicity" (atomic nature) to implement kernel locking techniques. By default the Linux kernel (>= 2.6) supports atomicity. To make your kernel to support multiprocessing you should build the kernel with "CONFIG_SMP=y".
We have two types of locking techniques:
1. Wait locking
2. Poll locking
Note: Any locking technique will disable pre-emption when they succeed in acquiring a lock. Pre-emption will be disable in local CPU (in case of multi core systems)
Wait locking:
wait locks are of two types
1. Semaphore
2. Mutexes
Poll locking:
poll locks are of two types
1. Spinlocks
Semaphores:
Initializing semaphore
#include
way1:
struct semaphore sem;
void sema_init(struct semaphore *sem, int value);
way2:
DECLARE_MUTEX(name);
or
DECLARE_MUTEX_LOCKED(name)
Acquiring a semaphore
we have 3 functions to acquire semaphore lock
1. void down(struct semaphore *sem);
It blocks until semaphore is available. This is un-interruptible.
2. int down_interruptible(struct semaphore *sem);
Blocks until semaphore is available, can be interrupted by signals. Non-zero return indicates it is interrupted and semaphore is not acquired
3. int down_trylock(struct semaphore *sem);
Will acquire semaphore if available, It will not sleep i.e non-blocking call. A return value zero indicates success
Releasing Semaphore
void up(struct semaphore *sem);
It always succeeds On failure(of acquiring semaphore lock) the calling process is pushed into wait state and enqueued into semaphore wait queue.
Sample critical section using semaphore locks:
{
.
.
.
if(down_interruptible(&mysem))
return -ERESTARTSYS //When interrupted we return this to tell app that the call is failed, restart the call
.
.
.
up(&mysem)
.
}
Issues with Semaphores
1. Accidental Release: Semaphores allows the unlock of semaphores with out acquiring it
2. Recursive Lock / Dead Lock: If we try to acquire a lock in the critical section i.e in the process which already acquired a lock
Example
{
.
.
down(&sem);
.
.
down(&sem); //dead lock
.
.
}
3. Owners Death: If the owner process killed
To overcome these we use Mutexes......
Mutexes:
Initializing Mutex
#include
way1: statical initialization
DEFINE_MUTEX(name);
way2: Dynamic initialization
void mutex_init(struct mutex *lock)
Acquiring a mutex
we have 3 functions to acquire semaphore lock
1. void mutex_lock(struct mutex *lock);
It tries to lock, sleep otherwise. This is un-interruptible.
2. int mutex_lock_killable(struct mutex *lock);
same as above call but can be interrupted only by fatal signals(SIGKILL). Non-zero return indicates it is interrupted and mutex lock is not acquired
3. int mutex_lock_interruptible(struct mutex *lock);
same as above call but can be interrupted by any signal. Non-zero return indicates it is interrupted and mutex lock is not acquired
4. int mutex_trylock(struct mutex *lock);
never waits, returns a non-zero value if the mutex is not available.
Releasing Mutex
void mutex_unlock(struct mutex *lock);
It releases the mutex
Additional
int mutex_is_blocked(struct mutex *lock);
It is a check to know whether the mutex is locked or not
Side effects of wait locks
1. Improper use of locking operations can result in circular dead locks. For instance if two processes of same driver acquire same locks in opposite order
read( ) write( )
{ {
mutex_lock(&lock1); mutex_lock(&lock2);
mutex_lock(&lock2); mutex_lock(&lock1);
. .
. .
. .
} }
2. Wait locks when applied on small data structures or critical sections that contain atomic code may introduce delays and results drop in application performance. In this scenario you need to use Poll locks.
Spin Locks:
Linux kernel provides set of operations called spinlock which implements poll based locking technique. These locks are to be applied on smaller critical sections with atomic code in them.
Initializing Spinlock
#include
way1:
spinlock_t mylock = SPIN_LOCK_UNLOCKED;
way2:
spinlock_t mylock;
void spin_lock_init(*mylock)
Acquiring spinlock
we have 3 functions to acquire semaphore lock
1. void spin_lock(spinlock_t *lock);
This is un-interruptible.
2. int spin_lock_irqsave(spinlock_t *lock, unsigned long flags);
Disables all interrupts and saves previous state. flags are passed by value
3. int spin_lock_irq(spinlock_t *lock);
Disables all interrupts with out saving its previous state. non-recommended.
4. void spin_lock_bh(spinlock_t *lock);
Disables bottom halves.
Releasing spinlock
1. void spin_unlock(spinlock_t *lock);
2. void spin_unlock_irqrestore(spinlock_t *lock, unsigned long flags);
3. void spin_unlock_irq(spinlock_t *lock);
4. void spin_unlock_bh(spinlock_t *lock);
