Задачи с ответами, страница 4

Итого получаются следующие результаты: 5+8 отправок сообщения, 5+8 запросов, 8 уведомлений, 5+8 ответов.

Времени надо: 13*(Ts+N*Tb)+13*(Ts+Lz*Tb)+8*(Ts+Ln*Tb)+13(Ts+La*Tb)

Выделив основные компоненты, получим: 47*Ts+13*N*Tb

1. Протоколы голосования. Алгоритмы и применение. Дайте оценку времени выполнения одним процессом 2-х операций записи и 10 операций чтения N байтов информации с файлом, расположенным (размноженным) на остальных 10 ЭВМ сети с шинной организацией (без аппаратных возможностей широковещания). Определите оптимальные значения кворума чтения и кворума записи для N=300. Время старта (время «разгона» после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Операции с файлами и процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

Хотя собственно алгоритм предписывает назначить каждой копии отдельное число голосов, будем считать, что у каждой копии ровно 1 голос.

Одна запись в память потребует:

Vw*(Ts+Tb*Lz)+Vw*(Ts+Tb*Lo)+Vw*(Ts+Tb*N), или приведя Vw

Vw*(3*Ts+Tb*Lz+Tb*Lo+Tb*N)

Возможно, если писатель не обладает актуальной копией, ему придется запросить её за

Ts+Tb*Lz+Ts+Tb*N

Одно чтение потребует:

Vr*(Ts+Tb*Lz)+Vr*(Ts+Tb*Lo)

Возможно, если читатель не обладает актуальной копией, ему придется запросить её за

Ts+Tb*Lz+Ts+Tb*N

Получается, что надо минимизировать Vw(1000+2Lz+2Lo)+Vr(2000+10Lz+10Lo)

Наилучший результат будет при Vw=9, Vr=1. То есть, согласие на запись должны дать все, согласие на чтение должен дать любой процесс.

1. Консистентное и строго консистентные множества контрольных точек. Дайте оценку накладных расходов на синхронную фиксацию строго консистентного множества контрольных точек для сети из 10 ЭВМ с шинной организацией (без аппаратных возможностей широковещания), если накладные расходы на синхронную фиксацию консистентного множества равны Т1. Время старта (время «разгона» после получения доступа к шине для передачи сообщения) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса на передачу (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

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

Шаг 2. Получение результатов операции.

Шаг 3. Когда 2 успешно, то есть все процессы перестали посылать сигналы.

Посылается операция проверки каналов:

Каждый процесс должен получив такое сообщение поставить его в очередь для данного канала.

Когда сообщение пройдет через данный канал, значит все неслужебные сообщения были отправлены.

Если сообщение проверки приходит по прочищенному каналу или в очереди канала уже стоит такое сообщение, тогда не следует его распространять дальше.

Шаг 4: Когда 3 успешно, то есть все процессоры освободили свои исходящие очереди. Когда у каждого процессора все входящие каналы прочищены (по ним получен сигнал очистки), тогда он должен послать сигнал готовности к фиксации строго консистентной контрольной точки.

Шаг 5: Когда координатор получит все сообщения о готовности к строго консистентной контрольной точке, он принимает её.

Если известно, что физическая среда единая и очередь сообщений к ней одна, тогда координатор делает следующее: рассылает всем сообщение о прочистке канала. Каждый узел должен вернуть это сообщение. Получив любое информационное сообщение процесс его буферизует и фиксирует новую точку консистентности. Получив все сообщения координатор вправе считать, что все процессы строго консистентны. После чего он должен разослать сообщение о принятии строго консистентного множества контрольных точек. При получении такого сообщения процесс обязан зафиксировать имеющуюся контрольную точку как принадлежащую множеству строго консистентных КТ и дальше её не модифицировать.

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

Сложность: 9+9+9+9+9+9+9= 9*7 = 63*(Ts+L*Tb) , L мало

Замечания.

При решении задач по теме 2 обратить внимание на следующее.

1. Нельзя модифицировать общие переменные вне КС.

2. При наличии вложенных КС или запросов нескольких семафоров необходимо убедиться, что не могут возникнуть тупики.

3. Нельзя обращаться к семафорам и событиям обычными операторами – только посредством операций, которые определены над ними (P, V, POST, WAIT, CLEAR).

4. Нельзя освобождать свободный семафор и объявлять уже объявленное событие.

5. Определять начальные значения семафоров и событий, если они должны быть отличны от нуля (семафор занят, событие не объявлено).

При ответах на вопросы по теме 6 следовать следующему плану.

1. Определение модели консистентности.

2. Алгоритм реализации в DSM с полным размножением (много писателей и много читателей, каждый из которых имеет свою копию всех переменных). Алгоритм должен быть корректным для любой коммуникационной сети и обеспечивать высокую эффективность для конкретной сети, указанной в задаче. Описание алгоритма должно содержать ответы на следующие вопросы:
   а) что делается при записи;
   б) что делается при чтении;
   в) когда, кому и как рассылаются значения модифицируемых переменных;
   г) блокируется ли процесс на время выполнения записи или рассылки значений переменных;
   д) если речь идет о моделях консистентности, связанных с синхронизацией, то указать алгоритм синхронизации (например, алгоритм входа в КС и выхода из нее).

3. Оценить время работы описанного в пункте 2 алгоритма применительно к конкретной задаче.