Ticket Lock的Relaxed Atomics优化

简介:

原文地址 作者:Pedro Ramalhete,译者:周可人,校对:梁海舰

Tick lock是mutual lock的一种简单实现:

http://web.mit.edu/6.173/www/currentsemester/readings/R06-scalable-synchronization-1991.pdf

它是由John Mellor-Crummey和Michael Scott在1991年提出的(pdf中2.2节),感谢C++11和C11中新的内存模型,我们可以对单个变量进行具有屏障或者不具有屏障的原子操作。当屏障没有使用,只有原子性保证时,我们称之为“relaxed atomic”:

http://en.cppreference.com/w/cpp/atomic/memory_order

注意在C11/C++11内存模型中,一个原子变量并不具有内在的“顺序一致性”或者“relaxed”性质,然而我们可以在每次访问的时选择它的行为。

原子修饰符只能保证原子性,即这个变量会被单步读或写。其他语言,如Java和Scala则不同,它们可以保证几乎所有的原生类型提供原子性保证,从而表现为“relaxed atomic”。并且,所有被声明为顺序一致性的变量可以在整个程序中保持性质(除非在Java中使用sun.misc.unsafe)。尽管这个细微的差异可能看起来并不重要,但是当我们的目标是从同步或是并发算法中挖掘最大性能时,就需要关注这个差异了。

假设你想要在不同语言中声明一个原子整型,下面是你可能会做的:


01 C11 (can be relaxed or sequentially consistent)
02  
03 _Atomic int x;
04  
05 C++11 or C++14 (can be relaxed or sequentially consistent)
06  
07 atomic<int> x;
08  
09 Java (sequentially consistent)
10  
11 volatile int x;

当具备上述信息时,我们可以写出一个简单的Ticket Lock C11版本的实现,如下所示:


01 typedef struct
02  
03 {
04  
05     _Atomic long ingress;
06  
07     char padding[64];      // To avoid false sharing between ingress and egress
08  
09     _Atomic long egress;
10  
11 } ticket_mutex_t;
12  
13   
14  
15 void ticket_mutex_lock(ticket_mutex_t * self)
16  
17 {
18  
19     long lingress = atomic_fetch_add(&self->ingress, 1);
20  
21     while (lingress != atomic_load(&self->egress)) {
22  
23         sched_yield();
24  
25     }
26  
27     // This thread has acquired the lock on the mutex
28  
29 }
30  
31   
32  
33 void ticket_mutex_unlock(ticket_mutex_t * self)
34  
35 {
36  
37     atomic_fetch_add(&self->egress, 1);
38  
39 }

 

这里有3处不明显的优化,我们可以在上述代码的基础上利用releaxed atomics实现。让我们一个一个看。

  1. 在lock方法中,当egress变量第一次被读取的时候,我们可以用relaxed load优化。

代码如下:


01 void ticket_mutex_lock(ticket_mutex_t * self)
02  
03 {
04  
05 long lingress = atomic_fetch_add(&self->ingress, 1);
06  
07 // If the ingress and egress match, then the lock as been acquired and
08  
09 // we don't even need to do an acquire-barrier.
10  
11 if (lingress == atomic_load_explicit(&self->egress, memory_order_relaxed)) return ;
12  
13 while (lingress != atomic_load(&self->egress)) {
14  
15 sched_yield();  // Replace this with thrd_yield() if you use <threads.h>
16  
17 }
18  
19 // This thread has acquired the lock on the mutex
20  
21 }

我们这样做的原因是atmoic_fetch_add(ingress)将会获取一个barrier,这代表着atomic_load_explicit(egress, memory_order_relaxed)将永远不能在atomic_fetch_add()之前被执行,但是它可以获得一个最新的egress的值,至少在atomic_fetch_add(ingress)执行之后。这意味着egress变量的值将永远不会比atomic_fetch_add(ingress)所返回的值更大。

在x86架构中,这个优化并不会带来效率提升,因为获得屏障是没有代价的,这代表节省一个屏障并不能带来任何收益。但是在其他架构中——如ARMv8,这个优化将带来少量的收益。当我可以在ARMv8上开发,并且配有支持C11/C++11的gcc时,我会详细说明。

 

  1. 在unlock()方法中,我们可以使用atomic_load()和atomic_store()来替代atomic_fetch_add()。

unlock()方法中并没有在一个原子操作中同时读/写的需求,因为同一时间只有一个线程可以调用这个方法。这说明我们可以这样实现egress变量的增加操作:使用atomic_load()读取egress变量的当前值,然后使用atomic_store()操作将当前值加1写入egress变量。

 

  1. 在前面提到的atomic_load()操作可以是relaxed。

步骤2可以通过relaxed atomic_load()进一步优化。在lock()方法中,atomic_fetch_add()有一个获取屏障的操作,或者在糟糕的情况下,这个屏障在while循环中的atomic_load(),用来保证当前线程获得最新的egress值。我们可以保证在这个屏障和unlock()之间没有其他线程调整egress变量,所以这样做是安全的。

最后的代码如下:


1 void ticket_mutex_unlock( ticket_mutex_t * self)
2  
3 {
4  
5 long legress = atomic_load_explicit(&self-> egress, memory_order_relaxed);
6  
7 atomic_store(&self-> egress, legress+1);
8  
9 }

上述是一些关于如何使用relaxed atomics来优化代码的例子。

现在,我们可以实际地说这些特殊优化所带来的提升是非常小的,并且一些优化是令人费解的,更是难以证明其正确性的。有利的一点是这个代码仍然是跨平台的。你可以在x86,ppc,mips,arm上运行它,因为内存模型的一致性,你有信心保证代码仍然是安全的。

这是我喜爱C11/C++1x内存模型的原因。

可以在github上找到C11 Ticket Lock源代码:

https://github.com/pramalhe/ConcurrencyFreaks/blob/master/C11/locks/ticket_mutex.h

https://github.com/pramalhe/ConcurrencyFreaks/blob/master/C11/locks/ticket_mutex.c

目录
相关文章
|
30天前
|
关系型数据库 MySQL Java
MySQL数据锁:Record Lock,Gap Lock 和 Next-Key Lock
本文基于 MySQL 8.0.30 版本及 InnoDB 引擎,深入解析三种行锁机制:记录锁(Record Lock)、间隙锁(Gap Lock)和临键锁(Next-key Lock)。记录锁锁定索引记录,确保事务唯一修改;间隙锁锁定索引间的间隙,防止新记录插入;临键锁结合两者,锁定范围并记录自身,有效避免幻读现象。通过具体示例展示了不同锁的作用机制及其在并发控制中的应用。
66 2
|
6月前
|
安全 算法 程序员
【C++入门到精通】Lock_guard与Unique_lock C++11 [ C++入门 ]
【C++入门到精通】Lock_guard与Unique_lock C++11 [ C++入门 ]
78 0
|
6月前
|
安全 C++
C++标准库中的锁lock_guard、unique_lock、shared_lock、scoped_lock、recursive_mutex
C++标准库中的锁lock_guard、unique_lock、shared_lock、scoped_lock、recursive_mutex
164 0
|
6月前
lock_guard和unique_lock
lock_guard和unique_lock
|
6月前
|
C++
[C++] 互斥锁(unique_lock、lock_guard)
[C++] 互斥锁(unique_lock、lock_guard)
75 0
|
JavaScript 索引
Atomics.wait()
Atomics.wait()
216 0
|
Oracle 关系型数据库 数据库
innodb_lock_wait_timeout参数的了解
前言:在管理ORACLE的工作中,经常发现因为锁等待的原因导致应用宕机了。Mysql考虑到自身的性能和架构等因素,InnoDB数据库引擎增加了参数innodb_lock_wait_timeout,避免在资源有限的情况下产生太多的锁等待; 一、innodb_...
3124 0
|
Oracle 关系型数据库 数据库
PMON failed to acquire latch, see PMON dump
前几天,一台Oracle数据库(Oracle Database 10g Release 10.2.0.4.0 - 64bit Production)监控出现"PMON failed to acquire latch, see PMON dump"错误,连接数据库出现短暂异常,告警日志中具体错误如下所...
1136 0
|
缓存 Oracle 关系型数据库