Требования, предъявляемые к алгоритму

Программные алгоритмы организации взаимодействия процессов

Критическая секция

Interleaving race condition

Алгоритмы синхронизации

Взаимодействия процессов необходимо особым образом организовывать. В этом случае говорят об организации.

Под активностями понимают последовательные выполнения некоторых действий, направленных на достижения некоторых целей.

Будем разбивать активность на некоторые действия и неделимые операции.

Пусть есть активность

P_i 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 условий хорошего алгоритма необходимого для организации правильного взаимодействия процессов, имеющих критические участки:

· задача должна быть решена чисто программным способом. (на машине нет аппаратных программ взаимоисключения)

· не должно существовать предположений о соотношении скоростей выполняющихся процессов

· если процесс P_i исполняется в своем критическом участке, то не существует других процессов, которые выполняются так же в своём критическом участке

· процессы, находящиеся не в своих критических участках и не собирающиеся в них входить не могут препятствовать другим процессам, входить в их собственные критические участки.

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

Дата добавления: 2014-01-07