Требования, предъявляемые к алгоритмам организации взаимодействия процессов.

1) Условие взаимоисключения: в критической секции не может быть больше одного процесса.

2) Условие ограниченного ожидания: Процесс которому необходимо войти в критическую секцию должен получить возможность сделать это в конечное время.

3) Условие прогресса: Решение о вхождении в критическую секцию должны принимать только те процессы, которым в данный момент нужно войти в критическую секцию. Процессы, которые находятся в остальной части программы и которым не нужно входить в критическую секцию не должны препятствовать вхождению в критическую секцию другим процессам.

4) Алгоритм синхронизации должен быть реализован на обычном процессоре с обычным набором команд.

7. Способы реализации взаимного исключения: запрещение прерываний

В прологе процесс входит в критическую секцию, запрещает прерывания, благодаря чему пока он находится в критической секции, он не будет снят с выполнения, и управление не будет передано ни другому процессу ни обработчику прерываний. В эпилоге разрешаются прерывания и другие процессы могут войти в критическую секцию. В случае сбоя, процесса в критической секции нарушается условие ограниченного ожидания. Поскольку эпилог не будет выполнен, прерывания не будут разрешены, и процессы будут бесконечно долго ждать выполнения. Алгоритм используется только в ядре ОС при выполнении критически важных операций.

8. Способы реализации взаимного исключения: переменная-замок

shared int lock = 0

while (true) {

while (lock)

lock = 1

critical section

lock = 0

remainder section }

Процессы разделяют переменную lock. Если она равно 0, то доступ в критическую секцию открыт, если 1, то закрыт. В прологе процесс проверяет значение lock до тех пор, пока оно не станет равно 0, выполняет бесконечный цикл. После чего закрывает замок и входит в критическую секцию. В эпилоге замок открывается, позволяя другому процессу выйти из бесполезного цикла пролога. Алгоритм нарушает условие взаимоисключений из-за неатомарности пролога. Если 2 процесса одновременно подходят к прологу, то возмодна ситуация, когда сначала 1 процесс выполнит проверку переменной-замка, перейдет к следующей команде, и в этот момент управление будет переданно другому процессу. Другой тоже выполнит проверку, тоже выйдет из цикла, и в результате оба процесса окажутся в критической секции.

9. Способы реализации взаимного исключения: строгое чередование

shared int turn = 0

while (true) {

while (turn!= id)

critical section

turn = 1 – turn

remainder section }

Алгоритм подразумевает поочередный вход в критическую секцию двух процессов. Разделяемая между процессами переменная turn показывает какому процессу в данный момент разрешен вход в критическую секцию. В прологе процесс проверяет равна ли переменная turn его id. Если равна, то входит в критическую секцию, иначе выполняется бесполезный бесконечный цикл проверки значения turn. В эпилоге turn устанавливается равной id другого процесса, позволяя тому выйти из бесконечного цикла пролога. Алгоритм нарушает условие прогресса, если процесс которому разрешено войти в критическую секцию работает в remainder section, не собираясь входить в critical section. При этом, процесс которому надо выполнять критическую секцию будет бесконечно выполнять пролог.

10. Способы реализации взаимного исключения: флаги готовности

shared int ready[] = {0, 0}

while (true) {

ready[id] = 1;

while(ready[1-id])

critical section

ready[id] = 0;

remainder section }

Алгоритм подразумевает, что процессы должны сообщать о том, что им необходимо войти в критическую секцию. Процессы разделяют массив флагов, которые равны 0 если процессу не надо войти в критическую секцию, и 1 если надо. В прологе процесс устанавливает свой флаг готовности и в бесконечном цикле проверяет флаг готовности другого процесса. Если тот установлен, то это значит что другой процесс в критической секции, поэтому продолжается цикл проверки. В эпилоге процесс сбрасывает свой флаг готовности. Алгоритм нарушает условие ограниченного ожидания из-за неатомарности пролога. Поскольку одновременно 2 процесса могут подойти к прологу, оба выполнить установку своего флага и оба бесконечно долго ждать пока не будет сброшен флаг другого процесса. А он сброшен не будет, потому что ни один процесс не выйдет из цикла в критическую секцию и не выполнит эпилог.

11. Способы реализации взаимного исключения: алгоритм Петерсона и алгоритм булочной.

Дата добавления: 2015-08-13