Распределённые операционные системы. Задачи и ответы. (esyr) (1162821), страница 2
Текст из файла (страница 2)
Произвольноечисло процессов-читателей может работать одновременно, но любой читатель может получить доступ только при отсутствии работающих писателей.Запросы на доступ должны удовлетворяться “справедливо” - в порядке их поступления (можно исходить из “справедливости“ удовлетворения запросов на двоичные семафоры).Ответ:semaphore sem_r = 1, sem_ra = 1, sem_w = 1;int readers_count = 0;r_enter() {// Читатель хочет начать читатьsem_r.P();sem_ra.P();++readers_count;if (readers_count == 1)sem_w.P();// Первый читатель блокирует возможность писатьsem_ra.V();sem_r.V();}r_leave() {// Читатель выходит из области чтенияsem_ra.P();--readers_count;if (readers_count == 0)sem_w.V();// Последний читатель освобождает семафорsem_ra.V();}w_enter() {sem_r.P();}sem_w.P();w_leave() {sem_w.V();sem_r.V();}// Писатель хочет писать// Чтобы новые читатели не начинали читать и чтобы// избежать блокировки при одновременном входе читателя и писателя.// Писатель выходит из области записиТема 3[править]Задача 1 (MPI_BARRIER)[править]В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию барьер (MPI_BARRIER) для всех процессов.
Скольковремени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно Ts, время передачи байта равно Tb (). Процессорныеоперации, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ: MPI_Barrier останавливает выполнение вызвавшей ее задачи до тех пор, пока не будет вызвана изо всех остальных задач, подсоединенных к указываемомукоммуникатору.
Гарантирует, что к выполнению следующей за MPI_Barrier инструкции каждая задача приступит одновременно с остальными.Задача 2 (MPI_BCAST)[править]В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию передачи сообщ ения длиной N байт всем процессамот одного (MPI_BCAST) - процесса с координатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно 100, времяпередачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ:Без конвейера: Операция MPI_BCAST осущ ествляет посылку сообщ ений всем соседям данного транспьютера. Следовательно, каждая посылка сообщ ения в транспьютернойopen in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comматрице операцией (MPI_BCAST) заполняет очередную диагональ матрицы: 0 - (0, 0); 1 - (1, 0), (0, 1); 2 - (2, 0), (1, 1), (0, 2) и т.д (где (i, j) - координата процесса).
Следовательно,для осущ ествения операции MPI_BCAST в матрице 4x4 нужно 6 * (Ts + N*Tb) единиц времени.С конвейером (но, наверное, неправильно): А если разбить сообщ ение на байты и передавать конвейерно: тогда потребуется 6*Ts на инициализацию узлов, 6*Tb наинициализацию конвейера (предположим, что маршрут один), и (N-1)*Tb для передачи всего сообщ ения.Небольшой комментарий:Для конвейера неправильно.Исходим из определения времени старта: Время старта-время инициализации канала для передачи любого количества данных (хоть одного байта)Разобьем сообщ ение на К кусков.Время передачи первого куска до последней точки (3,3) (загрузка конвейера) равно 6*(Ts+Tb*N/K) (см.
пункт без конвейера)Время прохода остальных кусков (конвейер загружен) (K-1)*(Ts+Tb*N/K)ИТОГО: 6*(Ts+Tb*N/K)+(K-1)*(Ts+Tb*N/K)Для особых эстетов минимум достигается при K = [sqrt( 5 * Tb * N / Ts)]Задача 3 (MPI_GATHER)[править]В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию сбора данных от всех процессов (длиной один байт)для одного (MPI_GATHER) - процесса с координатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно 100, времяпередачи байта равно 1 (Ts=100,Tb=1).
Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ:Матрица 4*4 и собирающ ий узел - (0,0), значит входящ их каналов 2. Передающ их узлов 15, каналов 2, значит минимальное количество тактов передач - 8. И её просто достичь,передавая сообщ ения по двум конвейерным маршрутам. Итого: Если считать, что узлы не могут накапливать информацию, то потребуется 8 тактов инициализаций и 8 тактовсинхронных передач.
8*Ts+8*TbЗадача 4 (MPI_SCATTER)[править]В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию рассылки данных (длиной один байт) всем процессамот одного (MPI_SCATTER) - процесса с координатами (0,0). Сколько времени потребуется для этого, если все процессы выдали ее одновременно. Время старта равно 100, времяпередачи байта равно 1 (Ts=100,Tb=1). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ:Похоже, что эта задача отличается от предыдущ ей только направлением потока данных. Так что ответ такой же.Задача 5 (суммирование)[править]В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию суммирования 16 чисел (каждый процесс имеет своечисло).
Сколько времени потребуется для получения всеми суммы, если все процессы выдали эту операцию редукции одновременно? А сколько времени потребуется длясуммирования 64 чисел в матрице 8*8? Время старта равно единице, время передачи байта равно нулю (Ts=1,Tb=0). Процессорные операции, включая чтение из памяти и записьв память считаются бесконечно быстрыми.Ответ:Пусть никакой буферизации не предусмотрено. Для получения суммы на одном из четырёх центральных процессов ((1,1),(2,1),(1,2),(2,2)) необходимо 4 операции (2 операции дляполучения суммы своего угла из 4 процессов для каждого центрального процесса, ещ ё две, чтобы получить общ ую сумму на всех - на каждом такте складываем сумму натранспьтере с соседями (к примеру, (1,1) с (2,1) и (1, 2). После этого на каждом из 4х транспьютеров получается удвоенная сумма, из которой получается просто сумма)).
Затемнужно ещ ё 2 операции, чтобы разослать информацию во все углы. Итого: 6*(Ts+Tb).open in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comЕсли процессов 64, то разобьём квадрат на 4 подквадрата. Как было показано ранее, за 4 операции пожно получить сумму своего квадрата в (2,2), (5,2), (2,5) и (5,5). Ещ ё двеоперации нужно на пересылку в центральные процессы. Там за 2 операции получаем сумму на всех из них (как и в первом случае), и ещ ё 6 на рассылку. Итого: 14*(Ts+Tb).Задача 6 (максимум)[править]В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо выполнить операцию нахождения максимума среди 16 чисел (каждыйпроцесс имеет свое число). Сколько времени потребуется для получения всеми максимального числа, если все процессы выдали эту операцию редукции одновременно.
Асколько времени потребуется для нахождения максимума среди 64 чисел в матрице 8*8? Время старта равно единице, время передачи байта равно нулю (Ts=1,Tb=0).Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ:Концептуально задача не отличается от предыдущ ей. Ответ тот же.Задача 7 (передача сообщения)[править]В транспьютерной матрице размером 4*4, в каждом узле которой находится один процесс, необходимо переслать очень длинное сообщ ение (длиной L байт) из узла скоординатами (0,0) в узел с координатами (3,3).
Сколько времени потребуется для этого? А сколько времени потребуется для пересылки из узла с координатами (1,1) в узел сopen in browser PRO versionAre you a developer? Try out the HTML to PDF APIpdfcrowd.comкоординатами (2,2)? Время старта равно времени передачи байта (Ts=Tb). Процессорные операции, включая чтение из памяти и запись в память считаются бесконечно быстрыми.Ответ:В задаче 3.2 был получен результат 6*(Ts+Tb*L/K)+(K-1)*(Ts+Tb*L/K). При передаче из одного в угла другой можно получить то же время, деля это длинное сообщ ение на Kкусков.
Кроме того, его можно распилить пополам и пустить двумя путями (больше не получится -- около углов узкое место), тогда время будет такое: 6*(Ts+Tb*L/(2K))+(K1)*(Ts+Tb*L/(2K)).С передачей из (1,1) в узел с координатами (2,2) немного сложнее. Строго говоря, там возможны 4 пути: два длины 2 и два длины 6. Пусть есть N - часть сообщ ения L, которуюмы пустим по коротким каналам. Тогда 0.5L < N < L из соображений здравого смысла, и будем N дробить на K1 частей, а (L-N) на K2 частей.
Тогда получаем формулу:max{ 2*(Ts+Tb*N/(2K1))+(K1-1)*(Ts+Tb*N/(2K1)), 6*(Ts+Tb*(L-N)/(2K2))+(K2-1)*(Ts+Tb*(L-N)/(2K2)) }.И эту жесть надо минимизировать по N, K1, K2.Ответ (вариант 2):На консультации сказали, что если в задании есть слова очень длинное сообщение, то можно пренебречь временем старта, временем разгона конвейера и длиной маршрута.Таким образом, у нас остается только Tb.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
