Электронный коспект лекций (1162752), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Если Pj имеетсвободный маркер, то он его посылает Pk только в томслучае, когда RNj[k]==LN[k]+1 (запрос не старый).Выход из критической секции процесса Pk.1) Устанавливает LN[k] в маркере равным RNk[k].2) Для каждого Pj, для которого RNk[j]=LN[j]+1, он добавляетего идентификатор в маркерную очередь запросов (если тамего еще нет).3) Если маркерная очередь запросов не пуста, то из нееудаляется первый элемент,а маркер посылаетсясоответствующему процессу (запрос которого был первым вочереди).Алгоритм древовидный маркерный (Raymond).Все процессы представлены в виде сбалансированногодвоичного дерева.

Каждый процесс имеет очередь запросов отсебя и соседних процессов (1-го, 2-х или 3-х) и указатель внаправлении владельца маркера.Вход в критическую секциюЕсли есть маркер, то процесс выполняет КС.Если нет маркера, то процесс:1) помещает свой запрос в очередь запросов2) посылает сообщение «ЗАПРОС» в направлении владельцамаркера и ждет сообщений.Поведение процесса при приеме сообщенийПроцесс, не находящийся внутри КС должен реагировать насообщения двух видов -«МАРКЕР» и «ЗАПРОС».А) Пришло сообщение «МАРКЕР»М1.

Взять 1-ый запрос из очереди и послать маркер его автору(концептуально, возможно себе);М2. Поменять значение указателя в сторону маркера;М3. Исключить запрос из очереди;М4. Если в очереди остались запросы, то послать сообщение«ЗАПРОС» в сторону маркера.Б) Пришло сообщение «ЗАПРОС».1. Поместить запрос в очередь2. Если нет маркера, то послать сообщение «ЗАПРОС» в сторонумаркера, иначе (если есть маркер) - перейти на пункт М1.Выход из критической секцииЕсли очередь запросов пуста, то при выходе ничегоделается, иначе - перейти к пункту М1.неИзмерение производительности.Введем следующие три метрики.1) MS/CS - количество операций приема сообщений, требуемоедля одного прохождения критической секции.2) TR - время ответа, время от появления запроса до полученияразрешения на вход.3) SD - синхронизационная задержка, время от выхода изкритической секции одного процесса до входа в нее следующегопроцесса (другого!).При оценке производительности интересны две ситуации: низкая загрузка (LL), при которой вероятность запроса входав занятую критическую секцию очень мала; высокая загрузка (HL), при которой всегда есть запросы навход в занятую секцию.Для некоторых метрик интересно оценить наилучшее инаихудшее значение (которые часто достигаются при низкой иливысокойзагрузки).Сравнение алгоритмов.При оценке времен исходим из коммуникационной среды, вкоторой время одного сообщения (Т) равно временишироковещательного сообщения.Название алгоритмаЦентрализованныйTRSDMS/CSMS/CS(LL)(HL)2T2T33NTT2(N-1)2(N-1)Круговой маркерныйДревовидный маркерныйДецентрализованный с временными меткамиШироковещательныймаркерныйВсеалгоритмынеустойчивыккрахампроцессов(децентрализованные даже более чувствительны к ним, чемцентрализованный).

Они в такомвиде не годятся дляотказоустойчивых систем.4.4Координация процессов1) Сообщения точка-точка (если известно, кто потребитель).2) Если неизвестно, кто потребитель, то: сообщения широковещательные; сообщения в ответ на запрос.3) Если неизвестно, кто потребляет и кто производит, то: сообщения и запросы через координатора: широковещательный запрос.Лекция 75 Распределенные файловые системыДве главные цели.Сетевая прозрачность.Самая важная цель - обеспечить те же самые возможности доступак файлам, распределенным по сети ЭВМ, которые обеспечиваютсяв системах разделения времени на централизованных ЭВМ.Высокая доступность.Другая важная цель - обеспечение высокой доступности.

Ошибкисистемилиосуществлениеоперацийкопированияисопровождения не должны приводить к недоступности файлов.Понятие файлового сервиса и файлового сервера.Файловый сервис - это то, что файловая система предоставляетсвоим клиентам, т.е. интерфейс с файловой системой.Файловый сервер - это процесс, который реализует файловыйсервис.Пользователь не должен знать, сколько файловых серверовимеется и где они расположены.Так, как файловый сервер обычно является обычнымпользовательским процессом, то в системе могут быть различныефайловые серверы, предоставляющие различный сервис(например, UNIX файл сервис и MS-DOS файл сервис).5.1Архитектура распределенных файловых системРаспределенная файловая система обычно имеет два существенноотличающихся компонента - непосредственно файловый сервер исервер директорий.5.1.1Интерфейс файлового сервераДля любой файловой системы первый фундаментальныйвопрос - что такое файл.

Во многих системах, таких как UNIX иMS-DOS, файл - не интерпретируемая последовательностьбайтов. На многих централизованных ЭВМ (IBM/370) файлпредставляется как последовательность записей, которую можноспецифицировать ее номером или содержимым некоторого поля(ключом). Так, как большинство распределенных систембазируются на использовании среды UNIX и MS-DOS, то онииспользуют первый вариант понятия файла.Файл может иметь атрибуты (информация о файле, неявляющаяся его частью).

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

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

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

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

Тесно связанос этим решением наличие единой корневой директории (можноиметь такую директорию с поддиректориями для каждого сервера).Прозрачность именования.Две формыпрозрачностиименования различают прозрачность расположения (/server/d1/f1) и прозрачностьмиграции (когда изменение расположения файла не требуетизменения имени).Имеются три подхода к именованию: машина + путь; монтирование удаленных файловых систем в локальнуюиерархию файлов; единственное пространство имен, которое выглядитодинаково на всех машинах.Последний подход необходим для достижения того, чтобыраспределенная система выглядела как единый компьютер.Двухуровневое именование.Большинство систем используют ту или иную формудвухуровневого именования. Файлы (и другие объекты) имеютсимволические имена для пользователей, но могут также иметьвнутренние двоичные имена для использования самой системой.Например, в операции открыть файл пользователь задаетсимволическое имя, а в ответ получает двоичное имя, которое ииспользует во всех других операциях с данным файлом.Способы формирования двоичных имен различаются в разныхсистемах: имя может указывать на сервер и файл; в качестве двоичных имен при просмотре символьных именвозвращаются мандаты, содержащие помимо прав доступалибо физический номер машины с сервером, либо сетевойадрес сервера, а также номер файла.В ответ на символьное имя некоторые системы могут возвращатьнесколько двоичных имен (для файла и его дублей), что позволяетповысить надежность работы с файлом.5.1.3Семантика разделения файлов.UNIX-семантика.Естественная семантика однопроцессорной ЭВМ - если заоперацией записи следует чтение, то результат определяетсяпоследнейизпредшествующихоперацийзаписи.Враспределенной системе такой семантики достичь легко только втом случае, когда имеется один файл-сервер, а клиенты не имеюткэшей.

При наличии кэшей семантика нарушается. Надо либосразу все изменения в кэшах отражать в файлах, либо менятьсемантику разделения файлов.Еще одна проблема - трудно сохранить семантику общегоуказателя файла (в UNIX он общий для открывшего файл процессаи его дочерних процессов) - для процессов на разных ЭВМ трудноиметь общий указатель.Неизменяемые файлы - очень радикальный подход к изменениюсемантики разделения файлов.Только две операции - создать и читать. Можно заменить новымфайлом старый - т.е. можно менять директории. Если один процессчитает файл, а другой его подменяет, то можно позволить первомупроцессу доработать со старым файлом, в то время как другиепроцессы могут уже работать с новым.Семантика сессий.Изменения открытого файла видны только тому процессу (илимашине), который производит эти изменения, а лишь послезакрытия файла становятся видны другим процессам (илимашинам).

Характеристики

Список файлов лекций