12

原子指令是什么意思？

以下如何成为原子的？

测试和设置

int TestAndSet(int *x){
   register int temp = *x;
   *x = 1;
   return temp;
}

从软件的角度来看，如果不想使用非阻塞同步原语，如何保证指令的原子性？是否只能在硬件或某些汇编级指令优化中使用？

4

5 回答 5

14

一些机器指令本质上是原子的——例如，读取和写入正确对齐的本机处理器字长值在许多架构上都是原子的。

这意味着硬件中断、其他处理器和超线程不能中断读取或存储以及读取或写入部分值到同一位置。

更复杂的事情，例如一起原子地读取和写入，可以通过显式的原子机器指令来实现，例如 x86 上的 LOCK CMPXCHG。

锁定和其他高级构造建立在这些原子原语之上，它们通常只保护一个处理器字。

一些聪明的并发算法可以仅使用指针的读取和写入来构建，例如在单个读取器和写入器之间共享的链表中，或者通过努力，多个读取器和写入器。

于 2009-11-19T10:01:32.563 回答
11

以下是我关于原子性的一些笔记，可以帮助您理解其含义。这些注释来自最后列出的来源，如果您需要更全面的解释而不是像我这样的点式项目符号，我建议您阅读其中的一些。请指出任何错误，以便我更正。

定义 ：

  • 源自希腊语，意思是“不可分割成更小的部分”
  • 始终观察到“原子”操作已完成或未完成，但永远不会完成一半。
  • 原子操作必须完全执行或根本不执行。
  • 在多线程场景中，变量直接从未变异变为变异，没有“中途变异”值

示例 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

  • 操作转换为：

    1. 读我
    2. 增加/减少读取值
    3. 将新值写回 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 Class 作为 System.Threading 命名空间的一部分提供
    • Interlocked Class 提供原子操作，例如递增、比较、交换等。 
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 字节的任何内置值类型的操作是原子的
  • 对 volatile long 和 double 的赋值也保证是原子的
  • Java 提供了一个小的类工具包，通过 java.util.concurrent.atomic 支持对单个变量进行无锁线程安全编程
  • 这提供了基于低级原子硬件原语的原子无锁操作，例如比较和交换（CAS） - 也称为比较和设置：
    • CAS 形式 - boolean compareAndSet(expectedValue, updateValue);
      • 如果它当前持有预期值，则此方法自动将变量设置为 updateValue - 成功时报告 true
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();
     }
}

来源
http://www.evernote.com/shard/s10/sh/c2735e95-85ae-4d8c-a615-52aadc305335/99de177ac05dc8635fb42e4e6121f1d2

于 2014-03-02T05:00:57.803 回答
8

原子来自希腊语ἄτομος（atomos），意思是“不可分割的”。 （警告：我不会说希腊语，所以也许这真的是别的东西，但大多数说词源的说英语的人都是这样解释的。:-)

在计算中，这意味着操作发生了。在完成之前没有任何可见的中间状态。因此，如果您的 CPU 被中断以服务硬件 (IRQ)，或者另一个 CPU 正在读取相同的内存，则不会影响结果，并且这些其他操作将观察它是否已完成或未启动。

举个例子……假设你想为某个东西设置一个变量，但前提是它之前没有设置过。你可能倾向于这样做：

if (foo == 0)
{
   foo = some_function();
}

但是，如果这是并行运行的呢？可能是程序将 fetch foo，将其视为零，同时线程 2 出现并执行相同的操作并将值设置为某个值。回到原来的线程，代码仍然认为foo是零，变量被分配了两次。

对于这种情况，CPU 提供了一些指令，可以将比较和条件赋值作为原子实体进行。因此，测试和设置、比较和交换以及加载链接/存储条件。您可以使用这些来实现锁定（您的操作系统和 C 库已经完成了此操作。）或者您可以编写依赖原语做某事的一次性算法。（这里有一些很酷的事情要做，但大多数凡人都避免这样做，因为害怕弄错。）

于 2009-11-19T10:17:37.917 回答
2

当您拥有包括共享资源的任何形式的并行处理（包括不同的应用程序合作或共享数据）时，原子性是一个关键概念。

用一个例子很好地说明了这个问题。假设您有两个程序想要创建一个文件，但前提是该文件尚不存在。这两个程序中的任何一个都可以在任何时间点创建文件。

如果你这样做（我将使用 C，因为它是你的示例中的内容）：

 ...
 f = fopen ("SYNCFILE","r");
 if (f == NULL) {
   f = fopen ("SYNCFILE","w");
 }
 ...

您不能确定其他程序没有在您打开读取和打开写入之间创建文件。

您自己无法做到这一点，您需要操作系统的帮助，通常为此目的提供同步原语，或者保证是原子的其他机制（例如，锁定操作是原子的关系数据库，或较低级别的机制，如处理器“测试和设置”指令）。

于 2009-11-19T10:06:52.280 回答
-4

原子性只能由操作系统来保证。操作系统使用底层处理器功能来实现这一点。

所以创建自己的 testandset 函数是不可能的。（虽然我不确定是否可以使用内联 asm 片段，并直接使用 testandset 助记符（可能此语句只能使用 OS 权限完成））

编辑：根据这篇文章下面的评论，可以直接使用 ASM 指令制作自己的“bittestandset”函数（在英特尔 x86 上）。但是，这些技巧是否也适用于其他处理器尚不清楚。

我坚持我的观点：如果你想做大气的事情，使用操作系统的功能，不要自己做

于 2009-11-19T10:00:22.737 回答