Spinlock explained

Большинство разработчиков пишут сложные программные комплексы на языках 3-го поколения. При этом их знания начинаются с языка и заканчиваются библиотеками для этого языка. Что происходит за кулисами - страшная тайна, доступная лишь немногим. Еще пару лет назад многопоточность и виртуальная память у меня асоциировались с космосом, о котором не хочется думать потому, что страшно и совершенно непонятно. Сейчас же я имею хорошее представление о том, как выполняются мои программы - от трансляции исходного кода в ассемблерные инструкции до цифрового логического уровня. Хочу сказать, что ничего страшного или сверхестественного нет ни в ассемблере, ни в операционной системе, ни даже в механизме работы процессора. Ну, и продемонстрирую это на примере реализации простейшего примитива синхронизации потоков под названием spinlock.

Механизм работы spinlock

Блокировка может находится в двух состояниях - свободна и захвачена. Ее состояние должно быть отражено в ячейке памяти, доступной двум или более потокам. Соответственно, лучшего места, чем оперативная память, для нее найти невозможно. Поток, который пытается захватить блокировку, обязан ждать, пока она не освободится. Ожидание представляет собой цикл попыток захватить блокировку и прерывание цикла в случае успеха. И никакие два потока не должны захватить блокировку одновременно.

Последнее предложение предыдущего абзаца диктует требование к операции захвата блокировки - она должна быть атомарной. Поскольку, грубо говоря, атомарной операцией является одна ассемблерная инструкция, то и захват блокировки должен выполнятся одной такой инструкцией. При этом, одним из аргументов должен быть адрес памяти, где хранится состояние блокировки.

Реализация spinlock

Код функций (объяснение дальше):

__declspec(naked) void __fastcall SpinLock(int *cookie) {
    __asm {
        mov eax, 1
spinLoop:
        lock xchg eax, [ecx]
        test eax, eax
        jnz spinLoop
        ret
    }
}

__declspec(naked) void __fastcall SpinUnlock(int *cookie) {
    __asm {
        mov eax, 0
        lock xchg eax, [ecx]
        ret
    }
}

Код функций состоит исключительно из ассемблерных инструкций, поэтому они объявлены, как __declspec(naked). Конвенция вызова __fastcall подарит нам единственный аргумент (адрес состояния блокировки) в регистре ecx. xchg - атомарная инструкция, которая в нашем случае меняет местами значение в регистре eax (где всегда хранится единица) и по адресу памяти, который хранится в ecx. В результате выполнения одной неделимой инструкции, мы получим в eax нолик, если блокировка успешно захвачена. Состояние блокировки изменится соответственно. Если блокировка занята, в eax будет находится единица. Оставшиеся инструкции проверяют регистр eax и реагируют на успех или провал захвата блокировки.

Вы, наверное, не заметили, что в коде используется не xchg, а lock xchg. Это потому, что у меня многопроцессорная машина и две инструкции xchg могут выполнятся одновременно. Чтобы их синхронизировать, применяется конструкция lock, которая заставляет блокировать шину памяти на время выполнения инструкции.

Использование spinlock

Спин блокировку следует использовать исключительно:

1. Для синхронизации действительно маленьких кусков исходного кода.

   Поток, ждущий освобождения блокировки, выполняет бесполезную работу, соответственно, расходует процессорное время. Основная цель - потребить меньше ресурсов, чем потребуется для использования примитивов синхронизации операционной системы, тоесть для переключения контекста выполнения.

2. На многопроцессорной машине.

   Поскольку на однопроцессорной машине два потока не могут выполнятся одновременно, поток, который владеет блокировкой, во время попыток ее захвата другим потоком приостановлен и не выполняет никаких действий по освобождению ресурса. Вообще, можно добиться отсутствия переключений контекста потока в момент, когда блокировка захвачена. Но, это очень сложно контролировать.

Proof of concept

Следующим кодом я проверял корректность работы spinlock:

// CppTest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <Windows.h>

__declspec(naked) void __fastcall SpinLock(int *cookie) {
    __asm {
        mov eax, 1
spinLoop:
        lock xchg eax, [ecx]
        test eax, eax
        jnz spinLoop
        ret
    }
}

__declspec(naked) void __fastcall SpinUnlock(int *cookie) {
    __asm {
        mov eax, 0
        lock xchg eax, [ecx]
        ret
    }
}

int lockCookie = 0;
int i = 0;
int j = 0;

DWORD WINAPI Thread1(LPVOID lpParameter) {
    while (true) {
        SpinLock(&lockCookie);
        i++;
        j++;
        if (i != j)
            DebugBreak();
        SpinUnlock(&lockCookie);
    }
}

DWORD WINAPI Thread2(LPVOID lpParameter) {
    while (true) {
        SpinLock(&lockCookie);
        i++;
        j++;
        if (i != j)
            DebugBreak();
        SpinUnlock(&lockCookie);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{

    InterlockedIncrement(reinterpret_cast<volatile LONG*>(&argc));

    DWORD thread1Id;
    DWORD thread2Id;

    HANDLE hThread1 = CreateThread(NULL, 100, Thread1, NULL, 0, &thread1Id);
    HANDLE hThread2 = CreateThread(NULL, 100, Thread2, NULL, 0, &thread2Id);

    Sleep(INFINITE);

    return(0);
}

Кстати, глянув на ассемблерный код функции InterlockedIncrement я убедился, что на процессорах Core 2 Duo нужно использовать блокировку шины памяти. Как и на многопроцессорных станциях.

Зачем нужна операционная система, если блокировки так элементарно пишутся вручную?!

А затем, что ассемблерный код не является переносимым даже в пределах одной архитектуры! Скажем, будь у меня однопроцессорная машина, я бы не использовал конструкцию lock и мой код бы не работал корректно на двуядерном процессоре! Кстати, просматривая исходники Windows 2000 я заметил, что реализация всех Interlocked операций завязана на архитектуре и мультипроцессорности. Отсюда и непереносимость утановленной винды на другую платформу. Версий ядра то несколько!