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

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

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

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

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

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

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

Последовательность событий, необходимых для использования ресурса, представлена ниже в абстрактной форме.

1. Запрос ресурса.

2. Использование ресурса.

3. Возврат ресурса.

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



3.3.2. Понятие взаимной блокировки

Определение взаимоблокировки формально можно озвучить так:

Группа процессов находится в тупиковой ситуации, если каждый процесс из группы ожидает события, которое может вызвать только другой процесс из той же группы.

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

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

Условия взаимоблокировки

Коффман (Coffman et al.) [70] и другие исследователи доказали, что для возникновения ситуации взаимоблокировки должны выполняться четыре условия.

1. Условие взаимного исключения. Каждый ресурс в данный момент или отдан ровно одному процессу, или доступен.

2. Условие удержания и ожидания. Процессы, в данный момент удерживающие полученные ранее ресурсы, вправе запрашивать новые ресурсы.

3. Условие отсутствия принудительной выфузки ресурса. У процесса нельзя принудительным образом забрать ранее полученные ресурсы. Процесс, владеющий ими, должен сам освободить ресурсы.

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

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

Моделирование взаимоблокировок

в [44] Холт (Holt) показал, как можно смоделировать четыре условия возникновения тупиков, используя направленные фафы. Графы имеют два вида узлов:



процессы, показанные кружочками, и ресурсы, нарисованные квадратиками. Ребро, направленное от узла ресурса (квадрат) к узлу процесса (круг), означает, что ресурс ранее был запрошен процессом, получен и в данный момент используется этим процессом. На рис. 3.5, а ресурс R в настоящее время отдан процессу А.

Ребро, направленное от процесса к ресурсу, означает, что процесс в данный момент блокирован и находится в состоянии ожидания доступа к этому ресурсу. На рис. 3.5, б процесс В ждет ресурс S. На рис. 3.5, в мы видим взаимоблокировку: процесс С ожидает ресурс Т, удерживаемый в настоящее время процессом D. Процесс D вовсе не намеревается освобождать ресурс Т, потому что он ждет ресурс и, используемый процессом С. Оба процесса будут ждать до бесконечности. Цикл в фафе означает наличие взаимоблокировки, циклично включающей процессы и ресурсы (предполагается, что в системе есть по одному ресурсу каждого вида). В этом примере циклом является последовательность C-T-D-U-C.

©



Рис. 3.5. Графы распределения ресурсов: а - ресурс занят; 6 - запрос ресурса;

в - взаимоблокировка

Теперь рассмотрим пример того, как извлечь пользу из графов ресурсов. Представим, что у нас есть три процесса: А, В и С, и три ресурса: R, S и Т. Последовательность запросов и возвратов ресурсов для трех процессов показана на рис. 3.6, а-в. Операционная система может запустить любой незаблокированный процесс в любой момент времени, значит, таковым может оказаться процесс А. Процесс А будет выполняться до тех пор, пока не закончит всю свою работу, затем будет запущен процесс В до его завершения и, наконец, процесс С.

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

Теперь предположим, что процессы выполняют как расчеты, так и ввод/вывод, соответственно циклический алгоритм планирования является рациональ-



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.
Копирование материалов разрешено исключительно при условии цититирования.