Распределённые операционные системы. Задачи и ответы. (esyr) (1158846), страница 5
Текст из файла (страница 5)
Запрос может получить одобрение у половины серверов плюс один.При этом должно быть согласие относительно номера текущ ей версии файла. Этот номер увеличивается на единицу с каждой коррекцией файла. Можно использоватьразличные значения для кворума чтения (Nr) и кворума записи (Nw). При этом должно выполняться соотношение Nr+Nw>N. Поскольку чтение является более частойоперацией, то естественно взять Nr=1.
Однако в этом случае для кворума записи потребуются все серверы.Тема 6 (задачи на консистентность)[править]Общий хинт - в Таненбауме "Распределенные системы" расписано, как реализуется та или иная консистентность в главе 6. Нужно аккуратно посмотреть какие и кудаopen in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comбудут пересылки сообщений при такой консистентности.При ответах на вопросы по теме 6 следовать следующему плану.1. Определение модели консистентности.2.
Алгоритм реализации в DSM с полным размножением (много писателей и много читателей, каждый из которых имеет свою копию всех переменных). Алгоритм должен бытькорректным для любой коммуникационной сети и обеспечивать высокую эффективность для конкретной сети, указанной в задаче. Описание алгоритма должно содержатьответы на следующ ие вопросы:что делается при записи;что делается при чтении;когда, кому и как рассылаются значения модифицируемых переменных;блокируется ли процесс на время выполнения записи или рассылки значений переменных;если речь идет о моделях консистентности, связанных с синхронизацией, то объяснить алгоритм синхронизации (например, алгоритм входа в КС и выхода из нее).3.
Оценить время работы описанного в пункте 2 алгоритма применительно к конкретной задаче.Последовательная[править]Последовательная консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация 10 различных переменных 10-юпроцессами (каждый процесс модифицирует одну переменную), находящ имися на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещ ания) иодновременно выдавшими запрос на модификацию. Время старта (время разгона после получения доступа к шине) равно 100, время передачи байта равно 1 (Ts=100,Tb=1).Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ).
Процессорные операции, включая чтение изпамяти и запись в память считаются бесконечно быстрыми.Ответ:Причинная[править]Причинная консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация 10 различных переменных, если все 10процессов (каждый процесс модифицирует одну переменную), находящ ихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещ ания),одновременно выдали запрос на модификацию своей переменной. Время старта (время разгона после получения доступа к шине) равно 100, время передачи байта равно 1(Ts=100,Tb=1).
Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции,включая чтение из памяти и запись в память считаются бесконечно быстрыми. Никаких сведений от компилятора о причинной зависимости операций модификации не имеется.Ответ:PRAM[править]PRAM консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует 3-кратная модификация 10 различных переменных, если все10 процессов (каждый процесс 3 раза модифицирует одну переменную), находящ ихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностейшироковещ ания), одновременно выдали запрос на модификацию.
Время старта (время разгона после получения доступа к шине) равно 100, время передачи байта равно 1(Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции,включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ: Семантике PRAM консистентности больше соответствует алгоритм с координатором — при записи в переменную соответствующ ий процесс посылает изменениекоординатору, а сам продолжает работу.
Тем не менее, поскольку записи одного процесса должны видеться всеми остальными процессами в одном порядке, придётся учитыватьи время рассылки обновлений от координатора к остальным процессам. Итак, если процесс, изменяющ ий переменную, не совпадает с координатором, то при каждом изменениипеременной потребуется (Ts + Tb * l1 ) на отправку изменённого значения координатору и ещ ё (N − 2) * (Ts + Tb * l2 ) на рассылку нового значения остальным процессам откоординатора (где N — число процессов; процессу, изначально изменившему переменную, и координатору не надо рассылать новое значение по шине).
Если же процессмодификатор переменной совпадает с координатором, то (Ts + Tb * l1 ) уже не нужно, зато нужно (N − 1) * (Ts + Tb * l2 ) на рассылку. Ещ ё необходимо учесть, что каждый процессменяет переменную трижды. Итого получаетсяopen in browser PRO versionAre you a developer? Try out the HTML to PDF API, т.е.pdfcrowd.com.Алгоритм без координатора также возможен — в этом случае процессу-модификатору самому необходимо рассылать остальным N-1 процессам новые значения переменнойпосле её модификации. Всего в этом случае потребуется 3 * N * (N − 1) * (Ts + Tb * l2 ).Процессорная[править]Процессорная консистентность памяти и алгоритм ее реализации в DSM с полным размножением.
Сколько времени потребует модификация 10 различных переменных, если все10 процессов (каждый процесс модифицирует одну переменную), находящ ихся на разных ЭВМ сети с шинной организацией (без аппаратных возможностей широковещ ания),одновременно выдали запрос на модификацию своей переменной. Время старта (время разгона после получения доступа к шине) равно 100, время передачи байта равно 1(Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно в порядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ).
Процессорные операции,включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ: Поскольку процессорная консистентность — это PRAM + когерентность памяти, то нам необходимо, чтобы процессы, прежде чем редактировать переменные, сначалапосылали запросы к коррдинатору, а уже после согласия коодинатора изменяли их (важно!). Затем, в реализации процессорной консистентности нам не обойтись безкоординаторов, в результате получаем два случая: когда у каждой переменной по координатору и когда 1 координатор отвечает за все переменные.1 случай: много координаторов.
Предположим, что для каждой переменной тот процесс, который её изменяет, является её же координатором. Тогда, процессам не нобходимопосылать никакие запросы (всё это происходит внутри процесса), необходимо только уведомлять другие процессы о совершенных изменениях. В итоге получаем: каждый из Nпроцессов рассылает остальным (N-1) процессам уведомления об изменениях.
Ответ: N * (N − 1) * (Ts + Tb * L)2 случай: 1 координатор. Итак, если процесс, изменяющ ий переменную, не совпадает с координатором, то посл-ть такова: при запросе записи в переменную соответствующ ийпроцесс посылает сообщ ение координатору, (Ts + Tb * Lzapr), затем получает подтверждение от него (Ts + Tb * Lok), процесс изменяет переменную и шлёт изменение координатору(Ts + Tb * Lnew2coord ), а тот уже рассылает остальным изменения: (N − 2) * (Ts + Tb * Lnew2all). Если же процесс-модификатор переменной совпадает с координатором, то требуетсятолько уведомление остальных процессов об изменении переменной: (N − 1) * (Ts + Tb * Lnew2all) на рассылку.
Суммируем, и, учитывая кол-во процессов, получаем:и (N − 1) * (Ts + Tb * Lnew2all).Ответ:.Слабая[править]Слабая консистентность памяти и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует модификация одним процессом 10 обычных переменных, азатем 3-х различных синхронизационных переменных, если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратными возможностями широковещ ания). Времястарта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно впорядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечнобыстрыми.Ответ:По выходу[править]Консистентность памяти по выходу и алгоритм ее реализации в DSM с полным размножением.
Сколько времени потребует трехкратное выполнение критической секции имодификация в ней 10 переменных каждым процессом , если DSM реализована на 10 ЭВМ сети с шинной организацией (с аппаратными возможностями широковещ ания). Времястарта (время разгона после получения доступа к шине для передачи) равно 100, время передачи байта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно впорядке выдачи запроса (при одновременных запросах - в порядке номеров ЭВМ). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечнобыстрыми.Ответ: У нас 10 ЭВМ.
Широковещ ательный доступ. Консистентность по входу - мы можем как угодно разбить переменные на блоки, которые будут защ ищ атьсясинх.переменными. Поэтому, пусть критическая секция будет под одной переменной.open in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comПри захвате переменной ЭВМ посылает всем широковещ ательный запрос на захват. Все должны ответить ОК. Тогда переменная наша и можно все менять.Если переменная у нас, то собираем очередь запросов. ЗАкончили работу, теперь надо сделать широковещ ательную рассылку новых данных.
И только после этого послылаемсообщ ение первому в очереди с ОК и (как мне кажется) передаем ему очередь запросов.(Ts + Tb * Lzapr) + // запрос9 * (Ts + Tb * Lok) + //все должны ответить(Ts + Tb * Lv)// время на синхронизацию на выходе.Итого: 10 * 3 * (10 * Ts + Tb * (Lzapr + 9 * Lok + Lv))По входу[править]Консистентность памяти по входу и алгоритм ее реализации в DSM с полным размножением. Сколько времени потребует трехкратное выполнение критической секции имодификация в ней 11 переменных каждым процессом, если DSM реализована на 10 ЭВМ сети с шинной организацией(с аппаратными возможностями широковещ ания).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
