-
21-09-2019 - |
题
原子指令是什么意思?
下面的内容如何变成原子的?
测试并设置
int TestAndSet(int *x){
register int temp = *x;
*x = 1;
return temp;
}
从软件的角度来看,如果不想使用非阻塞同步原语,如何保证指令的原子性?是否只能在硬件上或可以使用某些汇编级指令优化?
解决方案
一些机器指令是固有的原子 - 例如,读,写的本机处理器字的正确对准值大小是原子的在许多体系结构
这意味着,硬件中断,其它处理器和超线程不能中断读或存储和读取或写入的局部值到相同的位置。
更复杂的东西,如读出和写入原子一起可以通过显式的原子机器指令例如实现LOCK CMPXCHG在x86
锁定和其他高级别构建体构建在这些原子基元,其通常仅守护单个处理器字。
一些巧妙并发算法可以使用指针的只是读取和写入例如建在一个单一的读取器和写入器之间共享链表,或经过努力,多个读取器和写入器。
其他提示
原子来源于希腊语ἄτομος(ATOMOS),这意味着“不可分割”。 (警告:我不会说希腊语,所以也许它真的别的东西,但大多数说英语的人援引词源这样理解: - )的
在计算,这意味着操作,那么,发生的。没有完成之前这是任何可见的中间状态。所以,如果你的CPU被中断服务的硬件(IRQ),或者如果另一个CPU正在读取相同的内存,它不会影响结果,而这些其他的操作将观察它作为完成或尚未启动。
作为一个例子...让我们说你想设置的东西一个变量,但只有当它以前没有设置。你可能会倾向于这样做:
if (foo == 0)
{
foo = some_function();
}
但是,如果这是在并行运行?这可能是因为该程序将取foo
,把它看作是零,同时线程2出现了,做同样的事情,并将价值的东西。回到原来的线程,代码仍然认为foo
是零,且变量被分配两次。
有关这样的情况下,所述CPU提供一些指令,可以做比较和有条件分配作为一个原子实体。因此,检查并设置,比较并交换,并加载链接/条件存储。您可以使用这些来实现锁(你的操作系统和你的C库已经这样做了)。或者你可以写依赖于原语做一些一次性的算法。 (有很酷的东西在这里完成,但大多数凡人避免这种情况,生怕犯错的。)
原子性是一个关键的概念,当你有任何形式的并行处理(包括不同的应用协作或共享数据),其包括共享的资源。
的问题是公用一个例子来说明。比方说,你有希望创建一个文件,但只有当该文件不已经存在两种方案。任何两个程序可以创建在任何时间点的文件。
如果你(我会用C,因为它是什么在你的例子):
...
f = fopen ("SYNCFILE","r");
if (f == NULL) {
f = fopen ("SYNCFILE","w");
}
...
你不能肯定的是,其他程序并没有造成你打开的文件进行读取和你开写。
有没有办法,你可以这样做你自己,你需要从操作系统的帮助,通常用于这一目的提供同步化原语,或者是保证另一种机制是原子(例如关系数据库,其中锁定操作是原子的,或者更低的水平机构像处理器“的测试和设置”指令)。
以下是我对原子性的一些注释,可以帮助您理解其含义。这些注释来自最后列出的来源,如果您需要更彻底的解释而不是像我一样的点状项目符号,我建议您阅读其中的一些注释。有错误的地方请指出,以便我改正。
定义 :
- 源自希腊语,意思是“不可分割成更小的部分”
- 总是观察到“原子”操作是完成或未完成的,但从未完成。
- 必须完全执行或根本不执行原子操作。
- 在多线程的场景中,一个变量从未直接变为突变,没有“中途突变”值
示例1:原子操作
考虑不同线程使用的以下整数:
int X = 2; int Y = 1; int Z = 0; Z = X; //Thread 1 X = Y; //Thread 2
在上面的示例中,两个线程使用 X、Y 和 Z
- 每次读写都是原子的
- 线程将竞争:
- 如果线程 1 获胜,则 Z = 2
- 如果线程 2 获胜,则 Z=1
- Z 肯定是这两个值之一
示例2:非原子操作:++/-- 操作
考虑增量/减量表达式:
i++; //increment i--; //decrement
这些操作转化为:
- 读我
- 增加/减少读取值
- 将新值写回 i
- 每个操作都由 3 个原子操作组成,并且本身不是原子操作
- 在不同线程上尝试递增 i 的两次尝试可能会交错,从而导致其中一个增量丢失
示例 3 - 非原子操作:大于 4 字节的值
- 考虑以下不可变结构:
struct MyLong { public readonly int low; public readonly int high; public MyLong(int low, int high) { this.low = low; this.high = high; } }
我们创建具有 MyLong 类型的特定值的字段:
MyLong X = new MyLong(0xAAAA, 0xAAAA); MyLong Y = new MyLong(0xBBBB, 0xBBBB); MyLong Z = new MyLong(0xCCCC, 0xCCCC);
我们在单独的线程中修改字段,没有线程安全:
X = Y; //Thread 1 Y = X; //Thread 2
在 .NET 中,复制值类型时,CLR 不会调用构造函数 - 它一次移动一个原子操作的字节
- 因此,两个线程中的操作现在是四个原子操作
- 如果没有强制执行线程安全,数据可能会被损坏
考虑以下操作的执行顺序:
X.low = Y.low; //Thread 1 - X = 0xAAAABBBB Y.low = Z.low; //Thread 2 - Y = 0xCCCCBBBB Y.high = Z.high; //Thread 2 - Y = 0xCCCCCCCC X.high = Y.high; //Thread 1 - X = 0xCCCCBBBB <-- corrupt value for X
在 32 位操作系统上的多个线程上读取和写入大于 32 位的值而不添加某种锁定以使操作原子化可能会导致如上所述的损坏数据
处理器操作
在所有现代处理器上,您可以假设自然对齐的本机类型的读取和写入是原子的,只要:
- 1:内存总线的宽度至少与正在读取或写入的类型一样宽
- 2:CPU 在单个总线事务中读取和写入这些类型,使得其他线程无法看到它们处于半完成状态
在 x86 和 X64 上,不保证大于 8 个字节的读取和写入是原子的
- 处理器供应商定义了每个处理器的原子操作 软件开发人员手册
- 在单处理器/单核系统中,可以使用标准锁定技术来防止 CPU 指令被中断,但这可能效率低下
- 如果可能的话,禁用中断是另一种更有效的解决方案
- 在多处理器/多核系统中,仍然可以使用锁,但仅使用单个指令或禁用中断并不能保证原子访问
- 原子性可以通过确保所使用的指令在总线上断言“LOCK”信号来实现,以防止系统中的其他处理器同时访问内存
语言差异
C#
- C# 保证对任何占用最多 4 个字节的内置值类型的操作都是原子的
- 对占用四个字节以上的值类型(double、long 等)的操作不保证是原子的
- CLI 保证对处理器自然指针大小(或更小)的值类型变量的读取和写入是原子的
- Ex - 在 64 位版本的 CLR 中的 64 位操作系统上运行 C# 以原子方式执行 64 位双精度数和长整型的读取和写入
- 创建原子操作:
- .NET 提供 Interlocked 类作为 System.Threading 命名空间的一部分
- Interlocked 类提供原子操作,例如增量、比较、交换等。
using System.Threading; int unsafeCount; int safeCount; unsafeCount++; Interlocked.Increment(ref safeCount);
C++
- C++ 标准不保证原子行为
- 所有 C / C++ 操作都被假定为非原子操作,除非编译器或硬件供应商另有规定 - 包括 32 位整数赋值
- 创建原子操作:
- C++ 11 并发库包括 - 原子操作库 ()
- Atomic 库提供原子类型作为模板类,可与您想要的任何类型一起使用
- 原子类型上的操作是原子的,因此是线程安全的
结构体原子计数器
{std::atomic< int> value; void increment(){ ++value; } void decrement(){ --value; } int get(){ return value.load(); }
}
爪哇
- Java 保证对任何占用最多 4 个字节的内置值类型的操作都是原子的
- 对易失性长整型和双精度型的赋值也保证是原子的
- Java 提供了一个小型类工具包,通过 java.util.concurrent.atomic 支持对单个变量进行无锁线程安全编程
- 这提供了基于低级原子硬件原语的原子无锁操作,例如比较和交换(CAS) - 也称为比较和设置:
- CAS 形式 - boolean CompareAndSet(expectedValue, updateValue );
- 如果该方法当前持有预期值,则此方法自动将变量设置为 updateValue - 成功时报告 true
- CAS 形式 - boolean CompareAndSet(expectedValue, updateValue );
import java.util.concurrent.atomic.AtomicInteger; public class Counter { private AtomicInteger value= new AtomicInteger(); public int increment(){ return value.incrementAndGet(); } public int getValue(){ return value.get(); } }
原子性只能由OS被保证。操作系统使用底层处理器特征实现这一目标。
所以,创建自己的检查并设置功能是不可能的。 (虽然我不知道,如果能使用内联汇编代码片段,并直接使用的检查并设置助记符(可能是,这种说法只能OS特权时进行))
编辑: 根据这篇文章底下留言,使得使用ASM指令,你自己的“bittestandset”功能,直接是可能的(在Intel的x86)。但是,如果这些招数也对其它处理器的工作是不明确的。
我坚持我的观点:如果你想要做的事情atmoic,使用OS的功能,不要自己做