随笔 - 118  文章 - 1  trackbacks - 0
<2020年4月>
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

常用链接

留言簿

随笔分类

随笔档案

收藏夹

调试技巧

搜索

  •  

最新评论

阅读排行榜

评论排行榜

60天内阅读排行

这里说的环形队列是一种内存通讯机制,本身这个机制和语言没有什么关系,不过上篇提到了volatile语法和acquire/release语义,就以这个机制做一个例子,C语言实现。这方面的内容涉及到一些现有的语言实现的东西 
环形队列的数据结构是一个数组,简单起见我们认为通讯内容就是一个个int,则定义一个int数组和头尾索引: 
int queue[SIZE]; 
int head; 
int tail; 
方便起见可以约定:head表示队列首元素的索引,tail表示队列尾元素后面的空位的索引,队列中最多可容纳SIZE-1个元素,因为这样可以head==tail表示队列空,head==(tail+1)%SIZE表示队列满,如果能容纳SIZE个元素,就不能区分这两种情况了 
然后是读写: 
ErrorType read(int *v) 
    if (head == tail) 
    { 
        return EMPTY; 
    } 
    *v = queue[head]; 
    head = (head + 1) % SIZE; 
    return SUCCESS; 
ErrorType write(const int *v) 
    if (head == (tail + 1) % SIZE) 
    { 
        return FULL; 
    } 
    queue[tail] = *v; 
    tail = (tail + 1) % SIZE; 
    return SUCCESS; 
假如有多个线程读写队列,则一般需要锁来实现同步,但是做一点点约束和修改,就能实现无锁: 
1 队列只能单读单写 
2 共享的数据用volatile修饰 
可以就上面的代码简单分析下,read操作只会读写head,读tail和queue,反之write操作读写tail,读head,写queue,而head和tail都是正向增长的。这里的关键在于,head和tail使用int,它们的读写用一条机器指令即可完成,是原子的,在这个前提下,上述两个函数分别在两个线程执行时,无论怎么调度穿插,都不会产生冲突。例如,在读的时候,另一个线程正在写,由于是内容写完再修改tail的值,因此不会读到写了一半的数据,最多就是返回一个EMPTY错误,下次轮询的时候还能读到,反之写的时候如果有人在读,因为是读完内容才修改head,因此不会冲乱正在读的数据(当然,由于上面举例中queue的元素是int,所以不会出现单个元素不一致的情况,不过如果是结构体或一段数据就可能)。但若不是单读单写,就可能出问题了 
然后分析下为什么数据要加volatile,估计很多人都会说,因为如果不加,编译器会优化变量到寄存器,比如write修改了tail的值,而read把tail优化到寄存器里,就一直以为队列还是空的。的确volatile能阻止编译器做这类优化,每次读取都会保证从内存重新读取到寄存器,但是就上面这个例子而言,不存在这个问题,read函数在被调用的时候,还是要从内存读一下tail,因为一般来说不可能在read退出后还给它把tail值保存在寄存器里,事实上只有当在一个函数的代码段中重复使用一个变量的时候,才做上面这种优化 
这个例子里面用volatile,是为了执行的顺序性,根据上面的分析可以看到,除int的读写是原子外,这个无锁机制依赖于执行顺序,即读的时候先读,再改head,写的时候先写,再改tail。不少人可能觉得,我代码既然这么写了,那应该是按这个顺序执行,可惜这只是天真的想法,举例: 
static int a; 
static int b = 1; 
int main() 
    a = b + 1; 
    b = 0; 
    return 0; 
这段代码,如果编译器优化级别很低,比如vs的debug或g++的O0和O1,编译出来的执行序列是和语句一样的,但是在优化编译下会指令乱序(gcc): 
movl b, %eax 
movl $0, b 
addl $1, %eax 
movl %eax, a 
可以看到,将b加载到eax后,立即执行了b=0,然后才对eax+1,再复制给a,相当于把b=0提前执行了,假如我们在另一个线程判断b的值是否为0,然后访问a的值,就可能和预期不符,因为可能还没执行到写a的内存就访问了,出现了不一致的情况(vs2008下也乱序了) 
P.S.这个乱序的原因,个人猜测是将对b的存取聚在一起,减少cpu cache miss 
这里,先给出acquire和release的语义: 
acquire:禁止read-acquire之后所有的内存读写操作,被提前到read-acquire操作之前进行 
release:禁止write-release之前所有的内存读写操作,被推迟到write-release操作之后进行 
具体到volatile变量,就是说,对于一个volatile变量的读操作,所有代码中在它后面的指令不得提前到它之前执行,反之对于写操作,所有在它之前的代码不得延迟到它之后执行 
很明显上面的例子中,我们需要release语义,因此可以把b修饰为volatile,根据release语义,b=3之前的所有语句不得乱序到它后面执行,在vs下测试时,的确起作用了: 
00401000 mov eax,dword ptr [___defaultmatherr+8 (40301Ch)] //load b 
00401005 inc eax //+1 
00401006 mov dword ptr [__fmode+4 (403378h)],eax //store a 
0040100B mov dword ptr [___defaultmatherr+8 (40301Ch)],0 //store b 
但是,如果在gcc下测试,给b加volatile是没有任何效果的,对a的赋值依然像上面一样被乱序到后面执行,这显然是有问题的。不过这并不是gcc的bug,而是因为C语言对于volatile并没有规定acquire和release语义,gcc就没有实现,那为啥vs可以呢,因为vs实现了这俩语义(windows程序员欢呼吧) 
如果要解决上面这个例子在gcc的问题,只需要把a也声明为volatile即可,也就是说,虽然gcc没有实现对单独volatile变量操作时release语义,但是多个volatile变量的顺序似乎是保证的。说似乎,因为我还没有找到权威资料证明,但从经验来看是没什么问题。对于实际问题,比如实现一个无锁环形队列,最好还是用-S参数输出下汇编,确认下没有乱序比较好 
如果说,我们已经注意到并避免了上述问题,甚至对可执行文件反汇编,并对汇编做了确认,那是不是就没问题了?可惜这个想法还是太天真了,即便你保证了汇编(机器代码)级别的有序性,它最终还是要到cpu里面执行的,而cpu为了执行速度,也会采用乱序优化,这个是volatile无法控制的领域 
回忆一下大学的计算机组成和体系结构,cpu是由一些硬件组件组成,而硬件组件的工作是可以高度并行的,于是有了最经典的五级流水线,而现在的cpu的流水线是非常复杂的,还有指令乱序和分支预测等技术 
cpu指令乱序是一种统筹规划,比如小时候都做过统筹相关的题目:小明要做若干菜,其中对每个菜,切菜xx分钟,煮xx分钟,腌xx分钟,其中若干步骤可以并行,问如何安排等 
举个简单的例子(寄存器表达式伪代码): 
eax /= ebx 
eax += eax 
ecx -= edx 
ecx *= ecx 
执行这个序列的时候,如果按最原始的办法,一个个指令串行执行,则可能很浪费,因为第一个除法可能要消耗十几个cpu周期,后面的加减乘法又有几个周期。如果不用乱序执行,只考虑流水线,则效率提升也不大,因为只有第二和第三条指令能在流水线同时执行,第二条指令依赖第一条的结果,第四条依赖第三条的结果,流水线会停顿 
如果有了乱序执行技术,则cpu在执行第一条指令时会对后面的若干指令进行分析,找到可以提前执行的指令,具体在上面的例子,由于第二条要等第一条的eax结果,因此加法就停顿住,但是第三条和第一条没有关系,就提前到cpu执行,由于减法很快,第三条执行完后还可以把第四条提前执行,甚至可能三四都执行完成后,第一条还在除法器里面循环,然后一直等到第一条执行完,这时候再执行第二条的加法,最后的结果和简单串行执行一样,但是总耗时只是一次除法和一次加法而已 
上面是用寄存器运算乱序做个例子,对于volatile变量来说,主要受内存访问指令乱序的影响,具体的就是load和store两条指令顺序的问题,例如: 
x=x*x 
y=1 
假设我们用y=1来表示x计算完毕,根据上面的讨论,x和y都应该是volatile,编译后可能是(寄存器表达式伪代码): 
eax = x //load 
eax *= eax 
x = eax //store 
y = 1 //store 
cpu在执行这段时,分析出前三条指令有依赖关系,第四条跟前三条无关,于是可能在算乘法的时候将y的store指令乱序执行,如果另一个线程在另一个核执行,检测到y的值已经被store,以为x算完了,可能出问题,因为这时候可能还在算乘法,没有store x,这个例子中是将两次无关(cpu认为无关,但实际上是有关)的store乱序执行,简称SS乱序,对应的还有LL乱序,LS乱序和SL乱序 
很显然SS乱序会对我们上面讨论的volatile变量或无锁队列产生影响,可以从acquire和release语义来看这个问题: 
acquire:一个volatile变量的读行为之后的所有动作不应该提前到读之前,因此LL和LS乱序是不可以的 
release:一个volatile变量的写行为之前的所有动作不应该推迟到写之后,因此LS和SS乱序是不可以的 
于是乎,也只剩下SL乱序在这种情况下是安全的,幸运的是,我们常用的x86和amd64架构的cpu都只支持SL乱序,所以只要正确使用volatile和实现代码,基本不会出什么问题,各种CPU的乱序支持参考下图(前四行): 
可以看到,只有四种cpu只支持SL乱序,而其他cpu为了提高运行效率,支持力度会高一些,大部分四种乱序都支持 
既然乱序执行是cpu本身的特性,那么在支持各种乱序的cpu上,单纯依靠软件岂不是无法实现并发访问了?这显然是不可能的,解铃还须系铃人,可以利用一些特殊的机器指令能实现acquire和release语义,这也是操作系统中各种互斥量实现的基础
————————————————
版权声明:本文为CSDN博主「xtlisk」的原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/xtlisk/article/details/39098981
posted on 2020-04-21 16:13 长戟十三千 阅读(46) 评论(0)  编辑 收藏 引用 所属分类: 编程技巧随笔

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理