Сколько барьеров памяти нам нужно для реализации блокировки Петерсона? - PullRequest
Новая
       76

Сколько барьеров памяти нам нужно для реализации блокировки Петерсона?

1 голос
/ 06 июня 2019

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

https://bartoszmilewski.com/2008/11/05/who-ordered-memory-fences-on-an-x86/

На практике кажется, что этого достаточно, основываясь на ряде тестов, выполненных в разных архитектурах.Однако, теоретически, нужны ли нам дополнительные?

Я пробовал код ниже

мой peterson_lock не удалось в этой ситуации

при изменении порядкамежду Mark A и Mark B, и это работает!Тем не менее, забор памяти не фиксирует порядок между меткой A и меткой B. Значит ли это, что программа по-прежнему неверна?

#include <pthread.h>

typedef struct {
    volatile bool flag[2];
    volatile int victim;
} peterson_lock_t;

void peterson_lock_init(peterson_lock_t &lock) {
    lock.flag[0] = lock.flag[1] = false;
    lock.victim = 0;
}

void peterson_lock(peterson_lock_t &lock, int id) {
    lock.victim = id; // Mark as A
    lock.flag[id] = true; // Mark as B
    asm volatile ("mfence" : : : "memory");
    while (lock.flag[1 - id] && lock.victim == id);
}

void peterson_unlock(peterson_lock_t &lock, int id) {
    lock.flag[id] = false;
    lock.victim = id;
}

После замены порядка строк «Пометить как A» и «Пометить как B» я ожидал, что программа будет работать почти всегда корректно, поскольку теперь это соответствует записи в Википедии о блокировке Петерсона.

https://en.wikipedia.org/wiki/Peterson%27s_algorithm

Однако ограждение памяти не защищает порядок между метками A и Mark B. Следовательно, все еще возможно, что программа неверна?Если да, то как это исправить?

1 Ответ

2 голосов
/ 06 июня 2019

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

Ваша реализация блокировки Петерсона неверна (также после замены строк «Пометить как A» и «Пометить как B»).
Если вы переводите псевдокод Википедии в C++, правильныйреализация становится: 

typedef struct {
    volatile bool flag[2];
    volatile int victim;
} peterson_lock_t;

void peterson_lock(peterson_lock_t &lock, int id) {
    lock.flag[id] = true;
    lock.victim = 1-id;
    asm volatile ("mfence" ::: "memory"); // CPU #StoreLoad barrier
    while (lock.flag[1-id] && lock.victim == 1-id);
}

void peterson_unlock(peterson_lock_t &lock, int id) {
    asm volatile("" ::: "memory"); // compiler barrier
    lock.flag[id] = false;
}

В дополнение к использованию volatile для переменных lock, инструкция mfence (в peterson_lock) необходима для предотвращения переупорядочения #StoreLoad.Это показывает редкий случай, когда алгоритм требует последовательной согласованности;т.е. операции с переменными lock должны выполняться в едином общем порядке.

Использование volatile основано на непереносимых (но «почти» правильных) свойствах gcc/X86."почти" правильно ", потому что, хотя volatile хранилище на X86 является операцией освобождения на уровне ЦП, компилятор все еще может переупорядочивать операции с volatile и не- volatile данными.
По этой причинеЯ добавил барьер компилятора перед сбросом lock.flag[id] в peterson_unlock.

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

Обратите внимание, что при использовании volatile для общих данных барьер компилятора в peterson_unlock становится избыточным.

...