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

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

3.3.4. Обнаружение и устранение взаимоблокировок

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

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

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

3.3.5. Предотвращение взаимоблокировок

Как мы видели, уклонение от взаимоблокировок, в сущности, невозможно, так как оно требует наличия никому не известной информации о будущих процессах. Тогда возникает справедливый вопрос: как же реальные системы избегают попадания в тупики? Для того чтобы ответить на этот вопрос, вернемся назад к четырем условиям, сформулированным в [11] (см. раздел Условия взаимоблокировки данной главы), и посмотрим, дадут ли они нам ключ к разрешению проблемы. Если мы сумеем гарантировать, что хотя бы одно из этих условий никогда не будет выполнено, тогда взаимоблокировки станут конструктивно невозможными [41].

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

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



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

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

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

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

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

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

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

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



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

1. Фотонаборное устройство

2. Сканер

3. Плоттер

4. Накопитель на магнитной ленте

5. Устройство для чтения компакт-дисков

Рис. 3.7. а - пронумерованные ресурсы; б - граф ресурсов

При выполнении такого соглашения граф распределения ресурсов никогда не будет иметь циклов. Покажем, что это так, в случае двух процессов (рис. 3.7, б). Мы попадаем в тупик, только если процесс А запросит ресурс j, а процесс В обратится к ресурсу i. Предположим, что ресурсы i и j различны, значит, они имеют разные номера. Если i > j, тогда процессу А не позволяется запрашивать ресурс j, потому что его номер меньше, чем номер уже имеющегося у него ресурса. Если же i < j, процесс В не может запрашивать ресурс i, так как этот номер меньше номера уже занятого им ресурса. Так или иначе, взаимоблокировка исключена.

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

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

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

В табл. 3.3 подведены итоги различных методов для предотвращения тупиков.



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