(2016) Ответы (1162879), страница 6

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

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

Потом второй процесс в сообщении, помимо модификации, прикрепляетчто ему известна модификация первого процесса. Третьему известны модификациипервого и второго процессов и т.д. Каждый процесс рассылает по 9 сообщений – почислу процессов. Пусть под адрес и значение переменной отведем по 1 байту. Подномер модификации – тоже 1 байт. Под номер процессора, которому принадлежитмодификация – тоже 1 байт. Тогда размер сообщения 1-го процесса – 2 байта, второго –4, третьего – 6 и т.д.Размер десятого – 20 байт.

Соответственно времена:Т1 = 9*(Ts+2*Tb)T2 = 9*(Ts+4*Tb)………..T10 = 9*(Ts+20*Tb)Общее время Т = Т1+….+Т10 = 9*(10*Ts+110*Tb) = 9*(1000+110) = 9*1110 = 9990.3.Процессорная консистентность памяти и алгоритм ее реализации в DSM сполным размножением. Сколько времени потребует модификация 10 различныхпеременных, если все 10 процессов (каждый процесс модифицирует однупеременную), находящихся на разных ЭВМ сети с шинной организацией (безаппаратных возможностей широковещания), одновременно выдали запрос намодификацию своей переменной. Время старта (время «разгона» послеполучения доступа к шине для передачи сообщения) равно 100, время передачибайта равно 1 (Ts=100,Tb=1).

Доступ к шине ЭВМ получают последовательно впорядке выдачи запроса на передачу (при одновременных запросах – в порядкеномеров ЭВМ). Процессорные операции, включая чтение из памяти и запись впамять, считаются бесконечно быстрыми.1) Процессорная консистентность – каждый процессор видит модификации,производимые одним процессором, в том же порядке, как они были произведены.Кроме того для каждой переменной x есть общее согласие относительно порядка, вкотором процессоры модифицируют эту переменную, операции записи в разныепеременные – параллельны.2) Сам алгоритм. За каждую группу переменных отвечает свой координатор, которыйполучает от процессов запросы на модификацию и рассылает всем указания опроведении модификации. Чтобы не нарушить порядок получения процессамиуказаний о модификациях различных переменных, запрошенных одним процессому разных координаторов, надо каждому процессу нумеровать свои модификации, иэти номера должны рассылаться всем вместе с указаниями о проведениимодификаций.

Тогда любой процесс, получающий указание о проведениимодификации, может задержать его выполнение до получения недостающихуказаний о предшествующих модификациях соответствующего процесса.a) при записи координатору, который отвечает за данную переменную,отправляется запрос на модификацию;b) при чтении происходит чтение из локальной памяти;c) координатор принимает запросы на модификацию и рассылает всемуказания о проведении модификации;d) на время выполнения записи или рассылки значений переменных процессблокируется и ждет получения указания от координатора о модификации.3) Оценка времени.Пусть каждый процессор отвечает за одну переменную.1 вариант. Пусть координатором переменной, которую изменяет данный процессорне является он сам, т.е.

для каждого процессора координатором изменяемой импеременной является другой процессор. Так как в случае, если координаторизменяет свою переменную, задача сводится к простой рассылке модификаций. Унас все переменные разные, поэтому можно в них записывать параллельно.Рассмотрим время выполнения одной модификации. Сначала координаторуотправляется запрос на модификацию. Он рассылает указания о проведениямодификации (всем, кроме себя).

В запросе на модификацию содержится адреспеременной, ее значение, номер модификации. Координатор может прикреплять куказаниям о модификации номера процессов, запросивших эти модификации, чтобыможно было различать модификации с одинаковыми номерами различныхпроцессов. Время модификации = время запроса + время рассылки:T​M​ = T​R​ + 9*T​MD​,M – Modification;R – Request;MD – ModificationDirective.T​R​ = Ts + SIZE​R​*Tb;T​MD​ = Ts + SIZE​MD​*Tb;Для простоты, пусть под адрес переменной, значение переменной, номермодификации отведем по 1 байту.

Тогда SIZE​R = 3 байта. Под номер процессаотведем тоже 1 байт. SIZE​MD​ = 4 байта. Так как у нас 10 модификаций, общее время:T = 10*T​M = 10*(T​R + 9*T​MD​) = 10*(Ts + 3*Tb + 9*(Ts+4*Tb)) = 10*(10*Ts + 39*Tb) =10390.2 вариант. Каждый из процессов модифицирует переменную, которой владеет;получается, что только отсылается сообщение о модификации остальным процессам:T​R​ = 0;T = 10*T​M​ = 10*(T​R​ + 9*T​MD​) = 90*(Ts + SIZE​MD​*Tb) = 90*(100 + 4) = 9360.4.PRAM консистентность памяти и алгоритм ее реализации в DSM с полнымразмножением. Сколько времени потребует 3-кратная модификация 10различных переменных, если все 10 процессов (каждый процесс 3 разамодифицирует одну переменную), находящихся на разных ЭВМ сети с шиннойорганизацией (без аппаратных возможностей широковещания), одновременновыдали запрос на модификацию.

Время старта (время «разгона» послеполучения доступа к шине для передачи сообщения) равно 100, время передачибайта равно 1 (Ts=100,Tb=1). Доступ к шине ЭВМ получают последовательно впорядке выдачи запроса на передачу (при одновременных запросах – в порядкеномеров ЭВМ). Процессорные операции, включая чтение из памяти и запись впамять, считаются бесконечно быстрыми.1) Операции записи, выполняемые одним процессором, видны всем остальнымпроцессорам в том порядке, в каком они выполнялись, но операции записи,выполняемые разными процессорами, могут быть видны в произвольном порядке.2) Алгоритм: выстраиваем операции модификации в конвейер, можем не ждатьокончания операции, надо только быть уверенным, что модификацию увидят все водном порядке.a) при записи – ставим сообщение о модификации в конвейер, продолжаемработу; сообщение посылается, если пришло подтверждение о предыдущеймодификации (подтверждения гарантируются протоколом передачи);b) чтение – из локальной памяти;c) значения модифицируемых переменных рассылаются другим процессам приизменении (записи) переменных;d) блокировок нет.3) 3 раза модифицируют переменную.

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

Процессорные операции, включая чтение из памяти и запись впамять, считаются бесконечно быстрыми.1) При слабой консистентности соблюдается последовательная непротиворечивостьмежду группами операций, а не между отдельными операциями. Для выделенияэтих групп используются переменные синхронизации (Таненбаум –«Распределенные системы», слабая непротиворечивость).Модель слабой консистентности имеет три свойства:1.

Доступ к синхронизационным переменным определяется модельюпоследовательной консистентности;2. Доступ к синхронизационным переменным запрещен (задерживается), покане выполнены все предыдущие операции записи;3. Доступ к данным (запись, чтение) запрещен, пока не выполнены всепредыдущие обращения к синхронизационным переменным.2) См. пп. e)a) запись происходит в локальную память;b) чтение происходит из локальной памяти;c) при вызове операции синхронизации значения модифицируемыхпеременных рассылаются всем;d) процесс, вызвавший операцию синхронизации, блокируется пока незавершится операция синхронизации;e) Алгоритм.

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

В сообщении содержатся адреса переменных и их значения. Ненарушая общность рассуждений, для простоты отведем под адрес и значение по 1байту. Тогда первая синхронизация займет T​S1 = Ts + 10*(SIZE​ADDRESS +SIZE​VALUE​)*Tb = 120. Т.к. после первой синхронизации ничего не модифицировали,можем не делать широковещательную рассылку, т.к. в силу данного алгоритма причтении всегда имеем актуальные копии (то, которое записал какой-то процесс,успевший сообщить об этом всем посредством синхронизации памяти, а если неимели бы актуальные копии, то пришлось бы их доставать). Поэтому при вызовеоперации синхронизации имеет смысл делать широковещательную рассылкутолько при наличии модификации после предыдущего вызова операциисинхронизации.

Т.е. при вызове остальных синхронизации не будет никакихобменов сообщениями.Ответ: Общее время T = T​S1​ = 120.Дополнительные вопросы.1. Как определяются переменные, которые модифицировались?Модифицированные переменные можно определить двумя способами:a. С помощью компилятора, т.е. компилятор вместо операций присваиванияможет вставлять вызовы определенных функций;b. Запоминать старые значения переменных и потом сравнивать. В данномслучае можно каждый раз сразу же после операции синхронизацииобновлять значения запомненных переменных и при вызове сравниватьтекущие значения переменных с запомненными. Если есть расхождение, торассылать текущие значения переменных, если нет расхождений, то ничегоделать. Т.о. перечень действий при вызове операции синхронизации:i.сравнить текущие значения с сохраненными;ii.если есть расхождения, то разослать текущие значения переменных,которые расходятся, а также обновить значения сохраненныхпеременных.2.

Если при синхронизации в процессе А все измененные им переменныерассылались всем, то зачем процессу Б требуется перед чтением переменнойдавать операцию синхронизации?Компилятор может хранить значения переменных на регистрах, в кэше и т.д.,обновить их другие процессы не могут, поэтому операция синхронизации передчтением нужна, чтобы компилятор обновил такие значения (а в его памяти онибудут обновлены при выполнении операциях синхронизации, выданныхдругими процессами).6.Консистентность памяти по выходу и алгоритм ее реализации в DSM с полнымразмножением.

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

Доступ к шине ЭВМ получают последовательно впорядке выдачи запроса на передачу (при одновременных запросах – в порядкеномеров ЭВМ). Процессорные операции, включая чтение из памяти и запись впамять, считаются бесконечно быстрыми.1) Консистентность по выходу - совместно используемые данные становятсянепротиворечивыми после выхода из критической секции. В моделиконсистентности по выходу введены специальные функции обращения ксинхронизационным переменным: ACQUIRE - захват синхронизационнойпеременной, информирует систему о входе в критическую секцию; RELEASE освобождениесинхронизационнойпеременной,определяет завершениекритической секции. Захват и освобождение используются для организациидоступа не ко всем общим переменным, а только к тем, которые защищаютсяданной синхронизационной переменной.

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

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