Теперь рассмотрим пример, связанный с компьютерами. Пусть у нас есть очень простой совместно используемый ресурс: одна глобальная целочисленная переменная и очень простой критический участок — операция инкремента значения этой переменной:
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) -
Две атомарные операции никогда не могут перекрываться. Процессор на физическом уровне гарантирует это. Использование такой инструкции решает проблему. Ядро предоставляет несколько интерфейсов, которые позволяют реализовать атомарные операции. Эти интерфейсы будут рассмотрены в следующей главе.
Блокировки
Теперь давайте рассмотрим более сложный пример конкуренции за ресурсы, который требует более сложного решения. Допустим, что у нас есть очередь запросов, которые должны быть обработаны. Как реализована очередь — не существенно, но мы будем считать, что это — связанный список, в котором каждый узел соответствует одному запросу. Очередью управляют две функции: одна— добавляет новый запрос в конец очереди, а другая — извлекает запрос из головы очереди и делает с ним нечто полезное. Различные части ядра вызывают обе эти функции, поэтому запросы могут постоянно поступать, удаляться и обрабатываться. Все манипуляции очередью запросов, конечно, требуют нескольких инструкций. Если один из потоков пытается считывать данные из очереди, а другой поток находится в средине процесса манипуляции очередью, то считывающий поток обнаружит, что очередь находится в несогласованном состоянии. Легко понять, что при конкурентном обращении к очереди может произойти разрушение структуры данных. Часто ресурс общего доступа — это сложная структура данных, и в результате состояния конкуренции возникает разрушение этой структуры.
Вначале кажется, что описанная ситуация не имеет простого решения. Как можно предотвратить чтение очереди на одном процессоре в тот момент, когда другой процессор обновляет ее? Вполне логично аппаратно реализовать простые инструкции, такие как атомарные арифметические операции или операции сравнения, тем не менее было бы смешно аппаратно реализовывать критические участки неопределенного размера, как в приведенном примере. Все что нужно — это предоставить метод, который позволяет отметить начало и конец; критического участка, и предотвратить или заблокировать (lock) доступ к этому участку, пока другой поток выполняет его.
Блокировки (lock) предоставляют такой механизм. Он работает почти так же, как и дверной замок. Представим, что комната, которая находится за дверью, — это критический участок. Внутри комнаты в любой момент времени может присутствовать только один поток выполнения. Когда поток входит в комнату, он запирает за собой дверь. Когда поток заканчивает манипуляции с совместно используемыми данными, он выходит из комнаты, отпирая дверь перед выходом. Если другой поток подходит к двери, когда она заперта, то он должен ждать, пока поток, который находится внутри комнаты, не отопрет дверь и не выйдет. Потоки удерживают блокировки, а блокировки защищают данные.
В приведенном выше примере очереди запросов для защиты очереди может использоваться одна блокировка. Как только необходимо добавить запрос в очередь, поток должен вначале захватить блокировку. Затем он может безопасно добавить запрос в очередь и после этого освободить блокировку. Если потоку необходимо извлечь запрос из очереди, он тоже должен захватить блокировку. После этого он может прочитать запрос и удалить его из очереди. В конце поток освобождает блокировку. Любому другому потоку для доступа к очереди также необходимо аналогичным образом захватывать блокировку. Так как захваченная блокировка может удерживаться только одним потоком в любой момент времени, то только один поток может производить манипуляции с очередью в любой момент времени. Блокировка позволяет предотвратить конкуренцию и защитить очередь от состояния конкуренции за ресурс.
Код, которому необходимо получить доступ к очереди, должен захватить соответствующую блокировку. Если неожиданно появляется другой поток выполнения, то это позволяет предотвратить конкуренцию.
Поток 1 Поток 2
Попытаться заблокировать очередь попытаться заблокировать очередь
успешно: блокировка захвачена неудачно: ожидаем...