(2016) Ответы (1162879)

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

Текст из файла

Распределённые системыЛекторы: Крюков Виктор Алексеевич, Бахтин Владимир АлександровичДок собрали Синельников И., Клюшкина Е.Спасибо всем, кто помог с составлением этого дока!При большом количестве народа док может лагать, поэтому скачайте его передэкзаменом (Файл -> Скачать как).Если при ответе возникнут замечания к решениям, пишите, пожалуйста,комментарии. И заносите дополнительные вопросы, если будут.Ссылки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Модели консистентности:МодельСтрогаяДа, так как данные полностью согласованы.ПоследовательнаяДа.

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

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

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