3

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!

4

1 回答 1

2

有没有人熟悉替换linux内核中基本自旋锁算法的票锁算法?我希望找到这方面的专家。我从一些在线资源中了解到票证锁定算法应该更快,因为天真的算法使 CPU 总线不堪重负,所有线程都试图同时获得锁定。任何人都可以为我确认/否认这一点吗?

我自己做了一些实验。票证锁确实是公平的,但它的性能与 pthread 自旋锁算法差不多。事实上,它只是慢了一点。

我认为引入票锁主要是出于公平的原因。票证锁和自旋锁的速度和可扩展性与 MCS 等可扩展锁相比几乎相同。它们都引入了大量的缓存行无效和内存读取,这使 CPU 总线不堪重负。

在我看来,一个不公平的算法应该更快一点,因为早期占用锁的线程完成得更快,给调度程序更少的工作要做。

不涉及调度程序。票证锁和自旋锁是忙等待锁,等待时不阻塞,而是不断检查锁值。一旦锁被释放,程序就会继续运行。控制流永远不会进入调度程序并返回。我们使用自旋锁而不是块唤醒锁的原因是块唤醒涉及上下文切换,这很昂贵,而我们只是等待和消耗 CPU 时间变得更便宜。所以忙等待锁只能用在“短”临界区。

我想对此有更多的看法。如果不是更快,为什么在内核中实现票证锁,为什么不在用户空间中使用?谢谢!

它在内核中,因为内核代码也有临界区,所以你需要内核空间锁来保护内核数据。但是,当然,您可以实现一个使用空间票锁,并在您的应用程序中使用它。

于 2012-07-17T01:44:50.750 回答