使用x86汇编语言实现信号量

Question

我对信号量实现方案很感兴趣，我了解到在x86中，我们可以使用“lock前缀”来实现原子操作，并想用它来实现互斥锁。我知道C++ 11现在有标准互斥锁，但我想自己实现。以下是我的代码：

#include <iostream>
#include <thread>
#include <vector>

struct Semaphore
{
private:
    int s;
public:
    Semaphore( int s ) : s(s){}
    void wait()
    {
        int *p = &s;
        _asm
        {
            mov eax, p
            lock dec DWORD PTR [eax]
    begin : mov ebx, DWORD PTR [eax]
            cmp ebx, 0
            jl begin
        };
    }

    void signal()
    {
        int *p = &s;
        _asm
        {
            mov eax, p
            lock inc DWORD PTR [eax]
        };
    }
} s(1);

void print()
{
    s.wait();
    std::cout << "Print Thread " << std::this_thread::get_id() << std::endl;
    s.signal();
}

int main( int argc, char* argv )
{
    std::vector< std::thread > vec;
    int n = 3;
    for( int i = 0; i < n; ++i ) vec.push_back( std::thread( print ) );
    for( int i = 0; i < n; ++i ) vec[i].join();

    return 0;
}

问题在于，当有两个线程时，代码可以正常运行，但是在有3个线程的情况下，程序似乎陷入了死锁状态，有人能解释一下为什么吗？或者给我一些关于如何在x86机器上实现它的建议？

- JavaBeta

---

就像Antti所说的那样，如果没有操作系统的支持，你是无法实现任何合理的信号量的。 - Martin James

一个合适的互斥锁或信号量无法完全在用户空间中实现，因为它需要与操作系统的调度程序进行通信。 - Kerrek SB

Answer 1

你的wait实际上是一个自旋锁——当锁被争用时，它会（尝试）使用100%的CPU资源直到其他线程释放信号量。很不幸，因为它正在使用100%的CPU资源，这将阻止其他线程获得CPU时间，从而导致类似死锁的情况。

猜测你可能在双核CPU上运行。在这种情况下，即使自旋锁处于紧密循环中浪费CPU时间，其他线程也可以全速运行。当你的线程数超过可用CPU核心时，事情就会变得非常拖沓。

如果你有充分理由相信信号量会很快清除（在这种情况下，你希望避免任务切换的开销），自旋锁可以很有用。然而，在典型情况下，你想限制“自旋”所花费的时间，这样你的循环看起来会像：

        mov ecx, 100
begin : mov ebx, DWORD PTR [eax]
        test ebx, ebx
        loopnz begin

然后，在它跳出循环后，您检查信号量是否已清除，或者是否达到了您的限制（在这种情况下为100次迭代）。如果达到了限制，您将调用调度程序以让其他线程运行（并在此线程再次运行时重新尝试等待）。

- Jerry Coffin

---

使用“100％的CPU”并不会阻止其他线程获得CPU时间 - 任何明智的操作系统都不会像那样被挂起。任何进程/线程/任务都会被一个[定时器]中断抢占，例如当它的时间片用完时，让其他任务继续运行。CPU利用率与此无关，与可抢占内核也无关。如果您认为我错了，请随时纠正我。 - Armen Michaeli

@amn：好的：你错了。是的，只要你的线程以正常优先级运行，它（可能）最终会被中断，另一个线程将得以运行（这就是我说“接近死锁”而不仅仅是“死锁”的原因）。同时，他有一个线程尽力使用所有的CPU，所以另一个线程不会很快得到运行的机会——在具有足够高优先级的线程中，没有其他东西可以使用该核心（例如，在Windows上，“时间关键”线程可以抢占几乎所有其他线程）。 - Jerry Coffin

当我说“几乎所有其他东西”时，我真的是指几乎所有——它被赋予了足够高的优先级，以至于如果您在该优先级上长时间运行占用所有CPU的程序，它可能会通过防止需要进行内存刷新而导致机器崩溃。 - Jerry Coffin

你的回答没有提及优先级，我也没有假设。如果线程B具有相等的优先级，即使线程A使用“100% CPU”，线程B最终将会释放信号量，而且当然是在有限的时间内。我错了吗？这就是我想要澄清的内容。如果线程A在等待低优先级线程B持有的锁时旋转，那么我当然不反对。 - Armen Michaeli

@amn：是的，通常情况下是这样的，但并非总是如此。例如，在VMS上，系统不会在时间关键线程之间进行轮询调度。一旦启动了一个时间关键线程，即使其他时间关键线程正在等待和准备运行，它也将继续运行直到完成。 - Jerry Coffin

Answer 2

您编写的代码并不是一个合适的信号量实现。信号量应将等待任务放入信号量的等待队列中；在此之后，直到该信号量再次被发信号为止，其代码不会运行；当信号量被发信号时，等待线程将被唤醒。信号量的一半代码位于内核中，如何访问它的详细信息在线程库实现中。因此，在C++中正确地实现信号量需要做一些更复杂的事情。或者您可以编写自己的操作系统。

另外，您没有说出您使用的编译器，但有可能您的编译器过于激进地优化了asm子句。

- Antti Haapala -- Слава Україні

Answer 3

这里涉及到多个问题，以下是其中两个：

1. 你的wait()例程无条件地减少计数器。如果有两个等待者，则计数将为-2，并且在任何等待者停止等待之前，你需要两个信号。

2. 信号量代码完全依赖于调度程序。因此，根据调度程序和等待者和发信者的优先级，等待任务（它们是忙循环）完全有可能永远不会让出另一个执行上下文。

希望这可以帮到你。

- Sparky

Answer 4

是的，我承认在没有操作系统或机器的帮助下无法实现自己的版本，所以我尝试使用C++11标准来实现一个版本，并且我发现斯坦福大学的一门课程提供了一个解决方案，我想与任何需要的人分享，这里是链接：http://www.stanford.edu/class/cs110/lectures/18-threading-and-semaphores.html#(3)。

- JavaBeta