Linux Kernel Locking Techniques

Linux Kernel Locking Techniques

 In any multi-threaded environment, multi-threading is achieved by switching CPU between two or more tasks concurrently. It is very common to share data structures or resources among the threads in execution. A problem might arise when these resources are used by more than one thread concurrently. For example a bank has issued two ATM cards on same account. If both the ATMs are used at same time to withdraw money, account database may be incorrectly updated due to concurrent execution. A typical scenario is given below:

ATM Card1	ATM Card2	Explaination
Acc_balance=   get_acc_balance() Debit_amt = get_user_debit() if(debit_amt< acc_balance) {     Debit(debit_amt); }		Say account balance is 10000 and debit amount entered by user is 5000. Since debit amount is less than account balance debit command is issued. Context switch happens..
	Acc_balance=   get_acc_balance() Debit_amt = get_user_debit() if(debit_amt< acc_balance) {     Debit(debit_amt); }	At second ATM, account balance read is 10000 as database is not yet updated at ATM1. Say debit amount entered by user is 3000. Since debit amount is less than balance debit command is issued. Context switch..
Update_account_balance(      acc_balance-debit_amt) Account_database_commit();		Account Balance 5000= (10000-5000) is committed to database.
	Update_account_balance( acc_balance - debit_amt) Account_database_commit();	Now here calculated account balance is 7000 = (10000-3000). Account balance 7000 will be committed to database which is incorrect.

This problem could have been avoided if second transaction is forced to wait until first completes. Such type of scenarios where the result depends on relative timing of multiple tasks is called a race condition. The piece of code which is used to share data structure or resources if contains the concurrency issue is called a critical section. In critical section at least one task modifies the shared data structure. If a piece of code is sharing data among multiple tasks but no task is modifying any shared data then it is not a critical section.
Linux kernel provides various locking techniques to synchronize the tasks competing for shared resource. It ensures only one task can execute inside critical section. Different locking techniques are discussed in further sections. 

• Semaphore
• Mutex
• Wait queue
• Spin lock
• Atomic Operations

  

Next(Semaphore)