Решённые задачи к экзамену (1162834), страница 4
Текст из файла (страница 4)
Наихудшийслучай будет, если на каждом следующем слое номер процесса будет больше, чем на предыдущем (т.е.выбираемый координатор находится в 3х3). Тогда каждому процессу (на всех слоях, кроме первого и последнего)надо будет потратить 2*(Ts + N*Tb) для информирования предыдущего слоя и начала выборов для следующего.Тогда общий ответ 6*2*(Ts + N*Tb).Если же выбираемый координатор находится где-то еще, а не в 3х3, то просто всем процессам на следующих слояхне надо пересылать сообщения обратно, что ускорит процесс.7. Сколько времени потребует выбор координатора среди 16 процессов, находящихся в узлах транспьютернойматрицы размером 4*4, если используется круговой алгоритм? Время старта равно 100, время передачи байтаравно 1 (Ts=100,Tb=1).
Процессорные операции, включая чтение из памяти и запись в память считаютсябесконечно быстрыми.Решение.Алгоритм основан на использовании кольца (физического или логического), но без маркера. Каждый процесс знаетследующего за ним в круговом списке. Когда процесс обнаруживает отсутствие координатора, он посылаетследующему за ним процессу сообщение "ВЫБОРЫ" со своим номером.
Если следующий процесс не отвечает, тосообщение посылается процессу, следующему за ним, и т.д., пока не найдется работающий процесс. Каждыйработающий процесс добавляет в список работающих свой номер и переправляет сообщение дальше по кругу.Когда процесс обнаружит в списке свой собственный номер (круг пройден), он меняет тип сообщения на"КООРДИНАТОР" и оно проходит по кругу, извещая всех о списке работающих и координаторе (процессе снаибольшим номером в списке). После прохождения круга сообщение удаляется.Предположим, что у нас в логическом кольце N живых процессов. Заметим также, что отправка подтвержденийсообщений не отнимают у всего алгоритма времени.1-ый этап - рассылка сообщения ВЫБОРЫ (длинны А).
Она происходит за N шагов.2-ой этап - рассылка КООРДИНАТОР (длинны B), это тоже N шагов. В сумме - N * ( Ts + A * Tb ) + N * ( Ts + B *Tb).Ответ: N * ( 2 * Ts + (A+B) * Tb )[ Ответ выписан с ошибкой :)Отмечу, что для матрицы 4х4 в простом случае можно взять N=16, A=B=3 байта (1 байт - тип сообщения + 16 бит битовый массив участников кольца).
Если же не все процессы живы (что в данной задаче, похоже, неподразумевается), то нужно еще учитывать Timeout.] - [ Ответ починил. Про Timeout - точно, этот ответ годитсятолько для N = 16 ;) ]17Тема 5(См. Лекция 5: "Распределенные файловые системы")1. Какие принципиальные решения приходится принимать при обеспечении файлового сервиса?Решение.1.2.3.4.Как определить файл - произвольная последовательность байтов + множество атрибутов, илипоследовательность записей, или еще как-то.Можно ли модифицировать файлы после созданияКак защищать файлы (разграничивать доступ)Использовать модель загрузки/разгрузки (полной пересылки файла) или удаленного доступа (частичнойпересылки)2.
Интерфейс сервера директорий.Решение. Обеспечивает операции создания и удаления директорий, именования и переименования файлов,перемещение файлов из одной директории в другую. Прозрачность именования. Две формы прозрачностиименования различают - прозрачность расположения (/server/d1/f1) и прозрачность миграции (когда изменениерасположения файла не требует изменения имени). Имеются три подхода к именованию:1.2.3.машина + путьмонтирование удаленных файловых систем в локальную иерархию файловединственное пространство имен, которое выглядит одинаково на всех машинахДвухуровневое именование.
Используют большинство систем. Файлы имеют символические имена дляпользователей, но могут также иметь внутренние двоичные имена для использования самой системой. Например, воперации открыть файл - символическое имя, а в ответ получает двоичное имя, которое и использует во всехдругих операциях с данным файлом. Способы формирования двоичных имен различаются в разных системах:•••если имеется несколько не ссылающихся друг на друга серверов (директории не содержат ссылок наобъекты других серверов), то двоичное имя может быть то же самое, что и в ОС UNIXимя может указывать на сервер и файлв качестве двоичных имен при просмотре символьных имен возвращаются мандаты, содержащие помимоправ доступа либо физический номер машины с сервером, либо сетевой адрес сервера, а также номерфайла.В ответ на символьное имя некоторые системы могут возвращать несколько двоичных имен (для файла и егодублей), что позволяет повысить надежность работы с файлом.3.
Семантика разделения файлов.Решение.18UNIX-семантика - естественная семантика однопроцессорной ЭВМ - если за операцией записи следует чтение, торезультат определяется последней из предшествующих операций записи. В распределенной системе такойсемантики достичь легко только в том случае, когда имеется один файл-сервер, а клиенты не имеют кэшей. Приналичии кэшей семантика нарушается.
Надо либо сразу все изменения в кэшах отражать в файлах, либо менятьсемантику разделения файлов.Еще одна проблема - трудно сохранить семантику общего указателя файла (в UNIX он общий для открывшегофайл процесса и его дочерних процессов) - для процессов на разных ЭВМ трудно иметь общий указатель.Неизменяемые файлы - очень радикальный подход к изменению семантики разделения файлов. Только двеоперации - создать и читать. Можно заменить новым файлом старый - т.е. можно менять директории.
Если одинпроцесс читает файл, а другой его подменяет, то можно позволить первому процессу доработать со старым файломв то время, как другие процессы могут уже работать с новым.Семантика сессий - изменения открытого файла видны только тому процессу (или машине), который производитэти изменения, а лишь после закрытия файла становятся видны другим процессам (или машинам). Что происходит,если два процесса одновременно работали с одним файлом - либо результат будет определяться процессом,последним закрывшим файл, либо можно только утверждать, что один из двух вариантов файла станет текущим.Транзакции - процесс выдает операцию НАЧАЛО ТРАНЗАКЦИИ, сообщая тем самым, что последующиеоперации должны выполняться без вмешательства других процессов. Затем выдает последовательность чтений изаписей, заканчивающуюся операцией КОНЕЦ ТРАНЗАКЦИИ. Если несколько транзакций стартуют в одно и тоже время, то система гарантирует, что результат будет таким, каким бы он был в случае последовательноговыполнения транзакций (в неопределенном порядке).
Пример - банковские операции.4. Серверы с состоянием и без состояния. Достоинства и недостатки.Решение.Серверы с состоянием. Достоинства.•••••Короче сообщения (двоичные имена используют таблицу открытых файлов).выше эффективность (информация об открытых файлах может храниться в оперативной памяти).блоки информации могут читаться с упреждением.убедиться в достоверности запроса легче, если есть состояние (например, хранить номер последнегозапроса).возможна операция захвата файла.Серверы без состояния. Достоинства.•••••устойчивость к ошибкам.не требуется операций ОТКРЫТЬ/ЗАКРЫТЬ.не требуется память для таблиц.нет ограничений на число открытых файлов.нет проблем при крахе клиента.5. Алгоритмы обеспечения консистентности кэшей в распределенных файловых системах.19Решение.Алгоритм со сквозной записью.
Необходимость проверки, не устарела ли информация в кэше. Запись вызываеткоммуникационные расходы (MS-DOS).Алгоритм с отложенной записью. Через регулярные промежутки времени все модифицированные блокипишутся в файл. Эффективность выше, но семантика непонятная пользователю (UNIX).Алгоритм записи в файл при закрытии файла. Реализует семантику сессий.
Не намного хуже случая, когда двапроцесса на одной ЭВМ открывают файл, читают его, модифицируют в своей памяти и пишут назад в файл.Алгоритм централизованного управления. Можно выдержать семантику UNIX, но не эффективно, ненадежно, иплохо масштабируется.6. Способы организации размножения файлов и коррекции копий.Решение. Система может предоставлять такой сервис, как поддержание для указанных файлов нескольких копийна различных серверах. Главные цели:1.2.3.Повысить надежность.Повысить доступность (крах одного сервера не вызывает недоступность размноженных файлов.Распределить нагрузку на несколько серверов.Схема реализации:1.2.3.Явное размножение (непрозрачно). В ответ на открытие файла пользователю выдаются несколькодвоичных имен, которые он должен использовать для явного дублирования операций с файлами.Ленивое размножение.
Одна копия создается на одном сервере, а затем он сам автоматически создает (всвободное время) дополнительные копии и обеспечивает их поддержание.Симметричное размножение. Все операции одновременно вызываются в нескольких серверах иодновременно выполняются.Протоколы коррекции.Просто посылка сообщений с операцией коррекции каждой копии является не очень хорошим решением,поскольку в случае аварий некоторые копии могут остаться не скорректированными. Имеются два алгоритма,которые решают эту проблему.1.2.3.Метод размножения главной копии. Один сервер объявляется главным, а остальные - подчиненными. Всеизменения файла посылаются главному серверу. Он сначала корректирует свою локальную копию, а затемрассылает подчиненным серверам указания о коррекции.
Чтение файла может выполнять любой сервер.Для защиты от краха главного сервера до завершения всех коррекций, до выполнения коррекции главнойкопии главный сервер запоминает в стабильной памяти задание на коррекцию. Слабость - выход из строяглавного сервера не позволяет выполнять коррекции.Метод одновременной коррекции всех копий. Все изменения файла посылаются (используя надежные инеделимые широковещательные рассылки) всем серверам. Чтение файла может выполнять любой серверМетод голосования. Идея - запрашивать чтение и запись файла у многих серверов (запись - у всех!).Запрос может получить одобрение у половины серверов плюс один.
При этом должно быть согласиеотносительно номера текущей версии файла. Этот номер увеличивается на единицу с каждой коррекциейфайла. Можно использовать различные значения для кворума чтения (Nr) и кворума записи (Nw). Приэтом должно выполняться соотношение Nr+Nw>N. Поскольку чтение является более частой операцией, тоестественно взять Nr=1. Однако в этом случае для кворума записи потребуются все серверы.20Тема 6(См. Лекция 6: "Распределенная разделяемая память")Комментарии: насколько я понял, алгоритм DSM (например, с полным размножением) для поддержкиопределенной схемы консистентности, модифицируется.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
