Второе издание
 Скачать 3.09 Mb.
|
|
Поток 1 Поток 2 получить значение i из памяти (7) увеличить i на 1 <7->8) записать значение i в память (8) получить значение i из памяти (8) увеличить i на 1 (8->9) записать значение i в память (9) Как и ожидалось, значение переменной ±, равное 7, было увеличено на единицу два раза и стало равно 9. Однако возможен и другой вариант. Поток 1 Поток 2 получить значение i из памяти (7) получить значение i из памяти (7) увеличить i на 1 (7->8) увеличить i на 1 (7->8) записать значение i в память (8) записать значение i в память (8) Если оба потока выполнения прочитают первоначальное значение переменной i перед тем, как оно было увеличено на 1, то оба потока увеличат его на единицу и запишут в память одно и то же значение. В результате переменная i будет содержать значение 8, тогда как она должна содержать значение 9. Это один из самых простых примеров критических участков. К счастью, решение этой проблемы простое — необ- ходимо просто обеспечить возможность выполнения всех рассмотренных операций за один неделимый шаг. Для большинства процессоров есть машинная инструкция, которая позволяет атомарно считать данные из памяти, увеличить их значение на 1 166 Глава Ясно, что финансовые учреждения считают своим долгом гарантировать, чтобы такой ситуации не могло возникнуть никогда. Необходимо блокировать счет во вре- мя выполнения некоторых операций, чтобы гарантировать атомарность транзакций по отношению к другим транзакциям. Такие транзакции должны полностью выпол- няться не прерываясь или не выполняться совсем. Общая переменная Теперь рассмотрим пример, связанный с компьютерами. Пусть у нас есть очень простой совместно используемый ресурс: одна глобальная целочисленная перемен- ная и очень простой критический участок — операция инкремента значения этой переменной: i++ и записать обратно в память, выделенную для переменной. Использование такой ин- струкции позволяет решить проблему. Возможно только два варианта правильного выполнения этого кода — следующий. Поток 1 Поток 2 \ увеличить i на 1 (7->8) увеличить i на 1 (8->9) Или таким образом. Поток 1 Поток 2 увеличить i на 1 (7->8) увеличить i на 1 (8->9) Две атомарные операции никогда не могут перекрываться. Процессор на физи- ческом уровне гарантирует это. Использование такой инструкции решает проблему. Ядро предоставляет несколько интерфейсов, которые позволяют реализовать ато- марные операции. Эти интерфейсы будут рассмотрены в следующей главе. Блокировки Теперь давайте рассмотрим более сложный пример конкуренции за ресурсы, ко- торый требует более сложного решения. Допустим, что у нас есть очередь запросов, которые должны быть обработаны. Как реализована очередь — не существенно, но мы будем считать, что это — связанный список, в котором каждый узел соответствует одному запросу. Очередью управляют две функции: одна— добавляет новый запрос в конец очереди, а другая — извлекает запрос из головы очереди и делает с ним не- что полезное. Различные части ядра вызывают обе эти функции, поэтому запросы могут постоянно поступать, удаляться и обрабатываться. Все манипуляции очередью запросов, конечно, требуют нескольких инструкций. Если один из потоков пытается считывать данные из очереди, а другой поток находится в средине процесса манипу- ляции очередью, то считывающий поток обнаружит, что очередь находится в несо- гласованном состоянии. Легко понять, что при конкурентном обращении к очереди может произойти разрушение структуры данных. Часто ресурс общего доступа — это сложная структура данных, и в результате состояния конкуренции возникает разру- шение этой структуры. Вначале кажется, что описанная ситуация не имеет простого решения. Как можно предотвратить чтение очереди на одном процессоре в тот момент, когда другой про- цессор обновляет ее? Вполне логично аппаратно реализовать простые инструкции, такие как атомарные арифметические операции или операции сравнения, тем не менее было бы смешно аппаратно реализовывать критические участки неопределен- ного размера, как в приведенном примере. Все что нужно — это предоставить метод, который позволяет отметить начало и конец; критического участка, и предотвратить или заблокировать (lock) доступ к этому участку, пока другой поток выполняет его. Блокировки (lock) предоставляют такой механизм. Он работает почти так же, как и дверной замок. Представим, что комната, которая находится за дверью, — это кри- тический участок. Внутри комнаты в любой момент времени может присутствовать только один поток выполнения. Когда поток входит в комнату, он запирает за собой дверь. Когда поток заканчивает манипуляции с совместно используемыми данными, он выходит из комнаты, отпирая дверь перед выходом. Если другой поток подхо- Введение в синхронизацию выполнения кода ядра 167 дит к двери, когда она заперта, то он должен ждать, пока поток, который находится внутри комнаты, не отопрет дверь и не выйдет. Потоки удерживают блокировки, а блокировки защищают данные. В приведенном выше примере очереди запросов для защиты очереди может ис- пользоваться одна блокировка. Как только необходимо добавить запрос в очередь, поток должен вначале захватить блокировку. Затем он может безопасно добавить запрос в очередь и после этого освободить блокировку. Если потоку необходимо извлечь запрос из очереди, он тоже должен захватить блокировку. После этого он может прочитать запрос и удалить его из очереди. В конце поток освобождает блокировку. Любому другому потоку для доступа к очереди также необходимо ана- логичным образом захватывать блокировку. Так как захваченная блокировка может удерживаться только одним потоком в любой момент времени, то только один поток может производить манипуляции с очередью в любой момент времени. Блокировка позволяет предотвратить конкуренцию и защитить очередь от состояния конкурен- ции за ресурс. Код, которому необходимо получить доступ к очереди, должен захватить соот- ветствующую блокировку. Если неожиданно появляется другой поток выполнения, то это позволяет предотвратить конкуренцию. Поток 1 Поток 2 Попытаться заблокировать очередь Попытаться заблокировать очередь успешно: блокировка захвачена неудачно: ожидаем... ожидаем... обратиться к очереди... ожидаем... разблокировать очередь успешно: блокировка захвачена обратиться к очереди.,. разблокировать очередь Заметим, что блокировки бывают необязательными (рекомендуемыми, advisory) и обязательными (навязываемыми, voluntary). Блокировки— это чисто программные конструкции, преимуществами которых должны пользоваться программисты. Никто не запрещает писать код, который манипулирует нашей воображаемой очередью без использования блокировок. Однако такая практика в конечном итоге приведет к со- стоянию конкуренции за ресурс и разрушению данных. Блокировки бывают различных "форм" и "размеров". В операционной системе Linux реализовано несколько различных механизмов блокировок. Наиболее суще- ственная разница между ними — это поведение кода в условиях, когда блокировка захватываетя (конфликт при захвате блокировки, contended lock). Для некоторых типов блокировок, задания просто ожидают освобождения блокировки, постоянно выполняя проверку освобождения в замкнутом цикле (busy wait 2 ), в то время как дру- гие тины блокировок переводят задание в состояние ожидания до тех пор, пока бло- кировка не освободится. 2 Иными словами, "вращаются" (spin) в замкнутом цикле, ожидая на освобождение блокировки. 168 Глава 8 В следующей главе рассказывается о том, как ведут себя различные типы блоки- ровок в операционной системе Linux, и об интерфейсах взаимодействия с этими блокировками. Проницательный читатель в этом месте должен воскликнуть: "Блокировки не ре- шают проблемы, они просто сужают набор всех возможных критических участков до кода захвата и освобождения блокировок. Тем не менее, здесь потенциально может возникать состояние конкуренции за ресурсы, хотя и с меньшими последствиями!" К счастью, блокировки реализованы на основе атомарных операций, которые гаран- тируют, что состояние конкуренции за ресурсы не возникнет. С помощью одной ма- шинной инструкции выполняется проверка захвачен ли ключ, и, если нет, то этот ключ захватывается. То, как это делается, очень сильно зависит от аппаратной плат- формы, но почти для всех процессоров определяется машинная инструкция test-and- set (проверить и установить), которая позволяет проверить значение целочисленной переменной и присвоить этой переменной указанное число, если се значение равно нулю. Значение нуль соответствует незахваченной блокировке. Откуда берется параллелизм При работе в пространстве пользователя необходимость синхронизации возни- кает из того факта, что программы выполняются преемптивно, т.е. могут быть вы- теснены другой программой по воле планировщика. Поскольку процесс может быть вытеснен в любой момент и другой процесс может быть запущен планировщиком для выполнения на этом же процессоре, появляется возможность того, что процесс может быть вытеснен независящим от него образом во время выполнения критиче- ского участка. Если новый, запланированный на выполнение процесс входит в тот же критический участок (скажем, если оба процесса — потоки одной программы, ко- торые могут обращаться к общей памяти), то может возникнуть состояние конкурен- ции за ресурс. Аналогичная проблема может возникнуть даже в однопоточной про- грамме при использовании сигналов, так как сигналы приходят асинхронно. Такой тип параллелизма, когда два события происходят не одновременно, а накладываются друг на друга, так вроде они происходят в один момент времени, называется псевдо- параллелизмом (pseudo-concurrency). На машине с симметричной многопроцессорностью два процесса могут действи- тельно выполнять критические участки в один и тот же момент времени. Это назы- вается истинным, параллелизмом (true concurrency). Хотя причины и семантика истин- ного и псевдопараллелизма разные, они могут приводить к совершенно одинаковым состояниям конкуренции и требуют аналогичных средств защиты. В ядре причины параллельного выполнения кода следующие. • Прерывания. Прерывания могут возникать асинхронно, практически в любой момент времени, прерывая код, который выполняется в данный момент. • Отлаженные прерывания и тасклеты. Ядро может выполнять обработчики softirq и тасклеты практически в любой момент времени и прерывать код, который выполняется в данный момент времени. • Преемптивностъ ядра. Так как ядро является вытесняемым, то одно задание, ко- торое работает в режиме ядра, может вытеснить другое задание, тоже работа- ющее в пространстве ядра. Введение в синхронизацию выполнения кода ядра 169 • Переход в состояние ожидания и синхронизация с пространством пользователя. Задание, работающее в пространстве ядра, может переходить в состояние ожида- ния, что вызывает активизацию планировщика и выполнение нового процесса. • Симметричная многопроцессорность. Два или больше процессоров могут выпол- нять код в один и тот же момент времени. Важно, что разработчики ядра поняли все причины и подготовились к возмож- ным случаям параллелизма. Если прерывание возникает во время выполнения кода, который работает с некоторым ресурсом, и обработчик прерывания тоже обращает- ся к этому же ресурсу, то это является ошибкой. Аналогично ошибкой является и то, что код ядра вытесняется в тот момент, когда он обращается к совместно использу- емому ресурсу. Переход в состояние ожидания во время выполнения критического участка в ядре открывает большой простор для состояний конкуренции за ресурсы. И наконец, два процессора никогда не должны одновременно обращаться к совмест- но используемым данным. Когда ясно, какие данные требуют защиты, то уже нетруд- но применить соответствующие блокировки, чтобы обеспечить всем безопасность. Сложнее идентифицировать возможные условия возникновения таких ситуаций и определить, что для предотвращения конкуренции необходима та или иная форма защиты. Давайте еще раз пройдем через этот момент, потому что он очень важен. Применить блокировки в коде для того, чтобы защитить совместно используемые данные, — это не тяжело, особенно если это делается на самых ранних этапах разра- ботки кода. Сложность состоит в том, чтобы найти эти самые совместно используе- мые данные и эти самые критические участки. Именно поэтому требование аккурат- ного использования блокировок с самого начала разработки кода — а не когда-нибудь потом — имеет первостепенную важность. Постфактум очень сложно отследить, что необходимо блокировать, и правильно внести изменения в существующий код. Результаты подобной разработки обычно не очень хорошие. Мораль — всегда нужно аккуратно учитывать необходимость применения блокировок с самого начала про- цесса разработки кода. Код, который безопасно выполнять параллельно с обработчиком прерывания, на- зывается безопасным при прерываниях (iterrupt-safe). Код, который содержит защиту от конкурентного доступа к ресурсам при симметричной многопроцессорной обра- ботке, называется безопасным при SMP-обработке (SMP-safe). Код, который имеет за- щиту от конкурентного доступа к ресурсам при вытеснении кода ядра, называется безопасным при вытеснения 3 (preempt-safe). Механизмы, которые во всех этих случаях используются для обеспечения синхронизации и защиты от состояний конкуренции, будут рассмотрены в следующей главе. Что требует защиты Жизненно важно определить, какие данные требуют защиты. Так как любой код, который может выполняться параллельно, может потребовать защиты. Вероятно, легче определить, какие данные не требуют защиты, и работать дальше, отталкива- ясь от этого. Очевидно, что все данные, которые доступны только одному потоку выполнения, не требуют защиты, поскольку только этот поток может обращаться к 3 Дальше будет показано, что, за некоторыми исключениями, код, который безопасен при SMP-об- работке, также безопасен и при вытеснениях. 170 Глава 8 этим данным. Например, локальные переменные, которые выделяются в автомати- ческой памяти (и те, которые находятся в динамически выделяемой памяти, если их адреса хранятся только в стеке), не требуют никаких блокировок, так как они су- ществуют только в стеке выполняющегося потока. Точно так же данные, к которым обращается только одно задание, не требуют применения блокировок (так как один поток может выполняться только на одном процессоре в любой момент времени). Что же тогда требует применения блокировок? Это — большинство глобальных структур данных ядра. Есть хорошее эмпирическое правило: если, кроме одного, еще и другой поток может обращаться к данным, то эти данные требуют примене- ния какого-либо типа блокировок. Если что-то видно кому-то еще — блокируйте его. Помните, что блокировать необходимо данные, а не код. Параметры КОНФИГУРАЦИИ ядра: SMP или UP Так как ядро операционной системы Linux может быть сконфигурировано на этапе компиляции, имеет смысл "подогнать" ядро под данный тип машины. Важной функцией ядра является под- держка симметричной многопроцессорной обработки (SMP), которая включается с помощью параметра конфигурации ядра C O N F I G _ S M P . На однопроцессорной {uniprocessor, UP) маши- не исчезают многие проблемы, связанные с блокировками, и, следовательно, если параметр CONFIG_SMP не установлен, то код, в котором нет необходимости, не компилируется в испол- няемый образ ядра. Например, это позволяет на однопроцессорной машине отказаться от на- кладных расходов, связанных со спин-блокировками. Аналогичный прием используется для па- раметра C O N F I G _ P R E E M P T (параметр ядра, который указывает, будет ли ядро вытесняемым). Такое решение является отличным проектным решение, поскольку позволяет использовать общий четкий исходный код, а различные механизмы блокировок используются при необхо- димости. Различные комбинации параметров C O N F I G _ S M P И C O N F I G _ P R E E M P T на различных аппаратных платформах позволяют компилировать в ядро различные механизмы блокировок. При написании кода необходимо обеспечить все возможные варианты защиты для всех воз- можных случаев жизни и всех возможных сценариев, которые будут рассмотрены. При написании кода ядра следует задать себе следующие вопросы. • Являются ли данные глобальными? Может ли другой поток выполнения, кроме текущего, обращаться к этим данным? • Являются ли данные совместно используемыми из контекста процесса и из контекста прерывания? Используют ли их совместно два обработчика преры- ваний? • Если процесс во время доступа к данным будет вытеснен, может ли новый про- цесс, который запланирован на выполнение, обращаться к этим же данным? • Может ли текущий процесс перейти в состояние ожидания (заблокироваться) на какой-либо операции? Если да, то в каком состоянии он оставляет все со- вместно используемые данные? • Что запрещает освободить память, в которой находятся данные? • Что произойдет, если эта же функция будет вызвана на другом процессоре? • Как все это учесть? Если коротко, то почти все глобальные данные требуют применения тех или дру- гих методов синхронизации, которые будут рассмотрены в следующей главе. Введение в синхронизацию выполнения кода ядра 1 7 1 Взаимоблокировки Взаимоблокировка (тупиковая ситуация, deadlock) — это состояние, при котором каждый поток ожидает на освобождение одного из ресурсов, а все ресурсы при этом захвачены. Потоки будут ожидать друг друга, и они никогда не смогут освободить захваченные ресурсы. Поэтому ни один из потоков не сможет продолжать выполне- ние, что означает наличие взаимоблокировки. Хорошая аналогия— это перекресток, на котором стоят четыре машины, кото- рые подъехали с четырех разных сторон. Каждая машина ожидает, пока не уедут остальные машины, и ни одна из машин не сможет уехать; в результате получается тупиковая ситуация. Самый простой пример взаимоблокировки— это самоблокировка 4 (self-deadlock). Если поток выполнения пытается захватить ту блокировку, которую он уже удержи- вает, то ему необходимо дождаться, пока блокировка не будет освобождена. Но по- ток никогда не освободит блокировку, потому что он ожидает на ее захват, и это приводит к тупиковой ситуации. захватить блокировку захватить блокировку еще раз ждать, пока блокировка не будет освобождена Аналогично рассмотрим n потоков и n блокировок. Если каждый поток удержива- ет блокировку, на которую ожидает другой поток, то все потоки будут заблокированы до тех пор, пока не освободятся те блокировки, на освобождение которых ожидают потоки. Наиболее часто встречающийся пример — это два потока и две блокировки, что часто называется взаимоблокировка типа ABBA (ABBA deadlock). |