Роберт Лав - Разработка ядра Linux
Зачем нужна защита
Для лучшего понимания того, к чему может привести состояние конкуренции, давайте рассмотрим примеры повсеместно встречающихся критических участков.
В качестве первого примера рассмотрим ситуацию из реальной жизни; банкомат (который еще называют ATM, Automated Teller Machine, или кэш-машиной).
Одно из наиболее часто встречающихся действий, которые приходится выполнять с помощью банкомата — это снятие денег с персонального банковского счета физического лица. Человек подходит к банкомату, вставляет карточку, вводит PIN-код, проходит аутентификацию, выбирает пункт меню Снятие наличных, вводит необходимую сумму, нажимает OK, забирает деньги и отправляет их автору этой книги.
После того как пользователь ввел необходимую сумму, банкомат должен проверить, что такая сумма действительно есть на счету. Если такие деньги есть, то необходимо вычесть снимаемую сумму из общего количества доступных денег. Код, который выполняет эту операцию, может выглядеть следующим образом.
int total = get_total_from_account(); /* общее количество денег на счету */
int withdrawal = get_withdrawal_amount(); /* количество денег,
которые хотят снять */
/* проверить, есть ли у пользователя деньги на счету */
if (total < withdrawal)
error("У Вас нет таких денег!");
/* Да, у пользователя достаточно денег: вычесть снимаемую сумму из
общего количества денег на счету */
total -= withdrawal;
update_total_funds(total);
/* Выдать пользователю деньги */
spit_out_money(withdrawal);
Теперь представим, что в тот же самый момент времени со счета этого же пользователя снимается еще одна сумма денег. Не имеет значения, каким образом выполняется снятие второй суммы. Например, или супруг пользователя снимает деньги с другого банкомата, или кто-то переводит со счета деньги электронным платежом, или банк снимает со счета в качестве платы за что-то (как это обычно любят делать банки), или происходит что-либо еще.
Обе системы, которые снимают деньги со счета, выполняют код, аналогичный только что рассмотренному: проверяется, что снятие денег возможно, после этого вычисляется новая сумма денег на счету и, наконец, деньги снимаются физически. Теперь рассмотрим некоторые численные значения. Допустим, что первая снимаемая сумма равна $100, а вторая — $10, например, за то, что пользователь зашел в банк (что не приветствуется: необходимо использовать банкомат, так как в банках людей не хотят видеть). Допустим также, что у пользователя на счету есть сумма, равная $105. Очевидно, что одна из этих двух транзакций не может завершиться успешно без получения минусов на счету.
Можно ожидать, что получится что-нибудь вроде следующего: первой завершится транзакция по снятию платы за вход в банк. Десять долларов — это меньше чем $105, поэтому, если от $105 отнять $10, на счету останется $95, а $10 заработает банк. Далее начнет выполняться снятие денег через банкомат, но оно завершится неудачно, так как $95 — это меньше чем $100.
Тем не менее жизнь может оказаться значительно интереснее, чем ожидалось. Допустим, что две указанные выше транзакции начинаются почти в один и тот же момент времени. Обе транзакции убеждаются, что на счету достаточно денег: $105 — это больше $100 и больше $10. После этого процесс снятия денег с банкомата вычтет $100 из $105 и получится $5. В это же время процесс снятия платы за вход сделает то же самое и вычтет $10 из $105, и получится $95. Далее процесс снятия денег обновит состояние счета пользователя: на счету окажется сумма $5. В конце транзакция снятия платы за вход также обновит состояние счета, и на счету окажется $95. Получаем деньги в подарок!
Ясно, что финансовые учреждения считают своим долгом гарантировать, чтобы такой ситуации не могло возникнуть никогда. Необходимо блокировать счет во время выполнения некоторых операций, чтобы гарантировать атомарность транзакций по отношению к другим транзакциям. Такие транзакции должны полностью выполняться не прерываясь или не выполняться совсем.
Общая переменнаяТеперь рассмотрим пример, связанный с компьютерами. Пусть у нас есть очень простой совместно используемый ресурс: одна глобальная целочисленная переменная и очень простой критический участок — операция инкремента значения этой переменной:
i++
Это выражение можно перевести в инструкции процессора следующим образом.
Загрузить текущее значение переменной i из памяти в регистр.
Добавить единицу к значению, которое находится в регистре.
Записать новое значение переменной i обратно в память.
Теперь предположим, что есть два потока, которые одновременно выполняют этот критический участок, и начальное значение переменной i равно 7. Результат выполнения будет примерно следующим (каждая строка соответствует одному интервалу времени ).
Поток 1 Поток 2
получить значение i из памяти (7) -
увеличить i на 1 (7->8) -
записать значение i в память (8) -
- получить значение i из памяти (8)
- увеличить i на 1 (8->9)
- записать значение i в память (9)
Как и ожидалось, значение переменной i, равное 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 и записать обратно в память, выделенную для переменной. Использование такой инструкции позволяет решить проблему. Возможно только два варианта правильного выполнения этого кода — следующий.
Поток 1 Поток 2
увеличить i на 1 (7->8) -
- увеличить i на 1 (8->9)
Или таким образом.
Поток 1 Поток 2
- увеличить i на 1 (7->8)
увеличить i на 1 (8->9) -
Две атомарные операции никогда не могут перекрываться. Процессор на физическом уровне гарантирует это. Использование такой инструкции решает проблему. Ядро предоставляет несколько интерфейсов, которые позволяют реализовать атомарные операции. Эти интерфейсы будут рассмотрены в следующей главе.
Блокировки
Теперь давайте рассмотрим более сложный пример конкуренции за ресурсы, который требует более сложного решения. Допустим, что у нас есть очередь запросов, которые должны быть обработаны. Как реализована очередь — не существенно, но мы будем считать, что это — связанный список, в котором каждый узел соответствует одному запросу. Очередью управляют две функции: одна— добавляет новый запрос в конец очереди, а другая — извлекает запрос из головы очереди и делает с ним нечто полезное. Различные части ядра вызывают обе эти функции, поэтому запросы могут постоянно поступать, удаляться и обрабатываться. Все манипуляции очередью запросов, конечно, требуют нескольких инструкций. Если один из потоков пытается считывать данные из очереди, а другой поток находится в средине процесса манипуляции очередью, то считывающий поток обнаружит, что очередь находится в несогласованном состоянии. Легко понять, что при конкурентном обращении к очереди может произойти разрушение структуры данных. Часто ресурс общего доступа — это сложная структура данных, и в результате состояния конкуренции возникает разрушение этой структуры.
