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

    Синхронизация нужна в любой малтитредной программе. (Если, конечно, она не состоит из локлесс алгоритмов на 100%, что вряд ли). Будь то приложение или компонента ядра современной операционной системы.

    Меня всё нижесказанное, конечно, больше волнует с точки зрения разработки ядра ОС. Но почти всё применимо и к пользовательскому коду.

    Кстати, ядра старых ОС в примитивах синхронизации не нуждались, поскольку преемптивной мультизадачности внутри ядра в старые добрые времена не было. (Уж за Юникс 7-й версии я отвечаю. Не было.) Точнее, единственным методом синхронизации был запрет прерываний. Но об этом позже.

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

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

    Зачем всё это нужно, читатель, наверное, знает, но всё же уточним.

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

    Простой пример. Список.

    struct list { list *next; list *prev };
    


    Вставляем элемент в список.

    new_el->next = curr_el->next;
    new_el->prev = curr_el;
    curr_el->next->prev = new_el; // 3
    curr_el->next = new_el;
    


    Всё примитивно. Но если этот код будут исполнять две нити параллельно, то вместо связного списка получится взрыв на макаронной фабрике. Например, если вторая нить включится в момент, когда первая нить закончила строку 3, то обходя список слева направо мы встретим на одном и том же месте один объект, а справа налево — другой.

    Неприятно.

    Применим мьютекс — mutually exclusive lock. Этот замок запрещает параллельное исполнение запертого им кода — если одна нить начала его исполнять, вторая будет ждать на входе до тех пор, пока первая не закончит.

    mutex_lock( &list->mutex);
    
    new_el->next = curr_el->next;
    new_el->prev = curr_el;
    curr_el->next->prev = new_el; // 3
    curr_el->next = new_el;
    
    mutex_unlock( &list->mutex);
    


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

    Что происходит? Нить А делает вызов mutex_lock для мьютекса list->mutex. Который, очевидно, принадлежит списку, который мы хотим поменять, и защищает доступ именно к нему. Он не заперт, нить А запирает мьютекс (теперь он знает, что заперт, и знает, кто его запер) и продолжает работу. Если теперь нить Б попробует войти в тот же регион кода (или другой, защищённый тем же мьютексом — например, в функции удаления элемента списка), то второй раз запереть запертый мьютекс не получится. Нить Б будет ждать, пока нить А не вызовет mutex_unlock.

    Кстати, если мы с вами — ядерные разработчики, то важно понимать ещё одно, неинтересное для прикладного программиста свойство мьютекса (как и всех «тяжеловесных» примитивов синхронизации) — если мы пытаемся запереть мьютекс, который уже заперт другой нитью, мы не просто ждём — нашу нить «снимут с процессора», произойдёт переключение контекста. Это ценно, потому что позволяет куда более эффективно загружать процессор, но есть и проблемы. Внутри обработчика прерываний, например, такие примитивы применять нельзя совсем, потому что переключение контекста внутри прерывания запрещено и грозит изрядным раздраем в работе системы. Но, наверное, об этом надо будет написать отдельно.

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

    Рассмотрим функции alloc_mem и free_mem:

    // NB! Заведомо неверный код!
    alloc_mem() 
    {
    
    while(total_free_mem <= 0)
        {
        wait_cond(&got_free_mem);
        }
    
    // actually allocate
    
    }
    
    free_mem() 
    {
    // actually free mem
    total_free_mem++;
    signal_cond(&got_free_mem);
    }
    


    Что здесь происходит? Всё банально. В функции аллокации памяти мы смотрим на глобальный счётчик свободной памяти. Если пусто, свободной памяти нет, ждём пока кто-то не освободит память — вызываем wait_cond, который нас приостанавливает, пока кто-то не просигналит — готово, память освободили.

    Это, конечно, функция free_mem() — она возвращает память в кучу, увеличивает счётчик свободной памяти и вызывает signal_cond — сообщает страждущим, что память есть. Тот, кто спал внутри wait_cond, «проснётся» после такого сигнала, проверит что да, память есть, и выделит её. Всё верно?

    Ну, нет, конечно. Если функцию alloc_mem вызовут две нити сразу, то будет беда — одна из них получит сигнал первой, проснётся, убедится, что свободная память есть, и тут вдруг шедулер возьми да сними её с процессора. И дай проснуться второй такой же нити. Вторая нить проснётся, тоже увидит, что память есть, заберёт её и закончится. Просыпается мафия первая нить, и у неё всё плохо. Только что она проверила переменную free_mem, убедилась, что всё есть, и вот — никакой свободной памяти в пуле не находится. Беда.

    Для данного случая беда не смертельная — можно просто вернуться к началу функции и снова ждать у моря погоды. Хотя, конечно, и это плохо — мы теряем процессорное время на пустые метания.

    Но, вроде бы, мы же знаем ответ? Добавим mutex!

    // NB! Снова заведомо неверный код!
    alloc_mem() 
    {
    
    mutex_lock( &allocator_mutex );
    while(total_free_mem <= 0)
        {
        wait_cond(&got_free_mem);
        }
    
    // actually allocate
    mutex_unlock( &allocator_mutex );
    
    }
    
    free_mem() 
    {
    mutex_lock( &allocator_mutex );
    // actually free mem
    total_free_mem++;
    signal_cond(&got_free_mem);
    mutex_unlock( &allocator_mutex );
    }
    


    Так хорошо? Нет. Освобождение памяти не случится — функция alloc_mem() его заперла, заснула на ожидании cond, и никто больше в мьютекс войти не может, и никто не освободит память, и не просигналит.

    Беда. Но ладно же, мы знаем, что делать! Перед тем, как заснуть на ожидании cond, мы отопрём mutex, и позволим другим войти в free и вернуть нам память. Вот так:

    // NB! И опять заведомо неверный код!
    alloc_mem() 
    {
    
    mutex_lock( &allocator_mutex );
    while(total_free_mem <= 0)
        {
        mutex_unlock( &allocator_mutex );
        wait_cond(&got_free_mem);
        mutex_lock( &allocator_mutex );
        }
    
    // actually allocate
    mutex_unlock( &allocator_mutex );
    
    }
    


    По комментарию вы уже видите, что опять не слава богу. Что теперь? А теперь есть щёлочка, тонкая линия между моментом, когда мы проснулись и вышли из функции wait_cond, получив от free_mem сигнал об освобождении памяти, и захватом мьютекса. В этот момент мьютекс не взят, и другие нити опять могут нас опередить и набезобразить. Именно по этой причине функция wait_cond выглядит несколько иначе:

    wait_cond( cond *c, mutex *m );
    


    Работает это вот как: функция принимает на вход conditional variable, которая передаст нам сигнал «проснуться», и запертый мьютекс:

    alloc_mem() 
    {
    
    mutex_lock( &allocator_mutex );
    while(total_free_mem <= 0)
        {
        wait_cond(&got_free_mem,&allocator_mutex);
        }
    
    // actually allocate
    mutex_unlock( &allocator_mutex );
    
    }
    


    Функция wait_cond отопрёт мьютекс, во-первых, самостоятельно, а во-вторых сделает это атомарно по отношению к переходу в спящее состояние. То есть нить, входящая в wait_cond сначала заснёт, а потом, не прерывая сна, отопрёт мьютекс. И наоборот, просыпаясь, она сначала захватит мьютекс, а потом проснётся и продолжит работу. (Это требует от кода переключения нитей изрядной хитрости, постараюсь рассказать об этом в одной из следующих заметок.)

    Только такая семантика обеспечивает 100% консистентность и отсутствие «гонок» — race conditions.

    Отметим, что код функции free у нас получился вполне правильный:

    free_mem() 
    {
    mutex_lock( &allocator_mutex );
    // actually free mem
    total_free_mem++;
    signal_cond(&got_free_mem); // 4
    mutex_unlock( &allocator_mutex ); // 5
    }
    


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

    К сказанному, наверное, имеет смысл добавить, что реальная функция signal_cond пробуждает не все ожидающие потоки, а только один (обычно — с наивысшим приоритетом), так что ситуация в приведённом примере несколько проще и сложнее одновременно. Проще потому что уже внутри сигнализации встроен механизм, который после одного free пробудит только один alloc, а сложнее потому, что реально это ничего не решает — мы не знаем, подойдёт ли данному alloc-у освобождённый участок, так что надо вместо signal_cond применить broadcast_cond, который таки пробудит всех страждущих, дав им возможность в честной драке определиться, кому достанется ресурс.

    Посмотреть на фактическую реализацию этих примитивов можно здесь:

    mutex.c, cond.c

    В следующей серии — sema семафор, который в одиночку заменяет и mutex, и cond. Практически без ансамбля.

    Это серия статей «Обзор примитивов синхронизации»:

    Средняя зарплата в IT

    110 000 ₽/мес.
    Средняя зарплата по всем IT-специализациям на основании 8 707 анкет, за 2-ое пол. 2020 года Узнать свою зарплату
    Реклама
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее

    Комментарии 15

      +3
      Все хорошо, только многопоточное программирование давно уже не относится исключительно к разработке ядра. И еще, если мы говорим например о Линуксе, все синхронизующие примитивы сделаны поверх futex — реализации mutex в user-space. Было бы интересно где-нибудь ближе к концу почитать как они устроены и чем именно отличаются от классического in-kernel mutex.
        +1
        В Линуксе, все синхронизующие примитивы сделаны поверх futex — реализации mutex в user-space
        Как-то некорректно это, futex-ы реализованы в ядре. Другое дело, что реализация, например, блокировки мьютекса, во многих случаях обходится без вызова futex_wait, т.е. целиком отрабатывает в user-space.
        +1
        Это просто сочетание user-level спинлока и kernel-level примитивов, которые фактически останавливают тред. Дело в том, что спинлоки катастрофически быстрее мьютексов, но применимы только для очень коротких захватов, иначе они долго и бессмысленно жрут процессор. Поэтому делают так — сначала пытаются захватить спинлок (без ухода в ядро), если удалось — ура, мы обошлись малой кровью. Если спинлок занят то уходим в ядро на полновесный системный вызов, который усыпляет нас, пока спинлок не освободится.

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

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

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

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

        Что есть спинлоки — напишу позже. Впрочем, Вы про них и так знаете.
          0
          Это просто сочетание user-level спинлока и kernel-level примитивов
          futex-ы реализованы в ядре
          ну все таки не совсем так. Синхронизация легко делается в user-space из атомарных примитив, спинлок скорее вспомогательный механизм. А вот остановить поток и передать управление другому — без помощи ядра не обойтись. Вот и хотелось бы знать подробнее о механизмах.
            +2
            могу предположить, что если кто-то ждёт нашего запертого спинлока, то ядро переводит страницу со спинлоком в 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>
            0
            Мне известны следующие примитивы синхронизации:

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

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

              Ну и, кроме того, там же написано — "мне известно". Наверняка на свете есть что-то, что мне неизвестно. :)
                0
                Это сочетание спинлока и мьютекса, аналогично фьютексам выше

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

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

                Я не говорю, что чего-то не хватает. Я говорю, что деление неверное.
                  0
                  А, Вы о том, что спинлоки могут быть не в ядре? Тут всё сложно, на самом деле. Вообще-то не могут. Без поддержки ядра они работать не будут — в какой-то момент шедулер всё равно заберёт у нас процессор, и может отдать его другой нити нашего же процесса, если его никак не убедить в обратном, что требует поддержки ядра. Они могут быть инструментом оптимизации тяжёлых мьютексов.
                    +2
                    Я о том, что "критическая секция" — это не примитив сам по себе. Это концепция, которая реализуется при помощи, по сути, мьютекса.
                    Мьютекс может быть как ядерным, так и юзерспейсным. Спинлок находится в обоих мирах сразу, но может быть и чисто ядерным.
                    ИМХО, вместо

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

                    Стоило бы написать
                    Мьютекс (Я/Ю), Семафор (Я/Ю).
                    Потому что Critical Section — это и есть мьютекс, некоторая штукенция, которая охраняет "часть кода". Сама критическая секция — это и есть разделяемый ресурс, а EnterCriticalSection (в win32, например) — это по сути тот же acquire mutex.
                    Spinlock — это тоже мьютекс, а то, что он "бьется о стенку" по кругу, прежде, чем нырнуть в ядро — деталь реализации, это не меняет того, что это — мьютекс.
                    Управление прерываниями — это тоже мьютекс, но здесь в качестве разделяемого ресурса выступает сам процессор. Никакой разницы, по сути, между CLI и EnterCriticalSection и OpenMutex или функции типа AcquireSpinLock нет. То, что там творится внутри — это детали реализации.
                      +1
                      В Ваших словах есть изрядная правота. Но семантическая разница между спинлоком и мьютексом есть. Это переключение контекста. В ядре это важно. В юзерспейсе — Вы правы полностью, есть только мьютекс, и чем он делается — вопрос оптимизации.
                    0
                    Корректировка: работать могут, в описанной выше ситуации новый тред упрётся в запертый спинлок и прокрутится в нём весь свой таймслайс. Просто будут невменяемо неэффективны.
                0
                Подскажите, почему Вы не рассматриваете event как отдельный примитив синхронизации OS?
                Известные мне реализации condition не умеют работать сами по себе без мьютекса, а вот event вполне себе может.
                  0
                  Это специфичная реализация семафора, посмотрите следующую статью. Специфичная в том, что значения семафора ограничены 0 и 1, в одном из режимов. Во втором режиме это cond.
                    0
                    Семафор не очень подходит, если нужно пробудить все ждущие потоки (логика manual reset event), а mutex+cond лично мне кажется избыточным, когда нужен флаг-событие. В WinAPI, к примеру, нет такого синхронизационного объекта как condition variable, эта абстракция реализуется на этой платформе с использованием event-а или семафора.

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

                Самое читаемое