2013 Nurmambetov_2-kr (Задачи прошлых лет)

Вариант 7

1. Сколько времени потребует выбор координатора среди 16 процессов, находящихся в узлах транспьютерной матрицы размером 4*4, если используется круговой алгоритм? Время старта равно 200, время передачи байта равно 1 (Ts=200,Tb=1). Процессорные операции, включая чтение из памяти и запись в память, считаются бесконечно быстрыми.

Решение:

Круговой алгоритм.

Алгоритм основан на использовании кольца (физического или логического). Каждый процесс знает следующего за ним в круговом списке. Когда процесс обнаруживает отсутствие координатора, он посылает следующему за ним процессу сообщение «ВЫБОРЫ» со своим номером. Если следующий процесс не отвечает, то сообщение посылается процессу, следующему за ним, и т.д., пока не найдется работающий процесс. Каждый работающий процесс добавляет в список работающих свой номер и переправляет сообщение дальше по кругу. Когда процесс обнаружит в списке свой собственный номер (круг пройден), он меняет тип сообщения на «КООРДИНАТОР» и оно проходит по кругу, извещая всех о списке работающих и координаторе (процессе с наибольшим номером в списке). После прохождения круга сообщение удаляется.

Пусть кольцо имеет следующий вид. Пусть сообщение «ВЫБОРЫ» занимает 1 байт. Под номер процесса тоже отведем 1 байт для простоты.

Процесс 0 отправляет процессу 1 «ВЫБОРЫ» + свой номер. Процесс добавляет к полученному сообщению свой номер, и отправляет процессу 2 и т.д. Для полного прохождения круга надо отправить 16 сообщений. Размер сообщения с каждым разом будет расти на 1 байт, и составит арифметическую прогрессию 2, 3, …, 17. Один круг «ВЫБОРОВ» займет T1 = (Ts+2*Tb)+(Ts+3*Tb)+…+(Ts+17*Tb)=16*Ts+152*Tb. После этого процесс 0 найдет себя в списке, обнаружит что круг пройден, выберет максимальный номер среди номеров процессов (в данном случае 15), сформулирует сообщение «КООРДИНАТОР» + номер координатора, и отправит процессу 1. Процесс 1 в свою очередь отправляет процессу 2, и т.д. Под «КООРДИНАТОР» отведем 1 байт для простоты. Тогда размер соощения будет 2 байта. Для полного прохождения круга потребуется 16 сообщений. Это займет T2=16*(Ts+2*Tb) = 16*Ts+32*Tb.

Ответ: Общее время Т = Т1+Т2 = 32*Ts+184*Tb = 32*200+184=6584.

===отлично

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

Решение:
Вводится новый вид переменной - синхронизационная переменная, связанная с общими переменными.

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

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

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

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

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

Алгоритм (децентрализованный). У каждого процесса есть своя очередь запросов на доступ к синхронизационной переменной. Запросы бывает двух типов: запрос на монопольный доступ и немонопольный доступ. Для получения права владения синхронизационной переменной, процесс выполняет неделимый широковещательный запрос с указанием типа запроса. При получении запроса, процесс добавляет запрос в очередь. Если процесс не выдавал запрос, то он отвечает на все запросы "ОК". Если процесс выдавал запрос на монопольный доступ, то отвечает всем запросам, стоящим перед ним в очереди "ОК" (себе тоже для удаления из очереди). Если процесс выдавал запрос на немонопольный доступ, то отвечает всем запросам, стоящим перед ним в очереди "ОК", а также всем стоящим после него немонопольным запросам до первого запроса в монопольным режиме. Процесс в обоих случаях отправляет "ОК" себе тоже. При отправке "ОК" какому-то запросу в очереди, этот запрос удаляется из очереди. Процесс получает право собственности на переменную в соответствующем режиме при получении «ОК» от всех процессов. При выходе из КС, процесс отправляет «ОК» всем остальным процессам в очереди. При выходе из КС, процесс, владеющий монопольным правом собственности на переменную, помимо «ОК», отправляет текущие значения переменных связанных с синхронизационной переменной, всем немонопольным запросам в очереди до первого монопольного запроса включительно. Т.е. каждый процесс имеет очередь запросов, и она продвигается аналогично очереди координатора в предыдущем алгоритме, но у каждого процесса независимо. Порядок запросов будет совпадать у всех процессов в силу неделимых широковещательных рассылок - это не так, надо было использовать неделимые широковещательные рассылки (рассчитывать на особенности коммуникаций в алгоритме нельзя – эти особенности надо учитывать только при вычислении времен!) . Да, надо использовать неделимую широковещательную рассылку.

Для разных синхронизационных переменных заводятся разные очереди.

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

2)

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

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

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

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

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

3. Оценка времени:

В этой задаче все запросы на монопольный доступ. Оценим время одного прохождения КС. Надо сделать одну широковещательную рассылку. Принять 8 «ОК» ПОЧЕМУ 8?. 8, т.к. всего 10 ЭВМ, 1 ЭВМ мы сами, осталось 9 ЭВМ. 8 из них будет просто «ОК», одно сообщение «ОК», еще плюс актуальные значения. Одно сообщение «ОК» + актуальные значения связанных переменных. Всего прохождений КС = 3*10=30. Пусть под «ОК» и тип запроса отведем по 1 байту, адрес и значение переменных тоже по 1 байту. В запросе указывается: тип запроса, и синхр. переменная (адрес и значение).

Запрос = тип запроса+адрес и значение синхр. переменной = 3 байта.

ОК = 1байт.

ОК+ актуальные значения = 1байт + 12 (ПОЧЕМУ 12? 12, т.к. 11 модифицируемых переменных + 1 синхронизационная переменная) * 2байта =25 байтов.

Итого Т = Ts + 3b*Tb + 8*(Ts+1b*Tb) + Ts + 25b*Tb = 100+3+8*(100+1)+100+25 = 1036.

Пусть в начале у процесса 0 находится монопольное право на синхр. переменную. Тогда ему не придется делать запрос и ждать ответов. ПОЧЕМУ – ведь трехкратное выполнение критической секции и модификация в ней 11 переменных каждым процессом. Если бы Вы выбрали маркерный алгоритм, тогда бы для одного процесса вход в критическую секцию не потребовал бы сообщений.

Точно, по приведенному выше алгоритму всегда делаем неделимый широковещательный запрос перед входом в КС.

1. Если предыдущий монопольный владелец синхронизационной переменной сам процесс, то не будем перессылок актуальных значений, т.к. уже имеем. Поэтому надо получить просто 9 «ОК».

2. А если предыдущий владелец другой процесс, тогда перессылок актуальных значений не избежать.

В зависимости от этого, общее время будет Т = Ts + 3b*Tb + 9*(Ts+1b*Tb) + 29*1036 = 30044 + 1012 = 31056 в первом случае, и Т = 1036*30 = 31080 во втором случае.

Тогда общее время 29*1036 = 30044.
===хорошо

Я не могу считать алгоритм правильным, есть вопрос об определении предыдущего владельца – ведь о входе в КС и выходе из нее процессы другим не сообщают. Но идея заменить логическое время на неделимые рассылки – она интересная.

Гораздо более простое решение – взять за основу маркерный алгоритм и передавать вместе с маркером требуемую информацию – очередь на вход в монопольную и немонопольную КС и количество читателей.

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

Решение:

Сначала выполняем алгоритм фиксации консистентного множества контрольных точек. Эти контрольные точки будем считать промежуточными. Исходя из определения, для того, чтобы консистентное множество точек стало строго консистентным, надо убедиться, что между процессами нет никаких сообщений. Для этого мы можем просто пропустить по всем каналам свои собственные сообщения. Если они все пройдут, значит,

каналы пусты и множество строго консистентно. Однако, стоит обратить внимание, что координатор уже посылал всем служебные сообщения, так что его каналы проверять не нужно. У нас остается 9 ЭВМ, которые хотят проверить по 8 каналов каждая. ЭВМ запоминают, по каким каналам им приходят эти служебные сообщения. Если придут по всем 8, посылают сообщение координатору с указанием того, что они

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

SM – ServiceMessage;

IM – ImplementMessage.

T1 – фиксация консистентного множества контрольных точек;
9*8*(Ts+Tb*SIZE_SM) – проверка каналов;

9*(Ts+Tb*SIZE_OK) – уведомления о готовности;

9*(Ts*Tb*SIZE_IM) – фиксация пробных точек.

Пусть все служебные сообщения занимают по 1 байту.

Ответ: T = T1 + 10*(Ts+Tb) = T1 + 1010

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

Алгоритм.

1-ая фаза

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

2-ая фаза

Инициатор информирует все процессы о своем решении. В результате либо все процессы будут иметь новые постоянные контрольные точки, либо ни один из процессов не создаст новой постоянной контрольной точки. Только после выполнения принятого процессом инициатором решения все процессы могут посылать сообщения.