Где Ln – длина программы в байтах, Lq – число байтов, передаваемых между оперативной и внешней памятью за время q, равное минимальной длительности кванта.
Ln/Lq – определяет число квантов времени, необходимых для загрузки программы в оперативную память и для вывода ее из оперативной памяти.
Работа с приоритетом P заносится в очередь Op. Очередям с номерами р=1,…,n выделяются кванты времени длительности qp=2p-1*q. Таким образом очередям О1, О2, О3, О4 соответствуют кванты времени q, 2q, 4q, 8q и т.д.
Алгоритм Макнотона.
Рассмотрим систему с n идентичными процессорами, на которой необходимо решить L независимых задач. Каждая задача решается одним процессором в течение времени ti (i=1,…,L). Требуется найти алгоритм, который для каждого данного пакета строил бы расписание решения задач на процессорах системы, обеспечивающее минимально возможное время решения, при этом достигается максимально возможная производительность системы.
Например, пусть имеется двух процессорная система и набор задач с временами t(3,3,2,2,2), тогда возможны различные варианты назначения задач на решение.
Наилучший в смысле минимизации общего времени решения задач такой вариант, для которого время T решения пакета задач совпадает с соответствующим оптимальным значением .
Данный алгоритм используется для решения задач класса NP.
Задача класса NP (Non-deterministic polynomial) – это задача распознавания, решение которой при наличии каких-либо сведений можно проверить на машине Тьюринга.
LPT –Longest-processing task first.
Алгоритм LPT является наиболее эффективным и нетрудоемким алгоритмом организации вычислений, в котором самая длинная задача решается первой. Суть заключается в назначении задач в порядке убывания времени решения на освобождающие процессоры.
Где Т – время решения пакеты при распределения задач LPT.
То – длина соответствующего оптимального расписания.
n – количество процессоров
1) Модель МПС с общей памятью и её характеристики.
2) Модель МПС с индивидуальной памятью и её характеристики.
Для увеличения производительности в состав вычислительной системы может вводиться несколько процессоров способных функционировать параллельно во времени и независимо друг от друга и наряду с тем взаимодействовать между собой и с другим оборудованием системы.
Вычислительные системы, содержащие несколько процессоров, связанных между собой и с общим для них комплектом внешних устройств, называются Мультипроцессорными.
Производительность МПС увеличивается по сравнению с однопроцессорной системой в результате того, что МПС-ая организация дает возможность для одновременной обработки нескольких задач или параллельной обработки различных частей одной задачи.
В некоторых случаях требуется обеспечить непрерывность функционирования системы во времени. Это означает, что отказ в любом устройстве вычислительной системы, в том числе и в процессоре, не должен приводить к катастрофическим последствиям, то есть система должна сохранять работоспособность и после отказа. В таком случае все устройства вычислительной системы должны быть по крайней мере задублированы и система должна содержать не менее двух процессоров, то есть строится как МПС.
МПС с общей памятью.
В МПС с общей памятью каждый из процессоров имеет доступ к любому модулю памяти, которые могут функционировать независимо друг от друга и в каждый момент времени могут выполняться одновременные обращения для записи или чтения информации, количество которой определяется числом модулей.
Конфликтные ситуации (обращения к одному и тому же модулю памяти) разрешаются коммутатором, начинающим обслуживать первым устройство с наибольшим приоритетом. Например, процессор с наименьшим номером. Каждый из процессоров может инициировать работу любого канала ввода/вывода.
Структура МПС с общей памятью наиболее универсальна: любая информация, хранимая в памяти системы, в равной степени доступна любому процессору и каналу ввода/вывода. Недостаток МПС с общей памятью – это большие затраты оборудования в коммутаторах (эти затраты пропорциональны произведению числа устройств, подключенных к памяти, и числа модулей памяти).
Режим работы МПС, при котором каждый из процессоров может обслуживать любую заявку, называется режимом разделения нагрузки. При этом режиме каждый из N процессоров принимает на обслуживание N-ую часть заявок, то есть N-ую часть общей нагрузки.
CPU
CPU
CPU
БЛОКНОТ
Пр – процессор
Процесс обслуживания заявок в режиме разделения нагрузки можно рассматривать как процесс функционировать одной многоканальной системы массового обслуживания с интенсивностью l входящего потока, общей очередью О, заявки из которой выбираются в порядке поступления их в систему, и средней длительностью обслуживания заявки в каждом из процессоров, равной j.
Заявка, поступающая в систему из N процессоров, при наличии свободного процессора немедленно принимается последним на обслуживание, если все процессоры заняты, поступающая заявка помещается в очереди.
Пусть в МПС поступает M потоков с интенсивностями от l1 до lМ. Обслуживание заявок сводится к выполнению соответствующих программ, средние трудоемкости которых равны q1 - qМ операций в расчете на один прогон программы. Примем, что обслуживание заявок выполняется на основе дисциплины FIFO. В таком случае можно считать, сто система обслуживает однородный поток заявок с интенсивностью L .
Для обслуживания любой заявки из суммарного потока требуется в среднем . пусть заявка, поступившая на обслуживание, захватывает процессор до полного завершения обслуживания, в таком случае средняя длительность обслуживания заявки процессором с быстродействием B равна
И интенсивность обслуживания заявок одним процессором равна
Параметры системы L, N, j должны отвечать условиям существования стационарного режима, при котором в очереди пребывает конечное число заявок и следовательно конечные времена ожидания и пребывания заявок. На каждый из процессоров поступает N-ая доля заявок и следовательно, отдельный процессор обслуживает поток с интенсивностью L/N.
Загрузка процессора:
Стационарный режим существует, если r<1. Следовательно, параметры МПС должны отвечать соотношению
В теории массового обслуживания доказывается, что при указанных предположениях, вероятность пребывания в системе N заявок, обслуживаемых в процессоре и стоящих в очереди равна:
