Реализация мьютекса в библиотеке потоков пользовательского уровня

Question

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

mutex_init, mutex_lock и mutex_unlock

Я думал, что моя структура mutex_t будет выглядеть примерно как

 typedef struct 
 {
   int available; //indicates whether the mutex is locked or unlocked
   queue listofwaitingthreads;
   gtthread_t owningthread; 
 }mutex_t;

В моем mutex_lockфункции, я сначала проверим, доступен ли мьютекс в цикле while.Если это не так, я выдам процессор для выполнения следующего потока.

В моей функции mutex_unlock я проверю, является ли поток владельца текущим потоком.Если это так, я установлю доступным 0.

Это способ сделать это?Кроме того, как насчет тупика?Должен ли я позаботиться об этих условиях в своей библиотеке уровня пользователя или я должен оставить программистов приложений для правильного написания кода?

Answer 1

Это не сработает, потому что у вас есть состояние гонки. Если два потока попытаются одновременно захватить блокировку, оба увидят available == 0, и оба подумают, что им удалось получить мьютекс.

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

Существуют алгоритмы, которые дают вам взаимное исключение без такой аппаратной поддержки, но они делают некоторые предположения, которые много раз неверны. Для получения более подробной информации об этом, я настоятельно рекомендую прочитать книгу Херлихи и Шавита Искусство многопроцессорного программирования , глава 7.

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

Answer 2

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

Answer 3

В общем случае реализация мьютекса должна выглядеть следующим образом:

Блокировка:

while (trylock()==failed) {
    atomic_inc(waiter_cnt);
    atomic_sleep_if_locked();
    atomic_dec(waiter_cnt);
}

Trylock:

return atomic_swap(&lock, 1);

Разблокировка:

atomic_store(&lock, 0);
if (waiter_cnt) wakeup_sleepers();

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

Обратите внимание, что atomic_sleep_if_locked и wakeup_sleepers соответствует FUTEX_WAIT и FUTEX_WAKE ops в Linux.Другие атомы, вероятно, являются инструкциями ЦП, но могут быть системными вызовами или кодом функции пользовательского пространства с поддержкой ядра, как в случае Linux / ARM и атомарного вызова сравнения и замены 0xffff0fc0.

Answer 4

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

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

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