4551
правка
Параллельное программирование, взаимное исключение: различия между версиями
Материал из WEGA
Параллельное программирование, взаимное исключение (посмотреть исходный код)
Версия от 12:53, 6 августа 2017
, 6 августа 2017→Постановка задачи
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 43: | Строка 43: | ||
Взаимное исключение: никакие два процесса не находятся в своих критических секциях в одно и то же время. | '''Взаимное исключение:''' ''никакие два процесса не находятся в своих критических секциях в одно и то же время.'' | ||
Отсутствие взаимной блокировки: если процесс пытается войти в свою критическую секцию, тогда некоторый процесс (не обязательно тот же самый) в конечном итоге входит в критическую секцию. | '''Отсутствие взаимной блокировки:''' ''если процесс пытается войти в свою критическую секцию, тогда некоторый процесс (не обязательно тот же самый) в конечном итоге входит в критическую секцию.'' | ||
Свойство отсутствия взаимной блокировки гарантирует, что система в целом продолжает двигаться вперед. Однако при соблюдении этого свойства возможно «голодание» некоторых процессов. Это происходит в случае, когда процесс пытается войти в критическую секцию, но не получает такой возможности и бесконечно ждет на этапе кода входа. Более строгое требование, исключающее возможность голодания, можно определить следующим образом. | Свойство отсутствия взаимной блокировки гарантирует, что система в целом продолжает двигаться вперед. Однако при соблюдении этого свойства возможно «голодание» некоторых процессов. Это происходит в случае, когда процесс пытается войти в критическую секцию, но не получает такой возможности и бесконечно ждет на этапе кода входа. Более строгое требование, исключающее возможность голодания, можно определить следующим образом. | ||
Отсутствие голодания: если процесс пытается войти в свою критическую секцию, то этот процесс в конечном итоге входит в критическую секцию. | '''Отсутствие голодания:''' ''если процесс пытается войти в свою критическую секцию, то этот процесс в конечном итоге входит в критическую секцию.'' | ||
Требование отсутствие голодания является более сильным, чем требование отсутствия взаимной блокировки, однако оно все же позволяет процессам выполнять свою критическую секцию произвольное количество раз до того, как некоторый процесс- соискатель сможет выполнить свою критическую секцию. Подобное поведение можно предупредить при помощи следующего требования справедливости. | Требование отсутствие голодания является более сильным, чем требование отсутствия взаимной блокировки, однако оно все же позволяет процессам выполнять свою критическую секцию произвольное количество раз до того, как некоторый процесс- соискатель сможет выполнить свою критическую секцию. Подобное поведение можно предупредить при помощи следующего требования справедливости. | ||
Первым вошел, первым вышел (First-in-first-out, FIFO): ни один если процесс не может войти в свою критическую секцию до процесса, который уже ожидает своей очереди для входа в критическую секцию. | '''Первым вошел, первым вышел (First-in-first-out, FIFO):''' ''ни один если процесс не может войти в свою критическую секцию до процесса, который уже ожидает своей очереди для входа в критическую секцию.'' | ||
Первые два требования (взаимного исключения и отсутствия взаимной блокировки) были изложены в оригинальной формулировке задачи Дейкстрой. Это минимальные требования, которые могут применяться в данном случае. В ходе решения задачи предполагается, что после того как процесс начал выполнение критической секции, он всегда завершает ее выполнение, независимо от действий других процессов. Задача взаимного исключения является одной из самых широко исследовавшихся в сфере межпроцессной синхронизации. Эта задача обманчива: на первый взгляд кажется, что решить ее очень просто. | Первые два требования (взаимного исключения и отсутствия взаимной блокировки) были изложены в оригинальной формулировке задачи Дейкстрой. Это минимальные требования, которые могут применяться в данном случае. В ходе решения задачи предполагается, что после того как процесс начал выполнение критической секции, он всегда завершает ее выполнение, независимо от действий других процессов. Задача взаимного исключения является одной из самых широко исследовавшихся в сфере межпроцессной синхронизации. Эта задача обманчива: на первый взгляд кажется, что решить ее очень просто. | ||
