Теория операционных систем
Формулировка задачи
| Я что-то не вижу пивного ларька. Должно быть, его Успели снести за ночь. Б. Гребенщиков |
Чтобы понять, какие же методики применимы для взаимодействия параллельно
исполняющихся нитей, давайте более четко сформулируем задачу. Для этого
нам также надо ввести некоторое количество терминов. Кроме того, нам придется
высказать ряд соображений, часть которых может показаться читателю банальностями.
Установим, что для каждой из нитей создается иллюзия строго последовательного
исполнения (например, обработчик прерывания может создать для основного
потока программы такую иллюзию, аккуратно сохраняя при вызове и восстанавливая
при завершении все регистры процессора). Если для какой-то из нитей это
условие не всегда соблюдается, мы будем считать ее двумя или большим числом различных нитей. Если это условие не соблюдается никогда, мы имеем дело с процессором нефон-неймановской архитектуры.
Общепринятое название для взаимодействия между различными нитями — асинхронное взаимодействие, в противоположность синхронному взаимодействию между различными модулями последовательно исполняемой программы.
Если нить работает только с объектами (под объектом мы, в данном случае, понимаем не только группу переменных в оперативной памяти или объект в смысле ООП, но и физические объекты, например управляемые компьютером внешние устройства), состояние которых не может быть изменено другими нитями, проблемы взаимодействия, да и самого взаимодействия, как такового, не существует.
Если нить работает с объектами, состояние которых вообще не подвергается модификации, например, с кодом или таблицами констант, проблемы также нет. Проблема возникает тогда и только тогда, когда модификации подвергается объект, разделяемый несколькими нитями. При этом для возникновения проблемы достаточно, чтобы только одна нить занималась модификацией, а остальные нити считывали состояние объекта.
Интервал, в течение которого модификация нарушает целостность разделяемой структуры данных, и, наоборот, интервал, в течение которого алгоритм нити полагается на целостность этой структуры, называется критической секцией. Задача написания корректной многопоточной программы, таким образом, может решаться двумя способами: либо искоренением критических секций из всех используемых алгоритмов, либо обеспечением гарантии того, что никакие две нити никогда одновременно не войдут в критическую секцию, связанную с одним и тем же разделяемым объектом. Наличие в программе критической секции с негарантированным исключением и есть ошибка соревнования, которая рано или поздно сработает.
Полное искоренение критических секций из кода требует глубокой переработки всех алгоритмов, которые используются для работы с разделяемыми данными. Результат такой переработки мы видели в примере 5.2: странная, на первый взгляд, двойная загрузка регистра в настроенной записи PLT в этом примере обусловлена именно желанием избежать проблем при параллельной настройке одной и той же записи двумя разными нитями (в качестве упражнения читателю предлагается разобраться, в каком порядке интерпретатор модифицирует запись, и как выглядит промежуточный код). У автора нет примеров, демонстрирующих невозможность такой переработки в обшем случае, но очевидно, что даже к крайне простым алгоритмам она совершенно не применима на практике.
Второй путь — предоставление гарантий взаимоисключения (mutual exclusion) — также непрост, но, в отличие от первого, практически реализуем и широко применяется.
Примечание
Важно подчеркнуть, что сокращение времени, которое каждая из нитей проводит
в критических секциях, хотя и полезно, со многих точек зрения, в частности
с точки зрения улучшения масштабируемости алгоритма, само по себе оно
проблемы решить не может. Без гарантии взаимоисключения, сокращение критического
времени лишь понижает вероятность срабатывания ошибки соревнования (и,
в частности, затрудняет поиск такой ошибки при тестировании), но не исправляет
эту ошибку.
Группа операций модификации разделяемой структуры данных, которая происходит атомарно (неделимо), не прерываясь никакими другими операциями с той же структурой данных, называется транзакцией. В разд.
