The design of the UNIX Operating System 28 страница
void Swap (int *a, int *b){ int tmp = *a;
*a = *b; *b = tmp;
}
Применяя атомарную команду Swap, мы можем реализовать предыдущий алгоритм, введя дополнитель-ную логическую переменную key, локальную для каждого процесса:
shared int lock = 0; int key;
while (some condition) { key = 1;
do Swap(&lock,&key); while (key);
critical section lock = 0;
remainder section
}
Заключение
Последовательное выполнение некоторых действий, направленных на достижение определенной цели, называется активностью. Активности состоят из атомарных операций, выполняемых неразрывно, как единичное целое. При исполнении нескольких активностей в псевдопараллельном режиме атомарные операции различных активностей могут перемешиваться между собой с соблюдением порядка следова-ния внутри активностей. Это явление получило название interleaving (чередование). Если результаты вы-полнения нескольких активностей не зависят от варианта чередования, то такой набор активностей назы-вается детерминированным. В противном случае он носит название недетерминированного. Существует достаточное условие Бернстайна для определения детерминированности набора активностей , но оно на-кладывает очень жесткие ограничения на набор, требуя практически не взаимодействующих активно-стей. Про недетерминированный набор активностей говорят, что он имеет race condition (условие гонки , состязания). Устранение race condition возможно при ограничении допустимых вариантов чередований атомарных операций с помощью синхронизации поведения активностей. Участки активностей, выполне-ние которых может привести к race condition, называют критическими участками. Необходимым услови-ем для устранения race condition является организация взаимоисключения на критических участках: внутри соответствующих критических участков не может одновременно находиться более одной актив-ности.
|
|
|
|
|
|
|
|
|
|
|
|
Для эффективных программных алгоритмов устранения race condition помимо условия взаимоисключе-ния требуется выполнение следующих условий: алгоритмы не используют специальных команд процес-
| Основы операционных систем | 58 |
сора для организации взаимоисключений , алгоритмы ничего не знают о скоростях выполнения процес-сов, алгоритмы удовлетворяют условиям прогресса и ограниченного ожидания. Все эти условия выпол - няются в алгоритме Петерсона для двух процессов и алгоритме булочной – для нескольких процессов.
Применение специальных команд процессора, выполняющих ряд действий как атомарную операцию, – Test-and-Set, Swap – позволяет существенно упростить алгоритмы синхронизации процессов.
6. Лекция: Механизмы синхронизации
Для повышения производительности вычислительных систем и облегчения задачи программистов суще-ствуют специальные механизмы синхронизации. Описание некоторых из них – семафоров Дейкстры, мо-ниторов Хора, очередей сообщений – приводится в этой лекции.
Рассмотренные в конце предыдущей лекции алгоритмы хотя и являются корректными, но достаточно громоздки и не обладают элегантностью. Более того, процедура ожидания входа в критический участок предполагает достаточно длительное вращение процесса в пустом цикле, то есть напрасную трату драго-ценного времени процессора . Существуют и другие серьезные недостатки у алгоритмов, построенных средствами обычных языков программирования. Допустим, что в вычислительной системе находятся два взаимодействующих процесса: один из них – H – с высоким приоритетом, другой – L – с низким приори-тетом. Пусть планировщик устроен так, что процесс с высоким приоритетом вытесняет низкоприоритет-ный процесс всякий раз, когда он готов к исполнению, и занимает процессор на все время своего CPU burst (если не появится процесс с еще большим приоритетом ). Тогда в случае, если процесс L находится в своей критической секции, а процесс H, получив процессор, подошел ко входу в критическую область, мы получаем тупиковую ситуацию. Процесс H не может войти в критическую область, находясь в цикле, а процесс L не получает управления, чтобы покинуть критический участок.
Дата добавления: 2021-01-21; просмотров: 105; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!