Требования, предъявляемые к алгоритму.
Программные алгоритмы организации взаимодействия процессов
Критическая секция
Interleaving race condition
Алгоритмы синхронизации
Взаимодействия процессов необходимо особым образом организовывать. В этом случае говорят об организации.
Под активностями понимают последовательные выполнения некоторых действий, направленных на достижения некоторых целей.
Будем разбивать активность на некоторые действия и неделимые операции.
Пусть есть активность
Pi a,b,c a,b,c,d,e,f – выполняются как единое целое (атепарные)
Q d,e,f
Что произойдет, если эти активности будут выполнятся псевдо … в режиме разделения времени?
abdcef
abdecf
Получается, что атепарные операции активности могут чередоваться определенным способом внутри активности.
Проблема: результат выполнения атепарных операций может сказаться зависимым от перекладывания следования операций.
Говорят, что набор активности программ детерменирован, если каждый раз при псевдопараллельности исполнения для одного и того же набора взодных данных он дает одинаковые выходные данные, в противном случае активность называется недетерменированной.
Вывод: детерменированный набор активностей можно выполнять в произвольном порядке.
Существует условие, которое позволяет определять является ли набор детерменированным. Условие Бернштейна:
R(P) – входные переменные
W(P) – выходные переменные
P: x = u +v
Y = x*W
R(P) = {u,v,x,W}
W(P) = {x,y}
Если для двух активностей P и Q:
1) W(P) ∩W(Q) =
2) W(P) ∩ R(Q) =
3) R(P) ∩ W(Q) =
То выполнения P и Q детерменированны.
Если условия не соблюдаются, то выполнения недетерменированны. Условия требуют, чтобы процессы были не взаимодействующие. Про детерменированный набор программ говорят, что он имеет … (состязаний)
.
При изучении синхронизации процессов важным является понятие критической секции. Понятие критическая секция программ. Критическая секция – часть программы, выполнение которой может привести к возникновению гонок (?)
Для исключения эффекта гонок необходимо организовать работу так, чтобы в каждый момент временив критической секции мог находиться только 1 процесс. Если процесс находится в своей критической секции, другие процессы не могут находиться в своих критических секциях – процесс взаимоисключения.
организация взаимоисключений
5 условий хорошего алгоритма необходимого для организации правильного взаимодействия процессов, имеющих критические участки:
· задача должна быть решена чисто программным способом. (на машине нет аппаратных программ взаимоисключения)
· не должно существовать предположений о соотношении скоростей выполняющихся процессов
· если процесс Pi исполняется в своем критическом участке, то не существует других процессов, которые выполняются так же в своём критическом участке
· процессы, находящиеся не в своих критических участках и не собирающиеся в них входить не могут препятствовать другим процессам, входить в их собственные критические участки.
· не должно быть бесконечного ожидании для входа в свой критический участок.