Аппаратные способы достижения взаимного исключения

Запрещение прерываний

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

- применимо только в однопроцессорных системах;

- могут быть не обработаны важные события ввода-вывода;

- в случае краха процесса внутри КС ОС выйдет из строя.

Специальные команды, выполняющиеся атомарно

Такие команды выполняют за один цикл шины две или более операций, например, чтение из ячейки памяти и запись в нее значения "занято".

Программные способы достижения взаимного исключения

Переменные блокировки.

Процесс для входа в КС непрерывно проверяет значение некоторой переменной, чтобы определить, что разделяемый ресурс свободен. Переменная блокировки записывает состояние КС. Начальное значение переменной блокировки равно 0. Если процесс хочет попасть в КС, он предварительно считывает значение переменной блокировки. Если переменная равна 0, процесс изменяет ее на 1 и входит в КС. Если же переменная равна 1, то процесс ждет, пока ее значение сменится на 0. Таким образом, 0 означает, что ни одного процесса нет в КС, а 1 означает, что какой-либо процесс находится в КС.

while (busy);

busy = 1;

/* critical section */

…………………

busy = 0;

/* noncritical section */

…………………….

 

Недостатки такого подхода:

1) те же проблемы, что и при доступе к общим переменным.

2) если после выхода из КС процесс по какой-либо причине не установит КС=0, то другие процессы не смогут войти в КС – нарушается условие 3.

3) непроизводительное расходование времени процессора.

Активное ожидание (busy waiting) – постоянная проверка переменной в ожидании некоторого значения. Спин-блокировка – блокировка, использующая активное ожидание.

Алгоритм Деккера

Датский математик Деккер (1970) был первым, кто разработал программное решение проблемы взаимного исключения. Когда процесс P0 намерен войти в КС, он устанавливает свой флаг flag[0] равным true, а затем проверяет состояние флага процесса P1. Если он равен false, P0 может немедленно входить в КС; в противном случае P0 обращается к переменной turn. Если turn=0, это означает, что сейчас – очередь процесса P0 на вход в КС, и P0 периодически проверяет состояние флага процесса P1. Этот процесс, в свою очередь, в некоторый момент времени обнаруживает, что сейчас не его очередь для входа в КС, и устанавливает свой флаг равным false, давая возможность процессу P0 войти в КС. После того как P0 выйдет из КС, он установит свой флаг равным false для освобождения КС и присвоит переменной turn значение 1 для передачи прав на вход в КС процессу P1.

P0	P1
flag[0] = true; while (flag[1]) { if(turn == 1) { flag[0] = false; while(turn == 1)/*ждать*/; flag[0] = true; } } /* КС */ turn = 1; flag[0] = false;	flag[1] = true; while (flag[0]) { if(turn == 2) { flag[0] = false; while(turn = 1)/*ждать*/; flag[1] = true; } } /* КС */ turn = 0; flag[1] = false;

Алгоритм Петерсона

Петерсон (1981 г.) разработал существенно более простой алгоритм взаимного исключения. С этого момента алгоритм Деккера стал считаться устаревшим.

int turn; // 0,1 Чья сейчас очередь?

int interested[2]; /* Все переменные изначально = 0 */

 

void enter_cs(int proc)

{

int other = 1 - proc;

interested[proc] = true;

turn = proc;

while (turn==proc && interested[other]);

}

 

void leave_cs(int proc)

{

interested[proc] = false;

}

 

Перед входом в КС процесс вызывает функцию enter_cs со своим номером (0 или 1) в качестве параметра. После выхода из КС процесс вызывает функцию leave_cs, чтобы обозначить свой выход и тем самым разрешить другому процессу вход в КС. Исходно оба процесса находятся вне КС. Процесс 0 вызывает enter_cs. Поскольку процесс 1 не заинтересован в попадании в КС, функция возвращает управление. Теперь, если процесс 1 вызовет enter_cs, ему придется подождать, когда interested[0]=FALSE, а это произойдет только в тот момент, когда процесс 0 вызовет leave_cs.

Пусть оба процесса вызвали enter_cs практически одновременно. Оба сохранят свои номера в turn. Сохранится номер того процесса, который был вторым, а предыдущий номер будет утерян. Пусть вторым был процесс 1, следовательно, turn=1. Когда оба процесса дойдут до while, процесс 0 войдет в КС, а процесс 1 останется в цикле и будет ждать, пока процесс 0 выйдет из КС.

Вопросы для самоконтроля

1. Дайте определение понятиям "параллельные процессы", "последовательные процессы".

2. Перечислите виды взаимодействия процессов.

3. Перечислите основные проблемы, связанные с концепцией параллельных вычислений.

4. Почему процессы, работающие на разных компьютерах, не могут взаимодействовать при помощи разделяемых переменных?

5. В чем основное различие между конкурирующими и сотрудничающими процессами?

6. Поясните понятие "состояние гонок" и приведите пример такого состояния.

7. Дайте определения понятиям "взаимное исключение", "критический ресурс", "критическая секция".

8. Поясните, в чем заключается состояние голодания процессов. Приведите пример.

9. Перечислите требования к взаимоисключениям.

10. Какие существуют подходы к достижению взаимного исключения,

11. Почему в прикладных программах для достижения взаимного исключения не следует использовать запрещение прерываний?

12. Приведите примеры программных способов достижения взаимного исключения.

13. Поясните работу алгоритма Деккера достижения взаимного исключения.

14. Поясните работу алгоритма Петерсона достижения взаимного исключения.