Понятие взаимоисключения нескольких процессов и критические участки

При работе вычислительной системы в режиме мультипрограм­мирования (многозадачности) возможны ситуации, когда:

- несколько процессов обмениваются данными посредством об­ращения к общим областям памяти (сотрудничают). При этом необ­ходимо, чтобы в каждый момент времени модифицировать разделяе­мую область памяти мог только один из сотрудничающих процессов;

- несколько независимо работающих процессов время от времени должны получать в монопольное владение какой-либо ресурс систе­мы.

Любая из названных ситуаций приводит к необходимости взаи­моисключения, то есть процесс, получивший право модифицировать разделяемую область памяти или использовать ресурс системы, ис­ключает эту возможность для других процессов на время, необходи­мое ему для выполнения своих задач.

Взаимоисключение обеспечивается включением в код програм­мы специальных критических участков (или критических секций). Каждый критический участок отвечает за свой разделяемый ресурс. Процесс может войти в свой критический участок только в том слу­чае, если ни один другой процесс не вошёл в такой же свой крити­ческий участок. В противном случае процесс должен ждать выхода другого процесса из своего критического участка.

Основные требования, выдвигаемые к разработке кодов крити­ческих участков:

- в любой момент времени только один процесс может находить­ся в своей критической секции. Возможно, что в какой-то момент времени ни один процесс не будет находиться в критической секции;

- ни один процесс не должен бесконечно находиться в своей кри­тической секции;

- ни один процесс не должен бесконечно долго ожидать разре­шения на вход в свою критическую секцию;

- процесс, находящийся вне своей критической секции не должен мешать другим процессам входить в свои критические секции;

- если два или более процесса хотят войти в свои критические секции, то решение вопроса о том, кто из них первым войдёт в кри­тическую секцию, не должно быть бесконечно долгим;

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

Режим взаимоисключения может быть реализован различными средствами.

Прежде всего, это могут быть программные и программно-аппаратные методы.

В первом случае режим взаимоисключения реализуется полно­стью программным образом без поддержки специфических аппарат­ных компонентов ЭВМ. В этом смысле такие реализации являются лучше переносимыми между различными архитектурами.

Во втором случае для реализации взаимоисключения использу­ются специальные неделимые команды конкретных ЭВМ, позволяю­щие единым актом проверить значение ячейки памяти и установить в ней новое значение.

Среди программных методов выделяют методы:

- основанные на программном коде, встраиваемом в сами при­кладные процессы (алгоритмы Деккера и Петерсона);

- основанные на семафорах;

- основанные на мониторах.