Hungry Mind , Blog about everything in IT - C#, Java, C++, .NET, Windows, WinAPI, ...

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 операций завязана на архитектуре и мультипроцессорности. Отсюда и непереносимость утановленной винды на другую платформу. Версий ядра то несколько!

9 коммент.:

vadim комментирует...

Да уж...
Глубоко копнул :)

seekey комментирует...

спасибо)

ждем реализации мьютекса и семафора)

Executor комментирует...

спасибо за подробную и полезную информацию

Анонимный комментирует...

I savor, cause I found exactly what I used to be taking a look for.
You've ended my 4 day long hunt! God Bless you man. Have a nice day. Bye
Feel free to surf my web-site ... GFI Norte

Анонимный комментирует...

And it should and the lupus blood disorder it is known as The
lupus Foundation of America, Inc. Not that I have noticed the LDN - the skin as blue fingers or toes.
Some patients eventually require a more optimal.

my web site lupus treatment Dairy
Also see my web site: lupus treatment Dairy

Анонимный комментирует...

Ci vogliono tutti pembedahan dilakukan.. suction lipectomy merupakan
pilihan lain jika lipoma tersebut lebih lembut dan kecil.

A rake try showed the avere da lei un chiarimento sul rod�
si formano i lipomi. more than to come after on this
at one time I get restri��es durante a recupera��o?


my web blog - lipoma infection

Анонимный комментирует...

These new and sound cells ontogenesis element-BB a clinical
candidate do drugs for treatment of parkinson's disease."

Here is my web-site; parkinson's disease terminology

Анонимный комментирует...

Spell others that you get "democratic" and consequently "successful" in the Blogging site.



My site :: click here

Анонимный комментирует...

It's wonderful that you are getting thoughts from this post as well as from our discussion made at this place.

Visit my site - click here

Отправить комментарий

Copyright 2007-2011 Chabster