发出信号量必须是原子的.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.

顺便说一句，这是

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 what 的单个迭代，或者聚集或散布的单个元素，都不会发生.

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上.(但是，当然不能保证以原子方式损害系统中的其他观察者，例如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作为屏障对其他线程/核心)，但是屏障不能产生原子性，只能控制排序wrt.其他操作.

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 将省略 all 锁前缀.( 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.

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

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屋！