Главная » Ядро Linux » Критические участки и состояние конкуренции за ресурсы – ЧАСТЬ 2

0

Вначале кажется, что описанная ситуация не имеет  простого решения. Как  можно предотвратить чтение очереди на  одном  процессоре в тот  момент, когда  другой  процессор обновляет ее?  Вполне логично аппаратно реализовать простые инструкции, такие  как  атомарные арифметические операции  или  операции сравнения, тем  не менее  было  бы  смешно аппаратно реализовывать критические участки  неопределенного  размера, как  в приведенном примере. Все что нужно  — это  предоставить метод, который позволяет отметить начало  и конец; критического участка, и предотвратить или  заблокировать  (lock)  доступ  к этому  участку, пока  другой  поток  выполняет его.

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

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

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

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

Поток  1                                                             Поток  2

Попытаться  заблокировать  очередь          Попытаться  заблокировать  очередь

успешно:  блокировка  захвачена                      неудачно:    ожидаем… ожидаем…

обратиться к очереди.. .                            ожидаем…

разблокировать  очередь                                     успешно:   блокировка   захвачена обратиться к   очереди., . разблокировать   очередь

.. .

Заметим, что блокировки бывают  необязательными (рекомендуемыми, advisory) и обязательными (навязываемыми, voluntary). Блокировки— это чисто программные конструкции, преимуществами которых  должны  пользоваться программисты. Никто не запрещает писать  код, который манипулирует нашей  воображаемой очередью  без использования блокировок. Однако такая  практика в конечном итоге приведет  к состоянию конкуренции за ресурс  и разрушению данных.

Блокировки бывают  различных "форм"  и "размеров". В операционной системе Linux  реализовано несколько различных механизмов блокировок. Наиболее существенная разница между ними  — это  поведение кода  в условиях, когда  блокировка захватываетя (конфликт при  захвате  блокировки, contended lock).  Для  некоторых типов  блокировок, задания просто  ожидают  освобождения блокировки, постоянно выполняя проверку освобождения в замкнутом цикле  (busy wait2), в то время  как другие тины  блокировок переводят задание  в состояние ожидания до тех пор, пока блокировка не освободится.

2  Иными словами,  "вращаются" (spin) в замкнутом цикле, ожидая на освобождение блокировки.

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

Проницательный читатель  в этом  месте  должен  воскликнуть: "Блокировки  не  решают  проблемы,  они  просто  сужают  набор  всех  возможных критических участков  до кода  захвата  и  освобождения блокировок. Тем  не  менее, здесь  потенциально может возникать состояние конкуренции за  ресурсы, хотя  и  с  меньшими последствиями!" К счастью, блокировки реализованы на  основе  атомарных операций,  которые гарантируют, что  состояние конкуренции за ресурсы  не  возникнет. С помощью одной  машинной  инструкции выполняется проверка захвачен  ли  ключ, и,  если  нет, то  этот ключ  захватывается. То,  как  это  делается, очень  сильно  зависит  от аппаратной платформы, но  почти  для  всех  процессоров определяется машинная  инструкция test-andset (проверить и установить), которая позволяет проверить значение целочисленной переменной и присвоить этой  переменной указанное число, если  се значение равно нулю.  Значение нуль  соответствует незахваченной  блокировке.

Откуда берется параллелизм

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

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

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

Отлаженные  прерывания и тасклеты. Ядро  может выполнять обработчики softirq  и  тасклеты практически  в любой  момент   времени и  прерывать код,  который выполняется в данный момент  времени.

Преемптивностъ ядра.  Так  как  ядро  является вытесняемым, то одно  задание,  которое  работает   в  режиме   ядра,  может  вытеснить другое  задание,  тоже  работающее  в  пространстве ядра.

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

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

Симметричная  многопроцессорность.  Два  или  больше процессоров  могут  выполнять  код  в один  и тот же момент времени.

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

Код, который безопасно выполнять параллельно с обработчиком прерывания, называется  безопасным  при  прерываниях  (iterrupt-safe). Код,  который  содержит защиту от  конкурентного доступа  к  ресурсам при  симметричной многопроцессорной обработке, называется безопасным при SMP-обработке (SMP-safe).  Код,  который имеет  защиту  от  конкурентного доступа  к  ресурсам при  вытеснении кода  ядра, называется безопасным при   вытеснения3    (preempt-safe).  Механизмы,  которые во  всех  этих  случаях используются для  обеспечения синхронизации и защиты от состояний конкуренции, будут  рассмотрены в  следующей главе.

Что требует защиты

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

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

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

Что  же тогда требует применения блокировок?  Это — большинство  глобальных структур данных  ядра.  Есть  хорошее  эмпирическое   правило:  если,  кроме  одного, еще  и другой поток  может  обращаться  к данным,  то эти  данные  требуют применения  какого-либо типа блокировок.  Если  что-то  видно  кому-то  еще — блокируйте  его. Помните,  что блокировать  необходимо  данные, а не код.

Параметры КОНФИГУРАЦИИ ядра: SMP или UP

Так как ядро операционной системы Linux может быть сконфигурировано на этапе компиляции, имеет смысл "подогнать"  ядро под данный тип машины. Важной функцией ядра является поддержка симметричной многопроцессорной обработки (SMP), которая включается с помощью параметра конфигурации ядра CONFIG_SMP . На однопроцессорной {uniprocessor, UP) машине исчезают многие проблемы, связанные с блокировками, и, следовательно, если параметр CONFIG_SM P не установлен, то код, в котором нет необходимости, не компилируется в исполняемый образ ядра. Например, это позволяет на однопроцессорной  машине отказаться от накладных расходов, связанных со спин-блокировками.  Аналогичный прием используется для параметра CONFIG_PREEMP T (параметр ядра, который указывает, будет ли ядро вытесняемым). Такое решение является отличным проектным решение, поскольку позволяет использовать общий четкий исходный код, а различные механизмы блокировок используются при необходимости. Различные комбинации  параметров  CONFIG_SM P И CONFIG_PREEMP T на различных аппаратных платформах позволяют компилировать в ядро различные механизмы блокировок.

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

При  написании   кода ядра следует задать себе  следующие вопросы.

• Являются ли данные  глобальными?  Может ли другой поток выполнения,  кроме текущего,  обращаться  к этим  данным?

• Являются  ли данные  совместно  используемыми  из контекста  процесса  и  из контекста  прерывания?   Используют  ли  их совместно  два обработчика  прерываний?

• Если процесс  во время доступа к данным  будет вытеснен,  может ли новый  процесс,  который  запланирован  на выполнение, обращаться  к этим же  данным?

• Может ли текущий  процесс  перейти  в состояние  ожидания  (заблокироваться) на какой-либо операции?  Если да,  то в каком  состоянии  он  оставляет  все совместно  используемые  данные?

• Что  запрещает  освободить  память,  в которой  находятся  данные?

• Что произойдет,  если эта же функция  будет вызвана на другом процессоре?

• Как  все это учесть?

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

Взаимоблокировки

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

Хорошая  аналогия— это  перекресток,  на  котором стоят  четыре  машины,  которые  подъехали  с  четырех  разных   сторон.  Каждая  машина  ожидает,  пока  не  уедут остальные машины,  и  ни  одна  из  машин не  сможет  уехать;  в  результате   получается тупиковая  ситуация.

Самый  простой  пример  взаимоблокировки— это   самоблокировка4     (self-deadlock). Если  поток  выполнения  пытается захватить  ту блокировку,  которую   он  уже  удерживает,  то  ему  необходимо дождаться,  пока  блокировка не  будет  освобождена.  Но  поток  никогда не  освободит блокировку,  потому  что  он  ожидает   на  ее  захват,  и  это приводит к тупиковой ситуации.

захватить блокировку захватить блокировку еще раз

ждать, пока блокировка не будет освобождена

Аналогично рассмотрим n потоков и n блокировок. Если  каждый  поток  удерживает блокировку, на  которую  ожидает  другой  поток, то  все  потоки будут заблокированы до  тех пор, пока  не  освободятся те  блокировки, на  освобождение которых  ожидают потоки.   Наиболее часто  встречающийся пример — это два потока  и две блокировки, что  часто  называется  взаимоблокировка типа  ABBA  (ABBA deadlock).

Поток   1                                                                     Поток  2

захватить блокировку А              захватить блокировку В

попытка захватить блокировку В      попытка захватить блокировку А

ожидание освобождения блокировки В   ожидание освобождения блокировки А

Оба  потока  будут ожидать  друг друга, и  ни  один  из  потоков никогда не  освободит первоначально захваченной блокировки,  поэтому  ни  одна  из  блокировок не  будет освобождена.  Такая  тупиковая  ситуация еще  называется  deadly  embrace  (буквально. смертельные  объятия).

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

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

4  Б некоторых ядрах такой  ти п тупиковой ситуации предотвращается с помощью рекурсивных блокировок, которы е позволяют одному  потоку  выполнени я захватывать  блокировку несколько раз. В операционно й системе  Linux,  к счастью,   таких  блокирово к нет.  И  эт о считаетс я хороши м тоном.  Хотя рекурсивные блокировки позволяют избежать  проблемы самоблокировок, они  приводят к небрежному использованию блокировок.

• Необходимо предотвращать зависания.  Следует  спросить себя:   "Всегда ли  этот код сможет завершиться’?”’.  Если  не  выполнится какое-либо условие, то не  будет ли  что-то   ожидать  вечно?

• Не  захватывать одну  и  ту же  блокировку дважды.

• Сложность в схеме  блокировок  — верный путь  к тупиковым ситуациям,  поэтому при  разработке необходимо стремиться к простоте.

Первый пункт  важный и  наименее  сложный для  выполнения. Если  две  или  более  блокировок захватываются в одном  месте, то  они  всегда должны  захватываться в строго  определенном порядке.  Допустим, у нас  есть  три  блокировки cat , dog  и  fox, которые  используются для  защиты данных  с  такими же  именами.  И  еще  допустим, что у нас  есть функция,  которая должна  работать  с  этими  тремя  структурами данных одновременно— например,  может  копировать данные между  ними. Б  любом  случае, для  того  чтобы  гарантировать безопасность доступа,  эти  структуры   данных   необходимо  защищать блокировками.  Если  одна  функция  захватывает эти  блокировки   в следующем порядке:  cat , dog  и  в  конце   fox, то  любая другая  функция должна  захватывать  эти  блокировки (или  только  некоторые из  них)  в том  же порядке. Например, если  захватывать  сначала   блокировку  fox , а  потом   блокировку dog , то  это  потенциальная возможность взаимоблокировки  (а значит,  ошибки   в работе), потому  что блокировка dog  всегда  должна  захватываться перед  блокировкой fox.  И  еще  раз  рассмотрим пример,  как  может  возникнуть взаимоблокировка.

Поток   1                                                                    Поток  2

захватить блокировку cat           захватить блокировку fox захватить блокировку dog           попытка захватить блокировку dog попытка захватить блокировку fox   ожидание освобождения блокировки dog ожидание освобождения блокировки fox  —

Поток   1  ожидает   освобождения блокировки  fox ,  которую  удерживает   поток    2, а  поток    2  в это  время  ожидает  освобождения  блокировки  dog, которую  удерживает поток    1.  Ни  один  из  потоков никогда не  освободит своих  блокировок, и,  соответственно, оба потока  будут ждать  вечно  — возникает тупиковая ситуация. Если  оба потока  всегда  захватывают блокировки  в одном  и том  же  порядке, то  подобной тупиковой  ситуации возникнуть не  может.

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

/*

* cat_lock всегда захватывать перед блокировкой dog

* (и всегда захватывать блокировку dog перед блокировкой fox)

*/

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

Очень  важно  предотвращать взаимоблокировки.  В ядре  Linux  есть  некоторые отладочные возможности,  которые  позволяют  обнаруживать взаимоблокировки  при выполнении кода  ядра.  Эти  возможности будут  рассмотрены в  следующем разделе.

Источник: Лав,  Роберт. Разработка ядра  Linux, 2-е  издание. : Пер.  с англ.  — М.  : ООО  «И.Д.  Вильяме» 2006. — 448 с. : ил. — Парал. тит. англ.

По теме:

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