Разработка ядра Linux

Можно ожидать, что получится что-нибудь вроде следующего: первой завершится транзакция по снятию платы за вход в банк. Десять долларов — это меньше чем $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