(2016) Ответы

Распределённые системыЛекторы: Крюков Виктор Алексеевич, Бахтин Владимир АлександровичДок собрали Синельников И., Клюшкина Е.Спасибо всем, кто помог с составлением этого дока!При большом количестве народа док может лагать, поэтому скачайте его передэкзаменом (Файл -> Скачать как).Если при ответе возникнут замечания к решениям, пишите, пожалуйста,комментарии. И заносите дополнительные вопросы, если будут.Ссылкиhttp://sp.cmc.msu.ru/courses/os/Всё, что нужно: ​https://goo.gl/Cjhq9GЛекции в одном файле: ​https://goo.gl/4nBWKHМодели консистентности (кратко): ​https://goo.gl/9a0REhАльтернативный док (NSFW на стр. 12): ​https://goo.gl/UovBS9esyr.org: ​esyr.org wikiМатериалы в гугл диске: ​https://goo.gl/CjbVtwПроцедура экзамена1. В билете 2 вопроса.

На подготовку 1 час.Далее отвечаете на билет, получаете дополнительные вопросы.2. Вопросы 2014 года актуальны.3. Можно пользоваться любыми материалами, но только при подготовке кответу.Тема-11.Какиеаппаратныемеханизмынеобходимыдляорганизациимультипрограммного режима? Как обеспечить мультипрограммный режим безэтих механизмов? Как обеспечить, если отсутствует только один из этихмеханизмов?Требуются: защита памяти, прерывания, привилегированный режим, таймер.Если нет таких механизмов, то можно использовать виртуальную машину - единыйинтерпретатор, исполняющий программы пользователей и обеспечивающий эмуляциювсех этих механизмов.Если отсутствует только один из перечисленных механизмов, можно обойтись безполной эмуляции. Например, защиту памяти будет осуществлять компилятор, причём онможет проверять не всякое обращение, а один раз проверить корректность какого-либоиндекса или указателя на область памяти, а затем использовать его без проверок.Другой пример: если нет таймера, вместо полной эмуляции и увеличения счётчикапри каждой команде можно увеличивать счётчик сразу на несколько единиц (например, надлину цикла).Тема-2При решении задач по теме 2 обратить внимание на следующее.1.

Нельзя модифицировать общие переменные вне КС.2. При наличии вложенных КС или запросов нескольких семафоров необходимоубедиться, что не могут возникнуть тупики.3. Нельзя обращаться к семафорам и событиям обычными операторами – толькопосредством операций, которые определены над ними (P, V, POST, WAIT, CLEAR).4. Нельзя освобождать свободный семафор и объявлять уже объявленное событие.5. Определять начальные значения семафоров и событий, если они должны бытьотличны от нуля (семафор занят, событие не объявлено).1.Имеется механизм двоичных семафоров.

Опираясь на него, реализуйтеP-операцию и V-операцию для общего (считающего) семафора. Активноеожидание освобождения семафора не допускается.Вариант 1struct DSemaphore {private:int s;public:BSemaphore access;BSemaphore wait;DSemaphore(semName_t name, int N) {s = N;access = 1;wait = 1;}DSemaphore(semName_t name) {}void P();void V();// создание владельцем семафора// Присоединение к семафору};void DSemaphore::P() {P(wait);P(access);s--;if (s>0)V(wait);V(access);}void DSemaphore::V() {P(access);s++;if (s==1)V(wait);V(access);}Вариант 2Int S = N;Semaphore access = 1;// семафор для монопольного доступа к SSemaphore wait = 1; // при помощи него мы будем реализовывать ожиданиеP(int S) {wait.P();access.P();S--;if (S > 0)wait.V();access.V();}V(int S) {access.P();S++;if (S == 1)wait.V();// если мы последним вошли в критическую секцию// (S == 0) - залочили после себя всех// мы освобождаем единственное место - надо разлочить// ожидающих, если мы освобождаем второе и далее место// - значит очереди нет, никого разлочивать не надоaccess.V();}2.Имеется команда TSL и команда объявления прерывания указанномупроцессору.

Опираясь на них, реализуйте на мультипроцессоре P-операцию иV-операцию для двоичного семафора. Активное ожидание освобождениясемафора не допускается.На одном процессоре может быть много процессов – активных и заблокированных(например, по ожиданию семафора). Команда TSL нужна для взаимного исключения,чтобы операционные системы одновременно не стали работать с очередями процессов изначениями семафоров. Для этого в начале операционные системы договариваются(командой TSL).При освобождении семафора разблокируетсяпервый процесс из очередиожидающих. Это происходит на том процессоре, на котором выполнена операцияосвобождения, и надо известить о разблокировании все другие процессоры (или одинконкретный, на котором должен выполняться разблокированный процесс) – для этогокоманда прерывания.Привязан ли процесс к процессору? Привязка позволяет повторно использовать кэшпроцесса, сохранённый на “его” процессоре, однако при этом появляется опасностьпростоя свободного процессора, не предназначенного для разблокированного процесса.Подводя итог: прерывание необходимо при освобождении семафора.Решение:Tsl(r, s) делает [r = s, s = 1] – это неделимая операция.Enter_region:// P-operationTsl reg, flagCmp reg, #0Je Go<Ждем прерывание>Go:RetLeave_region:// V-operationMove flag, #0<Отправляем сигнал>Ret3а.

Имеется механизм двоичных семафоров. Опираясь на него, реализуйтеоператоры POST(имя переменной-события) и WAIT(имя переменной-события).Активное ожидание события не допускается.Основное отличие событий от семафоров в том, что при объявлении одного событияразблокируются сразу несколько ожидающих его процессов, ресурс не исчерпывается.Суть операции Post: освободить семафор (V).Суть операции Wait: запросить семафор; нам его дадут; но нужно также освободитьего для других ожидающих процессов (P + V).Начальное состояние: семафор захвачен.Semaphore event;//Должен быть в захваченном состоянииPost(Semaphore event) {V(event);}Wait(Semaphore event) {P(event);V(event);}3б.

Оцените, во сколько раз нижеприведенный алгоритм метода последовательнойверхней релаксации можно выполнить быстрее, чем последовательный, есличисло процессоров мультипроцессора = N, время выполнения одного оператораприсваивания (​A[i][j]=....) равно 1, временами выполнения остальных операторовможно пренебречь.float A[ L1 ][ L2 ];semaphore s[ L1 ][ L2 ];// массив двоичных семафоров с нулевым начальным// значениемfor ( j = 0; j < L2; j++) { post( s[ 0 ][ j ]); }parfor ( i = 1; i < L1-1; i++)for ( j = 1; j < L2-1; j++) {wait( s[ i-1 ][ j ]);A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1][ j ] + A[ i ][ j-1 ] + A[ i][ j+1 ]) / 4;post( s[ i ][ j ]);}Важно объявить порядок распределения витков цикла между процессами.Пусть 1-ый процесс обрабатывает витки 1, N+1, 2N + 1, …2-ой процесс - витки 2, N+2, 2N+2, …т.е.

распределение круговое.Время последовательного выполнения программы:T​L​=(L1-2)*(L2-2)Рассмотрим время выполнения параллельной программы. Если будем рассматриватьвсе случаи, то решение получится громоздким, поэтому ограничимся следующимслучаем:N ≤ L1-2; N ≤ L2-2; (L1-2)modN=0;Первый шаг – 1 присваивание;Второй шаг – 2 присваивания;……………………………..N-ый шаг – N присваиваний.Т.е.

первые N-1 шага работают не все процессоры. Аналогично последние N-1 шага тоже самое. Первые N-1 шага назовем временем разгона. Последние N-1 шага временемторможения. За время разгона обработаем N*(N-1)/2 ячеек. За время торможениястолько же. Разгон(торможение) занимает T​A​=(N-1) времени.За разгон+торможение обработаем N*(N-1) ячеек и это займет 2*(N-1) времени.В оставшееся время работают все процессоры.

Назовем это время полногопараллелизма. Осталось обработать (L1-2)*(L2-2)-N*(N-1) ячеек.Время полного параллелизма T​FP​ = ((L1-2)*(L2-2)-N*(N-1)) / N;Время параллельной программы:T​P​ = T​FP​+2*T​A.Ответ:Ускорение A = T​L​/T​P ​= (L1-2)*(L2-2)/(((L1-2)*(L2-2)-N*(N-1)) / N + 2*(N-1))​ =​= N * (L1-2) * (L2-2) / (N*(N-1)+(L1-2)*(L2-2)).4.Имеется механизм двоичных семафоров. Опираясь на него, реализуйте задачучитателейи писателей (алгоритмы предоставленияправ доступапроцессам-читателям и процессам-писателям):Процесс-писатель должен получать исключительный (монопольный) доступ кбазе данных (других писателей или каких-либо читателей быть не должно).Произвольное число процессов-читателей может работать одновременно, нолюбой читатель может получить доступ только при отсутствии работающихписателей.Запросы на доступ должны удовлетворяться “справедливо” – в порядке ихпоступления (можно исходить из “справедливости“ удовлетворения запросов надвоичные семафоры).semaphore reader;semaphore writer;semaphore access;int rd=0;Write_enter() {Write_leave() {P(reader);V(reader);P(writer);V(writer);}}5.Read_enter() {P(reader);P(access);rd++;if (rd==1)P(writer);V(access);V(reader);}Read_leave() {P(access);rd--;if (rd==0)V(writer);V(access);}Какие модели консистентности памяти удовлетворяют алгоритму Деккера(алгоритм без каких-либо изменений будет работать правильно), а какие нет?Объясните ответ.Алгоритм позволяет двум потокам выполнения совместно использоватьнеразделяемый ресурс без возникновения конфликтов, используя только ​общую памятьдля коммуникации.flag[0] := falseflag[1] := falseturn := 0// or 1p0:p1:flag[0] := true​while​ flag[1]=true​if​ turn ≠ 0 {flag[0] :=​while​ turn}flag[0] :=}}{false≠ 0 {true// critical section...// remainder sectionturn := 1flag[0] := falseflag[1] := true​while​ flag[0]=true {​if​ turn ≠ 1 {flag[1] := false​while​ turn ≠ 1 {}flag[1] := true}}// critical section...// remainder sectionturn := 0flag[1] := falseМодели консистентности:МодельСтрогаяДа, так как данные полностью согласованы.ПоследовательнаяДа, так как процессоры видят записи в едином порядке.ПричиннаяНет, так как процессы независимо пишут в память.Причинности между записями не имеется.

Процессы могут неувидеть записи, сделанной на другом процессоре, и войти вКС.PRAMНет, т.к. процессы могут одновременно войти в КС(аналогично примеру в лекции про kill, где оба процессамогут быть убиты)ПроцессорнаяСчитая переменные flag[0] и flag[1] разными, припроцессорной консистентности алгоритм работать не будет. Ктому же каждый процесс пишет в свой флаг, а чужой толькочитает.Слабая/По выходу/По входуНет, так как необходимо выделение синхронизационныхпеременных и модификация кода.6.Какие модели консистентности памяти удовлетворяют алгоритму Петерсона(алгоритм без каких-либо изменений будет работать правильно), а какие нет?Объясните ответ.Алгоритм:flag[0]flag[1]turn= 0= 0= 0P0: flag[0] = 1turn = 1​while​( flag[1] ​&&​ turn == 1 );// do nothing// critical section...// end of critical sectionflag[0] = 0P1: flag[1] = 1turn = 0​while​( flag[0] ​&&​ turn == 0 );// do nothing// critical section...// end of critical sectionflag[1] = 0Модели консистентности:МодельСтрогаяДа, так как данные полностью согласованы.ПоследовательнаяДа.