The design of the UNIX Operating System 21 страница
В предыдущей лекции мы говорили о внешних проблемах кооперации, связанных с организацией взаи-модействия процессов со стороны операционной системы. Предположим, что надежная связь процессов организована , и они умеют обмениваться информацией. Нужно ли нам предпринимать еще какие-либо действия для организации правильного решения задачи взаимодействующими процессами? Нужно ли изменять их внутреннее поведение? Разъяснению этих вопросов и посвящена данная лекция.
|
|
|
Interleaving, race condition и взаимоисключения
Давайте временно отвлечемся от операционных систем , процессов и нитей исполнения и поговорим о некоторых "активностях". Под активностями мы будем понимать последовательное выполнение ряда действий, направленных на достижение определенной цели. Активности могут иметь место в программ-ном и техническом обеспечении, в обычной деятельности людей и животных. Мы будем разбивать ак-тивности на некоторые неделимые, или атомарные, операции. Например, активность "приготовление бу-терброда" можно разбить на следующие атомарные операции:
|
|
|
1. Отрезать ломтик хлеба.
2. Отрезать ломтик колбасы.
3. Намазать ломтик хлеба маслом.
4. Положить ломтик колбасы на подготовленный ломтик хлеба.
|
|
|
Неделимые операции могут иметь внутренние невидимые действия (взять батон хлеба в левую руку, взять нож в правую руку, произвести отрезание). Мы же называем их неделимыми потому, что считаем выполняемыми за раз, без прерывания деятельности.
Пусть имеется две активности
P: a b c
Q: d e f
где a, b, c, d, e, f – атомарные операции. При последовательном выполнении активностей мы получаем такую последовательность атомарных действий:
|
|
|
PQ: a b c d e f
Что произойдет при исполнении этих активностей псевдопараллельно, в режиме разделения времени? Активности могут расслоиться на неделимые операции с различным чередованием, то есть может про-изойти то, что на английском языке принято называть словом interleaving. Возможные варианты чередо-вания:
а b c d e f a b d c e f a b d e c f a b d e f c a d b c e f
......
d e f a b c
Атомарные операции активностей могут чередоваться всевозможными различными способами с сохра-нением порядка расположения внутри активностей. Так как псевдопараллельное выполнение двух актив-
| Основы операционных систем | 50 |
ностей приводит к чередованию их неделимых операций, результат псевдопараллельного выполнения может отличаться от результата последовательного выполнения. Рассмотрим пример. Пусть у нас имеет-ся две активности P и Q, состоящие из двух атомарных операций каждая:
P: x=2 Q: x=3
y=x-1 y=x+1
Что мы получим в результате их псевдопараллельного выполнения, если переменные x и y являются для активностей общими? Очевидно, что возможны четыре разных набора значений для пары (x, y): (3, 4), (2, 1), (2, 3) и (3, 2). . Мы будем говорить, что набор активностей (например, программ) детерминирован , ес-ли всякий раз при псевдопараллельном исполнении для одного и того же набора входных данных он дает одинаковые выходные данные. В противном случае он недетерминирован. Выше приведен пример неде-терминированного набора программ. Понятно, что детерминированный набор активностей можно безбо - язненно выполнять в режиме разделения времени. Для недетерминированного набора такое исполнение нежелательно.
Можно ли до получения результатов определить, является ли набор активностей детерминированным или нет? Для этого существуют достаточные условия Бернстайна. Изложим их применительно к про-граммам с разделяемыми переменными.
Дата добавления: 2021-01-21; просмотров: 101; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!