В данном примере число прерываний=1 (прерывание в задаче N=2, со временем=4 ).

Покажем, что n-1 (максимальное число прерываний для расписания, полученного в соответствии с алгоритмом Макнотона) является достижимой границей числа прерываний.

Для доказательства этого построим такой пример пакета задач, для которого алгоритм Макнотона дает расписание с числом прерываний n-1.

Пусть: L = n + 1 и ti = n, i =1,…, n + 1.

Тогда: Q = max {n ,(1/n)·(n + 1)n} = n + 1, а расписание, получаемое в соответствии с алгоритмом Макнотона, имеет вид:

Число прерываний в этом случае, как видно, равно (n –1), что и требовалось показать.

Покажем, что любое оптимальное расписание для этого пакета задач также имеет не менее n -1 прерываний. Очевидно, что в любом оптимальном расписании ни один процессор не простаивает на интервале [0, n + 1]. Предположим, что сущес-твует некоторое оптимальное расписание с числом прерываний, меньшим n -1. Тогда по крайней мере два процессора ( для определенности возьмем Рk и Pu) обслуживают заявки без прерываний. Очевидно, эти процессоры обслуживают некоторые задачи Zik и Ziu в интервале [0, n] без прерываний,

(если решение этих задач начинается позже момента времени t = 0, значит, до этого момента на этих процессорах решались некоторые другие задачи, решение которых прерывается в моменты начала решения задач Zik и Ziu). Найдутся моменты времени t, t', такие, что n ≤ t < t’ ≤ n + 1, и в интервале [t, t’] хотя бы один процессор простаивает, а потому рассматриваемое решение не может быть оптимальным.

Так как мы пришли к противоречию, делаем вывод о том, что предположение о числе прерываний, меньшем n-1, в оптимальном расписании ложно.

В чем заключается основное достоинство обработки пакетов независимых задач без прерывания?

МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ ПРИ ОБРАБОТКЕ ПАКЕТОВ НЕЗАВИСИМЫХ ЗАДАЧ БЕЗ ПРЕРЫВАНИЙ

Рассмотрим систему, содержащую n идентичных процессоров, на которой необходимо решить без прерываний набор из Lнезависимых задач с временами решения ti ,

где i = 1 , ., L. Получение расписания с минимальным временем решения и в этом случае является трудной задачей. Один из наиболее эффективных и нетрудоемких алгоритмов организации таких вычислений — алгоритм LPT

(Longest-ProcessingTaskfirst — самая длинная задача решается первой),

являющийся частным случаем алгоритма критического пути для независимых задач.

Суть этого алгоритма - в назначении задач в порядке убывания времени решения на освобождающиеся процессоры. Сотрудником фирмы BellLaboratories, США, Грэхемом в 1967 г. был получен следующий результат: при использовании алгоритма LPT для распределения любого пакета П независимых задач без прерываний, в системе с n идентичными процессорами справедливо:

где Т — время решения пакета П при распределении задач алгоритмом LPT;

tо — длина оптимального расписания.

Приведенная оценка является наилучшей.

За счет чего увеличивается производительность мультипроцессорных систем по сравнению с однопроцессорными системами?

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

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

Как строятся мультипроцессорные системы с общей памятью?

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

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

Структура МПС с общей памятью наиболее универсальна: любая информация, хранимая в памяти системы, в равной степени доступна любому процессору и каналу ввода-вывода.

Отрицательное свойство МПС с общей памятью — большие затраты оборудования в коммутаторах (эти затраты пропорциональны произведению числа устройств, подключенных к памяти, и числа модулей памяти).

Как строятся мультипроцессорные системы с индивидуальной памятью?

В МПС с индивидуальной памятью каждый из процессоров обращается в основном к своему модулю памяти. Для обмена данными между подсистемами «процессор — модуль памяти» в процессорах предусмотрены блоки обмена, обеспечивающие передачу сегментов информации между общей памятью и модулем памяти. При этом блок обмена может работать как селекторный канал: операция обмена инициируется процессором, и передача данных выполняется с параллельной работой последнего. Принцип индивидуальной памяти позволяет исключить коммутаторы в интенсивно используемом канале «процессор — модуль памяти», вследствие чего увеличивается номинальное быстродействие процессоров и уменьшаются затраты оборудования по сравнению с системами с общей памятью.

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

.

Какие недостатки имеет структура МПС с общей памятью перед МПС с индивидуальной памятью?

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