LockOne

Lock One

Учебный алгоритм, реализующий взаимное исключение для двух потоков.

Принцип работы

Код:

void thread_function(lock_one& m, std::size_t thread_idx)
{
    m.lock(thread_idx);
    // Критическая секция
    m.unlock(thread_idx);
}

Для входа в критическую секцию поток вызывает член-функцию lock. После того как функция lock возвращает управление, поток оказывается в критической секции - т.е. он захватывает (acquires) блокировку.

Пока поток находится в критической секции, он удерживает (holds) блокировку. Если поток удерживает блокировку, говорят, что блокировка занята (busy).

Для освобождения (release) блокировки вызывается член-функция unlock.

Захват блокировки

Код:

void lock(std::size_t idx)
{
    flags[idx] = true;
    while (flags[1 - idx]) {}
}

Поток записывает значение true в соответствующий элемент массива flags - это следует интерпретировать как то, что поток намерен захватить блокировку.

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

Освобождение блокировки

Поток записывает значение false в соответствующий элемент массива flags. При этом, если второй поток в этот момент находится в цикле ожидания (while(...)), то на следующей итерации выражение условия вычисляется в false, и он оказывается в критической секции.

Доказательство свойства mutual exclusion

Предположим, что оба потока оказались в критической секции. Тогда они должны были пройти цикл ожидания while (...). Это могло бы произойти только в том случае, если:

• для первого потока - flags[1] равен false
• для второго потока - flags[0] равен false

Первый поток мог прочесть flags[1] равный false только в том случае, если бы он сделал это до того, как второй поток выполнил команду flags[1] = true. Второй поток, аналогично, мог бы прочесть flags[0] равный false только в том случае, если бы сделал это до того, как первый поток выполнил команду flags[0] = true.

Но в обоих случаях, командам чтения предшествуют команды записи: flags[0] = true и flags[1] = true, а значит условия, указанные в абзаце выше, не могут быть выполнены одновременно. Соответственно, два потока не могут одновременно оказаться в критической секции.

Мертвая блокировка

Данный алгоритм обеспечивает взаимную блокировку, но не дает гарантий отсутствия мертвой блокировки.

Если первый поток выполнит команду flags[0] = true, а затем управление перейдет к второму потоку, и тот так же выполнит команду flags[1] = true, вне зависимости от дальнейших переключений потоков, каждый из них будет висеть на цикле ожидания while (...).