Примитивы синхронизации в linux

Обновлено: 03.07.2024

Open with Desktop
View raw
Copy raw contents Copy raw contents Loading

Copy raw contents

Синхронизация в компьютерных системах — это координация работы процессов таким образом, чтобы последовательность их операций была предсказуемой. Как правило, синхронизация необходима при совместном доступе к разделяемым ресурсам. Критическая секция — часть программы, в которой есть обращение к совместно используемым данным. При нахождении в критической секции двух (или более) процессов, возникает состояние гонки/состязания за ресурсы. Состояние гонки — это состояние системы, при котором результат выполнения операций зависит от того, в какой последовательности будут выполняться отдельные процессы в этой системе, но управлять этой последовательностью нет возможности. Иными словами, это противоположность правильной синхронизации.

Для избежания гонок необходимо выполнение таких условий:

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

Пример условий гонок: i++

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

Классические задачи синхронизации

Задача Производитель-потребитель (также известна как задача ограниченного буфера): 2 процесса — производитель и потребитель — работают с общим ресурсом (буфером), имеющим максимальный размер N. Производитель записывает в буфер данные последовательно в ячейки 0,1,2. пока он не заполниться, а потребитель читает данные из буфера в обратном порядке, пока он не опустеет. Запись и считывание не могут происходить одновременно.

Проблема синхронизации в этом варианте: если производитель будет прерван потребителем после того, как запишет данные в буфер buf[count] = item , но до того, как увеличит счетчик, то потребитель считает из буфера элемент перед только что записанным, т.е. в буфере образуется дырка. После того как производитель таки увеличит счетчик, счетчик как раз будет указывать на эту дырку. Симметричная проблема есть и у потребителя.

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

Еще одна проблема этого решения — это бессмысленная трата вычислительных ресурсов: циклы while (count == 0) /* do nothing */ ; — т.н. занятое ожидание (busy loop, busy waiting) или же поллинг (pooling) — это ситуация, когда процесс не выполняет никакой полезной работы, но занимает процессор и не дает в это время работать на нем другим процессам. Таких ситуаций нужно по возможности избегать.

Алгоритмы программной синхронизации

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

Пример программного адгоритма — алгоритм Петерсона:

См. также алгоритм Деккера, алгоритм пекарни Лемпорта и др.

Аппаратные инструкции синхронизации

Аппаратные инструкции синхронизации реализуют атомарные примитивные операции, на основе которых можно строить механизмы синхронизации более высокого уровня. Атомарность означает, что вся операция выполняется как целое и не может быть прерывана посредине. Атомарные примитивные операции для синхронизации, как правило, выполняют вместе 2 действия: запись значения и проверку предыдущего значения. Это дает возможность проверить условие и сразу записать такое значение, которое гарантирует, что условие больше не будет выполняться.

Try-and-set lock (TSL)

Инструкции типа try-and-set записывают в регистр значение из памяти, а в память — значение 1. Затем они сравнивают значение в регистре с 0. Если в памяти и был 0 (т.е. доступ к критической области был открыт), то сравнение пройдет успешно, и в то же время в память будет записан 1, что гарантирует, что в следующий раз сравнение уже не будет успешным, т.е. доступ закроется.

Реализация критической секции с помощью TSL :

То же самое на С:

Инструкции типа compare-and-swap записывают в регистр новое значение и при этом проверяют, что старое значение в регистре равно запомненому ранее значению.

В x86 называется CMPXCHG .

Проблема ABA (ABBA): CAS инструкции не могут отследить ситуацию, когда значение в регистре было изменено на новое, а потом снова было возвращено к предыдущему значению. В большинстве случаев это не влияет на работу алгоритма, а в тех случаях, когда влияет, необходимо использовать инструкции с проверкой на такую ситуацию, такие как LL/SC .

Другие аппаратные инструкции

Двойной CAS
Fetch-and-add
Load-link/store-conditional (LL/SC)

Системные механизмы синхронизации

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

Самым простым вариантом ограничения доступа в критическую область является переменная-замок: если ее значение равно 0, то доступ открыт, а если 1 — то закрыт. У нее есть 2 атомарные операции:

заблокировать (lock) — проверить, что значение равно 0, и устанавливает его в 1 или же ждать, пока оно не станет 0
разблокировать (unlock), которая устанавливает значение в 1

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

Спинлок — это замок, ожидание при блокировке которого реализовано в виде занятого ожидания, т.е. поток "крутится" в цикле, ожидая разблокировки замка.

Реализация на ассемблере с помощью CAS:

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

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

Концептуально семафор включает в себя счетчик и очередь ожидания для потоков. Интерфейс семафора состоит из двух основных операций: опустить (down) и поднять (up). Операция опустить атомарно проверяет, что счетчик больше 0 и уменьшает его. Если счетчик равен 0, поток блокируется и ставиться в очередь ожидания. Операция поднять увеличивает счетчик и посылает ожидающим потокам сигнал пробудиться, после чего один из этих потоков сможет повторить операцию опустить.

Бинарный семафор — это семафор с N = 1.

Мьютекс — от словосочетания mutual exclusion, т.е. взаимное исключение — это примитив синхронизации, напоминающий бинарный семафор с дополнительным условием: разблокировать его должен тот же поток, который и заблокировал.

Реализация мьютекса с помощью примитива CAS :

Стоит отметить, что не все системы предоставляют гарантии того, что мьютекс будет разблокирован именно заблокировавшим его потоком. В приведенном выше примере это условие как раз не проверяется.

Мьютекс с возможностью повторного входа (re-entrant mutex) — это мьютекс, который позволяет потоку несколько раз блокировать его.

RW lock — это особый вид замка, который позволяет разграничить потоки, которые выполняют только чтение данных, и которые выполняют их модификацию. Он имеет операции заблокировать на чтение (rdlock), которая может одновременно выполняться несколькими потоками, и заблокировать на запись (wrlock), которая может выполняться только 1 потоком. Также правильные реализации RW-замка позволяют избежать проблемы инверсии приоритетов (см. ниже).

Переменные условия и мониторы

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

Переменная условия (condition variable) — примитив синхронизации, позволяющий реализовать ожидание какого-то события и оповещение о нем. Над ней можно выполнять такие действия:

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

POSIX Threads (Pthreads) — это часть стандарта POSIX, которая описывает базовые примитивы синхронизации, поддерживаемые в Unix системах. Эти примитивы включают семафор, мьютекс и переменные условия.

Futex (быстрый замок в пользовательском пространстве) — это реализация мьютекса в Unix-системах, которая оптимизирована для минимального использования функций ядра ОС, за счет чего достигается более быстрая работа с ним. С помощью фьютексов в Linux реализованы семафоры и переменные условия.

Над фьютексами можно делать такие базовые операции:

ожидать — wait(addr, val) — проверяет, что значение по адресу addr равно val , и, если это так, то переводит поток в состояние ожидания, а иначе продолжает работу (т.е. входит в критическую область)
разбудить — wake(addr, n) — посылает n потокам, ожидающих на фьютексе по адресу addr опопвещение о необходимости проснуться

Помимо условий гонки и занятого ожидания неправильная синхронизация может привести к следующим проблемам:

Тупик/взаимная блокировка (deadlock) — ситуация, когда 2 или более потоков ожидают разблокировки замков друг от друга и не могут продвинуться. Простейший пример кода, который может вызвать взаимную блокировку:

Живой блок (livelock) — ситуация с более, чем двумя потоками, при которой потоки ожидают разблокировки друг от друга, при этом могут менять свое состояние, но не могут продвинуться глобально в своей работе. Такая ситуация более сложная, чем тупик и возникает значительно реже: как правило, она связанна с временными особенностями работы программы.

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

Голодание — ситуация, когда поток не может получить доступ к общему ресурсу и не может продвинуться. Такая ситуация может быть следствием как тупика, так и инверсии приоритета.

Способы предотвращения тупиковых ситуаций

Все способы борьбы с тупиками не являются универсальными и могут работать только при определенных условиях. К ним относятся:

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

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

Ничего общего (shared-nothing)

Взаимодействующие последовательные процессы (Communicating Sequential Processes, CSP) — это еще один подход к организации взаимодействия без использования замков. Единицами взаимодействия в этой модели являются процессы и каналы. В отличие от модели CPP, пересылка данных через канал в этой модели происходит, как правило, синхронно, что дает возможность установить определенную последовательность выполнения процессов. Данная концепция реализована в языке программирования Go.

Программная транзакционная память

Транзакция — это группа последовательных операций, которая представляет собой логическую единицу работы с данными. Транзакция может быть выполнена либо целиком и успешно, соблюдая целостность данных и независимо от параллельно идущих других транзакций, либо не выполнена вообще и тогда она не должна произвести никакого эффекта. В теории баз данных существует концепция ACID , которая описывает условия, которые накладываются на транзакции, чтобы они имели полезную семантику. A означает атомарность — транзакция должна выполняться как единое целое. С означает целостность (consistency) — в результате транзакции будут либо изменены все данные, с которыми работает транзакция, либо никакие из них. I означает изоляция — изменения данных, которые производяться во время транзакции, станут доступны другим процессам только после ее завершения. D означает сохранность — после завершения транзакции система БД гарантирует, что ее результаты сохраняться в долговременном хранилище данных. Эти свойства, за исключением, разве что, последнего могут быть применимы не только к БД, но и к любым операциям работы с данными. Программная система, которая реализует транзакционные механизмы для работы с разделяемой памятью — это Программная транзакционная память (Software Transactional Memory, STM). STM лежит в основе языка программирования Clojure, а также доступна в языках Haskell, Python (в реализации PyPy) и других.

Последняя статья про классические примитивы синхронизации.

(Наверное, потом напишу ещё одну про совсем уже нетипичную задачу, но это потом.)

Сегодня мы немножко заглянем в процессор. Чуть-чуть.

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

В комментариях к предыдущим заметкам возникла дискуссия — насколько справедливо вообще выделять спинлок как примитив, ведь по сути он — просто мьютекс, верно? Он выполняет ту же функцию — запрещает одновременное исполнение фрагмента кода несколькими параллельными нитями.

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

Но меня эта тема интересует не только с позиции программиста юзерленда, но и с позиции разработчика ядра, а так же и разработчика самих примитивов синхронизации. И тут уже различие принципиально.

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

Есть и ещё одно, семантическое различие. Мьютекс допускает и предполагает снятие нити с процессора, долгую остановку вызывающей нити. Мьютексом можно запереть объект на час или сутки, это приемлемо и нормально. Спинлок принципиально рассчитан только на кратчайшие приостановки, это всегда работа с неатомарным стейтом объекта. Присваивание группы переменных, небольшой цикл — это максимум того, что можно сделать под спинлоком.

Итак, иерархия реализации такова: mutex/cond/sema сделаны на базе спинлоков, спинлоки — на базе атомарных операций, предоставляемых процессором. Мы в них немного заглянем сегодня.

Как устроен спинлок?

Принцип невероятно прост. Спинлок — это просто переменная, которая содержит ноль или единицу (бывают варианты).

Если ноль — спинлок свободен, и его можно захватить. Если не ноль — спинлок заперт, и нить, которая желает его захватить, будет ждать, крутясь (spin — вращение) в небольшом цикле непрерывной проверки освобождения спинлока. Вот, собственно, реализация:

Операция _spin_try_lock — атомарная, реализована на ассемблере соответствующего процессора. Пытаемся запереть спинлок, если не удалось — крутимся в цикле, пока он заперт, потом снова пытаемся.

Вот и всё, в целом.

Теперь детали. Операция _spin_try_lock тоже очень проста:

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

Что происходит? Мы меняем местами значение sl->lock и регистр, в котором лежит единица. Если спинлок не был заперт (sl->lock был равен нулю), он станет равен единице и _spin_try_lock вернёт ноль — мы успешно заперли спинлок. Если sl->lock был равен единице, то в итоге sl->lock после обмена опять будет равен единице, но и результатом _spin_try_lock будет считанное предыдущее значение sl->lock — единица, что означает неуспех захвата спинлока.

Вообще проблема с атомарными операциями на уровне процессора очень велика. Пока в системе один процессор, этой проблемы нет. Но и ситуации такой реально тоже давно уже нет. Даже в дешёвых машинах уже несколько процессоров, или один многоядерный, и/или гипертредный.

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

Интересно, что есть совершенно иная схема работы с атомарными объектами. Процессоры mips не имеют инструкции вида «атомарно что-то сделать с ячейкой памяти». Вместо этого у MIPS есть интересная связанная пара инструкций:

LL - load linked
SC - store conditional

Первая инструкция — load linked — просто читает значение из памяти. Но при этом в процессоре взводится триггер, который «следит» за считанной ячейкой — не было ли в неё записи.

Вторая — store conditional — сохраняет значение в память. Но! Если со времени исполнения load linked в эту ячейку кто-то уже записал новое значение, store conditional вернёт признак неуспеха (и, конечно, ничего в ячейку памяти записывать не будет).

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

В отличие от Интеловского xchg такая пара позволяет делать не только спинлоки, но и реализовывать более сложные алгоритмы. Вернёмся к разговору о семафорах:

Все проблемы с этим кодом на процессоре MIPS можно решить довольно просто:

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

Что ещё важно знать про спинлоки в среде ядра ОС (или при программировании для микроконтроллеров, где, как правило, нет режима пользователя): при захвате спинлока прерывания должны быть запрещены.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Последняя статья про классические примитивы синхронизации.

(Наверное, потом напишу ещё одну про совсем уже нетипичную задачу, но это потом.)

Сегодня мы немножко заглянем в процессор. Чуть-чуть.

Вот и всё, в целом.

Теперь детали. Операция _spin_try_lock тоже очень проста:

LL - load linked
SC - store conditional

Все проблемы с этим кодом на процессоре MIPS можно решить довольно просто:

Open with Desktop
View raw
Copy raw contents Copy raw contents Loading

Copy raw contents

Синхронизация в Linux

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

Самый простой способ синхронизации — отсутствие необходимости в синхронизации. В ядре к примеру такое достигается “Процессорными переменными”. У каждого процессора свой собственный экземпляр таких переменных, для оптимальности массивы процессорных переменных выровнены по строчкам аппаратного кэша. Таким образом удаётся избежать конфликтов кэш-промахов и гонки за ресурсы между различными процессорами. Однако, это не спасает в ситуациях с вытеснением и прерываниями на 1 процессоре, тут нужны дополнительные примитивы синхронизации.

Примитивы для работы с “Процессорными переменными” описаны в include/linux/ percpu.h и arch/x86/include/asm/percpu.h.

Скажем так, классическое определение: Атомарные операции — выполняются, как неделимые, либо полностью, либо не выполняются вообще. Однако, что это значит в контексте исполнения процесса? Могут ли нас прервать во время исполнения, могут ли нас переключить на исполнение другого процесса? В классическом понимании прерывать исполнение нельзя, но в ядре стараются не запрещать прерывание, хотя такая возможность и поддерживается (/include/linux/irqflags.h). Процедура local_irq_save отключает прерывания, а local_irq_restore восстанавливает ранее отключенные прерывания, атомарные операции их иногда используют, но это не рекомендовано.

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

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

В ядре под атомарными операциями подразумевается именно операции с префиксом atomic_*, они платформозависимые. Для x86 их можно найти в /arch/x86/include/asm/atomic.h. В атомарных операциях используется тип данных atomic_t (/include/linux/types.h) или atomic64_t:

Как можно заметить класс atomic_* операций применяется в основном для простых объектов, таких как счётчики. Но как обеспечить атомарность работы с ними? В x86 есть несколько путей выполнения данной задачи:

Использовать lock префикс для ассемблерной операции. Lock префикс гарантирует уникальное(mandatory) владение ресурсом даже в многопроцессорной системе.
Специальные операции, такие как CMPXCHG, XCHG. В atomic операциях линукс используется lock префикс, что связано с тем, что она быстрее, чем CMPXCHG, так как он раскрывается примерно в следующую последовательность команд:

Реализуем теперь сами функцию atomic_dec_and_test, она должна уменьшить значение счётчика на единицу и вернуть 1, если counter == 0, или 0 в противном случае.

Как видим, после lock dcl %counter, дальше работаем с локальными регистрами, потому относительно других процессов всё происходит атомарно.

У современных компиляторов очень агрессивные алгоритмы оптимизации, они могут менять инструкции местами, чтобы оптимизировать обращение к регистрам, ускорить выполнение программы и т.д. Чтобы ассемблерные команды одной СИ-функции не перемешались с командами другой есть барьеры оптимизации в Linux. (/include/linux/compiler-gcc.h)

Такая пустая “ассмеблерная” инструкция говорит компилятору, что он не может свободно применять оптимизации здесь, так как функции полностью изменяют память.

Однако, кроме компилятора современные процессоры так же оптимизируют исполнение инструкция — Out Of Order Execution (OOO). Для того, чтобы процессор выполнил ассемблерные инструкции в нужном порядке, есть барьеры памяти.(!TODO: дописать с примером).

Если ресурс свободен, то процесс берёт на него блокировку и работает с ним, если же обнаруживается, что ресурс уже кем-то заблокирован, процесс крутится в цикле, пока блокировка не будет снята.

Это так называемое “Активное” ожидание. С одной стороны оно может показаться не очень эффективной, но в ядре многие ресурсы оказываются заблокированными на сравнительно небольшое время. А перевод процесса в состояние ожидания и обратно занимает приличное количество времени. В критической секции, защищённой спин блокировкой, отключается вытеснение. Spin lock описывается структурой spinlock_t (/include/linux/spinlock_types.h). Однако для понимания рассмотрим пример попроще.

spin_lock_init — инициализирует спин блокировку. После этого она будет в разблокированном состоянии = 1.

spin_lock() — выполнять цикл, пока спинлок не станет равен 1, после сделать его 0. Напишем свой void spin_lock, чуть-чуть попроще, при спинлок = 1 спинлок свободен и мы берём его, при <= 0 занят и мы крутимся в цикле:

Оригинальные функции можно начать разбирать с файла — /include/linux/ spinlock.h.

У такой спин блокировки есть несколько проблем:

Порядок попытки захвата спинлока не гарантирует порядок его взятия. Иными словами, такая блокировка не честна по отношению к процессам, которые её ожидают. Эту проблему могут решить Ticket spinlocks, но они не помогут во втором случае.
Можно взять только в исключительное пользование, а значит, что нельзя параллельно читать одни и те же структуры.

Для улучшения параллелизма есть read/write lock.

Практика показывает, что операции чтения более распространены, чем операции записи. При rwlock одновременно разрешено либо 1 операция записи, либо множество операций чтения. Описывается она структурой — rwlock_t (/include/linux/rwlock_types.h) rwlock_init() инициализирует rwlock = 0x01000000

read_lock() идейно выглядит так:

Каждая read блокировка уменьшает значение счётчика на 1 и так до нуля. Состояние lock == 0x0 означает, что блокировка уже взята на запись. Разблокировка — просто увеличить значение счётчика на 1.

Взятие и освобождение блокировки для записи:

Минус r/wlock в том, что приоритет запросов блокировки на чтение и запись одинакова => при последовательности запросов read -> write -> read нет определённости в том, что произойдёт. Запросто может оказаться, что 2-ое будут читать, а wirte запрос будет ждать, хотя он и пришёл раньше второго read.

С этой проблемой борется другой примитив синхронизации — seqlock (/include/linux/seqlock.h). Основное отличие в том, что приоритет записи намного выше приоритета операции чтения. Описывается данная блокировка структурой с двумя полями:

Каждый читающий должен прочитать счётчик sequence дважды: до и после чтения. Если они совпадают, то он прочитал консистентные данные, которые никто не изменил, если отличаются, то считанные данные устарели, так как активизировался пишущий тракт. Пишущие увеличивают значение счётчика на 1 до записи и после.

Этот механизм очень похож на работу со счётчиком jiffies_64 (/include/linux/jiffies.h). Это 64 битный счётчик на 32 битных машинах его нельзя атомарно прочитать или изменить. Потому на них применяется алгоритм похожий надписанный выше: int seqcount = 0;

RCU - Read Copy Update

RCU — обновление копии для чтения. (/include/linux/rcupdate.h) Это эволюция идей работы с ресурсами, которые обычно читаются чаще, чем изменяются. Эта технология позволяет работать в одними ресурсами одновременного нескольким писателям и читателям. Она lock-less и не требует постаянных попыток прочить данные. В ней нет совместно используемых структур данных, что существенно для скорости работы из-за конкуренции за них в кэше.

Можно защищать только динамические данные, доступные по ссылке.
Нельзя спать внутри RCU. Когда тракту в ядре надо прочитать данные он вызывает — rcu_read_lock(), что эквивалентно preempt_disable(). Затем читатель разыменовывает указатель и приступает к чтению. После окончания работы с данными нужно вызвать rcu_read_unlock()(preempt_enable).

Как видим читаль почти что ничего не делает, значит всё делает писатель. Когда он хочет изменить структуру, о сначала разыменовывает указатель, делает себе её копию, после обновляет копию. Закончив обновление, пишущий тракт заменяет указатель, чтобы он указывал на новую копию, подмена указателя происходит атомарно, а значит любой читающий и пишущий тракт видит консистентную либо старую, либо новую копию объекта. После всего остаётся только один вопрос — когда освобождать старый объект? Потенциально каждый читающий может читать старую копию, потому каждый из них должен сначала вызвать rcu_read_unlock(), а только потом старую копию можно освободить.

Читайте также: