risc cpu下用户态的原子加法问题-神马文学网

最近工作时碰到了这个问题，国外的网站上已有讨论，不过好像也没有什么结果，大家交流一下吧。
问题背景：
risc cpu的load/store特征，使得对某一地址的加法动作需要如下序列完成（以arm为例）
ldr r0,[r1]
add r0,r0,val
str r0,[r1]
问题在于如果在str之前如果被中断，并且另一个线程也对[r1]的内容做加法，则结果产生了错误。在内核中可以通过对整个操作关中断来解决问题，但是在用户态中无权关中断，低效的解决办法是使用互斥量，这需要陷入内核的操作（事实上在内核中对互斥量的加减操作还是需要关中断），在频繁运算时消耗过大。

问题：是否存在纯指令序列上的解决办法？

在gcc的arm相关的目录下的atomicity.h中给出了利用swap的解决办法，整理一下是下面的样子（寄存器都是我假设的）：
again:
ldr r0, [r1]
add r2,r0, val
swp r0, r2, [r1]
cmp r0,r2
swpne r2, r0,[r1]
bne again

但这是错误的，它保证不了三个原子加法对同一地址作加法的一个操作序列，大家可以想一想，不算太难。
希望集思广益，最后得出一个有用的结论来。

[
>>问题在于如果在str之前如果被中断，并且另一个线程也对[r1]的内容做加法，则结果产生了错误。

RE:从你的上下文来看，似乎你准备开发一套特殊的线程库；我印象中用户线程库实现的线程除了独享栈和线程调度之外，其他方面和普通的函数调用并无本质区别，也就是说，你所说的问题必然会自动在线程库的调度处理函数中得到妥善处理（如保存上下文），再者，用户态线程好象一般是非抢占的，就是不会发生中断回来后会被切换到另一个线程（这种情形惟有在可抢占的内核上下文中见到，以后更高级版本的linux内核线程调度中相信会有的）。所以这种忧虑可能是多余的了 ]

这里我可能没理解你的意思，保留在此，仅供参考。

附加一下，

不知道你的[r1]是不是进程范围全局的，而且用户线程是否bind到内核线程上去了？如果这样，以我的了解，只能依靠系统提供的同步原语了。设想一下，risc下并没有提供test&set&store之类的指令，而这里的中断是无法屏蔽的，所以应该没办法锁住系统保证其原子性；否则内核同步原语应该只作"内部流通"之用了。

fix me!

不知道你是否知道mips的ll/sc指令,我想用这个是可以实现用户态原子操作的

实际上，我正是在参与设计一个抢占式微内核才碰到的这个问题，r1代表的地址是共享地址。从硬件上来看，解决这个问题可以有很多办法实现，最简单的是违背risc的初衷，增加一条对指定地址内容加减的指令，像386一样；或者增加同时可以锁bus的指令，这样就可以使用开始文中提出的的指令序列。虽然cpu是我们自己设计的，可以进行硬件上的修改，但是现在希望先尽量能够在软件上给出复杂度较低的解法。这里的原子性实际上是要保证“最终运算结果的正确性”，而并非控制这一指令序列“运行过程的原子性”。不知诸位有何高见？

from Carnegie Mellon University

check the attachment

another paper from University of Rochester

2个附件好像我都看不到啊

正如你说的，原子性实际上是要保证“最终运算结果的正确性”，而并非控制这一指令序列“运行过程的原子性”。在risc里，CPU可以不支持原子加法操作，但必须有最基本的支持，例如，假设CPU支持原子swap指令，在寄存器和内存之间交换内容，可以用下面的伪程序实现PV操作：

P:
again:
r1 <- address of lock_var
r2 <- 1
swap r2, [r1] ; 这条指令必须是原子的
if (r2 == 1) goto again

V:
r1 <- address of lock_var
r2 <- 0
[r1] <- r2

利用上面的方法也可以实现原子加法，可以看到原子操作的实现很有技巧性，根据CPU对多任务/多处理器支持的不同方式，具体实现是和CPU相关的，你需要研究特定CPU对多任务/多处理器的支持策略，然后扩展为P/V操作以及原子加法。

这个解法还没有解决原子加法的问题，因为在if语句中你使用了常数1作为比较量，实际上潜在利用了二值信号量只有两个取值的特点。而且，事实上这个解法在抢占式内核中也是有一定问题的，假设线程A在将信号量成功置为1后，还未进行V操作的情况下，而被线程B抢占，系统可能就死锁了（实际上不是真正的死锁，因为抢占线程陷入死循环，还在运行），这可能迫使调度方式只能使用RR机制来使A重新被调度，即便如此，等待B耗光时间片时间可能会很长，这中间再次被抢占的话，系统的效率也难以容忍。

Reall all the messages. Just as foxsen said, your question is not really related to RISC, but for maybe some particular CPU, say, the ARM.

For mips and ppc, some bus-lock instructions are avaialble, which may fit your meet.

However, I am not able to find the corresponding instructions for ARM cpu.

Fix me

说的学究气一点，risc的初衷就是要减短指令的运行周期，而锁bus操作就等于把一串指令包装为“原子”的，实际上还是相当于一条用微程序写成的cisc指令（没有对流水线造成影响倒是一大优点），所以锁bus的方案我在开始虽然提到了，但是还是不希望这样做。实际上在gcc中alpha中的解决方案我也看过了，它也配合了硬件的机制（通过设置一个标志位），但在抢占内核的情况下也是错误的。

Well. You bet.

Could you point me out if there is another way to do the aotmic "add" if without using the above cpu instructions? I would be grateful.

Actaully, the atomic issue is nothing really risc or cisc. All the bottomline is: We need make sure the BUS transactions finished before the ADD or SUB done.

If entend your question further, would you please consider/think the Cache Coherence Protocol? For example, the MESI. Again, all the bottomline is to handle the BUS transactions.

For CPU, OS is just an application. All things on top of CPU BUS is transactions.

Fix me,

但在抢占内核的情况下也是错误的。

If not considering the concurrency, say, a non preemptive kernel, every add/sub is atomic and not even needed to be discussed.

Say, your object will never lose CPU until/after/when you explicitely call the "yield()" function . Hence, anything we need talk about ATOMIC primitives?

我不是正是要寻求指令序列上的解法才发这个贴子吗I'll be as grateful as you if somebody can solve it. ：）锁bus不能说是很好的解法，我的这个观点暂时还难以动摇。我之所以并不放弃指令序列的解法是因为不论解法存在与否，是否存在形式上的证明？一切问题正是源于抢占式内核，第五篇我提到过。还有，就实际情况而言，这个问题公司里已经暂定通过cpu直接增加对地址做加法的指令来解决，本质上还是锁了bus，不大甘心，呵呵。

>> 一切问题正是源于抢占式内核，

I don't think so. Let's say, a system with one CPU and one ASIC and one DMA controller.

Three of them read/write a memory address M in parallel. Then can you give an algorithm for CPU instructions???;-).

The essence of this atomic is: Modern Computer Architecture: Load/Store from/to Shared BUS/Memory.

-------- a system with one CPU and one ASIC and one DMA controller
实际上，大可不必为此伤脑筋，你不会在自己设计的os中让DMA区域的内存管理与普通内存区域有交叉，也不存在征用同一地址的烦恼，对吗？如果你充分利用各类处理器的特性并要顾及异构带来的麻烦来设计系统的话，你也不会让ASIC与CPU频繁通信，更重要的是，你差不多不需要它们对一块区域都来写操作，对吗？万一有的话，小小的向右转一点，解决也很简单，可以不在这里讨论，对吗？

-------The essence of this atomic is: Modern Computer Architecture: Load/Store from/to Shared BUS/Memory.
-------一切问题正是源于抢占式内核

Hell,both true but not complete. I think we can join them up,right?

我们不是在这里做生意，折衷还价；-) Please see my comments inside.

>实际上，大可不必为此伤脑筋，你不会在自己设计的os中让
>DMA区域的内存管理与普通内存区域有交叉，也不存在征用
>同一地址的烦恼，对吗？如果你充分利用各类处理器的特性并>要顾及异构带来的麻烦来设计系统的话，你也不会让ASIC与
>CPU频繁通信，

For example, high-end router,
ASIC(Data Plane) usually will read/write chip memory area, say, the PCI-memory. For example, set up the session table.

CPU(The data plane) will read/write the shared memory area for setting up the first session, for instance.

This is the common practise for ASIC-based embedded systems.

>-------The essence of this atomic is: Modern Computer
>Architecture: Load/Store from/to Shared BUS/Memory.
>-------一切问题正是源于抢占式内核
>Hell,both true but not complete. I think we can join them up,right?

BNN: Again, ATOMIC issue has nothing really related to OS kernel. For CPU layer, OS kernel is just an application.

If with theory speaking, the essence is: Concurrency.

You might be glad to konw that I'm trying my best to see your heart inside,but I don't think You've got the full point.
You seemed to take it for granted that all the problems came form hardwares only because OS is an application running on them, so you tend to focus on hardwares(at least for this problem).In fact we can see it is software that determines hardware's development,right?This is called co-design. the problem we are discussing is mostly a software demand(rising from preemptive kernel),and maybe it needs more hardware's help(but nobody can prove it),I wanna discuss the question with one CPU,ok?You can see this is my question's precondition.I have no power to discuss Concurrency to much(concurrency in this problem seems have some chances to be solved by software,and this is what I want) .Certainly,perhaps I can learn a lot about Concurrency theories from you and my books .

凑个热闹.(我是CPU设计外行:-p)
从您的描述来看,其实就是共享资源争用的问题.我能想到的解决办法有三个,
1,增加资源,如果允许使用其他的资源实现同一个目的,而不是局限于"r1",每个进程使用自己的"r?",那就什么问题也没有了.(当然,这里看来行不通,我猜测这个"r1"是地址加法部件的固定入口)
2.资源使用实现"原子性",不允许在使用共享资源期间出现调度.可以是:
*使用单一指令,使用资源就是一条单一指令,想拆开也办不到,自然不会错了.
*使用某种机制禁止打断这一序列的执行,效果和上一种是一样的.这个机制可以是硬件上的实际开关,也可以是软件中的开关量.
3.使用保护现场的方式,若第一个序列操作执行中发生调度,那么此时的r1必须被保存,直到该序列被恢复执行前再恢复到r1中.前提的r1必须可读.

这个问题看起来和我们在使用msp430嵌入式处理器的硬件乘法器时遇到的共享问题很相似.不知道我的理解对不对,请指正.(别眼睁睁的看我犯错误啊:-))

1.是不是r1没有关系的，因为线程切换时会保存/恢复寄存器内容，重要的在于对r1所代表地址的共享。
2. risc cpu里的load/store特性决定了不存在这样一个单一指令，您可以参考一下risc的相关文章便明白了。硬件的解决办法在第一篇文章中我提到了，与BNN朋友的讨论中也多有涉及。我的观点请仔细体会一下。
3. 同1，这并不是我的问题的关键所在。

最后，这是一个共享问题，但具有比较特别的地方。gcc的代码中给出了指令序列的解法，但却是错误的，我希望寻找正确的指令序列解法，或者得到一个无解的证明。

谢谢你的启蒙教育.:-)
我现在这样理解您的问题:
1.系统中有一个全局变量.
2.需要三个指令的序列来实现这个变量的运算:
(1).取数
(2).运算
(3).写回
3.这个运算有可能被中断并嵌套.
如何设计算法序列可以保证运算的结果正确?

您提到的GCC的做法就是,运算结束后写回并检查操作数有没有变化,如果已经改变,就恢复原值重新计算.可是,除非(比较->恢复)不可中断,否则还是会因为嵌套而出错.

是这样的吗?

还有,在GCC的算法中,运算结束后,如果发生过嵌套运算,目标变量会在恢复以前有短暂的错误值,如果在这个时候发生中断调度,并使用了这个值,也会导致错误.

要使GCC的算法正确,必须要有原子性的(读-比较-写)操作.
呵呵,比原问题中原子性的(读-运算-写)操作也差不多了.

还是觉得硬件上把risc指令序列合成一个sisc指令是最高效的做法.不知道这样会增加多少硬件开销?
另外,还是不太明白为什么会有在用户态操作全局共享单元的要求?我总觉得这个应该交给内核来处理.这样就保证了全局变量的操作是原子的,因为内核不可再被调度了.除非中断中也要做这个操作.

不设计成cisc指令的根源在于流水线效率。risc的指令执行周期非常短（普通指令1个周期，访存指令2个周期），这样相比cisc极大提高了流水效率，而对地址做加法则需要需要一读一运算一写5个周期，如果cisc里增加这样的指令，流水线就不得不在这条指令上空等较长的时间，如果编译器生成了过多的这种指令，效率损失可能会很惨重。

记得有个项目在做用户空间实现共享访问的互斥问题，很明显用户空间实现最大的好处是速度。因为不能关中断，所以要最大限度的发挥CPU的功能，也许有的CPU没法实现。

没错，arm中的解法问题正在于此，因为它只通过cmp来比较共享变量有没有变化，却无法得知变化了多少次。

可以参见《windows核心编程第四版》中的做法，的确是需要指令支持的。