multithreading - native 互斥体实现

Question

因此，在我出世的日子里，我开始思考Windows/Linux如何实现互斥体，我已经以100种方式实现了这个同步器……在许多不同的架构中都采用了不同的方式，但是从来没有想过它是如何在大型环境中真正实现的。 ass OS，例如在ARM世界中，我使一些同步器禁用了中断，但我始终尽管这样做并不是一个很好的方法。

我试图通过Linux内核“游动”，但是就像一个我看不到满足我好奇心的东西。我不是线程专家，但是我对线程的所有基本概念和中间概念都有扎实的了解。
有人知道互斥体是如何实现的吗？

Answer 1

快速浏览显然来自one Linux distribution的代码似乎表明它是使用互锁的比较和交换实现的。因此，从某种意义上说，由于互锁操作可能是在硬件级别处理的，因此OS并未真正实现它。

汉斯(Hans)指出，联锁交换以原子方式进行比较和交换。 Here is documentation for the Windows version。为了好玩，我刚才编写了一个小测试，以显示一个创建这样的互斥锁的非常简单的示例。这是一个简单的获取和发布测试。

#include <windows.h>
#include <assert.h>
#include <stdio.h>

struct homebrew {
    LONG *mutex;
    int *shared;
    int mine;
};

#define NUM_THREADS 10
#define NUM_ACQUIRES 100000

DWORD WINAPI SomeThread( LPVOID lpParam ) 
{ 
    struct homebrew *test = (struct homebrew*)lpParam;

    while ( test->mine < NUM_ACQUIRES ) {
        // Test and set the mutex.  If it currently has value 0, then it
        // is free.  Setting 1 means it is owned.  This interlocked function does
        // the test and set as an atomic operation
        if ( 0 == InterlockedCompareExchange( test->mutex, 1, 0 )) {
            // this tread now owns the mutex.  Increment the shared variable
            // without an atomic increment (relying on mutex ownership to protect it)
            (*test->shared)++;  
            test->mine++;
            // Release the mutex (4 byte aligned assignment is atomic)
            *test->mutex = 0;
        }
    }
    return 0;
}

int main( int argc, char* argv[] )
{
    LONG mymutex = 0;  // zero means
    int  shared = 0;
    HANDLE threads[NUM_THREADS];
    struct homebrew test[NUM_THREADS];
    int i;

    // Initialize each thread's structure.  All share the same mutex and a shared
    // counter
    for ( i = 0; i < NUM_THREADS; i++ ) {
        test[i].mine = 0; test[i].shared = &shared; test[i].mutex = &mymutex;
    }

    // create the threads and then wait for all to finish
    for ( i = 0; i < NUM_THREADS; i++ ) 
        threads[i] = CreateThread(NULL, 0, SomeThread, &test[i], 0, NULL);

    for ( i = 0; i < NUM_THREADS; i++ ) 
        WaitForSingleObject( threads[i], INFINITE );

    // Verify all increments occurred atomically
    printf( "shared = %d (%s)\n", shared,
            shared == NUM_THREADS * NUM_ACQUIRES ? "correct" : "wrong" );
    for ( i = 0; i < NUM_THREADS; i++ ) {
        if ( test[i].mine != NUM_ACQUIRES ) {
            printf( "Thread %d cheated.  Only %d acquires.\n", i, test[i].mine );
        }
    }

}

如果我将对InterlockedCompareExchange的调用注释掉，然后让所有线程以“免费提供”的方式运行增量，那么结果的确会导致失败。运行10次，例如，而不是互锁的比较调用:

shared = 748694 (wrong)
shared = 811522 (wrong)
shared = 796155 (wrong)
shared = 825947 (wrong)
shared = 1000000 (correct)
shared = 795036 (wrong)
shared = 801810 (wrong)
shared = 790812 (wrong)
shared = 724753 (wrong)
shared = 849444 (wrong)

奇怪的是，有一次结果现在显示出不正确的争用。这可能是因为没有“每个人都立即开始”同步。在这种情况下，也许所有线程都按顺序启动和完成。但是，当我安装了InterlockedExchangeCall时，它运行无故障(或者至少运行了100次无故障……这并不证明我没有在示例中编写一个细微的错误)。