当前位置：首页 → 问答吧 → [原]好吧X86上的线程，我们同步吧！

[原]好吧X86上的线程，我们同步吧！

时间：2010-09-01

来源：互联网

本帖最后由 zhangsuozhu 于 2010-09-01 09:36 编辑

好吧X86上的线程，我们同步吧！

生产者、消费者问题是我们在多线程编程中经常遇到的问题。我们一般用POSIX接口进行C语言的多线程编程，用锁对访问临界资源加以控制，使同一时只有一个线程访问临界资源

，以达到线程的同步。

有没有可能不用锁来实现生产者、消费者的同步呢？假如我们能巧妙的避开同时访问临界资源，或利用硬件的特性来实现无锁操作，无疑对整个程序的效率来讲，是个利好的

消息。

下面我们谈谈我们如何才能执弃这可恶的锁实现线程的同步。

一、我们可以避开同时访问临界资源吗？
这就要具体问题具体分析了，如果你真能想出一个方案避开对临界资源的访也是有可能的（保希望不是改为效率更低的单线程）。但大多时间，我们不得不对临界资源进行同一时刻的多线程并发访问。

二、我们可以在C语言中使用硬件特性，而不用锁来达到对临界点的屏蔽，而实现线程的同步吗？

这是我们具体要讨论的问题。利用硬件的特性来达到对临界资源的无锁操作，具体的思路是建立在原子操作的想法基础上的，即要实现二个或多个线程可以在任一时该同时访问一个临界资源点时在芯片级是不可并发的。比如，多个CPU同时对一个对齐内存地址进行一次访问时，将由存储器仲裁器，来决定哪个CPU优先访问该内存，而另一个CPU只能等待优先

的CPU访问完成后，才可以进行访问。而这种操作，就是原子操作。那么8086中那些指令是原子的呢？

1、进行零次或一次对齐内存访问是原子的。要注意的数量零次或一次，同时访问的目标是对齐内存（即内存的地址是以字节为单位的整数倍）。

2、操作码是前缀是0xf0的指令也是原子的。即在intel中，指令前缀0xf0代表lock。当CPU执行这样的指令时，会锁定地总线。直到这条指令执行完为止。

3、I/O端口操作

4、写控制寄存器，系统寄存器或调试寄存器的所有指令

5、内存屏障指令 lfence读内存屏障、 sfence写内存屏障、mfence读写内存屏障。
这里有必要讲解一下内存屏障（memory barrier)，它的作用就所有的指令在内存屏障结束后都应该是执行完毕的，即在下一条指令执行时，再没有读写内存的指令没有执行完。

举例来讲，前面我们说过，对非对齐的内存访问不是原子的，也就是说在访问一半时，这条读取指令后面的指令可能已经由另一个CPU同步执行了，而在这条对非对齐的内存访问之

后加入内存屏障指令，可以确保在读取完这条非对齐内存后再执行后面的指令。

用C是这样实现的如上所说的内存屏障的。

#define X86_FEATURE_XMM (0*32+25) /* "sse" */
#define X86_FEATURE_XMM2 (0*32+26) /* "sse2" */
#define ALTERNATIVE(oldinstr, newinstr, feature) \
\
"661:\n\t" oldinstr "\n662:\n" \
".section .altinstructions,\"a\"\n" \
_ASM_ALIGN "\n" \
_ASM_PTR "661b\n" /* label */ \
_ASM_PTR "663f\n" /* new instruction */ \
" .byte " __stringify(feature) "\n" /* feature bit */ \
" .byte 662b-661b\n" /* sourcelen */ \
" .byte 664f-663f\n" /* replacementlen */ \
" .byte 0xff + (664f-663f) - (662b-661b)\n" /* rlen <= slen */ \
".previous\n" \
".section .altinstr_replacement, \"ax\"\n" \
"663:\n\t" newinstr "\n664:\n" /* replacement */ \
".previous"
#define alternative(oldinstr, newinstr, feature) \
asm volatile (ALTERNATIVE(oldinstr, newinstr, feature) : : : "memory")
#define mb() alternative("lock; addl $0,0(%%esp)", "mfence", X86_FEATURE_XMM2)
#define rmb() alternative("lock; addl $0,0(%%esp)", "lfence", X86_FEATURE_XMM2)
#define wmb() alternative("lock; addl $0,0(%%esp)", "sfence", X86_FEATURE_XMM)

复制代码

alternative()宏用于在不同的cpu上优化指令。oldinstr为旧指令，newinstr为新指令，feature为cpu特征位。

除此之外的其它的指令都不是原子操作。

那么我们如何使用这些硬件的特性呢？

1、对GCC编译器优化的控制。
首先，几乎所有的编译器都会对最后生成的指令代码进行优化。这种优化的结果造成实际生成的指令与我们编写源代码的指令不一定相同，编译器可能得新安排生成的机器指令，

以最优的方式加速程序的执行，这对我们大多数时是有利的，但在我们处理多线程同步时，将产生问题。假设你原来的想法是一个线程改变内存中的某个值，另一个线程循环对内

存中的这个值进行判断，如果为某个条件时，将执行一个操作，但优化后的结果可能是由于另一个线程循环的取内存的值，所以干脆内存中的值存入寄存器中以加速循环。这样就

造成，这个条件永远不可能成立。
所以，我们要控制这种错误的优化。在linux中，我们可以用优化屏障宏barrier()来实现。

#define barrier() __asm__ __volatile__("": : :"memory")

复制代码

这条语句实际上不生成任何代码，但可使gcc在barrier()之后刷新寄存器对变量的分配。
如：

int x;
int y = 1;
barrier();
x = y;

复制代码

如果不加优化屏障宏barrier()生成优化的指令大约是这样

movl $1 $eax
movl $eax ($ebp-8)
movl $eax ($ebp-4)

复制代码

而加上优化屏障宏barrier()指令，将重读内存地址，生成如下代码。

movl $1 $eax
movl $eax ($ebp-8)
movl ($ebp-8) $eax
movl $eax ($ebp-4)

复制代码

可见，编译器没有优化该处代码，寄存器被刷新了。

2、在生产者消费者链表中实现不加锁的线程同步。

假使A线程是生产者，B线程是消费者

A线程要插入一个新结点。可以用以下方式实现。

T *new_node= (T*)malloc(sizeof(T));
new_node->xxx = xxx;
........
/* 下面该将进入临界区 */
new_node->next = list_elemnet->next;
mb();
list_elemnet->next = new_node;

复制代码

list_elemnet->next = new_node;将被编译成四条指令。
一、把list_elemnet->next的值取出存入寄存器
二、是把寄存器中的值存入new_node->next中
三、是new_node的值取出存入寄存器
四、是把寄存器中的值存入list_elemnet->next中。

加入mb()的原因是假如存入new_node->next中指令没有完成而存入list_elemnet->next的指令先完成。此时B线程访问了new_node,产得到一个损坏的连接。而这不是我们希望的。
所以我们要保证在给list_elemnet->next存入new_node结点时，new_now已经准备完整是一个可用的结点。同时，假设线程B正在读取list_elemnet->next 还没有读取完，比如读了三个字节，此时，如果线程A改写了st_elemnet->next的内存，B线程将得到一个错误的地址。而加入读写内存屏障，保证了以上二点。

现在我们看看B线程如何遍历。

T *node = head;
wmb();
while(node)
{
barrier();
wmb();
node = node->next;
}

复制代码

首先我们要保证每一次循环都要重新访问一次next的值。可以用barrier();来保证。
其次我们要保证，每次访问的结点必须是准备好的，可用的。不会产生A线程正在写结点node的next时(未完成)，B线程访问node的next的值。
所以我们加入wmb以保证B线程访问的结点都是准备好的。

如此，我们无锁现实了一个简单的生产者消费的的链表的同步。

作者: zhangsuozhu 发布时间: 2010-09-01

很强大的样子, 收藏了

作者: tmp 发布时间: 2010-09-01

本帖最后由 scupan 于 2010-09-01 08:15 编辑

看不懂得说,好吧,似懂非懂的样子,要回去看操作系统了

作者: scupan 发布时间: 2010-09-01

QUOTE:

加入mb()的原因是假如存入new_node->next中指令没有完成而存入list_elemnet->next的指令先完成。此时B线程访问了new_node,产得到一个损坏的连接。而这不是我们希望的。

能给解释下为什么会出现这种情况么？

作者: spongeliu 发布时间: 2010-09-01

因为现代多核CPU非常普，而且CPU上的指令流水线非不是像我们相像的一样，一条执行完成再执行下一条，CPU以它的最优方式同时执行几条并不冲突的指令。所以非原子操作的任何中间过程都可以被打断，现在假设有三个CPU的情况， CPU0执行向new_node->next存数据的指令。而CPU1执行向入list_elemnet->next存new_nodee地址的指令，而CPU2执行扇遍历链表访的指令。

假设CPU0在执行时突然被打断去做其它的事。此时，CPU1已经执行向入list_elemnet->next存new_node地址的指令。这时CPU2 也开始访问到了new_node结节，这时因为CPU0并没有执行向new_node结点写入数据的全部操作，比如new_node的next指针没有写完。此时，cpu2访问的new_node就不是一条完整的链表。

作者: zhangsuozhu 发布时间: 2010-09-01