2020-01-15
217
В многопроцессной системе из-за взаимодействия процессов возможны 4 ситуации 1) взаимное исключение 2) синхронизация 3)взаимоблокировка 4)коммуникация. Критические области - ресурс, который допускает обслуживание пользователя за один раз наз. критическим. Если несколько процессов пользуются таким ресурсом, они должны синхронизировать свои действия. Место в программе, где процесс обращается к такому ресурсу наз. критическим участком. В каждый момент времени только один процесс может выполнять свой критический участок при работе с ресурсом. Для предотвращения этого используется взаимное исключение. Для реализации задач взаимного исключения необход. выполнение след. условий. 1) 2 процесса не должны одновременно находиться в критич. областях. 2)при запросе критич. ресурса несколькими процессами, только один получает разрешение. 3) процесс вне крит. Области не может блокир. Другие процессы. 4) процесс использует Крит область конечное время 5)любой процесс переходит в неактивное состояние только за пределами критич. области. 6) невозможна ситуация, когда процесс вечно ждет попадания в крит. область.
|
|
|
Способы реализации взаимного исключения: запрещение прерываний, блокировка памяти, строгое чередование.
1. Запрет прерываний
Выход процесса из состояния исполнения может быть по 2-ум причинам:
- блокировка из-за нехватки ресурсов
- конец кванта времени
Квант времени заканчивается по прерыванию таймера, поэтому, если запретить системе получать и обрабатывать прерывания, то процесс из состояний выполнения не выйдет, пока сам не разрешит прерывания.
Недостаток:
В случае зацикливания программы в КС или невыполнения эпилога, систему приходится перезагружать.
Этот алгоритм используется внутри ядра системы.
2. Блокировка памяти (переменная «Замок»)
shared int lock = 0;
while (1){
while (lock)
lock = 1;
КС
lock = 0;
}
Пролог не является атомарным, поэтому до того, как замок будет закрыт (lock = 1), управление может быть передано другому процессу, который тоже сможет войти в КС. Нарушается условие взаимоисключения.
3. Строгое чередование
Вводится переменная, которая идентифицирует номер процесса, который должен войти в КС.
shared int turn = 0;
while (1){
wile (turn!= pid);
КС
turn=1-turn;
}
Взаимоисключение гарантируется, но алгоритм не удовлетворяет условию прогресса, потому что, если процессу, идентификатор которого равен turn не нужно в КС, то он и не выйдет из КС и не изменит значение turn, при этом другой процесс может бесконечно долго ожидать входа в КС.
Способы реализации взаимоисключения: алгоритм Деккера, операция «Проверка и установка» (команда TSL)
1. Алгоритм Деккера
|
|
|
Используется массив флагов и переменная кода.
shared int turn = 0;
while (1){
ready[pid] = 1;
turn = 1-pid;
while (ready[1-pid] && turn == 1-pid);
КС
ready[pid] = 0;
}
Процесс может войти в КС только, если флаг готовности другого процесса равен 0 и значение переменной turn = идентификатору текущего процесса.
Доказательство:
Представим, что 2 процесса одновременно находятся в КС. Значит, флаги готовности у них обоих равны 1, значит, условие цикла while у обоих процессов не выполнялось из-за второй части этого условия, т.е. для каждого процесса переменная turn равна идентификатору этого процесса, чего быть не может, что и требовалось доказать.
2. операция «Проверка и установка» (команда TSL).
Алгоритм Деккера, расширенный на n процессов.
int Test and Set (int *target)
{int tmp = *target; *target = 1;
Return temp;}
shared int lock = 0;
while (1){
while (Test and Set(&lock));
КС
Lock = 0;}.
