Задачи 2013 года

Задача 1.Последовательная консистентность.1) ОпределениеПри параллельном выполнении, все процессы должны «видеть» одну и ту жепоследовательность записей в память.2) АлгоритмПробую нецентрализованный – используется надежный неделимый широковещательныйалгоритм:1) при записи – отправить всем информацию о записи, дождаться, пока все пришлютлогическое время, выбрать максимальное время и отправить его всем; выполнитьзапись, только если запись стала первой в очереди модификаций2) при чтении – проверить, что пришли подтверждения о всех предыдущих операцияхзаписи данного процесса3) если пришло от кого-то сообщение о записи – посмотреть логическое время иотправить логическое время процессу-отправителю; сообщение указать как«недоставленное» и установить в очередь; когда пришло сообщение о конечномлогическом времени от процесса-отправителя, уточнить очередь сообщения; еслипервое сообщение в очереди стало «доступным» - выполнить запись4) процесс может продолжать выполнение работы, при этом он блокируется приследующей операции чтения/записи общей переменной, пока не будет выполненатекущая операция записиЦентрализованный алгоритм:1) при записи – отправить сообщение о записи координатору, ждет реакциюкоординатора; когда пришло подтверждение – обновить переменную2) при чтении – убедиться, что предыдущие записи прошли3) если пришла информация о модификации – модифицировать переменную4) блокироваться при ожидании сообщения от координатора (можно выполнятьработу до следующего чтения/записи, видимо)3) Для нецентрализованного алгоритм:- для каждой модификации: 9 рассылок, 9 приемов и еще 9 рассылок – 27сообщений, итого 10(27 Ts + 9 send Tb + 9 ans Tb + 9 resend Tb)Для централизованного:Для каждой модификации: 1 сообщение-запрос + 10 сообщений о модификацииИтого 10(11Ts + req Tb + 10 ans Tb)Задача 2.Причинная консистентность памяти1) Последовательность операций записи, которые потенциально причинно зависимы,должна наблюдаться всеми процессами системы одинаково, параллельные операциизаписи могут наблюдаться разными узлами в разном порядке».2) Алгоритм:Каждая модификация нумеруется.

В каждом процессе хранятся номеру всех известныхмодификаций других процессов1) при записи – если есть информация о модификациях, которые еще непроведены, то блокируемся до прихода сообщений с модификацией; отсылаеммодификацию и все известные ранее модификации всем процессам2) при чтении – без блокировок3) если пришла информация о записи, то модификация откладывается до тогомомента, как все модификации не осуществятся4) блокировки – при модификациях, если какие-то другие модификации еще невыполнены3) - Нулевой нумерует свое сообщение, отсылает его всем – 9(Ts + a Tb)- второй нумерует свое сообщение, добавляет информацию о сообщении нулевого,отсылает всем – 9(Ts + a Tb)…Итого: 10*9(Ts + a Tb)Задача 3.Процессорная консистентность:1) «Для каждой переменной x есть общее согласие относительно порядка, в которомпроцессоры модифицируют эту переменную, операции записи в разные переменные параллельны»2) Алгоритм:Все очень тупо – у каждого процесса – своя переменная, он нумерует изменения, отсылаетвсем модификацию1) при записи – отсылаем информацию о модификации переменной процессувладельцу, ждем, когда он вернет сообщение о модификации переменной2) при чтении – без блокировок3) если процесс – владелец переменной, то при получении сообщении омодификации отсылает всем информацию о модификации; если пришлопозднее сообщение о модификации (у него слишком большой номер и мы чтото пропустили), то процесс блокируется и ждет недостающих модификаций4) блокировка – при ожидании ответа от процесса-владельца3) Вариант, когда каждый из процессов модифицирует переменную, которой владеет;получается, что только отсылается сообщение о модификации остальным процессам,время: 9 (Ts + a Tb).Задача 4.PRAM консистентность.1) «Операции записи, выполняемые одним процессором, видны всем остальнымпроцессорам в том порядке, в каком они выполнялись, но операции записи, выполняемыеразными процессорами, могут быть видны в произвольном порядке».2) Алгоритм:Выстраиваем операции модификации в конвеер, можем не ждать окончания операции,надо только быть уверенным, что модификацию увидят все в одном порядке1) при записи – ставим сообщение о модификации в конвеер, продолжаем работу;сообщение посылается, если пришло подтверждение о предыдущеймодификации ( подтверждения гарантируются протоколом передачи)2) при чтении – без блокировки3) блокировок нет3) 3 раза модифицируют переменную.

3 раза надо послать сообщение о модификациикаждым процессом. Итого3*10(Ts + a Tb) (a – длина сообщения)Задача 5.Слабая консистентность.1) Основана на выделении среди переменных специальных синхронизационныхпеременных (доступ к которым производится специальной операцией синхронизациипамяти) и описывается следующими правилами:1. Доступ к синхронизационным переменным определяется моделью последовательнойконсистентности;2. Доступ к синхронизационным переменным запрещен (задерживается), пока невыполнены все предыдущие операции записи;3.

Доступ к данным (запись, чтение) запрещен, пока не выполнены все предыдущиеобращения к синхронизационным переменным.2) Алгоритм:Исходит из того, что доступ к синхронизационным переменным определяется модельюпоследовательной консистенции: все модификации делаются без отправки сообщений(запоминаются где-то), при вызове операции синхронизации все остальные процессыдолжны узнать о всех модификациях данного процесса, при этом синхронизации должныбыть видны всеми процессами в одинаковом порядке. Для этого можно использоватьцентрализованныйалгоритм(неинтересно)илинадежныйинеделимыйшироковещательный алгоритм (ниже его использую):1) при записи переменной – запомнить щапись в буфере2) при чтении – без блокировки3)при вызове синхронизации: отправить всем сообщение о всех модификацияхпеременных, дождаться, пока не вернутся логические времена приемасообщений, далее выбрать наибольшее время и отправить его всем –модификация считается отправленной; все модификации выстроить в очередь,когда первое сообщение станет отправленной, можно ее применить ипродолжить работу;4) если пришло сообщение о модификациях – отправить процессу-отправителюсообщение с логическим временем, когда он пришлет сообщение смаксимальным логическим временем – подтвердить сообщение и выставить егов очередь; если оно первое – то можно его применить; блокировки при этомнету, только при выполнении операции синхронизации5) блокировка – при синхронизации, пока она не выполнится3) 1 процесс меняет 10 переменных (операций коммуникации нет), затем меняет 3синхронизационные переменные.

На каждую такую смену – шлем сообщение всем,принимаем сообщение от всех (с логическим временем), отсылаем сообщение всем (смаксимальным логическим временем). Итого: 3*9(3Ts + send Tb + resv Tb + resend Tb)Задача 6.Консистентность по выходу.1) Две ситуации: вход в критическую секцию и выход из нее.(1) До выполнения обращения к общей переменной, должны быть полностьювыполнены все предыдущие захваты синхронизационных переменных даннымпроцессором.(2) Перед освобождением синхронизационной переменной должны быть закончены всеоперации чтения/записи, выполнявшиеся процессором прежде.(3) Реализация операций захвата и освобождения синхронизационной переменнойдолжныудовлетворятьтребованиямпроцессорнойконсистентности(последовательная консистентность не требуется, захваты разных переменныхосуществляются параллельно).2) Алгоритм:Фактически, используется маркер, в котором хранится информация о модификациях.Маркер присутствует у процесса, который выполнил последние преобразования скритической секцией (или выполняет).

Все преобразования заносятся в маркер. Лениваяреализация: после преобразований процесс не отсылает результаты, а передает их потребованию. Процесс, которому нужен доступ в секцию, отсылает запрос о маркере.1) при записи обычной (несинхранизационной) переменной – запись в локальнуюпамять2) при чтении – из локальной памяти3) выход из критической секции – запись всех модификаций в маркер4) вход в критическую секцию – запрос маркера у всех процессов, блокировка допоявления маркера5) если пришел запрос о маркере – запоминается6) блокировка – только при входе в критическую секцию3) Каждый процесс 3 раза отсылает запрос на маркер всем (возможна реализация, когдакаждый процесс 3 раза выполняет критическую секцию, после чего только выполняетпередачу маркера).

Каждый процесс 3 раза передает маркер. Итого:3*9 * 10 (Ts + req Tb) + 3 * 10 (Ts + resp Tb)(в реализации с 3мя последовательными заходами в Крит секцию – в 3 раза меньше)З.Ы. в данном решении не учитываются аппаратные возможности широковещания, ихможно легко учесть – поделить на 9 первое слагаемое, кажется)Задача 7.Консистенция по входу.1) Связана с захватом критической секции.(1) Процесс не может захватить синхронизационную переменную до того, пока необновлены все переменные этого процесса, охраняемые захватываемойсинхронизационной переменной;(2) Процесс не может захватить синхронизационную переменную в монопольномрежиме (для модификации охраняемых данных), пока другой процесс, владеющийэтой переменной (даже в немонопольном режиме), не освободит ее;(3) Если какой-то процесс захватил синхронизационную переменную в монопольномрежиме, то ни один процесс не сможет ее захватить даже в немонопольном режимедо тех пор, пока первый процесс не освободит эту переменную, и будут обновленытекущие значения охраняемых переменных в процессе, запрашивающемсинхронизационную переменную.2) Тут опять маркер.

Реализация почти как в предыдущем алгоритме, только с каждойсинхронизационной переменной связан свой маркер и в нем хранятся модификацииопределенных переменных (т.к. с каждой синхронизационной переменной связаны своипеременные). Если процесс хочет захватить переменную в немонопольном режиме, тождет сообщения от владельца переменной (хотя бы одного). Если в монопольном, тонужен ответ от всех процессов (либо ок, либо маркер).1) запись – из локальной памяти2) чтение – из локальной памяти3) захват переменной в немонопольный режим – шлем всем сообщение«немонопольный захват», ждем маркер4) захват в монопольном режиме – шлем всем сообщение «монопольный захват»,ждем ответа от всех5) если пришел «монопольный захват», то шлем «ок», если маркера нет и маркернам не нужен (если нужен – ждем маркер и потом отправляем), либо шлем маркер повозможности6) если пришло «немонопольный захват», то, если у нас есть маркер и мынемонопольно владеем им, то шлем копию маркера запросившему7) при каждом запросе «монопольный захват» или «немонопольный захват»блокировка до получения необходимых ответов8) выход из секции – модифицируем маркер3) 3 раза крит.

секция, каждый шлет всем сообщение о запросе крит. секции. Далее всеотвечают (т.к. монопольная модификация). И одно сообщение на передачу маркера.Итого:3*(9)*10*(Ts + req * Tb) + 3*9*10*(Ts + resp*Tb) + 3*10(Ts + marker*Tb)З.Ы. девятки убираются при широковещательной шине, тройки убираются, еслипоследовательно входим в критические секции на каждом процессе.Тема 7.Задача 1.Надежный и неделимый широковещательный алгоритм:В каждом процессоре – очередь поступающих сообщений.

Идентификатор – логическоевремя прибытия (всегда разное).1) Отправляется сообщение группе процессов (в сообщении хранятся идентификаторыпроцессов!)При приеме:- помечается как «недоставленное», в качестве приоритета – временная метка- информируется отправитель о присланном сообщении и о текущем логическомвремени2) Получает ответы от всех адресатов- выбирает из присланных сообщений максимальный приоритет- рассылает всем этот приоритетПри приеме:- сообщение устанавливается как «доставленное»- если оно становится первым в очереди, то выполняется3) При обнаружении недоставленного сообщения (отправитель сломался) выполняетсяследующее:- отправляем всем соседям «запрос» о данном сообщении- все отвечают, у кого-то есть «доставленное» - приоритет посылается всем- нету доставленного -> начинаем заново (шлем всем, ждем отметок о времени).Решение задачи:- 5 сообщений посылается, после чего падает отправитель- 5 сообщений с временными метками возвращается- таймаут- 9 сообщений от какого-нибудь процесса о времени- 9 ответов о том, что «недоставлено» или нету- 9 сообщений-запросов- 9 ответов с временем- 9 сообщений с финальным временемИтого:55*Ts + 14*req*Tb + 9*ask*Tb + 9*ans*Tb + 9*time*Tb + 9*final*TbReq – сообщения запросы (например, 9 байт с идентификаторами, 1 полезный байт)Ask – сообщения вопрос типа «есть ли у кого-нибудь доставленное сообщение?» (1 байт сномером сообщения, 1 байт с полезной инфой)Ans – Ответы на вопрос (нету или недоставлено)Time – сообщения с логическим временемFinal – финальное сообщение с итоговым логическим временемЗадача 3.Консистентное и строго консистентное множества контрольных точек.1.