Ответы на задачи

©syr@ok.ruВсе замечания, исправления и другие fix-ы приветствуются!Не рекомендую пользоваться, если не понимаете, почему здесь такие цифры/картинки/слова.Тема-11. Какиеаппаратныемеханизмынеобходимыдляорганизациимультипрограммного режима? Как обеспечить мультипрограммный режимбез этих механизмов? Как обеспечить, если отсутствует только один из этихмеханизмов?Требуются: защита памяти, прерывания, привилегированный режим, таймер.Если нет таких механизмов, то можно использовать виртуальную машину - единый интерпретатор,исполняющий программы пользователей и обеспечивающий эмуляцию всех этих механизмов.Видимо отсутствие одного из этих механизмов равносильно отсутствию всех.Возможно также выполнять на машине без этих требований программу, созданную специальнымкомпилятором, который всегда при создании машинного кода вставляет дополнительные инструкциии проверки для эмуляции мультипрограммного режима.

Этот способ эффективнее полной эмуляции,хотя и сложнее на создание компилятора.Тема-21. Имеется механизм двоичных семафоров. Опираясь на него, реализуйте Pоперацию и V-операцию для общего (считающего) семафора. Активноеожидание освобождения семафора не допускается.В приведенном алгоритме возникают интересные вопросы, связанные с выделением памяти.struct dsemaphore{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();private:int s;};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);}2.

Имеется команда TSL и команда объявления прерывания указанномупроцессору. Опираясь на них, реализуйте на мультипроцессоре P-операцию и2V-операцию для двоичного семафора. Активное ожидание освобождениясемафора не допускается.Init(s)Tbl[s][0]=2Tbl[s][1]=2Restart:P(s):own:V(s):sleep(rnd())tsl r0, syncmp r0,1jz restartmov tbl[s][tbl[s][0]], pidinc tbl[s][0]cmp tbl[s][0], tbl[s][1]+1jz ownmov syn, 0sleepretmov syn, 0retexit:tsl r0, syncmp r0,1jz Vinc tbl[s][1]cmp tbl[s][1], tbl[s][0]jz exitwake tbl[s][tbl[s][1]]mov syn, 0ret3. Имеется механизм двоичных семафоров. Опираясь на него, реализуйтеоператоры POST(имя переменной-события) и WAIT(имя переменнойсобытия).

Активное ожидание события не допускается.struct event{semaphore access;semaphore waiters[N];int nWaiters;int state;}POST(event *ev){P(ev->access);ev->state = 1;for(int i=0;i<nWaiters;i++){V(ev->waiters[i]);}V(ev->access);}s=0;POST(s){ V(s); }WAIT(event *ev){P(ev->access);if(ev->state == 1){V(ev->access);}else{int index = ev->nWaiters++;P(ev->waiters[index]);V(ev->access);P(ev->waiters[index]);V(ev->waiters[index]);}}WAIT(){ P(s);V(s); }4. Оцените, во сколько раз нижеприведенный алгоритмметодапоследовательной верхней релаксации можно выполнить быстрее, чемпоследовательный, если число процессоров мультипроцессора = 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++)3{ 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 ]);}Будем считать, что как минимум L2 > N+2Время последовательного выполнения: Tseq = (L1-2)*(L2-1)Время параллельного выполнения:Произойдёт (L1 div N) параллельных циклов с полной загрузкой процессоровПроизойдет (L1 mod N) параллельных циклов с неполной загрузкой.Задержка завершения последнего процесса составитЕсли полная загрузка процессоров {(L1 mod N)==0} – N /2 шаговЕсли полная загрузка (L1 mod N)/2 шаговОбщее время выполнения:(L1 div N)*(L2-2)+(L1 mod N)*(L2-2)+ (((L1 mod N)==0)?N/2: (L1 mod N)/2)Итого соотношение:/(L1-2)*(L2-1) (L1 div N)*(L2-2)+(L1 mod N)*(L2-2)+ (((L1 mod N)==0)?N/2: (L1 mod N)/2)Замечание: Если L2<N+2, тогда добавление процессоров сверх числа L2-2 не даст ни какоговыигрыша в производительности по сравнению с N=L2-2.5.

Имеется механизм двоичных семафоров. Опираясь на него, реализуйтезадачу читателей и писателей (алгоритмы предоставления прав доступапроцессам-читателям и процессам-писателям):Процесс-писатель должен получать исключительный (монопольный) доступк базе данных (других писателей или каких-либо читателей быть не должно).Произвольное число процессов-читателей может работать одновременно, нолюбой читатель может получить доступ только при отсутствииработающих писателей.Запросы на доступ должны удовлетворяться “справедливо” - в порядке ихпоступления (можно исходить из “справедливости“ удовлетворения запросовна двоичные семафоры).semaphore reader;semaphore writer;semaphore access;int rd=0;Write_enter(){P(writer);P(reader);}Write_leave(){V(reader);V(writer);}Read_enter(){P(writer);P(access);rd++;if(rd==1)P(reader);V(access);V(writer);}Read_leave(){P(access);rd--;if(rd==0)V(reader);V(access);}6.

Какие модели консистентности памяти удовлетворяют алгоритму Деккера(алгоритм без каких-либо изменений будет работать правильно), а какиенет? Объясните ответ.4void enter_region( int i ){try: flag[ i ]=TRUE;while (flag [( i+1 ) % 2]){if ( turn = = i ) continue;flag[ i ] = FALSE;while ( turn != i );goto try;}}void leave_region( int i ){turn = ( i +1 ) % 2;flag[ i ] = FALSE;}МодельСтрогаяПоследовательнаяПричиннаяДа, так как данные полностью согласованы.Да, так как процессоры видят записи в едином порядке,Нет, так как процессы независимо пишут в память. Причинности междузаписями не имеется.

Процессы могут не увидеть записи, сделанной надругом процессоре, и войти в КС.PRAMНет, так как ещё слабее, чем последовательная. Тот же пример.ПроцессорнаяСчитая переменные flag[0] и flag[1] разными при процессорнойконсистентности алгоритм работать не будет.СлабаяНет, так как необходимо выделение синхронизационных переменных.При любой модели консистентности с синхронизацией алгоритм работать не будет.7. Какие модели консистентности памяти удовлетворяют алгоритму Петерсона(алгоритм без каких-либо изменений будет работать правильно), а какиенет? Объясните ответ.void enter_region( int i ){int other=1- i;/* номер другого процесса */flag[ i ] = TRUE;turn = i;while (turn = = i && flag[ other ] = = TRUE) /* пустой оператор */;}void leave_region( int i ){flag[ i ] = FALSE;}МодельСтрогаяПоследовательнаяДа, так как данные полностью согласованы.Да.

Так как все процессоры видят модификации данных в едином порядке(включая и автора изменений)ПричиннаяНет. Причинные связи отслеживаются по чтению, предшествующемузаписи. Здесь наоборот. Запись предшествует чтению, что не будетотслежено.PRAMНет, так как каждый процессор сможет изменить значения разделяемыхпеременных в локальной памяти и войти в КС.ПроцессорнаяСчитая переменные flag[0] и flag[1] разными при процессорнойконсистентности алгоритм работать не будет, так как оба процессора могутвойти в КС.СлабаяНет, так как необходимо выделение синхронизационных переменных.При любой модели консистентности с синхронизацией алгоритм работать не будет.5Тема-31.

В транспьютерной матрице размером 4*4, в каждом узле которой находитсяодин процесс, необходимо выполнить операцию передачи сообщения длинойN байт всем процессам от одного (MPI_BCAST) - процесса с координатами(0,0). Сколько времени потребуется для этого, если все процессы выдали ееодновременно. Время старта равно 100, время передачи байта равно 1(Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и записьв память, считаются бесконечно быстрыми.Pr-0A0A0Pr-1BROADCASTA0èPr-2A0Pr-3A08*(Ts+N*Tb)2.

В транспьютерной матрице размером 4*4, в каждом узле которой находитсяодин процесс, необходимо выполнить операцию сбора данных от всехпроцессов (длиной один байт) для одного (MPI_GATHER) - процесса скоординатами (0,0). Сколько времени потребуется для этого, если всепроцессы выдали ее одновременно. Время старта равно 100, время передачибайта равно 1 (Ts=100,Tb=1).

Процессорные операции, включая чтение изпамяти и запись в память, считаются бесконечно быстрыми.Pr-0 A0 A1 A2 A3SCATTERA0èPr-1A1Pr-2GATHERA2çPr-3A368*(Ts+Tb*Lm) – время на извещение.8*(Ts+Tb*N) – время требуемое для получения данных при сбалансированной загрузке.Возможна оптимизация: первые сообщения посылаются ближайшим транспьютерам:Они начнут сразу передавать данные. Дальше при больших N сообщения посылаются самым дальним,И по мере удаления. Цель – сохранить оба входных канала приема максимально заполненными.Тогда 8*(Ts+N*Tb) +Ts+Lm.Если N не достаточно велико, то есть будет простой приема при такой схеме (например, N<100),подсчет усложняется. Усложняется также выбор оптимального порядка рассылки сообщений.3. В транспьютерной матрице размером 4*4, в каждом узле которой находитсяодин процесс, необходимо выполнить операцию рассылки данных (длинойодин байт) всем процессам от одного (MPI_SCATTER) - процесса скоординатами (0,0).