запутался о спин блокировки

Question

Я читаю код блокировки вращения отсюда , особенно эта часть

inline void Enter(void)
{
    int prev_s;
    do
    {
        prev_s = TestAndSet(&m_s, 0);
        if (m_s == 0 && prev_s == 1)
        {
            break;
        }
        // reluinquish current timeslice (can only
        // be used when OS available and
        // we do NOT want to 'spin')
        // HWSleep(0);
    }
    while (true);
}

Зачем нам проверять два условия m_s == 0 && prev_s == 1? Я думаю, что достаточно просто проверить prev_s == 1. Есть идеи?

РЕДАКТИРОВАТЬ: версия 2. мы должны исправить таким образом, если есть ошибка?

inline void Enter(void)
{
    do
    {
        if (m_s == 0 && 1 == TestAndSet(&m_s, 0))
        {
            break;
        }
        // reluinquish current timeslice (can only
        // be used when OS available and
        // we do NOT want to 'spin')
        // HWSleep(0);
    }
    while (true);
}

РЕДАКТИРОВАТЬ: версия 3. Я думаю, что версия 3 с функционального уровня является правильной, но производительность не достаточно хорошая, так как каждый раз, когда нам нужно писать, впереди тест на чтение. Правильно ли мое понимание?

inline void Enter(void)
{
    do
    {
        if (1 == TestAndSet(&m_s, 0))
        {
            break;
        }
        // reluinquish current timeslice (can only
        // be used when OS available and
        // we do NOT want to 'spin')
        // HWSleep(0);
    }
    while (true);
}

@ dragonfly, вот мое исправление ошибки версии 4 (исправлена ​​ошибка в версии 2, как вы указали), не могли бы вы проверить, правильно ли это, пожалуйста? Спасибо!

РЕДАКТИРОВАТЬ: версия 4.

inline void Enter(void)
{
    do
    {
        if (m_s == 1 && 1 == TestAndSet(&m_s, 0))
        {
            break;
        }
        // reluinquish current timeslice (can only
        // be used when OS available and
        // we do NOT want to 'spin')
        // HWSleep(0);
    }
    while (true);
}

Answer 1

Мне кажется, что попытка оптимизации пошла не так, как надо. Я подозреваю , что он пытается "TATAS" - "Test-and-test-and-set", где он даже не пытается выполнить TestAndSet, если видит, что блокировка уже снята. *

В посте о спин-блокировках для .NET Джо Даффи пишет этот код TATAS как:

class SpinLock {
    private volatile int m_taken;

    public void Enter() {
        while (true) {
            if (m_taken == 0 &&
                    Interlocked.Exchange(ref m_taken, 1) == 0)
                break;
        }
    }

    public void Exit() {
        m_taken = 0;
    }
}

(Обратите внимание, что Джо использует 1 для обозначения заблокированного и 0 для обозначения разблокированного, в отличие от примера проекта кода - либо в порядке, но не путайтесь между ними!)

Обратите внимание, что здесь вызов Interlocked.Exchange зависит от m_taken, равного 0 . Это уменьшает конфликт - относительно дорогая (я полагаю) операция «тест-и-установка» здесь не нужна. Я подозреваю , к чему автор стремился, но не совсем понял.

Это также упоминается в статье Википедии о спин-блокировках в разделе "Значительная оптимизация":

Чтобы уменьшить трафик между процессорами шины, когда замок не приобретен, код следует читать цикл, не пытаясь напишите что-нибудь, пока это не читает изменил значение. Из-за кэширования MESI протоколы, это вызывает строку кэша чтобы замок стал «общим»; затем автобусного движения нет пока процессор ждет блокировки. Эта оптимизация эффективна на всех Архитектуры ЦП, которые имеют кеш на процессор, потому что MESI так повсеместно.

Это "чтение цикла" - это именно то, что делает цикл while - пока он не увидит m_taken изменения, он только читает. Когда он видит изменение (то есть, когда блокировка снята), у него есть еще один способ блокировки.

Конечно, очень возможно, что я упускаю что-то важное - такие вопросы очень тонкие.

Answer 2

Почему оба условия? Потому что второй поток также получит блокировку в этом случае. (Изменить: но этот случай не может произойти, если все потоки следуют протоколу спин-блокировки.)

Если блокировка доступна (сигнализируется), m_s имеет значение 1. При получении каким-либо потоком оно имеет значение 0. Другие значения не допускаются.

Рассмотрим один поток, которому нужна блокировка, независимо от того, сигнализирована она или нет в тот момент, когда поток с именем Enter() не важен. Разрешается брать блокировку, если m_s равен 1, и для этого требуется изменить ее на 0. Первая итерация, в которой это происходит, приводит к выходу из цикла и блокировке потока.

Теперь рассмотрим два потока, которые хотят одну и ту же блокировку. Оба вызывают TestAndSet(), ожидая, чтобы значение 1 стало 0. Поскольку функция TestAndSet() является атомарной, только один из ожидающих потоков когда-либо сможет увидеть значение 1. Все остальные потоки только когда-либо видят m_s как 0, и должен продолжать ждать.

Условие, где m_s равно 1 после установки его в 0 в этом потоке, означает, что какой-то другой поток сигнализировал между атомарной операцией и условием. Поскольку предполагается, что только один поток за раз имеет блокировку, кажется, что этого не должно произойти , что не может произойти.

Я предполагаю, что это попытка удовлетворить неизменное обещание спин-блокировки. (Изменить: я больше не уверен, подробнее ниже ...) Если оно удерживается, значение m_s должно быть равно нулю. Если нет, то это один. Если установка его в ноль не «прилипает», то происходит что-то странное, и лучше не предполагать, что теперь он удерживается этим потоком, когда инвариант неверен.

Редактировать: Джон Скит отмечает, что этот случай может быть недостатком в первоначальной реализации. Я подозреваю, что он прав.

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

Редактировать 2: Предлагаемая ревизия выглядит намного лучше. Это явно позволило бы избежать взаимодействия когерентности многоядерного кэша, которое было у оригинала из-за того, что он всегда записывал сторожа m_s.

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

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

Answer 3

Все ваши версии верны, кроме 2. Ваши замечания о проверке m_s==0 в версии 1 и сниженной производительности в версии 3 верны.

Причиной уменьшения является способ реализации T & S, в частности то, что он вызывает запись при каждом вызове. Это связано с тем, что запись (даже если она фактически не изменяет данные m_s) или намерение записи приводят к тому, что ее строка кэша становится недействительной на других процессорах, что означает, что когда другой процессор (также ожидает того же самого) lock) тестирует m_s, он не может прочитать данные из своего кэша, но должен получить данные от процессора, который ранее владел им. Это явление называется кэш-пинг-понг, после сходства с игрой в пинг-понг, где мяч (в данном случае данные строки кэша) постоянно перемещается между игроками (процессором). Если вы добавите дополнительный тест перед T & S, все процессоры будут просто читать, что означает, что все они могут хранить данные в своих кэшах (то есть совместно использовать), пока кто-нибудь не запишет в него.

Это происходит в версиях 1 и 3, потому что они запускают T & S на каждой итерации цикла.

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

Другая проблема заключается в том, что на некоторых архитектурах вам необходимы барьеры памяти для обеспечения правильного упорядочения памяти, в частности, чтобы тест m_s действительно считывал значение каждый раз (некоторого барьера компилятора здесь должно быть достаточно) и что любое чтение (и возможно, напишите, если хотите), что происходит внутри критической секции, не «просачивается», то есть не выполняется ЦП до фактической блокировки. Разблокировка должна выполняться аналогично. Обратите внимание, что версия Джона Скита верна в этом отношении, потому что он использует Java (или C #? Я не уверен, но их семантика должна быть похожа) volatile.

Answer 4

На самом деле кто-то может вызвать TestAndSet(&m_s, 1), т.е. Leave() из другого потока сразу после TestAndSet(&m_s, 0) и до if теста в Enter(). Таким образом, блокировка не будет получена, и m_s не будет равно 0. Поэтому такая проверка необходима.

Answer 5

Ни один из этих примеров не является правильным на оборудовании с менее строгим порядком. PowerPC и IA64 являются двумя такими примерами, и операции isync и .acq требуются для операций test и set, которые получают блокировку (аналогично операциям lwsync и .rel при выходе).