Решённые задачи к экзамену (1162834)
Текст из файла
Тема 1.(См. Лекция 1: "Введение в параллельные и распределенные системы ")Какие аппаратные механизмы необходимы для организации мультипрограммного режима? Как обеспечитьмультипрограммный режим без этих механизмов? Как обеспечить, если отсутствует только один из них?Решение.•••Аппаратные средства:1. Система прерываний2.
Механизм защиты ОП3. Привелегированный режим4. ТаймерЕсли нет этих механизмов, то их можно имитировать программно, но это очень неэффективно. Такжеможно использовать специализированные компиляторы.Отсутствие одного из 4х пунктов-равносильно отсутствию всех.1Тема 2.(См. Лекция 2: "Операционные системы мультипроцессорных ЭВМ")1. Если в алгоритме Деккера не изменять значение переменной turn при выходе из критической секции, то какимтребованиям он перестанет удовлетворять? Объясните, почему.Решение. Он перестанет удовлетворять 3-ему требованию: "ни один процесс не должен бесконечно долго ждатьразрешения на вход в критический интервал (если ни один процесс не будет находиться внутри критическогоинтервала бесконечно )" .Один и тот же процесс легко может войти в критическую секцию два раза подряд. Кроме этого, один процессможет зависнуть в активном ожидании на операторе while (turn != i);Переменная turn определяет номер процесса, который получит доступ к критической секции, в случае, когда сразудва процесса попытались в нее войти.
Но не более того.2. Имеется механизм двоичных семафоров. Опираясь на него, реализуйте P-операцию и V-операцию для общего(считающего) семафора.Решение.Тут в лекциях допущена ошибка в описании функции P семафора. Наверно, достаточно завести двадвоичных семафора и int переменную для имитации ей считающего:Возможно, эта версия хорошая.int count = N;boolSemaphore sem = 1;P(s) {while(true) {P(sem);if(count > 0) {count--;V(sem);break;} else {V(sem);2}}}V(s) {count++;}Еще есть такая версияsemaphore access = 1;semaphore wait = 0;int s = <число процессов, которые могут находиться в КС>;P(s) {P(access);if s <= 0 { s = s - 1; V(access); P(wait); }else { s = s - 1; V(access); }}V(s) {P(access);if s < 0 { V(wait); }s = s + 1;V(access);}3.
Имеется механизм двоичных семафоров. Опираясь на него, реализуйте операторы POST(имя переменнойсобытия) и WAIT(имя переменной-события).Решение.В этом решении возможны ошибки в коде.Наверно, достаточно завести один двоичный семафор иbool переменную для обозначения самого события (произошло - не произошло) все.boolSemaphore pSem = 1;boolSemaphore wSem = 1;bool eventHappened = false;POST(event) {P(pSem);if (eventHappened == false) {eventHappened = true;<разблокировать все ожидающие процессы>}V(pSem);}3WAIT(event) {P(wSem);if (eventHappened == false) {<блокируем текущий процесс>}V(wSem);}Комментарии: семафор мы используем для того, чтобы не было ситуаций вроде:••Несколько одновременных вызовов POSTWAIT уже вошел в if и собрался блокироваться, а в это время POST полностью выполнился, однако вочереди на разблокировку еще не было WAIT-а. После этого WAIT вносит себя в очередь.
Результат событие объявлено, а процесс его ждет.[ Предлагается следующий код:bsemaphore sem = 0;WAIT(event) { P(sem); V(sem); }POST(event) { V(sem); } ]Вариант кода:void WAIT() {while(clearing); // подождать, если идет очисткаif (posting)return; // событие объявлено - можно работатьelse {waiting++; // событие не объявлено - записаться в ждущиеP(wait); // ждать :)}}void POST() {if(posting)return; // уже объявлено - ничего не надо делатьposting = true; // объявляемwhile(waiting > 0) { // разблокируем ждущие процессыwaiting--;V(wait);}}void CLEAR() {if(!posting) // не объявлено - ничего не делаемreturn;clearing = true; // начать очисткуposting = false; // очистка - дожидаемся пока POST освободит процессы, которые ждали до CLEAR.while(waiting > 0); // подождать пока POST освободит "старые" процессыclearing = false; // закончить очистку}44.
Имеется команда TSL и команда объявления прерывания указанному процессору. Опираясь на него, реализуйтена мультипроцессоре P-операцию и V-операцию для двоичного семафора.Решение.Пусть операция TSL работает с bool переменными и ее выполнение не может быть прервано:bool TSL(bool lock) {boolean initial = lock;lock = true;return initial;}Используют ее следующим образом:boolean lock = falsevoid Critical() {while TSL(lock)skip //spin until lock is acquiredcritical section //only one process can be in this section at a timelock = false //release lock when finished with the critical section}Попробуем реализовать P (занять) и V (освободить) операции для двоичного семафора с помощью этой штуки.bool forLock = false;bool forSemaphore = false;P(s) {while TSL(forLock) ;if (forSemaphore == true) <прерыванием остановить текущий процесс>;forSemaphore = true;forLock = false;}V(s) {while TSL(forLock) ;if (length == 0) <прерыванием запустить 1 ожидающий процесс>;forSemaphore = false;forLock = false;}<hr>По-моему, усложняете...
ИМХО, можно так:bool loc = false;bool glob = false;P(S) {dotsl(loc, glob)5until (loc == false);}V(S) {glob = false;}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 ]) }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 ]);}Решение.Parfor is a parallel loop construct that executes the iterations as separate threads, while the body of each iteration issequential.
The loop is unravelled by assigning a constant value for the loop control variable within each iteration. Theprequisite for this is that the values of the loop variable must be obtainable without executing the body of any iteration.Parfor statement completes only when all the iterations have completed, but as with par-statement nothing can be saidabout the order of execution of different threads. It is only quaranteed that when the program execution proceeds past theparfor block all the threads inside the parfor have finished.По поводу правильности - если сравнить этот код с тем, что в лекциях, то вот что имеем (красным отмеченпропущенный в задаче код):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 ]) }for ( i = 0; i < L1; i++){ post( s[ i ][ 0 ]) }for ( j = 0; j < L2; j++)6{ post( s[ 0 ][ j ]) }parfor ( i = 1; i < L1-1; i++)for ( j = 1; j < L2-1; j++){wait( s[ i ][ j-1 ]);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 ]);}Быстрее его можно выполнить, если выполнять действия A[]...
на разных процессорах, см. картинку. Цифры -номер процессора.Рассмотрим случай, когда T1 >= T2 (Другой - очевидно симметричен).1.N >= T2 - 2 (N - число работающих процессоров) Максимальная скорость, как на картинке. По сути нужностолько тактов, сколько диагоналей проходит через нужную нам область (прямоугольник за вычетомграницы толщиной 1). Это: (T1 - 2) + (T2 - 3).2.N < T2 - 2. Тут лучше привести задачу к виду 1, разделив на несколько.
Пусть A = T2 - 2 / N, B = T2 - 2 %N (частное и остаток), тогда можно выполнить эту задачу как последовательность из A + 1 задач .Получим время выполнения: A * (T1 - 2 + N - 1) + (T1 - 2 + B - 1)7Тема 3.(См. Лекция 3: "Коммуникации в распределенных системах")Главная мысль из этого флуда:"Задача найти ОДНО ИЗ решений, не занимайтесь поиском оптимального, простоскажите, какие есть методы оптимизации (конвейер, разделение и т.п.)"1. В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимовыполнить операцию барьер (MPI_BARRIER) для всех процессов.
Сколько времени потребуется для этого, есливсе процессы выдали ее одновременно. Время старта равно Ts, время передачи байта равно Tb (Ts=10,Tb=2).Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Решение. В лекциях про MPI_BARRIER почти ничего нет, вот для информации:Точки синхронизации, они же барьеры.Этим занимается всего одна функция:int MPI_Barrier( MPI_Comm comm );MPI_Barrier останавливает выполнение вызвавшей ее задачи до тех пор, пока не будет вызвана изо всех остальныхзадач, подсоединенных к указываемому коммуникатору.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
