获取信号量必须是原子的.Pintos 的 sema_down 安全吗? [英] Taking a semaphore must be atomic. Is Pintos's sema_down safe?

问题描述

这段代码来自 Pintos 源码:https://www.cs.usfca.edu/~benson/cs326/pintos/pintos/src/threads/synch.c

This piece of code comes from Pintos source: https://www.cs.usfca.edu/~benson/cs326/pintos/pintos/src/threads/synch.c

void
sema_down (struct semaphore *sema) 
{
  enum intr_level old_level;

  ASSERT (sema != NULL);
  ASSERT (!intr_context ());

  old_level = intr_disable ();
  while (sema->value == 0) 
    {
      list_push_back (&sema->waiters, &thread_current ()->elem);
      thread_block ();
    }
  sema->value--;
  intr_set_level (old_level);
}

采用信号量的事实是sema->value--;.如果它有效，它必须是一个原子操作.我们怎么知道它实际上是原子操作?我知道现代 CPU 保证对齐的内存操作(对于字/双字/四字 - 它取决于)是原子的.但是，在这里，我不相信为什么它是原子的.

The fact of taking a semaphore is sema->value--;. If it works it must be an atomic one operation. How can we know that it is atomic operation in fact? I know that modern CPU guarantees that aligned memory operation ( for word/doubleword/quadword- it depends on) are atomic. But, here, I am not convinced why it is atomic.

推荐答案

TL:DR:如果在 UP 系统上禁用中断，那么任何事情都是原子的，只要你不这样做使用 DMA 对观察内存的系统设备进行计数.

TL:DR: Anything is atomic if you do it with interrupts disabled on a UP system, as long as you don't count system devices observing memory with DMA.

注意intr_disable();/intr_set_level(old_level);周围的操作.

现代 CPU 保证对齐的内存操作是原子的

modern CPU guarantees that aligned memory operation are atomic

对于多线程观察者，这仅适用于单独的加载或存储，不适用于读-修改-写操作.

For multi-threaded observers, that only applies to separate loads or stores, not read-modify-write operations.

对于原子性的事物，我们必须考虑我们关心哪些潜在的观察者.重要的是没有任何东西可以观察部分发生的操作.实现这一目标的最直接方法是使操作在物理/电气上是瞬时的，并同时影响所有位(例如，并行总线上的加载或存储在时钟周期的边界从未启动变为完成，因此它是原子的免费"直到并行总线的宽度).这对于读-修改-写来说是不可能的，我们能做的最好的事情就是阻止观察者在加载和存储之间查看.

For something to be atomic, we have to consider what potential observers we care about. What matters is that nothing can observe the operation as having partially happened. The most straightforward way to achieve that is for the operation to be physically / electrically instantaneous, and affect all the bits simultaneously (e.g. a load or store on a parallel bus goes from not-started to completed at the boundary of a clock cycle, so it's atomic "for free" up to the width of the parallel bus). That's not possible for a read-modify-write, where the best we can do is stop observers from looking between the load and the store.

我在 x86 上的原子性 上的回答以不同的方式解释了同样的事情，关于它意味着什么是原子的.

My answer on Atomicity on x86 explained the same thing a different way, about what it means to be atomic.

在单处理器 (UP) 系统中，唯一的异步观察者是其他系统设备(例如 DMA)和中断处理程序.如果我们可以排除非 CPU 观察者写入我们的信号量，那么我们关心的只是中断的原子性.

In a uniprocessor (UP) system, the only asynchronous observers are other system devices (e.g. DMA) and interrupt handlers. If we can exclude non-CPU observers from writing to our semaphore, then it's just atomicity with respect to interrupts that we care about.

此代码采用简单的方法并禁用中断.这不是必需的(或者至少如果我们用 asm 编写就不需要).

This code takes the easy way out and disables interrupts. That's not necessary (or at least it wouldn't be if we were writing in asm).

在两条指令之间处理中断，而不是在一条指令的中间.机器的架构状态要么包含内存递减，要么不包含，因为 dec [mem] 要么运行，要么没有.为此，我们实际上不需要 lock dec [mem].

An interrupt is handled between two instructions, never in the middle of an instruction. The architectural state of the machine either includes the memory-decrement or it doesn't, because dec [mem] either ran or it didn't. We don't actually need lock dec [mem] for this.

顺便说一句，这是cmpxchg 没有 lock 前缀.我一直想知道为什么他们不只是让 lock 隐含在 cmpxchg 中，原因是 UP 系统通常不需要 lock> 前缀.

BTW, this is the use-case for cmpxchg without a lock prefix. I always used to wonder why they didn't just make lock implicit in cmpxchg, and the reason is that UP systems often don't need lock prefixes.

此规则的例外是可以记录部分进度的可中断指令，例如 rep movsb 或 vpgather/vpscatter 参见在执行过程中中断指令这些不会是原子的.即使唯一的观察者是同一内核上的其他代码，也会中断.只有 rep nothing 的一次迭代，或聚集或分散的单个元素，会发生与否.

The exceptions to this rule are interruptible instructions that can record partial progress, like rep movsb or vpgather / vpscatter See Interrupting instruction in the middle of execution These won't be atomic wrt. interrupts even when the only observer is other code on the same core. Only a single iteration of rep whatever, or a single element of a gather or scatter, will have happened or not.

大多数 SIMD 指令无法记录部分进度，因此例如 vmovdqu ymm0, [rdi] 要么完全发生，要么根本不从它运行的核心的 PoV 中发生.(但当然不能保证原子 wrt.系统中的其他观察者，如 DMA 或 MMIO，或其他内核.那是 正常的加载/存储原子性保证很重要.)

Most SIMD instructions can't record partial progress, so for example vmovdqu ymm0, [rdi] either fully happens or not at all from the PoV of the core it runs on. (But not of course guaranteed atomic wrt. other observers in the system, like DMA or MMIO, or other cores. That's when the normal load/store atomicity guarantees matter.)

没有可靠的方法来确保编译器发出 dec [value] 而不是这样的:

There's no reliable way to make sure the compiler emits dec [value] instead of something like this:

mov   eax, [value]
                           ;; interrupt here = bad
dec   eax
                           ;; interrupt here = bad
mov   [value], eax

ISO C11/C++11 没有提供一种方法来请求关于信号处理程序/中断的原子性，但不是其他线程.他们确实提供 atomic_signal_fence 作为编译器屏障(相对于 thread_fence 作为屏障，其他线程/核心)，但屏障不能创建原子性，只能控制顺序.其他操作.

ISO C11 / C++11 doesn't provide a way to request atomicity with respect to signal handlers / interrupts, but not other threads. They do provide atomic_signal_fence as a compiler barrier (vs. thread_fence as a barrier wrt. other threads/cores), but barriers can't create atomicity, only control ordering wrt. other operations.

C11/C++11 volatile sig_atomic_t 确实有这个想法，但它只为单独的加载/存储提供原子性，而不是 RMW.这是 x86 上 int 的 typedefLinux.请参阅该问题以了解标准中的一些引用.

C11/C++11 volatile sig_atomic_t does have this idea in mind, but it only provides atomicity for separate loads/stores, not RMW. It's a typedef for int on x86 Linux. See that question for some quotes from the standard.

在具体实现上，gcc -Wa,-momit-lock-prefix=yes 将省略所有 锁前缀.(GAS 2.28 文档)这对于单线程代码是安全的，或单处理器机器，如果您的代码不包括需要在 MMIO 位置执行原子 RMW 的设备驱动程序硬件访问，或者使用虚拟 lock add 作为更快的 mfence.

On specific implementations, gcc -Wa,-momit-lock-prefix=yes will omit all lock prefixes. (GAS 2.28 docs) This is safe for single-threaded code, or a uniprocessor machine, if your code doesn't include device-driver hardware access that needs to do an atomic RMW on a MMIO location, or that uses a dummy lock add as a faster mfence.

但这在需要在 SMP 机器上运行的多线程程序中是不可用的，如果您在线程之间以及线程和信号处理程序之间有一些原子 RMW.

But this is unusable in a multi-threaded program that needs to run on SMP machines, if you have some atomic RMWs between threads as well as some between a thread and a signal handler.

这篇关于获取信号量必须是原子的.Pintos 的 sema_down 安全吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！