Обзор примитивов синхронизации — mutex и cond

[degs]

Все хорошо, только многопоточное программирование давно уже не относится исключительно к разработке ядра. И еще, если мы говорим например о Линуксе, все синхронизующие примитивы сделаны поверх futex — реализации mutex в user-space. Было бы интересно где-нибудь ближе к концу почитать как они устроены и чем именно отличаются от классического in-kernel mutex.

[mejedi]

В Линуксе, все синхронизующие примитивы сделаны поверх futex — реализации mutex в user-space

Как-то некорректно это, futex-ы реализованы в ядре. Другое дело, что реализация, например, блокировки мьютекса, во многих случаях обходится без вызова futex_wait, т.е. целиком отрабатывает в user-space.

[dzavalishin]

Это просто сочетание user-level спинлока и kernel-level примитивов, которые фактически останавливают тред. Дело в том, что спинлоки катастрофически быстрее мьютексов, но применимы только для очень коротких захватов, иначе они долго и бессмысленно жрут процессор. Поэтому делают так — сначала пытаются захватить спинлок (без ухода в ядро), если удалось — ура, мы обошлись малой кровью. Если спинлок занят то уходим в ядро на полновесный системный вызов, который усыпляет нас, пока спинлок не освободится.

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

Разбираться неинтересно, но могу предположить, что если кто-то ждёт нашего запертого спинлока, то ядро переводит страницу со спинлоком в r/o и по пейджфолту выясняет, когда мы его отпираем.

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

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

Что есть спинлоки — напишу позже. Впрочем, Вы про них и так знаете.

[degs]

Это просто сочетание user-level спинлока и kernel-level примитивов

futex-ы реализованы в ядре

ну все таки не совсем так. Синхронизация легко делается в user-space из атомарных примитив, спинлок скорее вспомогательный механизм. А вот остановить поток и передать управление другому — без помощи ядра не обойтись. Вот и хотелось бы знать подробнее о механизмах.

[ion2]

могу предположить, что если кто-то ждёт нашего запертого спинлока, то ядро переводит страницу со спинлоком в r/o и по пейджфолту выясняет, когда мы его отпираем

Это слишком сурово. Фьютекс усыпляет поток, пока значение блокировки равно проверяемому значению. У мьютекса три состояния: 0 — свободен, 1 — захвачен одним потоком, 2 — захвачен и есть ожидающие потоки.

<code class="cpp">mutex_lock(mutex *lock)
{
//увеличиваем блокировку на 1 и проверяем предыдущее значение
//если был 0, то теперь там 1 и поток успешно захватил мьютекс
    if(xchg_add(&lock,1) == 0)
        return;
//ядро приостановит поток пока lock равен 2
    while(xchg(&lock, 2) != 0)
        syscall_futex(&lock, 2);
}
В идеальном случае lock равен 0 и захват обойдётся в одну операцию xchg_add (xadd для x86)  

mutex_unlock(mutex *lock)
{
    if(xchg(&lock, 0) != 1)
    {
//есть ожидающие потоки
//разбудим один
        syscall_futex_wake(&lock,1);     
    }
}
Аналогично, если нет ожидающих потоков lock равен 1 и освобождение происходит за одну операцию xchg,
в противном случае вызывается FUTEX_WAKE </code>

[MacIn]

Мне известны следующие примитивы синхронизации:

User/kernel mode: mutex+cond, sema, enter/leave critical section.
Kernel only: spinlock, управление прерываниями.

Это, наверно, корректно только для некоторой наперед заданной операционной системы.
В Windows, например, CS — это логически мьютекс, но легковесный, usermode, сделаный на LOCK CMPXCHG. CS — не вид примитива "сам по себе".
Почему "нить"? Особенно в сочетании с "любой малтитредной программе".

[dzavalishin]

Это сочетание спинлока и мьютекса, аналогично фьютексам выше. Семантика та же, а реализаций может быть много разных.

Ну и, кроме того, там же написано — "мне известно". Наверняка на свете есть что-то, что мне неизвестно. :)

[MacIn]

Это сочетание спинлока и мьютекса, аналогично фьютексам выше

В какой ОС? Это специфично.

Ну и, кроме того, там же написано — «мне известно». Наверняка на свете есть что-то, что мне неизвестно. :)

Я не говорю, что чего-то не хватает. Я говорю, что деление неверное.

[dzavalishin]

А, Вы о том, что спинлоки могут быть не в ядре? Тут всё сложно, на самом деле. Вообще-то не могут. Без поддержки ядра они работать не будут — в какой-то момент шедулер всё равно заберёт у нас процессор, и может отдать его другой нити нашего же процесса, если его никак не убедить в обратном, что требует поддержки ядра. Они могут быть инструментом оптимизации тяжёлых мьютексов.

[MacIn]

Я о том, что "критическая секция" — это не примитив сам по себе. Это концепция, которая реализуется при помощи, по сути, мьютекса.
Мьютекс может быть как ядерным, так и юзерспейсным. Спинлок находится в обоих мирах сразу, но может быть и чисто ядерным.
ИМХО, вместо

User/kernel mode: mutex+cond, sema, enter/leave critical section.
Kernel only: spinlock, управление прерываниями.

Стоило бы написать
Мьютекс (Я/Ю), Семафор (Я/Ю).
Потому что Critical Section — это и есть мьютекс, некоторая штукенция, которая охраняет "часть кода". Сама критическая секция — это и есть разделяемый ресурс, а EnterCriticalSection (в win32, например) — это по сути тот же acquire mutex.
Spinlock — это тоже мьютекс, а то, что он "бьется о стенку" по кругу, прежде, чем нырнуть в ядро — деталь реализации, это не меняет того, что это — мьютекс.
Управление прерываниями — это тоже мьютекс, но здесь в качестве разделяемого ресурса выступает сам процессор. Никакой разницы, по сути, между CLI и EnterCriticalSection и OpenMutex или функции типа AcquireSpinLock нет. То, что там творится внутри — это детали реализации.

[dzavalishin]

В Ваших словах есть изрядная правота. Но семантическая разница между спинлоком и мьютексом есть. Это переключение контекста. В ядре это важно. В юзерспейсе — Вы правы полностью, есть только мьютекс, и чем он делается — вопрос оптимизации.

[dzavalishin]

Корректировка: работать могут, в описанной выше ситуации новый тред упрётся в запертый спинлок и прокрутится в нём весь свой таймслайс. Просто будут невменяемо неэффективны.

[Ryadovoy]

Подскажите, почему Вы не рассматриваете event как отдельный примитив синхронизации OS?
Известные мне реализации condition не умеют работать сами по себе без мьютекса, а вот event вполне себе может.

[dzavalishin]

Это специфичная реализация семафора, посмотрите следующую статью. Специфичная в том, что значения семафора ограничены 0 и 1, в одном из режимов. Во втором режиме это cond.

[Ryadovoy]

Семафор не очень подходит, если нужно пробудить все ждущие потоки (логика manual reset event), а mutex+cond лично мне кажется избыточным, когда нужен флаг-событие. В WinAPI, к примеру, нет такого синхронизационного объекта как condition variable, эта абстракция реализуется на этой платформе с использованием event-а или семафора.