Распределённые операционные системы. Задачи и ответы. (esyr) (1162821), страница 6
Текст из файла (страница 6)
Процессорные операции, включая чтение из памяти и запись в память считаются бесконечнобыстрыми.Примечание: решение не верное, лектор сказал надо использовать какой-нибудь алгоритм с маркером.Ответ: Консистентность памяти по входу (она же поэлементная в Таненбауме), закрепляет каждую разделяемую переменную за своей синхронизационной переменной. Поэтомудля изменения каждой переменной необходимо производить свой захват и освобождение синхронизационной переменной. Так как Крюков сказал, что нужны децентрализованныеалгоритмы, пользуемся таким.Для захвата переменной процесс посылает широковещ ательный запрос. Все остальные отвечают ему.
Если процесс не владеет синхронизационной переменной, то сразуотвечает ОК, если владеет, то после освобождения синх.переменной он должен послать ответ ОК и новое значение разделяемой переменной. Итого, один захватсинх.переменной требует (Ts + Tb * Lzapr) + 8 * (Ts + Tb * Lok) + (Ts + Tb * (Lok + Lv)) = 10 * Ts + Tb * (Lzapr + 9 * Lok + Lv).Все захваты для всех 11 переменных для трех критических секций для 10 ЭВМ ничем не отличаются друг от друга.
Поэтому общ ий ответ: 10 * 3 * 11 * (10 * Ts + Tb * (Lzapr + 9 * Lok +Lv)).Алгоритм Деккера[править]Какие модели консистентности памяти удовлетворяют алгоритму Деккера (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.Ответ: не слабее последовательной консистентности. При последовательной консистентности невозможно, чтобы оба процесса прочли false, читая флаги другого процесса.
Такимобразом требование того, что в критической секции не могут одновременно находиться находиться оба процесса, выполнение. Тупика тоже для модели последовательнойконсистентности не будетАлгоритм Петерсона[править]Какие модели консистентности памяти удовлетворяют алгоритму Петерсона (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.Ответ:Тема 7[править]1.
Проблемы бесконечного восстановления и потери сообщ ений. Какие методы их решения сущ ествуют? Дайте оценку накладных расходов для сети из 10 ЭВМ с шиннойорганизацией (без аппаратных возможностей широковещ ания). Время старта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байтаравно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорныеоперации, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ:open in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.com2.
Консистентное и строго консистентное множество контрольных точек и алгоритмы их фиксации. Дайте оценку накладных расходов на синхронную фиксацию строгоконсистентного множества контрольных точек для сети из 12 ЭВМ с шинной организацией (без аппаратных возможностей широковещ ания), если расходы на синхроннуюфиксацию консистентного множетва точек составляют T1. Время старта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байта равно 1(Ts=100,Tb=1).
Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Операции с файлами ипроцессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ: Сначала прогоняем синхронную фиксацию консистентного множества КТ. Это потребует T1. Эти контрольные точки будем считать промежуточными.Исходя из определения, для того, чтобы консистентное множество точек стало строго консистентным, надо убедиться, что между процессами нет никаких сообщ ений.
Для этогомы можем просто пропустить по всем каналам свои собственные сообщ ения. Если они все пройдут, значит, каналы пусты и множество строго консистентно. Однако, стоитобратить внимание, что координатор уже посылал всем служебные сообщ ения, так что его каналы проверять не нужно. У нас остается 11 ЭВМ, которые хотят проверить по 10каналов каждая.
ЭВМ запоминают, по каким каналам им приходят эти служебные сообщ ения. Если придут по всем 10, посылают сообщ ение координатору с указанием того, чтоони готовы к созданию точки. Если координатору придут все сообщ ения, он рассылает уведомление о фиксации множества.Примечание: n(n-1) - плохая оценка, надо не проверять все каналы, а просто считать отосланные сообщенияИтак, по полочкам:T = T1 // консистентное множество+ 11*10*(Ts + Tb * L) // посылка служебных сообщ ений+ 11*(Ts + Tb * L_ok) // уведомление координатора о готовности+ 11*(Ts + Tb * L_coord) // фиксация множества3.
Протоколы голосования. Алгоритмы и применение. Дайте оценку времени выполнения одним процессом 2-х операций записи и 10 операций чтения одного байта информации сфайлом, размноженным на остальных 10 ЭВМ сети с шинной организацией (без аппаратных возможностей широковещ ания). Определите оптимальные значения кворума чтения икворума записи. Время старта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1).
Доступ к шине ЭВМполучают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Операции с файлами и процессорные операции, включая чтениеиз памяти и запись в память считаются бесконечно быстрыми.Ответ:4. Алгоритм надежных и неделимых широковещ ательных рассылок сообщ ений. Дайте оценку времени выполнения одной операции рассылки для сети из 10 ЭВМ с шиннойорганизацией (без аппаратных возможностей широковещ ания).
Время старта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байтаравно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорныеоперации, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ:Прочие вкусности от лектора[править]1.
Какую модель консистентности можно реализовать в мультипроцессорах (с общ ей памятью)?Ответ:Последовательную. Строгую не можем, так как у процессоров имеется кэш.2. MPI. В синхронизационном режиме отправка сообщ ения не начинается, пока у процесса, который должен принять сообщ ение, не появится RECEIVE. А как мы это узнаем?Ответ:Процесс, в котором появился SEND, должен отправить запрос, есть ли на другом конце RECEIVE. Это должен сделать именно он, так как:1. он знает получателя (второй процесс может не знать отправителя),2.
он знает, что отправка будет производиться в синхронизационном режиме (получатель не может и не должен знать режим).3. Зачем в задаче 2.4 необходимо наличие возможности прерывания, ведь и без него, казалось бы, всё можно реализовать?Ответ:open in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comЗадачи из лекций Вали Глазковой[править]Задача 1[править]Реализовать модель причинной консистентности без сервера и упорядоченного широковещания.Если верить дядюшке Таненбауму нужен граф зависимостей операций и алгоритм его обхода.
см. "Распределенные системы", Таненбаум, глава 6, Причинная консистентность.Задача 2[править]Пример "смерти процессов" возможен для PRAM консистентонсти и невозможен для последовательной. Возможен ли он для причинной консистентности?Задача 3[править]Написать алгоритмы Деккера и Петерсона.Алгоритм Деккера (enwiki)Суть алгоритма -- не дать двум параллельным процессам одновременно войти в критическую секцию.flag[0] := falseflag[1] := falseturn := 0// or 1p0:p1:flag[0] := truewhile flag[1]=trueif turn ≠ 0 {flag[0] :=while turn}flag[0] :=}}{false≠ 0 {true// critical section...// remainder sectionturn := 1flag[0] := falseАлгоритм Петерсона (enwikiflag[0]flag[1]turnflag[1] := truewhile flag[0]=true {if turn ≠ 1 {flag[1] := falsewhile turn ≠ 1 {}flag[1] := true}}// critical section...// remainder sectionturn := 0flag[1] := false)= 0= 0= 0P0: flag[0] = 1turn = 1while( flag[1] && turn == 1 );// do nothing// critical section...// end of critical sectionflag[0] = 0P1: flag[1] = 1turn = 0while( flag[0] && turn == 0 );// do nothing// critical section...// end of critical sectionflag[1] = 0Задача 4[править]Читатель не должен читать сырые данные.
Читать могут сразу много. Писать – только один.Int rd = 0; // количество читателейSemaphore access = 1;Semaphore reader = 1;// семафор для читателейopen in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comSemaphore reader = 1;Semaphore writer = 1;// семафор для читателей// семафор для писателейVoid writer_enter(){// мы должны дождаться, пока другие писатели закончат писатьP(writer);}// мы должны удостовериться, что в этот момент нет никаких читалелейP(reader);Void writer_leave(){V(reader);V(writer);}Void reader_enter(){P(writer);// а нет ли внутри писателя?// критическая секцияP(access);Rd++;If(rd == 1) P(reader);V(access);V(writer);// теперь писатель будет знать, что кто-то читает}Void reader_leave ( ) {P(access);Rd--;If(rd == 0) V(reader); // теперь писатель будет знать, что никто больше не читаетV(access);}Задача 5[править]Какого размера должен быть квант информации, чтобы минимизировать время передачи в конвейере?Можно выписать общ ую формулу.
Пусть P - длина пути, L - исходная длина сообщ ения, N - длина единичного куска, на который мы бьем сообщ ения.Тогда время передачи будет равно:. Первая часть - время прохода первого куска (разгон конвейера), вторая - времяпередачи остальных кусков. По сути - если мы бьем на очень мелкие куски, то слишком часто будет запускаться процесс передачи и очень часто будет возникать Ts, если оченьбольшие куски - очень большой множитель будет перед Tb .
Дифференцированием по N находим оптимум. Не забываем при этом, что исходное выражение можно таким образомпустить по двум путям (или больше) и разбивать уже нужно тогда не L, а, где K - число непересекающ ихся путей.Ссылки[править]Реализация считающ их семафоров с помощ ью двоичныхАлгоритм Деккера и модели консистентности памятимануал по MPIРаспределённые операционные системы01 02 03 04 05 06 07 08 09 10 11 12 13 14 15Календарьпт пт пт пт птФевральМарт08 15 22 2906 13 20 27Апрель 04 11 18 25open in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comМай0216 23Ответы на задачинавигацияЗаглав ная страницаНов остиУказательФронт работВнешние ресурсыинструментыСв ежие прав киСлучайная статьяразделыЛекцииLinuxmsu_cmcспецкурсыСов ременнаякриптографияДизайн и реализацияОС FreeBSD9 семестрФСВПТеория игры и ИОИстория математикиРоссийское прав оИстория религииПОД7 семестрВычислительныесистемыООАиПИИМатематическаялогикаФункциональныйанализСоциологияПараллельнаяобработка данных5 семестрБазы данныхЯзыкипрограммиров анияЭкономические Наукиopen in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.com3 семестрОперационныесистемыпоискПерейтиНайтиинструментыСсылки сюдаСв язанные прав киЗагрузить файлСпецстраницыВерсия для печатиПостоянная ссылкаПоследнее изменение этой страницы: 18:00, 3 июня 2013.К этой странице обращались 70 693 раза.Политика конфиденциальностиОписание eSyr's w ikiОтказ ототв етств енностиopen in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.com.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
