В. Столлингс - Операционные системы (1114679), страница 139
Текст из файла (страница 139)
Однако в рас пределенной системе процессы взаимодействуют между собой с помощью сооб щений. Поэтому имеет смысл ассоциировать события с сообщениями. Связать локальное событие с сообщением очень просто — наприм ер, процесс может отправлять сообщение, когда ему нужно войти в критический раздел или выйти из него. Чтобы избежать неоднозначности, события будем связывать только с от з вать толь о с отправкои сообщений, а не с их получением. Таким образом, каждый раз, когда процесс передает сообщение, задается событие, соответствующее мом н менту времени, когда сообщение покинуло процесс.
Схема временных меток предназначена для того, чтобы упорядочить события, заключающиеся в передаче сообщений. В каждой подключенной к сети системе ~ поддерживается локальный счетчик С,, выполняющий функцию часов. еред передачей каждого сообщения система увеличивает показания этого счетчика на 1. Сообщение имеет вид где т содержимое сообщения Т временная метка сообщения равная С ~ — численный идентификатор узла. Получив сообщение, система-адресат ~ устанавливает значение своего счетчика равным увеличенному на единицу максимальному значению из текущего показания счетчика системы и поступившей временной метки: С,.
~ — 1+шах~С, Т,.1 Упорядочение событий в каждом узле происходит по следующим правилам. Говопят что соо р, ообщение х, поступившее от узла ~, предшествует сообщению у, поступившему от узла 1, если выполняется одно из следующих условий. 1. Т, < Т; 2. У, = У, и ~ < ~. Временнои характеристикой каждого сообщения является его временная метка, а упорядочение времен определяется двумя приведенными выше правилами (т.е. два соо ( ..
д а сообщения, временные метки которых равны, упорядочиваются по номерам их злов . р узлов). Благодаря тому что применение этих правил не зависит от узлов, при таком подходе удается избежать проблем„связанных с расхождением часов процессов, которые обмениваются информацией. Пример работы этого алгоритма показан на рис. 14.8. В распределенной системе имеется т еется три узла, каждый из которых представлен процессом, выполняющим алго р м временных меток. Процесс Р, начинается с показанием часов, ванным О.
г~е Перед передачей сообщения а он увеличивает показание своих Часть 6. Распределенные системы Глава 14. Управление распределенными процессами Распределенная очередь Часть.Ц. Расцределенные, я'исуемы: часов на 1 и передает сообщение вида (а,1,1), в котором первое численное значение соответствует временной метке, а второе — идентиФикатору узла. Это сообщение принимается процессами на узлах 2 и 3.
В обоих случаях показания локальных часов равняются нулю, а после получения сообщения устанав- ливаютсЯ Равными 2 = 1 + тпах(О,Ц. ПРоцесс Рг генеРиРУет следУющее сообние увеличивая перед этим показание своих часов на 1 (т.е. до 3). Получив это сообщение„процессы 1 и 3 должны установить на своих часах значение 3 но в одно и то же время процесс Р, отправляет сообщение Ь, а Затем примерно в о процесс Р, — сообщение 1. Оба сообщения имеют одинаковые временные метки. Благодаря сФормулированному выше временному принципу это не приведет к путанице. После всех этих событий упорядочение событий на всех узлах будет одним и тем же, а именно «а, х, Ь, у).
Рис. 14.8. Пример работы алгоритма оремгниых меток Как показано на рис. 14.9„описанный алгоритм работает, несмотря на разли-' чия во времени передачи сообщений в паре систем. Процессы, 4 тпр сы Р и Р о авляют со-., общения с одинаковыми временными метками. Сообщение от процесса Р, прибывает на узел 2 раньше, чем сообщение от процесса Р4, а на узел 3 сообщения от этих про-: цессов прибывают в обратном порядке. Несмотря на это, после получения всех сообщений их упорядочение на всех узлах остается одинаковым: «а, 4. Заметим, что упорядочение по такой схеме не всегда соответствует реальной последовательности событий. Так как основой этих алгоритмов является схема ' временных меток, не важно, какое событие произошло первым на самом деле.
Важно только то, что упорядочение всех процессов по этому алгоритму выпол- . няется согласованно. Рис. 14.9..Еще одии лримар работы алгоритма аргмеииых меток В двух приведенных примерах процесс адр су ес ет каждое сообщение всею остальным процессам. . Если какие-то сообщения отправляются по-другому, ВЕВоторые узлы не получат всех соо ще общений пересланных в системе, и поэтому невозможно будет одинаково упорядочить сообщения на всех узлах. В этом случае пол ится множество частичных упорядочений. Однако использование времен- получится множество частич ось ля аспределе нных алгоритмов ных меток первоначально предназначалось д р х и о есс обычно взаимоисключений и взаимоблокировок. В таких алгоритмах процесс ычно отправляет сообщение (с временной метко й, всем гим процессам; временные дру й.
метки используются для того„чтобы определить р д * р по я ок об аботьи сообщени Первая версия Один из самых ранних подходов, предложенн дл нный я обеспечения распределенных взаимоисключений, связан с конце ц р и ней асп деленной очереди ()-АМР731. В основе этого алгоритма лежат такие предположения. е ванных числами от 1 до 1. Распределенная система состоит из Ф узлов, пронумеро иваю й взаимоисклю- Ф.
На к ом зле содержится один процесс, запрашивающи ессов этот и цесс также вычающий доступ к ресурсам от имени других процессов„этот ро ступает ароитром, разрешая шая перекрывающиеся во времени входящие запросы. 2. Получение сообщений, отправленных одним проц дру ессом гому, происходит в том же порядке, в котором зти сообщения были отправлены. и с в течение конечного 3. Каждое сообщение доставляется по указанному адресу времени.
4. С вляется полносвязной; это означает, что д каж ый п цесс может отаче какого- править сообщение любому другому процессу без участия в перед либо промежуточного процесса. Глава 14. управленцев распределенными процессами н ежный транспортный проУсловия и 2 3 можно выполнить, применяя над токол,такой, как ТОР. лучая когда каждый узел тм п дназначенный для того случ Опишем алгоритм, пре л ай управления нескольки- управляет только одн им ресурсом.
Обобщение на случаи упр ми ресурсами тривиально. В этом алгоритме пр д р е п инята попытка о о щ б б ить простой алгоритм, кото- . Е ес рсом управляет един ент ализованной системе. сли ресу рый мог бы работать в цен р пающие запросы в очео есс, он может выстраивать поступаю ный центральный процесс, он пления запросов. Чтобы ь ос и к ресурсу в порядке поступлен редь и предоставлять досту й на всех узлах должна го итм в распределенной системе, на реализовать этот же алгоритм р че и. Чтобы порядок предоста вления ресурса по быть копия одной и той же очереди. в еменные метки. При этом эл на всех узлах, можно применять временные мет запросам совпадал на в б е передается в течение какость.
из-за того что сообщение пе возникает одна сложност в х азличных узлах во гла- го-то конечного времени, возникает угроза, что на двух разли ов. Об атимся к рис. 14.9.. ться запросы разных процессов. ра ве очереди будут находиться з р общение а уже пое вал в смени, в течение которого соо Имеется некоторый интервал вре Р, но оба сообщения еще не а сообщение о — процессом,„но о а лучено процессом Р~, а с б тправлены.
Таким обрассов которым они также ыли о дошли до других процессо, . р Р и Р, считают, что первым в: инте вала времени процессы Р~ и, счи зом, в течение этого и р Р а т что первым является ооб ение а, а процессы Рз и Р4 считают, очереди является соо щен е сти к нарушению требования сообщение д. Подоб ная ситуация может привести к н я следующее ограничение: я. Во избежание этого накладывается с взаимоисключения. о из ей собственной очереди, примет есс исходя нз состояния свое со прежде чем процесс, ить от всех других узлов со-' решение о предоставлении р ур и ес са, он должен получить о ного сообщения, коточто в каналах не осталось ни одно общение, гарантирующее, что рое может занять пер вое место в очереди.
ает ру ых в которой хранятся На каждом узле поддерживает ру ается структура данных, ого зла (а также о тех," ооб ениях, полученных от каждого узла а так е записи о последних соо щен которые недавно р отп авлены с данного узла . ам ассивом, в котором каждому е ью. фактически она является массивом, структуру очередью; ф н элемент. В кажды момент й нт времени в элементе ло-.'. узлу соответствует один эл и о есса Р . Массив инициа-: одержится сообщение от процесса кального массива д[Д сод р * лизируется следующим образом: ц[Я=(Ве1еме,0,,1') 1=1,а,Ж В этом алгоритме используютс р я т и вида сообщений: мР- а (Вециез1, Та 1): запрос ресурса процессом Р ос па к ресурсу, который н ( ру Ве 1 Т '): предоставление процессом Р, д ту ходится под его управлением; Р вобождает предоставленный ему ресурс.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
