The design of the UNIX Operating System 22 страница
Введем наборы входных и выходных переменных программы. Для каждой атомарной операции наборы входных и выходных переменных – это наборы переменных, которые атомарная операция считывает и записывает. Набор входных переменных программы R(P) (R от слова read) суть объединение наборов входных переменных для всех ее неделимых действий. Аналогично, набор выходных переменных про-граммы W(P) (W от слова write) суть объединение наборов выходных переменных для всех ее неделимых действий. Например, для программы
|
|
|
P: x=u+v
y=x*w
получаем R(P) = {u, v, x, w}, W(P) = {x, y}. Заметим, что переменная x присутствует как в R(P), так и в
W(P).
Теперь сформулируем условия Бернстайна.
Если для двух данных активностей P и Q:
• пересечение W(P) и W(Q) пусто,
• пересечение W(P) с R(Q) пусто,
• пересечение R(P) и W(Q) пусто,
тогда выполнение P и Q детерминировано.
Если эти условия не соблюдены, возможно, параллельное выполнение P и Q детерминировано, а может быть, и нет.
|
|
|
Случай двух активностей естественным образом обобщается на их большее количество.
Условия Бернстайна информативны, но слишком жестки. По сути дела, они требуют практически не - взаимодействующих процессов. А нам хотелось бы, чтобы детерминированный набор образовывали ак-тивности, совместно использующие информацию и обменивающиеся ею. Для этого нам необходимо ог-раничить число возможных чередований атомарных операций, исключив некоторые чередования с по-мощью механизмов синхронизации выполнения программ, обеспечив тем самым упорядоченный доступ программ к некоторым данным.
|
|
|
Про недетерминированный набор программ (и активностей вообще) говорят, что он имеет race condition (состояние гонки , состояние состязания). В приведенном выше примере процессы состязаются за вычис-ление значений переменных x и y.
|
|
|
| Основы операционных систем | 51 |
Задачу упорядоченного доступа к разделяемым данным (устранение race condition) в том случае, когда нам не важна его очередность, можно решить, если обеспечить каждому процессу эксклюзивное право доступа к этим данным. Каждый процесс, обращающийся к разделяемым ресурсам, исключает для всех других процессов возможность одновременного общения с этими ресурсами, если это может привести к недетерминированному поведению набора процессов. Такой прием называется взаимоисключением (mutual exclusion). Если очередность доступа к разделяемым ресурсам важна для получения правильных результатов, то одними взаимоисключениями уже не обойтись, нужна взаимосинхронизация поведения программ.
Критическая секция
Важным понятием при изучении способов синхронизации процессов является понятие критической сек-ции (critical section) программы. Критическая секция – это часть программы, исполнение которой может привести к возникновению race condition для определенного набора программ . Чтобы исключить эффект гонок по отношению к некоторому ресурсу, необходимо организовать работу так, чтобы в каждый мо-мент времени только один процесс мог находиться в своей критической секции, связанной с этим ресур-сом. Иными словами, необходимо обеспечить реализацию взаимоисключения для критических секций программ. Реализация взаимоисключения для критических секций программ с практической точки зре-ния означает, что по отношению к другим процессам, участвующим во взаимодействии, критическая секция начинает выполняться как атомарная операция. Давайте рассмотрим следующий пример, в кото-ром псевдопараллельные взаимодействующие процессы представлены действиями различных студентов (таблица 5.1):
Дата добавления: 2021-01-21; просмотров: 118; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!