23

©syr@ok.ru

Все замечания, исправления и другие fix-ы приветствуются!

Не рекомендую пользоваться, если не понимаете, почему здесь такие цифры/картинки/слова.

Тема-1

1. Какие аппаратные механизмы необходимы для организации мультипрограммного режима? Как обеспечить мультипрограммный режим без этих механизмов? Как обеспечить, если отсутствует только один из этих механизмов?

Требуются: защита памяти, прерывания, привилегированный режим, таймер.

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

Видимо отсутствие одного из этих механизмов равносильно отсутствию всех.

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

Тема-2

1. Имеется механизм двоичных семафоров. Опираясь на него, реализуйте 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);

}

1. Имеется команда TSL и команда объявления прерывания указанному процессору. Опираясь на них, реализуйте на мультипроцессоре P-операцию и V-операцию для двоичного семафора. Активное ожидание освобождения семафора не допускается.

Init(s) Tbl[s][0]=2 Tbl[s][1]=2

Restart: sleep(rnd()) P(s): tsl r0, syn cmp r0,1 jz restart mov tbl[s][tbl[s][0]], pid inc tbl[s][0] cmp tbl[s][0], tbl[s][1]+1 jz own mov syn, 0 sleep ret own: mov syn, 0 ret

V(s): tsl r0, syn cmp r0,1 jz V inc tbl[s][1] cmp tbl[s][1], tbl[s][0] jz exit wake tbl[s][tbl[s][1]] exit: mov syn, 0 ret

1. Имеется механизм двоичных семафоров. Опираясь на него, реализуйте операторы 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); }	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]); } }
s=0; POST(s){ V(s); }	WAIT(){ P(s);V(s); }

1. Оцените, во сколько раз нижеприведенный алгоритм метода последовательной верхней релаксации можно выполнить быстрее, чем последовательный, если число процессоров мультипроцессора = 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 ]);

}

Будем считать, что как минимум 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.

1. Имеется механизм двоичных семафоров. Опираясь на него, реализуйте задачу читателей и писателей (алгоритмы предоставления прав доступа процессам-читателям и процессам-писателям):

Процесс-писатель должен получать исключительный (монопольный) доступ к базе данных (других писателей или каких-либо читателей быть не должно). Произвольное число процессов-читателей может работать одновременно, но любой читатель может получить доступ только при отсутствии работающих писателей.

Запросы на доступ должны удовлетворяться “справедливо” - в порядке их поступления (можно исходить из “справедливости“ удовлетворения запросов на двоичные семафоры).

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); }

1. Какие модели консистентности памяти удовлетворяют алгоритму Деккера (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.

void 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] разными при процессорной консистентности алгоритм работать не будет.
Слабая	Нет, так как необходимо выделение синхронизационных переменных.

При любой модели консистентности с синхронизацией алгоритм работать не будет.

1. Какие модели консистентности памяти удовлетворяют алгоритму Петерсона (алгоритм без каких-либо изменений будет работать правильно), а какие нет? Объясните ответ.

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] разными при процессорной консистентности алгоритм работать не будет, так как оба процессора могут войти в КС.
Слабая	Нет, так как необходимо выделение синхронизационных переменных.

При любой модели консистентности с синхронизацией алгоритм работать не будет.

Тема-3

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

Pr-0

A0

A0

Pr-1

BROADCAST

A0

Pr-2



A0

Pr-3

A0

8*(Ts+N*Tb)

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

Pr-0	A0	A1	A2	A3	SCATTER	A0
Pr-1						A1
Pr-2					GATHER	A2
Pr-3						A3

8*(Ts+Tb*Lm) – время на извещение.

8*(Ts+Tb*N) – время требуемое для получения данных при сбалансированной загрузке.