В. Столлингс - Операционные системы (1114679), страница 138
Текст из файла (страница 138)
В качестве частных примеров можно привести алгоритмы выявления взаимобло кировок и обнаружения прекращения процессов (см., например, 1ВЕ)ч90, ЬУЫС961). Этот алгоритм также можно использовать для работы контрольных точек распределенного алгоритма, с тем чтобы в случае ошибки можно было восстановить исходное состояние системы. ("Х4 3 РАСПРЕДЕЛЕННЬж Напомним, что в главах б, "Параллельные вычисления: взаимоисключения и многозадачность", и 6, "Взаимоблокировка и голодание", речь шла о вопросах, связанных с выполнением параллельных процессов.
Двумя основными проблемами, которые возникают при этом, являются взаимоисключение и взаимоблокировка. В указанных главах основное внимание сосредоточено на решениях указанных проблем в контексте одной системы, обладающей одним или несколькими процессорами, но единой основной памятью. В распределенной операционной системе, управляющей системой с множеством процессоров, которые не используют совместно основную память или часы, возникают новые трудности и требуются новые решения. Алгоритмы взаимоисключения и взаимоблокировки должны зависеть от обмена сообщениями и не могут зависеть от возможности доступа к общей памяти. В этом разделе и далее взаимо- исключения и взаимоблокировка изучаются в контексте распределенной операционной системы.
Процесс 2 Выходные каналы Канал 3: посланы для 1, 2, 3, 4 Канал 4: посланы для 1, 2, 3, 4 Входные каналы Канал 1: получены от 1, 2, 3, 4; остались 5, 6 Канал 3: получены от 1, 2, 3, 4, 5, 6, 7, 8 Процесс 3 Выходные каналы Канал 2; посланыдля1,2,3,4, 5,6,7,3 Входные каналы Канал 1; получены от 1, 2, 3; осталвсь 4, 5, 6 Канал 2: получены от 1, 2, 3; осталзсь 4 Канал 4: получены от 1, 2, 3 Рис.
14.5. Граф лроиессоа и каналов Часть 6. Распределенные системы Глава 14. 'Управление распределенными процессами концепции распределенных изаимоискл1очений Если два или большее количество процессов соревнуются за возможность использования системных ресурсов, нужен механизм обеспечения взаимоискщочений. Предположим, что двум или большему количеству процессов нужен доступ к единому неразделяемому ресурсу, например к принтеру.
Во время своей работы каждый процесс будет отдавать команды этому устройству вводавыэода, получая информацию о его состоянии, отправляя данные и~или получая их. Такой ресурс мы будем называть критическим, а использующую его часть программы — критическим разделом программы. Важно отметить, что в каждый момент времени может выполняться критический раздел только одной программы. Понимание и воплощение этого ограничения не может основываться лишь на операционной системе, так как точные требования могут быть не очевидными. Например, принтер должен находиться под управлением процесса до тех пор, пока не будет распечатан весь файл.
В противном случае в распечатанном документе будут чередоваться строки, направленные разными конкурирующими процессами. Чтобы успешно применять параллелизм процессов, нужно иметь возможность задавать критические разделы и реализовывать взаимоисключения. Это является основой любой схемы параллельной обработки. Устройство или средство, обеспечивающее взаимоисключения, должно удовлетворять следующим требованиям. 1. Необходимо обеспечить реализацию взаимоисключения: в каждый момент времени лишь один процесс из всех тех, в которых имеются критические разделы одного и того же ресурса или совместно используемого объекта, может находиться в этом критическом разделе. 2. Если выполнение процесса прекращается не в критическом разделе, это не должно влиять на работу других процессов.
3. Нельзя, чтобы процесс, которому нужен доступ к критическому разделу, ожидал до бесконечности: нельзя допускать взаимоблокировок и голодания, 4. Если в критическом разделе нет ни одного процесса, то любой процесс, которому нужно войти в этот критический раздел, должен иметь возможность сделать это без промедления. б. Не делается никаких предположений об относительной скорости выполнения процессов или об их количестве. 6.
Процесс остается в критическом разделе лишь в течение конечного времени. На рис. 14.7 показана модель, на примере которой можно изучать разные подходы к взаимоисключениям в контексте распределенных систем. Допустим, что некоторое количество систем соединены между собой с помощью какого-то сетевого устройства. Предположим также, что в операционной системе каждой системы имеется некоторая функция или процесс, отвечающий за распределение ресурсов. Каждый такой процесс управляет определенным количеством ресурсов и обслуживает несколько пользовательских процессов.
Нужно разработать алгоритм, согласно которому эти процессы могут совместно обеспечивать взаимоисключение. Система 1 Рис. 34.7. Модель длл изучения проблемы езаимоиеключенил а распределенных нроцеееах Механизм взаимоисключения может быть либо централизованным, либо распределенным. В полностью централизованном алгоритме один из узлов настраивается как управляющий; он управляет доступом ко всем совместно используемым объектам. Если какому-то процессу нужен доступ к критическому ресурсу, он генерирует запрос и отправляет его своему локальному процессу, управляющему ресурсами.
Локальный управляющий процесс, в свою очередь, передает этот запрос контрольному узлу, который возвращает ответ (разрешение), когда совместно используемый объект становится доступным. Закончив работу с ресурсом, запрашивавший его процесс отправляет управляющему узлу сообщение об освобождении ресурса.
Такой централизованный алгоритм обладает двумя определяющими свойствами. 1. Решения о распределении ресурсов принимает только управляющий узел. 2. Вся необходимая информация, включая сведения об идентификаторах и размещении всех ресурсов, а также о статусе распределения каждого ресурса, сосредоточена на управляющем узле. Централизованный подход является прямолинейным; легко понять„как в нем реализуются взаимоисключения: управляющий узел не удовлетворит запрос на ресурс до тех пор, пока этот ресурс не освободится. Однако такая схема имеет ряд недостатков.
При отказе управляющего узла механизм взаимоисключений разлаживается (по крайней мере, на некоторое время). Кроме того, для каждого предоставления или освобождения ресурса нужен обмен сообщениями с управляющим узлом. Таким образом, недостаточная мощность управляющего узла может тормозить работу всей распределенной системы. Глава 14. Управление распределенными процессами 704 Часть 6. Распределенные системы Из-за этих, присущих централизованным алгоритмам, проблем, возрос инрес к разработке распределенных алгоритмов. Полностью распределенный алритм обладает такими свойствами ~МАЕК871. ).
Каждый узел в среднем обладает одинаковым количеством информации. 2. Каждый узел имеет лишь частичные сведения обо всей системе и может принимать решения, основываясь на этих сведениях. 8. За принятие конечного решения все узлы отвечают в равной мере. 4. На осуществление конечного решения все узлы в среднем затрачивают одинаковые усилия. б. Отказ одного из узлов не приводит к упадку всей системы. 6. В системе нет общих часов, по которым можно координировать события.
Пункты 2 и б требуют некоторого уточнения. Что касается пункта 2, то в гкоторых распределенных алгоритмах требуется, чтобы все узлы обменивались ~вестной им информацией. Даже в этом случае в каждый Фиксированный моент времени некоторая часть информации находится в пути и может еще не >йти до всех остальных узлов. Таким образом, из-за временных задержек, возлкающих при передаче сообщений„хранящаяся на каком-то отдельном узле эформация не является полностью обновленной, и в этом смысле каждый узел владает лишь частичной информацией.
Что касается пункта б, из-за того что обмен информацией между системами роисходит с некоторой задержкой, невозможно поддерживать часы, которые ыли бы немедленно доступны для всех систем. Кроме того, с технической точки зения непрактично поддерживать одни централизованные часы, по которым ожно было бы точно синхронизовать все локальные часы.
Однако через некотоэе время в показаниях разных локальных часов возникнет расхождение, в ре~льтате чего утратится синхронизация. Существенное усложнение механизмов взаимоисключения в распределеных системах по сравнению с централизованными вызвано задержками, возниающими при обмене информацией, а также отсутствием общих часов. Перед ем как обратиться к некоторым алгоритмам распределенного взаимоисключеия, исследуем общий подход к проблеме преодоления рассогласованности часов. ~порядочение событий в распределенной системе Основой работы большинства распределенных алгоритмов взаимоисклюений и взаимоблокировок является временное упорядочение событий.
Основ'.ым ограничением в нашей ситуации является отсутствие общих часов или редств синхронизации локальных часов. Проблему можно сформулировать и ак: хотелось бы иметь возможность определить, какое из событий произошло з ~аньше, — событие а в системе ~ или событие Ь в системе ). Кроме того, жела'ельно было бы иметь возможность делать такие выводы относительно любой истемы, подключенной к сети. К сожалению, эта Формулировка не является 'очной по двум причинам. Во-первых, между самим событием и его наблюдением в других системах может возникать задержка. Во-вторых, из-за отсутст~ия синхронизации возникают разногласия в показаниях часов, установленных 1 различных системах.
Чтобы тобы преодолеть эти трудности, Лампорт (Еашрог$) ~).АМР78) пре о мето по д, лучившии название метода временных меток (Фипеэйатр1пд), кото помогает по я о упорядочивать события в распределенных системах, не использ я шр1пв, который зичес ие к часы. Эта технология оказалась настолько действенно" спользуя фи и и э ективной, что стала использоваться в подавляющем большинст ве алгоритмов взаимоисключений и взаимоблокировок. Для начала выберем определение понятия событие ~ечеп1). В конечном сче счете, мы имеем дело с событиями, происходящими в локальной системе н апр имер вхождением процесса в критический раздел или выходом из него.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
