Semaphore implementation using x86 assembly

Question

I am interested in the semaphore implemenation scheme, and I learned that in the x86, we could use the "lock prefix" to implement atomic operations, and I want to use it to implement a mutex, I know that C++ 11 has standard mutex now, but I want to implement my own. and here is my code:

#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;
}

The problem is that when there is two thread, the code goes well, while in case of 3 threads, the program seems to sink into a deadlock condition, could anyone explain why or give me some suggestions on how to implement is on a x86 machine?

Answer 1

Your wait is really a spinlock -- when the lock is under contention, it will (attempt to) use 100% of the CPU until the other thread(s) release the semaphore. Unfortunately, since it's using 100% of the CPU, that prevents the other threads from getting CPU time, so you get something closely approaching a dead lock.

At a guess, you're probably running on a dual core CPU. In such a case, the other thread can run full-speed, even though the spinlock is sitting in a tight loop, wasting CPU time. When you get more threads than available CPU cores, things drag to a halt.

Spinlocks can be useful if you have good reason to believe the semaphore will be clear quickly (in which case you want to avoid the overhead of a task switch). In a typical case, however, you want to limit the time spent "spinning", so your loop would look something like:

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

Then, after it breaks out of the loop, you check whether the semaphore cleared, or your limit (100 iterations, in this case) was reached. If the limit was reached, you invoke the scheduler to let some other thread run (and re-try the wait when this thread runs again).