Ticket Spin Lock in Linux Kernel

First of all why we need a lock.. Yeah, I know it is for protection.. but what? the protected area is called ‘critical session‘. A ‘open area’ can be accessed by any one at any time which will obviously cause ‘data corruption’ which is what we are avoiding with lock. In kernel, there are different mechanisms for ‘synchronization’, as the word stands, the mechanism to ‘synchronize’ the access to the critical session.. spin_lock() is one of them. It is as simple as that, when ever some one access the lock, he will decrement its value and check the result.. In that case what is the initialization value ? It is a “1”; that means it is “Unlocked” , so after decrementing its value , if the result is “-“ ve, it means ‘some one’ is accessing it.. True ? I heard an answer ‘yes’.. Then the ‘requestor’ will keep spinning till he acquire the lock. Thats how it named or called ‘spin_lock’ ( it is my assumption :), but true. ) .. At the time of ‘release’, the current holder will make it “1” ie “UNLOCKED”.

Well, then what is specific about ‘ticket spin lock’ ? Quite recently , there had thought on current ( Above explanation) implementation and found that, the above mechanism can not be ‘fair’ enough always. One of the example would be, the ‘next holder’ is based on ‘luck’ ( atleast in my words) , that said, when the current holder release the lock, the ‘next owner’ can be any one who tried to acquire the lock at the time of lock release, which may not be the process who was waiting for the lock from the start.. In simple terms ‘FIFO’ is not honoured.. Cache lines play a big role there..

 

This is the main reason for ‘reinventing ticket spinlock’ . Here ‘reinventing’ is in terms of ‘algorithm/idea’ and not in ‘implementation.. Without going further on that, ticket spin locks have 2 parts as shown below

+ ———————-+

| Next    | Owner   |

+———————-+

 

‘According to the arrival’ , “next” field will be ‘increased’. “Owner” is the current serving value. The processor will check its value ( before incrementing next) with the owner ( in single atomic operation) and if it matches , it is going to be the new ‘holder’ of the lock..

The starting value of both the fields are “zero”.. Releasing lock is just matter of incrementing ‘Owner’.

It was an attempt to explain ‘ticket spin lock’  in simple words.. Hope it helps. If yes/not, let me know.. 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *