The design of the UNIX Operating System 24 страница
Итак, для решения задачи необходимо, чтобы в том случае, когда процесс находится в своем критиче-ском участке, другие процессы не могли войти в свои критические участки. Мы видим, что критический участок должен сопровождаться прологом (entry section) – "закрыть дверь изнутри на засов" – и эпилогом (exit section) – "отодвинуть засов", которые не имеют отношения к активности одиночного процесса. Во время выполнения пролога процесс должен, в частности, получить разрешение на вход в критический участок, а во время выполнения эпилога – сообщить другим процессам, что он покинул критическую секцию.
|
|
|
В общем случае структура процесса, участвующего во взаимодействии, может быть представлена сле-дующим образом:
while (some condition) { entry section
critical section exit section
remainder section
}
Здесь под remainder section понимаются все атомарные операции, не входящие в критическую секцию.
|
|
|
Оставшаяся часть этой лекции посвящена различным способам программной организации пролога и эпи-лога критического участка в случае, когда очередность доступа к критическому участку не имеет значе-ния.
Программные алгоритмы организации взаимодействия процессов
Требования, предъявляемые к алгоритмам
Организация взаимоисключения для критических участков, конечно, позволит избежать возникновения race condition, но не является достаточной для правильной и эффективной параллельной работы коопера-тивных процессов. Сформулируем пять условий, которые должны выполняться для хорошего программ-ного алгоритма организации взаимодействия процессов, имеющих критические участки, если они могут проходить их в произвольном порядке.
|
|
|
|
|
|
1. Задача должна быть решена чисто программным способом на обычной машине, не имеющей спе-циальных команд взаимоисключения. При этом предполагается, что основные инструкции языка
| Основы операционных систем | 53 |
программирования (такие примитивные инструкции, как load, store, test) являются атомарными операциями.
2. Не должно существовать никаких предположений об относительных скоростях выполняющихся процессов или числе процессоров, на которых они исполняются.
3. Если процесс Pi исполняется в своем критическом участке, то не существует никаких других про-цессов, которые исполняются в соответствующих критических секциях. Это условие получило на-звание условия взаимоисключения (mutual exclusion).
4. Процессы, которые находятся вне своих критических участков и не собираются входить в них, не могут препятствовать другим процессам входить в их собственные критические участки. Если нет процессов в критических секциях и имеются процессы, желающие войти в них, то только те про-цессы, которые не исполняются в remainder section, должны принимать решение о том, какой про-цесс войдет в свою критическую секцию. Такое решение не должно приниматься бесконечно дол-го. Это условие получило название условия прогресса (progress).
5. Не должно возникать неограниченно долгого ожидания для входа одного из процессов в свой кри-тический участок. От того момента, когда процесс запросил разрешение на вход в критическую секцию, и до того момента, когда он это разрешение получил, другие процессы могут пройти че-рез свои критические участки лишь ограниченное число раз. Это условие получило название ус-ловия ограниченного ожидания (bound waiting).
Надо заметить, что описание соответствующего алгоритма в нашем случае означает описание способа организации пролога и эпилога для критической секции.
Дата добавления: 2021-01-21; просмотров: 132; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!