гуд работа. Курс лекций теория вычислительных процессов

• Название: Курс лекций теория вычислительных процессов
• Анкор: гуд работа
• Дата: 30.01.2022
• Размер: 1.54 Mb.
• Имя файла: tvp.pdf
• Тип: Курс лекций; #346626
• страница: 14 из 14

Producer %
В программе определены n+1 независимых параллельно протекающих процессов: один процесс- производитель Producer и n процессов-клиентов Client. Именно так могут быть описаны взаимодейст- вия файл-сервера и программ, запрашивающих (открывающих) нужные им файлы. При этом файл- сервер ответствен за то, чтобы только одна программа получала доступ к файлу по записи. Это же управление годится для программирования удаленного доступа к дисковому файлу нескольких про- грамм в сети. Много подобных задач в разных вариантах возникает при организации обработки данных в сети.
10.3.2. Параллельная программа разделения множеств
Определения MPI очевидны и просты. Так же просты и очевидны средства программирования в MPI. К сожалению, их простота и очевидность только кажущиеся.
В качестве примера рассмотрим программу разделения множеств, разработанную Э.Дейкстрой. Она много обсуждалась в публикациях, ее частичная корректность была доказана разными авторами, однако лишь недавно (в 1996 г) Ю.Г.Карпов (Санкт-Петербургский технический университет [Ю.Г.Карпов.
Анализ корректности параллельной программы разделения множеств. - Программирование, 1996. - N
5.]) формально доказал отсутствие свойства тотальной корректности. Программа называется коррект-
ной, если при остановке она вырабатывает правильный результат. Программа называется тотально
корректной, если она всегда останавливается и вырабатывает правильный результат.
И это при том, что программа совершенно тривиальна, в ней попросту не на что смотреть! Это хороший пример, показывающий, что простое тестирование, без формального обоснования правильности про- граммы, не в состоянии обеспечить правильность программы.
Но и применение одних лишь формальных методов не дает хороших результатов по той причине, что правильно применить формальный метод почти столь же трудно, как и разработать сам формальный метод. В литературе известны примеры некорректных программ, чья корректность была формально до- казана именно по причине неправильного применения формального метода самими авторами метода.
На практике следует комбинировать и тестирование и формальное доказательство правильности. Сле- дует также обратить внимание на опасную кажущуюся правильность частично корректных, но не то- тально корректных программ. Нередко такая программа долгое время нормально работает и обнаружи- вает ошибку в самый неподходящий момент.
Пусть заданы два множества натуральных чисел S и Т. Сохраняя мощность множеств S и Т, необходимо собрать в S наименьшие элементы множества S
∪ Т, а в Т - наибольшие.
Последовательный алгоритм и программа очевидны: множества S и Т сливаются, затем слитое множе- ство упорядочивается и вновь разделяется на множества S' и Т', удовлетворяющие условиям задачи.
Для параллельного асинхронного решения задачи используется следующий алгоритм.
1. Определяются два параллельно протекающих процесса Small и Large.
2. Процесс Small выбирает максимальный элемент в множестве S, а процесс Large параллельно (в то же самое время) находит минимальный элемент во множестве Т.

89 3. Процессы Small и Large синхронизируются и обмениваются данными: наибольшее значение множества S пересылается процессом Small процессу Large для включения в множество Т, а наименьшее значение множества Т пересылается процессом Large процессу Small для включения в множество S.
4. Далее циклически повторяются шаги 3 и 4.
5. Программа останавливается, когда наибольший элемент в множестве S окажется меньше наи- меньшего элемента в множестве Т.
По завершении программы все элементы множества S должны оказаться не больше любого элемента множества Т, а мощности этих множеств не изменяются.
Программа состоит из двух параллельных процессов, P = [Small\\Large],
P = [Small\\Large]:
Small ::
| Large :: mx:=max(S); α! mx; S:=S-{mx);
| α?y; T:=T
∪ {y}; mn:=min(T);
β? x; S: = S
∪ {x}; mx:=max(S);
| β! mn; T:=T-{mn}; mn:=min(T);
*[mx >x → α! mx; S:=S-{mx};
| *[mn∪ {y};
β? x; S:=S
∪ {x};
| mn:=min(T); β! mn; T:=T-{mn}; mx:=max(S); ] stop
| mn:=min(T) ] stop
Программу можно прокомментировать следующим образом. Определены два процесса Small и Large.
Символ || разрешает параллельное исполнение процессов Small и Large, оператор * задает циклическое исполнение (итерацию), пока истинно условие цикла. Процессы связаны однонаправленными каналами
α и β. По каналу α процесс Small передает данные в процесс Large, а данные из процесса Large переда- ются в процесс Small по каналу β.
Оператор ! задает передачу данных (аналог оператора send), а оператор ? - их прием (аналог оператора
receive). В частности, оператор α!mx в процессе Small задает передачу значения переменной mx в канал
α, а оператор α?у в процессе Large определяет прием значения из канала α и присваивание этого значе- ния переменной у.
В программе [Small\\Large] одновременное выполнение оператора α!mх в процессе Small и оператора
α?у в процессе Large (их выполнение синхронизуется, т.е., выполнение одного из них в одном из про- цессов задерживается до тех пор, пока другой оператор не начнет выполняться в другом процессе) име- ет семантику "удаленного присваивания" у:=mх. Аналогична семантика взаимодействия по каналу β.
Обозначим S
0
и Т
0
- начальные множества, a S
Term и T
Term
- заключительные их значения. При правиль- ном завершении программы ожидается выполнение соотношений (в соответствии с начальными усло- виями задачи):
(С1). Объединение множеств не изменилось: S
Term
∪ T
Term
= S
0
∪ Т
0
;
(С2). Мощности множеств сохранились: |S
Term
| = |S
0
|, |T
Term
| = |Т
0
|;
(СЗ). Каждый элемент S
Term не больше любого элемента Т
Term
: max(S
Term
) ≤ min(T
Term
).
Частичная корректность этой программы состоит в том, что если множества S
0
и Т
0
конечны и непусты, то после нормального завершения программы (т.е. когда каждый из процессов выходит на свой stop) свойства (С1), (С2) и (СЗ) выполняются. Тональная корректность ее состоит в том, что если множества
S
0
и Т
0
конечны и непусты, то программа завершается правильно и свойства (С1), (С2) и (СЗ) непремен- но выполняются после этого завершения.
Оставляя в стороне формальные детали, весьма поучительно рассмотреть технологические приемы, приводящие к пониманию того, что программа не является тотально корректной.

10.3.3. Коммуникационно-замкнутые слои параллельной программы
Это понятие вводится для упрощения верификации (доказательства правильности) параллельных про- грамм. Основная идея здесь - это разбиение каждого процесса Р
i параллельной программы Р:: = [Р
1
|| ... ||
P
n
] на последовательность его операторов: P
i
= Q
i,1
;Q
i,2
; ... Q
i,k
(k может быть выбрано одним и тем же для всех процессов, если допустить возможность использовать в качестве Q
i,r пустой оператор). Таким образом, параллельная программа Р может быть представлена как
P = [(Q
1,1
; Q
1,2
; ...; Q
1,k
)|| ... ||(Q
i,1
; Q
i,2
; ...; Q
i,k
)|| ... || (Q
n,1
; Q
n,2
; ...; Q
n,k
)].
Эту программу можно изобразить матрицей (рис. 10.13).
Рис. 10.13
Каждая i-я строка изображает процесс Р
i как последовательность оператоpoв:P
i
= Q
i,1
; Q
i,2
; ...; Q
i,k
Параллельная программа L
j
= [Q
1,j
||Q
2,j
|| ... || Q
n,j
] называется j-м слоем параллельной программы Р (j-й столбец матрицы).
Слой L
j называется коммуникационно-замкнутым, если при всех вычислениях Р взаимодействие про- цессов P
1
|| ...|| Р
n происходит только внутри этого слоя, или, иными словами, ни одна команда взаимо- действия среди операторов Q
rj при всех выполнениях Р не будет синхронизироваться (сочетаться) с командами взаимодействия из операторов Q
1,i при i ≠ j.
Тогда последовательность слоев L
1
; ...; L
k представляет собой параллельную программу:
Р* = L
1
; ...; L
k
= [Q
1,1
||Q
2,1
|| ... ||Q
n,1
]; ...; [Q
1,k
|| Q
2,k
|| ... ||Q
n,k
].
В программе Р* все L
j исполняются последовательно в порядке перечисления, а операторы каждой L
j исполняются параллельно. Программа Р* называется безопасной, если и только если все ее слои комму- никационно-замкнуты.
Если программа Р* безопасна, то вместо верификации всей параллельной программы Р можно прово- дить ее послойную верификацию, т.е., доказывать утверждение {p
0
}L
1
{p
1
}, ... ,{p k-1
}L
k
{p k
} вместо ут- верждения {р
0
}Р{р k
}. Здесь, как обычно, {s}P{q} обозначает утверждение, что программа Р частично корректна по отношению к предусловию s и постусловию q (вход-выходные соотношения), при этом если до начала исполнения программы Р предикат s истинен, то после исполнения Р предикат q тоже истинен.
Таким образом, если параллельную программу Р удается разбить на последовательность коммуникаци- онно-замкнутых слоев, то доказательство ее (частичной) корректности сводится к последовательному доказательству вход-выходных соотношений для каждого слоя. Это существенно упрощает анализ кор- ректности параллельной программы.
Процессы Small и Large разбиваются на коммуникационно-замкнутые слои совершенно естественно.
Разбиение приведено на рис. 10.14.
90

На рисунке показаны только "синхронизационные скелеты" параллельных процессов. В первый слой входят операторы до цикла, во второй слой - операторы внутри цикла, третий слой составляет оператор
stop после выхода из цикла. Процесс правильно завершается, если он заканчивает вычисления в заклю- чительном состоянии: процесс Small в состоянии E
S
, а процесс Large в состоянии E
L
. В общем cлучае процессы могут: a. оба завершиться нормально; b. оба не завершиться; c. один завершится, а другой нет, например, при невозможности выполнить операцию синхронного взаимодействия.
Рис. 10.14
Условия B
S
и B
L
определяют условия окончания циклов в процессах; они равны соответственно mх ≤ х и
mn ≥ у.
10.3.4. Когерентность параллельных программ
Для упрощения верификации параллельной программы уже при проектировании на нее можно нало- жить дополнительные требования, облегчающие ее понимание и анализ, и заранее устраняющие неко- торые типы возможных ошибок. Одним из таких требований является когерентность параллельной про- граммы.
Неформально требование когерентности означает:
• каждый раз, когда процесс хочет послать сообщение другому процессу, его партнер готов при- нять это сообщение, т.е. обязательно выходит на оператор приема сообщения;
• каждый раз тогда, когда процесс хочет получить сообщение некоторого типа от другого процес- са, его партнер посылает ему это сообщение.
91

В когерентной программе невозможна ситуация, когда в одном процессе выполняется оператор α!mx, a процесс-партнер не может выйти на исполнение оператора α?у.
Если параллельная программа Р:: = [Р ||...|| Р ] разбита на коммуникационно-замкнутые слои P
1
n i
=
Q
92 1,i
;Q ; ...; Q
i,2
i,k
, то требование когерентности состоит не только в том, что при всех вычислениях Р ни одна команда взаимодействия среди операторов Q
rj при всех выполнениях Р не будет синхронизиро- ваться (сочетаться) с командами взаимодействия из операторов Q
1,i при i ≠ j, но и в том, что каждая та- кая команда взаимодействия обязательно будет сочетаться с некоторой командой взаимодействия из операторов того же самого слоя. Для параллельной программы P = [Small \\ Large] такая синхронизация показана на рис. 10.15.
Рис. 10.15
Очевидно, что требование когерентности для этой программы выполняется тогда и только тогда, когда условия прекращения циклов в программах Small и Large тождественны при всех прохождениях цик- лов.
Некогерентность, с другой стороны, ведет к блокировке этой программы, т.е. к возникновению ситуа- ции, когда один из процессов выходит из цикла и переходит в заключительное состояние, а другой не выходит из своего цикла и "зависает" на операции синхронного взаимодействия внутри цикла, беско- нечно ожидая партнера.
Таким образом, условие B ≡ B
S
L
≡ И, или, что то же, mх ≤ х ≡ mn ≥ у при каждой проверке условий цик- лов в обеих программах, является необходимым условием тотальной корректности этой параллельной программы.
10.3.5. Анализ программы разделения множеств
Для анализа программы используем "истории" взаимодействий. Вводятся вспомогательные перемен- ные, которые хранят истории взаимодействия по каждому каналу программы.

93
Историческая переменная - это просто массив значений, последовательно переданных по соответст- вующему каналу. Пусть h
α
и h
β такие исторические переменные для каналов α и β соответственно, тогда компонент h
α
[k] содержит k-e значение, посланное по каналу α при выполнении операции α!e.
Проведем анализ первого слоя :
Q
Small,1
::
| Q
Large,1
:: mx:=max(S); α! mx; S:=S-{mx);
| α?y; T:=T
∪ {y}; mn:=min(T);
β? x; S: = S
∪ {x};
| β! mn; T:=T-{mn}; mx:=max(S);
| mn:=min(T)
Для того чтобы процессы Q
Small,1
и Q
Large,1
завершились, необходимо и достаточно, чтобы множество S содержало хотя бы один элемент, т.е. |S| > 0. По завершении каждого из этих параллельных процессов первого слоя будут справедливы следующие соотношения: для Q
Small,1
::
| для Q
Large,1
:: mx
0
=max(S
0
);
| y
1
= h
α
[0] h
α
[0] = mx
0
; | mn
0
; = min(T
0
∪ {y
1
}); x
1
= h
β
[0]
| h
β
[0] = mn
0
S
1
= (S
0
- {max (S
0
)})
∪ {x
1
};
| T
1
= T
0
∪ {y
1
} - { min(T
0
∪ {y
1
})}; mx
1
= max(S
1
);
| mn
1
=min(T
1
);
Эти соотношения просто описывают, что было сделано при исполнении операторов первого слоя.
Рассмотрим теперь второй слой:
Q
Small,2
::
| Q
Large,2
::
*mx > x → α! mx; S:=S-{mx);
| *[mn < y →
α?y; T:=T
∪
{y}; mn:=min(T);
β? x; S: = S
∪ {x};
| β! mn; T:=T-{mn}; mx:=max(S);
]
|
mn:=min(T)
]
Перед i-м выполнением каждого цикла для процессов Q
Small.2
и Q
Large 2
истинны следующие инварианты, что можно проверить непосредственно (где а
i
-значение переменной а перед i-м выполнением цикла): для Q
Small,2
::
| для Q
Large,2
::
I
Small,2
≡ h
α
[i-1] = mx i-1
∧
| I
Large,2
≡ y i
= h
α
[i-1]
∧ x i
= h
β
[i-1]
∧
| h
β
[i-1] = min(T i-1
∪ {y i
})
∧
S i
= (S i-1
- {max (S i-1
)})
∪ {x i
};
∧
| T i
= T i-1
∪ {y i-1
} - { min(T i-1
∪ {y i
})}
∧ mx i
= max(S i
);
| mn i
=min(T i
);
Как уже говорилось, требование когерентности в этой программе соответствует требованию общезна- чимости формулы mx i
≤ x i
≡ mn i
≥ у i
. При некоторых значениях исходных множеств S и Т она наруша- ется. Возможны два случая некогерентности: a. mх i
≤ х i
; или, что то max(S
i
) ≤ min(T
i-1
∪ { max(S
i-1
)}); mn i
< y i
; же: min(T i
) < max (S i-1
); при этом процесс Small завершается, а процесс Large продолжает выполнять цикл, что приводит к его блокировке; b. mx i
> x i
или, что то max(S
i
) > min(T i-1
∪ {max(S
i-1
)}); mn i
≥ уi же: min(T
i
) ≥ max(S i-1
); при этом процесс Large завершается, а процесс Small продолжает выполнять цикл и блокируется, бесконечно ожидая взаимодействия с процессом Large.

94
Учитывая, что min(T
i
) ≥ min(T
i
) и max(S
i
) ≤ max(S i-1
), условия некорректного поведения параллельной программы разделения множеств можно записать проще: i
i-1
i a) max(S ) ≤ min (T ); б) max(S ) > min(T i-1
); i
i-1
i i-1
min(T ) < max(S ); min(T ) ≥ max(S ).
Поясним полученный результат. Исследуемая параллельная программа разделения множеств имеет це- лью собрать все минимальные элементы объединения двух множеств S и Т в множестве S, а макси- мальные элементы S
∪ T - в множестве Т, причем мощности множеств не должны измениться. Упоря- дочим элементы исходных множеств: множества S по убыванию, а множества Т по возрастанию. На рис. 10.16,а. показано, что процесс Small, работая на множестве S, пересылает его максимальные эле- менты в множество Т, а процесс Large, работая на множестве Т, пересылает его минимальные элементы в множество S.
Рис. 10.16
Полученные выше условия некорректного поведения программы определены для (i-l)-гo и i-гo макси- мальных значений множества S и для (i-l)-гo и i-го минимальных значений множества Т, (i =1,2,...). Эти условия представлены диаграммами на рис. 10.16,б) и 10.16,в).
Иными словами, если между упорядоченными по убыванию элементами множества S и упорядоченны- ми по возрастанию элементами множества Т на одном и том же расстоянии от начала выполнится одно из отношений рис. 10.16,б) или рис. 10.16,в), то исследуемая программа будет работать некорректно: она входит в дедлок.
Можно указать тестовый пример, на котором эта программа работает некорректно: S = {5,10,15,20}, Т =
{17,18,30,40,60}. Этот пример относится к первому типу некорректностей при i = l: первое же вхожде- ние процесса Large в цикл приводит к дедлоку, поскольку Small завершится, не входя в цикл.
Однако полагаться на возможность обнаружения этой некорректности с помощью тестов нельзя. До- бавление, например, к множеству Т любого числа элементов, меньших 15, нарушит это соотношение и программа будет работать корректно.
В частности, ручной прокруткой можно проверить, что на множествах S = {5,10,15,20}, Т =
{14,17,18,30,40,60} программа работает правильно: сортирует множества и завершается после одно- кратного прохождения циклов в обоих процессах.

95
Литература:
1. Грис Д. Конструирование компиляторов для цифровых вычислительных систем. – М.: Мир, 1975.
2. Дейт К. Введение в системы баз данных. – М.: Мир, 1980.
3. Доновак Дж. Системное программирование. – М.: Мир, 1975.
4. Кнут Д. Искусство программирования для ЭВМ т.1, 2, 3. – М.: Мир, 1976 (1978).
5. Льюис Ф., Розенкранц Д., Стирнз Р. Теоретические основы проектирования компиляторов. – М.:
Мир, 1986 6. Мэдник С., Донован Дж. Операционные системы. – М.: Мир, 1978.
7. Хопгоуд Д. Методы компиляции. – М.: Мир, 1977.
8. Гитсбург С. Математическая теория контексно-свободных языков. – М.: Мир, 1970.
9. Вайнгартен Ф. Трансляция языков программирования. – М.: Мир, 1977.
10. Рейуорд-Смит В.Дж. Теория формальных языков. – М.: Мир, 1988 11. Бек Л. Введение в системное программирование. – М.: Мир, 1988 12. Ершов А.П. Введение в теоретическое программирование. – М.: Наука, 1977.
13. Кук. Д., Бейз Г. Компьютерная математика. – М.: Наука, 1990.
14. Бауэр Ф.Л., Гнау Р., Хилл У. Информатика задачи и решения. – М.: Мир, 1978.
15. Параллельные ЭВМ. – М.: Мир, 1986 16. Анисимов В. Программирование распределенных вычислительных систем / Под ред. В.Е.Котова.
Системная информатика 3. - М.: Наука, 1993. - с. 210-247.
17. Вальковский В., Малышкин В.А. Синтез параллельных программ и систем на вычислительных мо- делях. - Новосибирск: Наука, 1988. - 128 с.
18. Евстигнеев А. Введение в параллельные архитектуры ЭВМ. - Изд-во НГУ, 1994. - 78 с.
19. Евстигнеев А. VLIW-машины: развитие архитектуры и принципов построения программного обес- печения. Системная информатика N 4 / Под редакцией И. Поттосина. - Новосибирск: Наука - С. 304-
333.
20. Евстигнеев А. Основы параллельной обработки. Анализ программных зависимостей. - Новоси- бирск: Изд-во НГУ, 1996. - 75 с.
21. Ершов А. Вычислимость в произвольных областях и базисах // Семиотика и информатика. - 1982. -
Вып.19. - С. 3-58.
22. Клини С. Введение в метаматематику. - М.: Изд-во иностр. лит., 1957 (S.Kleene. Introduction to metamathematics/ - New York: Van Nostrand, 1952).
23. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алго- ритмов. - М.: Наука, 1984. - 223 с.
24. Малышев А. Алгоритмы и рекурсивные функции. - М.: Наука, 1986.
25. Программирование на параллельных вычислительных системах / Под редакцией Р. Бэбба. - М.:
Мир, 1991.
26. Малышкин В. Линеаризация массовых вычислений // Системная информатика N 1, 1991 / Под ре- дакцией В.Е. Котова. - Новосибирск: Наука -С.229-259.
27. Пападимитриу X., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир,
1985.
28. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир, 1972. ( Hartley
Rogers. Jr, Theory of Recursive Functions and Effective Computability, Me Graw - Hill, 1967).
29. Сачков В.Н. Комбинаторные методы дискретной математики. - М. Наука, 1977.-317 с.
30. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. - М.:Наука,
1987. - 288 с.
31. Шашкин Ю. Неподвижные точки. - М.: Наука, 1989. - 79 с.
32. Brawl Т. Parallel Programming. An Introduction. Prentice Hall, 1993 33. Endrews G. Concurrent Programming. Principles and Practice, Benjamin /Cummings Publishing, 1991.
34. Greene D., Knuth D. Mathematics for analysis of algorithms, Birkhauser, 1982 (Д.Грин, Д.Кнут. Ма- тематические методы анализа алгоритмов. - М.: Мир, 1987,119 стр)
35. Hoare G. Communicating sequential processes, Prentice-Hall (Ч. Xoap. Взаимодействующие после- довательные процессы. - М.: Мир, 1989. - 264 с.).
36. Lester B. Art of Parallel Programming. Prentice Hall, 1993.
37. Quinn М. Parallel Computing. McGraw-Hill, 1994.