Распределённые операционные системы. Задачи и ответы. (esyr) (1158846)
Текст из файла
Представ иться системестатьяобсуждениеправ итьисторияРОС, ответы на задачиСодержание [убрать]1 Тема 12 Тема 22.1 Задача 1 (Деккер)2.2 Задача 2 (считающий семафор через двоичный)2.3 Задача 3 (события через двоичный семафор)2.4 Задача 4 (двоичный семафор через TSL/прерывания)2.5 Задача 5 (верхняя релаксация)2.6 Задача 6 (Писатели и читатели)3 Тема 33.1 Задача 1 (MPI_BARRIER)3.2 Задача 2 (MPI_BCAST)3.3 Задача 3 (MPI_GATHER)3.4 Задача 4 (MPI_SCATTER)3.5 Задача 5 (суммирование)3.6 Задача 6 (максимум)3.7 Задача 7 (передача сообщения)3.8 Задача 8 (буферизуемая передача сообщения)3.9 Задача 9 (блокирующая/неблокирующая передача сообщения)4 Тема 44.1 Задача 1 (Круговой маркерный алгоритм)4.2 Задача 2 (Древовидный маркерный алгоритм)4.3 Задача 3 (Децентрализованный алгоритм с временными метками)4.4 Задача 4 (Широковещательный маркерный алгоритм)4.5 Задача 5 (Централизованный алгоритм)4.6 Задача 6 (Алгоритм задиры)4.7 Задача 7 (Круговой алгоритм)5 Тема 56 Тема 6 (задачи на консистентность)6.1 Последовательная6.2 Причинная6.3 PRAM6.4 Процессорная6.5 Слабая6.6 По выходу6.7 По входу6.8 Алгоритм Деккера6.9 Алгоритм Петерсона7 Тема 78 Прочие вкусности от лектора9 Задачи из лекций Вали Глазковой9.1 Задача 1open in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.com9.2 Задача 29.3 Задача 39.4 Задача 49.5 Задача 510 СсылкиТема 1[править]1.
Какие аппаратные механизмы необходимы для организации мультипрограммного режима? Как обеспечить мультипрограммный режим без этих механизмов? Как обеспечить,если отсутствует только один из них?Ответ:Для реализации мультипрограммного режима необходимы:1. Поддержка различных режимов выполнения (привилегированный и непривилегированный режим).2.
Поддержка механизма защ иты памяти (каждый процесс выполняется в своем адресном пространстве).3. Поддержка механизма прерываний (сигнализировать ОС об истечении кванта времени, сигнализировать о том, что процесс полез не в свою память).4. Поддержка таймера (кванты времени).Видимо, при отсутствии таких механизмов, необходимо воспользоваться паравиртуализацией (эмуляция аппаратных средств + гипервизор (ОС)).Защ ита памяти --- защ ита оперативной памяти.
Привилегированный режим необходим для защ иты внешней памяти (SkyHawk: Неправда, привилегированный режим необходимдля реализации защ иты памяти, иначе любой процесс сможет делать то же, что и ОС, а именно влезать в чужую память.).Тема 2[править]Задача 1 (Деккер)[править]Если в алгоритме Деккера (enwikiпочему.) не изменять значение переменной turn при выходе из критической секции, то каким требованиям он перестанет удовлетворять? Объясните,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 {// critical section...// remainder sectionturn := 1flag[0] := falsetrueflag[1] := truewhile flag[0]=true {if turn ≠ 1 {flag[1] := falsewhile turn ≠ 1 {}flag[1] := true}}// critical section...// remainder sectionturn := 0flag[1] := falseОтвет:Требованию конечного ожидания входа в критическую секцию --- после такой модификации один из процессов будет бесконечно долго ждать входа в критическую секцию(starvation).open in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comЗадача 2 (считающий семафор через двоичный)[править]Имеется механизм двоичных семафоров.
Опираясь на него, реализуйте P-операцию и V-операцию для общ его (считающ его) семафора.Ответ (не реализовано "блокирование" в случае если процесс ждет входа, заменено циклом)int count = N;boolSemaphore sem = 1;P(s) {bool success = false;while(!success) {P(sem);if(count > 0) {count--; success = true;}V(sem);}}V(s) {P(sem);count++;V(sem);}Ответ (2 вариант, из лекций)Int S = N;Semaphore access = 1; // семафор для монопольного доступа к SSemaphore wait = 1;// при помощи него мы будет реализовывать ожидание.P(Int S) {wait.P();access.P();S = S – 1;If(S > 0) wait.V(); //если мы последним вошли в критическую секцию(S == 0) - залочили после себя всехaccess.V();}V(Int S) {access.P();S++;If(S == 1) wait.V(); //мы освобождаем единственное место - надо разлочить ожидающих, если мы освобождаем второе и далее место - значит очереди нет, никого разлочивать не надоaccess.V();}Задача 3 (события через двоичный семафор)[править]Имеется механизм двоичных семафоров.
Опираясь на него, реализуйте операторы POST(имя переменной-события) и WAIT(имя переменной-события).Ответ:BinarySemaphore sem; // семафор должен быть в захваченном состоянии.void event::POST() {sem.V();}void event::WAIT() {sem.P();sem.V();}Задача 4 (двоичный семафор через TSL/прерывания)[править]Имеется команда TSL и команда объявления прерывания указанному процессору. Опираясь на него, реализуйте на мультипроцессоре P-операцию и V-операцию для двоичногосемафора. Активное ожидание освобождения семафора не допускается.Ответ:open in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comЧтобы не заморачиваться на регистровый вариант TSL можно предложить его логический аналогbool tsl(bool& val){bool i = val;val = 1;return i;}val = 0 // пусть это означает, что семафор свободенvoid P(){r = tsl(val) // получили старое значение val и поменяли егоif(r){<добавляем себя в список ждущих><ждем прерывания><удаляем себя из списка ждущих>}}void V(){if(<список ждущих не пуст>){<шлем прерывание 1 из списка>}else{val = 0}}Ответ(вариант 2):Tsl(r, s) делает [r = s, s = 1] – это неделимая операция.Задача 5 (верхняя релаксация)[править]Правильно ли использованы события в алгоритме, который реализует метод верхней релаксации? Оцените, насколько этот алгоритм можно выполнить быстрее, чемпоследовательный, если число процессоров мультипроцессора = N, время выполнения одного оператора присваивания (A[i][j]=....) равно 1, временами выполнения остальныхоператоров можно пренебречь.float A[ L1 ][ L2 ];struct condition s[ L1 ][ L2 ];for ( i = 0; i < L1; i++)for ( j = 0; j < L2; j++){ clear( s[ i ][ j ]) }// Цикл 1for ( j = 0; j < L2; j++){ post( s[ 0 ][ j ]) }// Цикл 2parfor ( i = 1; i < L1-1; i++)// Цикл 3for ( 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 ]);open in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.com}post( s[ i ][ j ]);Ответ: Введу читателя в курс дела:Механизм событийPOST(S) – объявление события S (является аналогом "V(S);" - освобождение семаформа S)WAIT(S) – процесс ожидает, когда произойдет событие S (является аналогом "P(S);V(S);" - освобождение семаформа S)CLEAR(S) – чистим значение S (я полагаю, эквивалентно S := 0, если продолжать аналогию с семаформа)Parfor - это цикл, витки которого распределяются между нитями (или процессами).Алгоритм последовательной верхней релаксации выглядит так:for ( i = 1; i < L1-1; i++)for ( j = 1; j < L2-1; j++)A[ i ][ j ] = (A[ i-1 ][ j ] + A[ i+1 ][ j ] + A[ i ][ j-1 ] + A[ i ][ j+1 ]) / 4;Нет, события использованы неправильно, так как забыли назначить посчитанным первый столбец:for ( i = 0; i < L1; i++)post( s[ i ][ 0 ])// Это надо вставить до начала// основного циклаТ.е.
конечный вариант:float A[ L1 ][ L2 ];struct condition s[ L1 ][ L2 ];for ( i = 0; i < L1; i++)for ( j = 0; j < L2; j++){ clear( s[ i ][ j ]) }// Цикл 1for ( j = 0; j < L2; j++){ post( s[ 0 ][ j ]) }// Цикл 2for ( i = 0; i < L1; i++){ post( s[ i ][ 0 ]) }parfor ( i = 1; i < L1-1; i++)// Цикл 3for ( 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 ]);}Причем, wait( s[ i ][ j-1 ]); делать во внутреннем цикле "Цикл 3" не нужно, так как внутри мы имеем for, а не parfor - это отличие данного алгоритма от алгоритма в лекциях.Оценка времени выполнения:Остановимся на оценке времени выполнения Цикла 3.Последовательное выполнение (без операторов wait и post) требует (L1 − 2) * (L2 − 2) присваиваний.При работе на N процессорах (без учета операторов wait и post):каждый процессор (кроме последнего) получает для обработкистрок.пока первая нить обрабатывает все свои строки, кроме своей последней, все остальные нити простаивают.
Преимущ ество возникает, когда первая нить начинаетобрабатывать свою последнюю строку. После того, как первая нить подсчитает первый элемент этой строки, в работу включится вторая нить, и L2-3 элемента первая ивторая нить будут обрабатывать параллельно. Далее первая нить будет простаивать, а работать будет вторая нить.как можно видеть, преимущ ество возникает только на таких таких строках m, что: m-я строка распределена k-й нити, а строка m+1 - нити с номером k+1. В каждом такомслучае мы получаем преимущ ество по времени равное (L2 − 3). Всего таких номеров m ровно N-1.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
