CODEWITHSUNDEEP
lockingpthreads
Boilermaker
Boilermaker

Reputation: 31

Ticket lock algorithm performance?

Is anyone familiar with the ticket lock algorithm which replaces the basic spinlock algorithm in the linux kernel? I am hoping to find an expert on this. I've read from a few online sources that the ticket lock algorithm is supposed to be faster, since the naive algorithm overwhelms the CPU bus with all threads trying to get the lock at the same time. Can anyone confirm/deny this for me?

I did some experiments of my own. The ticket lock is indeed fair, but its performance is just about on par with the pthread spinlock algorithm. In fact, it is just a touch slower.

The way I see it, an unfair algorithm should be a bit faster since the thread that hogs the lock early on finishes more quickly, giving the scheduler less work to do.

I'd like to get some more perspective on this. If it isnt faster, why is ticket lock implemented in the kernel and why is it not used in user space? thanks!

Upvotes: 3

Views: 2884

Answers (1)

cucufrog
cucufrog

Reputation: 731

Is anyone familiar with the ticket lock algorithm which replaces the basic spinlock algorithm in the linux kernel? I am hoping to find an expert on this. I've read from a few online sources that the ticket lock algorithm is supposed to be faster, since the naive algorithm overwhelms the CPU bus with all threads trying to get the lock at the same time. Can anyone confirm/deny this for me?

I did some experiments of my own. The ticket lock is indeed fair, but its performance is just about on par with the pthread spinlock algorithm. In fact, it is just a touch slower.

I think the introducing of ticket lock is mainly because of fairness reason. The speed and scalability of ticket lock and spinlock is almost the same comparing to scalable lock like MCS. Both of them introduce lot of cache line invalidate and memory read which overwhelms the CPU bus.

The way I see it, an unfair algorithm should be a bit faster since the thread that hogs the lock early on finishes more quickly, giving the scheduler less work to do.

There's no scheduler involved. Ticket lock and spinlock are busy-waiting lock, which are not blocked when waiting, but keep check the lock value. The program moves on once the lock is free. The control flow never goes the scheduler and comes back. The reason we use spinlock instead of block-wakeup lock is block-wakeup involve context switch, which is expensive, instead we just waiting and burning cpu time turns out cheaper. So busy-waiting locks can only be used in "short" critical sections.

I'd like to get some more perspective on this. If it isnt faster, why is ticket lock implemented in the kernel and why is it not used in user space? thanks!

It's in the kernel because kernel code has critical section too, so you need kernel space lock to protect kernel data. But of course, you can implement a use space ticket lock, and use it in your application.

Upvotes: 2

Related Questions