Распределённые операционные системы. Задачи и ответы. (esyr) (1158846), страница 4

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

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

Значит, всего потратим времени 3*48*(Ts+Tb).Комментарий: Сбор запросов происходит параллельно, а т.к. канала 2 - понадобится 15 / 2 = 8 тактов, итого получим (8+2*48)(Ts+Tb).Задача 6 (Алгоритм задиры)[править]6. Сколько времени потребует выбор координатора среди 16 процессов, находящ ихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностейшироковещ ания), если используется алгоритм «задиры»? «Задира» расположен в узле с координатами (0,0) и имеет уникальный номер 0. Время старта (время «разгона» послеполучения доступа к шине для передачи сообщ ения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1).

Доступ к шине ЭВМ получают последовательно в порядке выдачизапроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечнобыстрыми.Ответ: Так как задирой является процесс с наименьшим номером, то он пошлет сообщ ение ВЫБОРЫ всем остальным процессам и получит от всех ответ ОК. После этого всеостальные процессы будут инициировать выборы, рассылая сообщ ения процессам с бОльшими номерами и получая ответы.

Процесс же с наибольшмим номером (15) разошлетвсем сообщ ения КООРДИНАТОР, тем самым закончив выборы. Итого: (1 + 2 + ... + 15)(Ts + Tb * Lvybory) + (1 + 2 + ... + 15)(Ts + Tb * Lok) + 15(Ts + Tb * Lcoordinator) = 120(2Ts +Tb(Lvybory + Lok)) + 15(Ts + Tb * Lcoordinator)Задача 7 (Круговой алгоритм)[править]7. Сколько времени потребует выбор координатора среди 16 процессов, находящ ихся в узлах транспьютерной матрицы размером 4*4, если используется круговой алгоритм?Время старта равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ:Инициатор посылает сообщ ение ВЫБОРЫ со своим номером следующ ему по кругу.

Следующ ий живой процесс добавляет свой номер и посылает дальше. Так, пока не будетпройден круг (процесс увидел в сообщ ении свой номер). Тогда он выбирает максимальный номер и посылает сообщ ение КООРДИНАТОР с этим номером, оповещ ая о новомкоординаторе. Всего получается два круга сообщ ений. Итого: 16*(Ts + Tb*Lvibory) + 16*(Ts + Tb*Lcoordinator).Тема 5[править]1. Какие принципиальные решения приходится принимать при обеспечении файлового сервиса?Ответ:Есть ли разница между клиентами и серверами? Имеются системы, где все машины имеют одно и то же ПО и любая машина может предоставлять файловый сервис. Естьсистемы, в которых серверы являются обычными пользовательскими процессами и могут быть сконфигурированы для работы на одной машине с клиентами или на разных.Есть системы, в которых клиенты и серверы являются фундаментально разными машинами с точки зрения аппаратуры или ПО.open in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comДолжны ли быть файловый сервер и сервер директорий отдельными серверами или быть объединенными в один сервер.

Разделение позволяет иметь разные серверыдиректорий (UNIX, MS-DOS) и один файловый сервер. Объединение позволяет сократить коммуникационные издержки.Должны ли серверы хранить информацию о клиентах. См. вопрос про сервер с состоянием.2. Интерфейс сервера директорий.Ответ:Обеспечивает операции создания и удаления директорий, именования и переименования файлов, перемещ ение файлов из одной директории в другую.Определяет алфавит и синтаксис имен. Для спецификации типа информации в файле используется часть имени (расширение) либо явный атрибут.Все распределенные системы позволяют директориям содержать поддиректории - такая файловая система называется иерархической.

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

Обнаруживать такиеподдеревья в распределенных системах очень трудно).Ключевое решение при конструировании распределенной файловой системы - должны или не должны машины (или процессы) одинаково видеть иерархию директорий. Тесносвязано с этим решением наличие единой корневой директории (можно иметь такую директорию с поддиректориями для каждого сервера).Прозрачность именования. Две формы прозрачности именования различают - прозрачность расположения (/server/d1/f1) и прозрачность миграции (когда изменение расположенияфайла не требует изменения имени).Имеются три подхода к именованию:* машина + путь;* монтирование удаленных файловых систем в локальную иерархию файлов;* единственное пространство имен, которое выглядит одинаково на всех машинах.Последний подход необходим для достижения того, чтобы распределенная система выглядела как единый компьютер, однако он сложен и требует тщ ательного проектирования.3.

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

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

Что происходит, если два процесса одновременно работали с одним файлом - либо результат будет определяться процессом,последним закрывшим файл, либо можно только утверждать, что один из двух вариантов файла станет текущ им.Транзакции --- процесс выдает операцию “НАЧАЛО ТРАНЗАКЦИИ”, сообщ ая тем самым, что последующ ие операции должны выполняться без вмешательства другихпроцессов. Затем выдает последовательность чтений и записей, заканчивающ уюся операцией “КОНЕЦ ТРАНЗАКЦИИ”. Если несколько транзакций стартуют в одно и то жевремя, то система гарантирует, что результат будет таким, каким бы он был в случае последовательного выполнения транзакций (в неопределенном порядке). Пример банковские операции.4.

Серверы с состоянием и без состояния. Достоинства и недостатки.Ответ:Серверы с состоянием. Достоинства.Короче сообщ ения (двоичные имена используют таблицу открытых файлов).open in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comвыше эффективность (информация об открытых файлах может храниться в оперативной памяти).блоки информации могут читаться с упреждением.убедиться в достоверности запроса легче, если есть состояние (например, хранить номер последнего запроса).возможна операция захвата файла.Серверы без состояния. Достоинства.устойчивость к ошибкам.не требуется операций ОТКРЫТЬ/ЗАКРЫТЬ.не требуется память для таблиц.нет ограничений на число открытых файлов.нет проблем при крахе клиента.5. Алгоритмы обеспечения консистентности кэшей в распределенных файловых системах.Ответ:Алгоритм со сквозной записью.

Необходимость проверки, не устарела ли информация в кэше. Запись вызывает коммуникационные расходы (MS-DOS).Алгоритм с отложенной записью. Через регулярные промежутки времени все модифицированные блоки пишутся в файл. Эффективность выше, но семантика непонятнаяпользователю (UNIX).Алгоритм записи в файл при закрытии файла. Реализует семантику сессий. Не намного хуже случая, когда два процесса на одной ЭВМ открывают файл, читают его,модифицируют в своей памяти и пишут назад в файл.Алгоритм централизованного управления. Можно выдержать семантику UNIX, но не эффективно, ненадежно, и плохо масштабируется.6.

Способы организации размножения файлов и коррекции копий.Ответ:Система может предоставлять такой сервис, как поддержание для указанных файлов нескольких копий на различных серверах. Главные цели:1. Повысить надежность.2. Повысить доступность (крах одного сервера не вызывает недоступность размноженных файлов.3. Распределить нагрузку на несколько серверов.4. Явное размножение (непрозрачно).

В ответ на открытие файла пользователю выдаются несколько двоичных имен, которые он должен использовать для явногодублирования операций с файлами.5. “Ленивое” размножение. Одна копия создается на одном сервере, а затем он сам автоматически создает (в свободное время) дополнительные копии и обеспечивает ихподдержание.6. Симметричное размножение. Все операции одновременно вызываются в нескольких серверах и одновременно выполняются.Протоколы коррекции. Просто посылка сообщ ений с операцией коррекции каждой копии является не очень хорошим решением, поскольку в случае аварий некоторые копии могутостаться не скорректированными.

Имеются два алгоритма, которые решают эту проблему.1. Метод размножения главной копии. Один сервер объявляется главным, а остальные - подчиненными. Все изменения файла посылаются главному серверу. Он сначалакорректирует свою локальную копию, а затем рассылает подчиненным серверам указания о коррекции. Чтение файла может выполнять любой сервер.

Для защ иты от крахаглавного сервера до завершения всех коррекций, до выполнения коррекции главной копии главный сервер запоминает в стабильной памяти задание на коррекцию.Слабость - выход из строя главного сервера не позволяет выполнять коррекции.2. Метод голосования. Идея - запрашивать чтение и запись файла у многих серверов (запись - у всех!).

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

Список файлов ответов (шпаргалок)