![]() КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Требования, предъявляемые к алгоритму
Программные алгоритмы организации взаимодействия процессов Критическая секция 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 исполняется в своем критическом участке, то не существует других процессов, которые выполняются так же в своём критическом участке · процессы, находящиеся не в своих критических участках и не собирающиеся в них входить не могут препятствовать другим процессам, входить в их собственные критические участки. · не должно быть бесконечного ожидании для входа в свой критический участок.
Дата добавления: 2014-01-07; Просмотров: 341; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |