Главная страница  Межпроцессное взаимодействие (состязание) 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 [ 23 ] 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187

ется, что метод поочередного доступа к критической области не слишком удачен, если один процесс существенно медленнее другого.

Эта ситуация нарушает третье из сформулированных нами условий: один процесс блокирован другим, не находящимся в критической области. Возвратимся к примеру с каталогом спулера: если заменить критическую область процедурой считывания/записи в каталог спулера, процесс О не сможет послать файл на печать, поскольку процесс 1 занят чем-то другим.

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

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

Датский математик Деккер (Т. Dekker) был первым, кто разработал программное решение проблемы взаимного исключения, не требующее строгого чередования. Подробное изложение алгоритма можно найти в [7].

В 1981 году Петерсон (G. L. Peterson) придумал существенно более простой алгоритм взаимного исключения. С этого момента вариант Деккера стал считаться устаревшим. Алгоритм Петерсона, представленный в листинге 2.1, состоит из двух процедур, написанных на ANSI С, что предполагает необходимость прототипов для всех определяемых и используемых функций. В целях экономии места мы не будем приводить прототипы для этого и последующих примеров.

Листинг 2.1. Решение Петерсона для взаимного исключения

#define FALSE О #define TRUE 1

idefine N 2 /* Количество процессов */

int turn: /* Чья сейчас очередь? */

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

/* равны О (FALSE) */

void enter region(int process): /* Процесс О или 1 */

int other; /* Номер второго процесса */

other = 1 - process: /* противоположный процесс */

interested[process] = TRUE: /* Индикатор интереса */

turn = process: /* Установка флага */

while (turn == process && interested[other] == TRUE) /* Пустой цикл */:

void leave region(int process) /* Процесс, покидающий

/* критическую область */

interestedCprocess] = FALSE: /* Индикатор выхода из

/* критической области */

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



со своим номером (О или 1) в качестве аргумента. Поэтому процессу при необходимости придется подождать, прежде чем входить в критическую область. После выхода из критической области процесс вызывает процедуру leave region, чтобы обозначить свой выход и тем самым разрешить другому процессу вход в критическую область.

Рассмотрим работу алгоритма более подробно. Исходно оба процесса находятся вне критических областей. Процесс О вызывает enter region, задает элементы массива и устанавливает переменную turn равной 0. Поскольку процесс 1 не заинтересован в попадании в критическую область, происходит возврат из процедуры. Теперь, если процесс 1 вызовет enter region, ему придется подождать, пока interested [0] примет значение FALSE, а это произойдет только в тот момент, когда процесс О вызовет процедуру leave region при покидании критической области.

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

Команда TSL

Рассмотрим решение, требующее участия аппаратного обеспечения. Многие компьютеры, особенно разработанные с расчетом на несколько процессоров, имеют команду Test and Set Lock (TSL) - проверить и заблокировать , которая действует следующим образом. В регистр считывается содержимое слова памяти, а затем в этой ячейке памяти сохраняется ненулевое значение. Гарантируется, что операция считывания слова и сохранения неделима - другой процесс не может обратиться к слову в памяти, пока команда не выполнена. Процессор, выполняющий команду tsl, блокирует шину памяти, препятствуя обращениям к памяти со стороны остальных процессоров.

Воспользуемся командой tsl. Пусть разделяемая переменная lock управляет доступом к общей памяти. Если значение lock равно О, любой процесс может изменить его на 1 и обратиться к общей памяти, а затем вернуть его обратно в О, пользуясь обычной командой типа move.

Как использовать команду tsl для реализации взаимного исключения? Решение приведено в листинге 2.2. Здесь представлена подпрограмма из четырех команд, написанная на некотором обобщенном (но типичном) ассемблере. Первая команда копирует старое значение lock в регистр и затем устанавливает значение переменной в 1. Потом старое значение сравнивается с нулем. Если оно ненулевое, значит, блокировка уже была произведена, и проверка начинается сначала. Рано или поздно значение окажется нулевым (это означает, что процесс, находившийся в критической области, покинул ее), и подпрограмма вернет управление в вызвавшую программу, установив блокировку. Сброс блокировки не представляет собой ничего сложного - просто помещается О в переменную lock. Специальной команды процессора не требуется.



Листинг 2.2. Вход и выход из критической области с помощью команды tsl

enter region:

tsl register.lock /* значение lock копируется в регистр */

/* значение переменной устанавливается равным 1 */

стр register.#0 /* Старое значение lock сравнивается с нулем */

jne enter region /* Если оно ненулевое, значит, блокировка уже была */ /* установлена, поэтому цикл */

ret /* Возврат в вызывающую программу */

/* процесс вошел в критическую область */

leave region:

move 1оск.#0 /* Сохранение О в переменной lock */

Одно решение проблемы критических областей теперь очевидно. Прежде чем попасть в критическую область, процесс вызывает процедуру enter region, которая выполняет активное ожидание вплоть до снятия блокировки, затем она устанавливает блокировку и возвращает управление. По выходу из критической области процесс вызывает процедуру leave region, помещающую О в переменную lock. Как и во всех остальных решениях проблемы критической области, для корректной работы процесс должен вызывать эти процедуры своевременно, в противном случае исключить взаимное исключение не удастся.

2.2.4. Примитивы межпроцессного взаимодействия

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

Этот алгоритм не только бесцельно расходует время процессора, но, кроме этого, он может иметь некоторые неожиданные последствия. Рассмотрим два процесса: Н, с высоким приоритетом, и L, с низким приоритетом. Правила планирования в этом случае таковы, что процесс Н запускается немедленно, как только он оказывается в состоянии ожидания. В какой-то момент, когда процесс L находится в критической области, процесс Н оказывается в состоянии ожидания (например, он закончил операцию ввода/вывода). Процесс Н попадает в состояние активного ожидания, но поскольку процессу L при условии работающего процесса Н процессорное время никогда не будет предоставлено, у процесса L не будет возможности выйти из критической области, и процесс Н навсегда останется в цикле. Эту ситуацию иногда называют проблемой инверсии приоритета.

Теперь рассмотрим некоторые примитивы межпроцессного взаимодействия, применяемые вместо циклов ожидания (в которых лишь напрасно расходуется процессорное время). Эти примитивы блокируют процессы в случае запрета на вход в критическую область. Одной из простейших является пара примитивов sleep и wakeup. Примитив sleep - системный запрос, в результате которого вызывающий процесс блокируется, пока его не запустит другой процесс. Запрос wakeup ожидает один аргумент - идентификатор запускаемого процесса. Также



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 [ 23 ] 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187

© 2000 - 2018 ULTRASONEX-AMFODENT.RU.
Копирование материалов разрешено исключительно при условии цититирования.