2013 Saktaganov_3-kr (1162819), страница 2

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

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

Должны выполняться следующие условия:

А) N_R > N / 2 (Таненбаум – «Распределенные системы»);
Почему это?

Описался, должно быть N_W > N / 2, это для предотвращения конфликтов двойной записи. Повторения описки из-за копи-паста.

В лекциях сказано, что обращаться с записью надо ко всем серверам. В книге ситуация другая – не определяется, как должны работать несколько клиентов, желающих писать в файл. Реально есть два способа – либо на запись может открыть файл только один клиент, либо могут открыть несколько, но тогда для коррекции файла каждый должен его захватывать и освобождать. Операции открытия и захвата/освобождения мы не рассматриваем.

Б) N_W > 0;

В) N_R + N_W > N.

Г)T>0

Что это такое?

Условие Т > 0 добавил после того, как получил линейную функцию относительно кворума записи. Т.к. надо минимизировать эту функцию, но при этом значение отрицательным быть не может (Наверно условие лучше стоило добавить в конце).

Пусть N_R + N_W = N + 1 = 20;

Рассмотрим операцию записи. Запрашиваем запись у всех ЭВМ (В том числе собственный). Все ЭВМ отвечают ему, отправляя текущую версию файла.

Пусть текущая версия у всех ЭВМ совпадает, в том числе на ЭВМ, где выполняется наш процесс. Тогда достаточно записать у себя и на остальных N_W-1 ЭВМ.

WR – WriteRequest;

WA – WriteAnswer;

F – File.

(N-1)*(Ts+Tb*SIZE_WR) – время запроса у всех на запись;

(N-1)*(Ts+Tb*SIZE_WA) – время ответа;

(N_W-1)*(Ts+Tb*SIZE_F) – время записи.

Теперь рассмотрим операцию чтения. Запрашиваем чтение у N_R ЭВМ. Они отвечают текущей версией файла. Выбираем наиболее «свежую» версию и читаем.

RR – ReadRequest;

RA – ReadAnswer.

(N_R-1)*(Ts+Tb*SIZE_RR) – время запроса на чтение;

(N_R-1)*(Ts+Tb*SIZE_RA) – время ответа;

Ts+Tb*SIZE_F – время чтения(добавляем если у нас не самая «свежая» версия).

Пусть количество записей – A, количество чтений – B. Пусть при чтении у нас не самая «свежая» версия.

Общее время():

T = A*((N-1)*(Ts+Tb*SIZE_WR)+(N-1)*(Ts+Tb*SIZE_WA)+(N_W-1)*(Ts+Tb*SIZE_F))

+B*((N_R-1)*(Ts+Tb*SIZE_RR)+ (N_R-1)*(Ts+Tb*SIZE_RA)+Ts+Tb*SIZE_F)=

=A*(N-1)(3*Ts+Tb(SIZE_WR+SIZE_WA+SIZE_F))+

+(N_R-1)(Ts*(2B-A)+Tb*(B*(SIZE_RR+SIZE_RA)-A*SIZE_F)) + B*(Ts + SIZE_F*Tb)

Пусть размеры запросов и ответов по 1 байту. Тогда

Ts*(2B-A)+Tb*(B*(SIZE_RR+SIZE_RA)-A*SIZE_F) = 100*(24-2)+12*2-2*300=1624

Получили линейную функцию от N_R с положительным коэффицентом_. Учитывая условия, поставленные в начале задачи, получим N_R = 1;=>N_W=19.

Ответ: N_R = 1, N_W=19.

А как же А) N_R > N / 2 (Таненбаум – «Распределенные системы»);

Ответ был выше.

Пересмотрим решение с учетом Ваших исправлений:
У нас N = 18. N_R + N_W = N + 1 = 19. N_W > N / 2;

Запрашиваем у всех N ЭВМ. Все ЭВМ отвечают ему, отправляя текущую версию файла. Пусть текущая версия у всех ЭВМ совпадает. Тогда достаточно записать у N_W ЭВМ.

Смысл размножения – поддерживать все копии, но временно позволять некоторым серверам выходить из строя!!!

WR – WriteRequest;

WA – WriteAnswer;

F – File.

N*(Ts+Tb*SIZE_WR) – время запроса у всех на запись;

N*(Ts+Tb*SIZE_WA) – время ответа;

N_W*(Ts+Tb*SIZE_F) – время записи.

Теперь рассмотрим операцию чтения. Запрашиваем чтение у N_R ЭВМ. Они отвечают текущей версией файла. Выбираем наиболее «свежую» версию и читаем.

RR – ReadRequest;

RA – ReadAnswer.

N_R*(Ts+Tb*SIZE_RR) – время запроса на чтение;

N_R*(Ts+Tb*SIZE_RA) – время ответа;

Ts+Tb*SIZE_F – время чтения.

Пусть количество записей – A, количество чтений – B. Общее время:

T = A*(N*(Ts+Tb*SIZE_WR) + N*(Ts+Tb*SIZE_WA)+N_W*(Ts+Tb*SIZE_F))+

+ B*(N_R*(Ts+Tb*SIZE_RR)+N_R*(Ts+Tb*SIZE_RA)+Ts+Tb*SIZE_F) =

{ N_W = N + 1 – N_R} = A*N*(3*Ts+Tb*(SIZE_WR+SIZE_WA+SIZE_F)) +

+ (В+1)*(Ts+Tb*SIZE_F) +

+ N_R*(B*(2*Ts+Tb*(SIZE_RR+SIZE_RA)) – A*(Ts+Tb*SIZE_F))

Пусть размеры запросов и ответов по 1 байту.

Коэффициент при N_R есть B*(2*Ts+Tb*(SIZE_RR+SIZE_RA)) – A*(Ts+Tb*SIZE_F) =

= (2*B-A)*Ts + (B*(SIZE_RR+SIZE_RA)-A*SIZE_F)*Tb = 1624.

Получили линейную функцию от N_R с положительным коэффициентом. Т.к. кворум чтения натуральное число, минимум достигается при N_R = 1. Следовательно N_W = 18.

Ответ: N_R = 1, N_W=18.

===Хорошо

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

Решение:

Каждая переменная синхронизации имеет текущего владельца — процесс, который захватил ее последним. Владелец может многократно входить в критические области и выходить из них, не посылая в сеть никаких сообщений. Процесс, не являющийся в настоящее время владельцем переменной синхронизации, но желающий захватить ее, должен послать текущему владельцу сообщение, запрашивая право собственности и текущие значения данных, ассоциированных с переменной синхронизации. (Таненбаум – «Распределенные системы»).

Кроме того, критические секции, охраняемые одной синхронизационной переменной, могут быть двух типов:

• секция с монопольным доступом (для модификации переменных);

• секция с немонопольным доступом (для чтения переменных).

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

1. Консистентность по входу - совместно используемые данные, относящиеся к данной критической области, становятся непротиворечивыми при входе в эту область (Таненбаум – «Распределенные системы», поэлементная непротиворечивость).

а) пишем в локальную память;

б) читаем из локальной памяти;

в) значения модифицируемых переменных отправляются текущем владельцем процессу, запросившему право собственности при запросе если не выполняется критическая секция, или при выходе из критической секции если она выполнялась в момент запроса;

г) блокируется пока не получим актуальные копии и право собственности на синхр. переменную;

д) при входе КУДА? широковещательно отправляем «ЗАПРОС» на синхр.переменную. Если пришел «ЗАПРОС», а мы не выдавали еще широковещательно «ЗАПРОС», отвечаем «ОК». Если мы уже выдавали, добавляем в очередь, и ждем пока получим право собственности. После выполнения критической секции, первому в очереди отправляем «ОК» + текущие значения переменных, остальным отправляем просто «ОК».

Описание алгоритма. Для получения права собственности на переменную синхронизации отправляем «ЗАПРОС» широковещательно. При получении сообщения «ЗАПРОС»:

а) Если мы ждем право собственности переменной синхронизации, то добавляем «ЗАПРОС» в очередь;

б) иначе, отвечаем «ОК».

При получении права собственности (и последних значений модифицируемых переменных) на переменную синхронизации выполняем КС. После выхода из КС отвечаем первому в очереди «ЗАПРОСу» «ОК» + последние значения модифицируемых переменных. Остальным просто «ОК».

1. Оценка времени. Допустим все 11 переменных находятся под одной переменной синхронизации. Для однократного выполнения КС одним процессом нужно 1 широковещательное сообщение «ЗАПРОС», 16 «ОК», 1 «ОК» + последние значение модифицируемых переменных. Пусть в начальный момент времени право собственности у процесса 0. Тогда он выполняет КС, потом передает право процессу 1 и т.д. Не нарушая общность рассуждений, предположим для простоты что адрес переменной занимает 1 байт, значение тоже 1 байт. Под «ЗАПРОС» и «ОК» тоже выделим по 1 байту. В сумме у нас 11+1=12 переменных. Тогда однократное выполнение КС одним процессом займет:
   T_R = Ts + SIZE_R*Tb = 101

T_OK = Ts+SIZE_OK*Tb; = 101

T_OK+Rights = Ts + (SIZE_OK + 12*(SIZE_ADDRESS+SIZE_VALUE))*Tb = 100 + (1 + 12*(1+1)) = 100 + 1 + 24 = 125

T_KS = T_R + 16*T_OK + T_OK+Rights = 101+16*101+125 = 1732

Общее количество КС 18*3=54. Т.к. в начале право собстенности уже находится у процесса 0, то он не будет рассылать «ЗАПРОС».

Ответ: Общее время: T = 53*T_KS = 53*1732 = 91796

Про критические секции монопольные и немонопольные – ни слова!

Точно, вышеуказанный алгоритм не поддерживает немонопольное владение синхр. переменной. Будем использовать централизованный алгоритм владения синхр. переменной.

Для получения права владения синхронизационной переменной, процесс посылает координатору запрос, где указывается тип права на владение: монопольно или немонопольно. У координатора есть очередь запросов. При получении запроса координатор добавляет запрос в очередь. Если очередь запросов не пуста, он дает право владения переменной всем запросам в очереди и удаляет их из очереди, пока не встретит запрос на монопольное владение. Дальше он ждет пока процессы вернут права на немонопольный доступ к синхр. переменной. Когда все процессы вернут права на немонопольный доступ, он посылает право на монопольный доступ к переменной запросу в очереди, и ждет пока он не вернет право на владение. При посылке права на владение(монопольно/ немонопольно), координатор посылает значения связанных с синхр. переменной переменных. При возвращения координатору права на монопольный доступ, значения связанных с синхр. переменной переменных также посылаются (но не при возврате немонопольного доступа).

Приведем пример:

Пусть очередь запросов следующего вида как на рис.1 (рисунки ниже). Н – запрос на немонопольный доступ. М – запрос на монопольный доступ. Координатор посылает права на немонопольный доступ первым двум запросам, удаляет их из очереди, и ждет когда они вернут эти права. В этот момент вид очереди примет вид как в рис. 2. После возвращения прав, координатор посылает право на монопольный доступ следующему запросу и удаляет его из очереди(вид как в рис. 3), после возвращения этого монопольного права, передает монопольное право следующему (вид очереди как в рис. 4). Аналогично следующим двум запросам отправляются права на немонопольный доступ и запросы удаляются из очереди (рис. 5) и т.д. (рис. 6-7).

Ответы по плану:

1. Консистентность по входу - совместно используемые данные, относящиеся к данной критической области, становятся непротиворечивыми при входе в эту область (Таненбаум – «Распределенные системы», поэлементная непротиворечивость).

2. а) пишем в локальную память;

б) читаем из локальной памяти;

в) значения модифицируемых переменных оправляется координатором запросившим процессам по мере их продвижения в очереди;

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

д) при входе в КС координатору отправляется запрос на право владения синхр. переменной в соответствующем режиме (монопольный/ немонопольный). При выходе из КС право на синхр переменную возвращается координатору (а так же значения связанных с ней переменных, если был монопольный режим).

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

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