Размещено на http://www.allbest.ru/

20

Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

Как известно, совокупность объекта управления, управляющего органа и исполнительного образует систему управления, в которой выделяются две подсистемы: управляющая подсистема и управляемая подсистема. В зависимости от того, в какой системе (простой, сложной, большой) производится управление, различают системы автоматического управления и автоматизированные системы управления.

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

Для программной реализации выбран язык Turbo Pascal 7.0. BP применяется в общеобразовательных, профессионально-технических школах и в сфере высшего образования в качестве «первого» языка программирования. Благодаря широкой сфере применения и простоте использования, язык BP получил распространение как в профессиональных, так и в любительских кругах. Turbo Pascal 7.0 позволяет получать чрезвычайно компактную, быструю и легко читаемую программу.

алгоритм вычислительный программа

1. ПОСТАНОВКА ЗАДАЧИ

1.1 Цель и задачи

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

1.2 Входная информация

Входной информацией для данной программы размерность очереди заявки, количество процессоров в системе, разброс длительности заявок.

1.3 Выходная информация

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

1.4 Требования к аппаратной части

Персональный компьютер фирмы IBM серии PC (или совместимый с этими моделями), работающий под управлением операционной системы (ОС) Windows 7/ХР.

Дисковод для гибких дисков и жесткий диск.

1.5 Требования к программному обеспечению

Данная программа должна реализовывать следующие функции:

ввод и корректировку входных данных с клавиатуры в экранные формы;

представление входной информации в виде экранных форм и/или таблиц;

- предоставление пользователю дружественного интерфейса.

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

2. Теоретическая часть

2.1 Общие сведения

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

Элемент системы - часть системы выполняющая определенную функцию.

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

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

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

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

2.2 Алгоритм Макнотона

Рассмотрим систему с n идентичными процессорами, на которой необходимо решить L независимых задач; каждая задача решается одним процессором в течение времени t_i, i = 1 ,…, L. Требуется найти алгоритм, который для каждого данного пакета (набора) строил бы расписание решения задач на процессорах системы, обеспечивающее минимально возможное время решения. При этом достигается максимально возможная производительность системы. На пример, в случае 2-процессорной системы и набора задач с временами (3,3,2,2,2) возможны различные варианты назначения задач на решение. Приведем некоторые из них (рисунок 2.2.1).

Очевидно, что наилучший в смысле минимизации общего времени решения задач - вариант с), для которого время Т решения пакета задач совпадает с соответствующим оптимальным значением То и в данном случае равно величине

= max {max t_i , 1/n * t _i }

Величина является нижней границей для оптимального значения То. Действительно, длина Т любого расписания не может быть меньше ни mах - максимального из времен решения задач пакета П, ни величины (1/n * t_i ) , дающей длину расписания в том случае, когда до момента завершения решения последней из задач пакета ни один процессор не простаивает, то есть все процессоры имеют 100% загруженности.

Рисунок 2.2.1 (Алгоритм Макнотона)

В общем случае даже при n = 2 задача поиска оптимального значения Т при условии решения задач, является NР-трудной, то есть все известные алгоритмы ее решения имеют трудоемкость, экспоненциально зависящую от L. Однако, если допустить возможность прерывания решения задач пакета до завершения их обслуживания, то могут быть предложены полиномиально-трудоемкие алгоритмы, приводящие к расписанию оптимальной длины То. При этом считается, что после прерывания решение задачи может быть возобновлено с точки прерывания на любом процессоре, не обязательно на том, на котором она первоначально решалась. Число прерываний должно быть по возможности меньшим, так как с каждым актом прерывания связаны потери машинного времени на загрузку-выгрузку задач из оперативной памяти.

Рассмотрим предложенный Макнотоном в 1959 г. алгоритм построения оптимального по длине расписания с не более чем n-1 прерываниями.

Алгоритм Макнотона заключается в предварительном упорядочении задач по убыванию времени решения и назначении задач последовательно по порядку номеров одну за другой на процессоры системы справа налево от уровня .

Пример

n=2, L=4, времена решения задач: (5,4,3,2). Тогда

=mах {5, 1/2*(5+4+3+2)}=7.

И расписание, полученное в соответствии с алгоритмом Макнотона, имеет следующий вид (рисунок 2.2.2):

Рисунок 2.2.2 (Алгоритм Макнотона)

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

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

Пусть L=n+1 и t_i=n, i=1, n+1.

Тогда = mах { n , 1/n * (n+1)*n = n+1, а расписание, получаемое в соответствии с алгоритмом Макнотона, имеет вид (рисунок 2.2.3):

Т=n+1=

Рисунок 2.2.3 (Алгоритм Макнотона)

Число прерываний в этом случае, как видно, равно n-1,что и требовалось показать. Покажем теперь, что любое оптимальное расписание для этого пакета задач также имеет не менее n-1 прерываний. Очевидно, что в любом оптимальном расписании ни один процессор не простаивает на интервале [O, n+1]. Предположим, что существует некоторое оптимальное расписание с числом прерываний, меньшим n-1. Тогда по крайней мере 2 процессора (предположим для определенности Р_K и Р_l) обслуживают заявки без прерываний. Очевидно, эти процессоры обслуживают некоторые задачи Z_ik в интервале [О,n] без прерываний (если решение этих задач начинается позже момента времени t=0, значит до этого момента на этих процессорах решались некоторые другие задачи, решение которых прерывается в моменты начала решения задач Z_ik и Z_il). Найдутся моменты времени t, t, такие, что n t < t n+1, и в интервале [t, t] хотя бы один процессор простаивает, а потому рассматриваемое решение не может быть оптимальным.

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

Реализацию алгоритма Макнотона можно сформулировать следующим образом:

Шаг 1-й: рассчитываем среднюю длину очереди на процессор.

Для этого организуем цикл по заданиям внешней очереди и находим сумму длин всех заданий SDZ и максимальную длину задания MDZ. За среднюю длину очереди SDO принимаем максимальную из двух величин: SDZ/NP, MDZ.

Шаг 2-й: организуем цикл по процессорам.

Шаг 3-й: организуем цикл по заданиям внешней очереди.

Шаг 4-й: назначаем задание процессору.

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

Иначе переходим к следующему заданию меньшей длины.

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

Шаг 5-й: вычисляем результирующие величины.

Вычислить среднее время простоя процессоров системы AVP (суммарное время простоя всех процессоров SVP деленное на количество процессоров NP). Найти максимальную длину очереди MDO (общее время выполнения внешней очереди многопроцессорной системой).

2.3 Методы управления ресурсами многопроцессорных систем при обработке пакетов независимых задач без прерываний. Алгоритм LPT

Рассмотрим систему, содержащую n идентичных процессоров, на которой необходимо решить без прерываний набор из L независимых задач с временами решения t_i,i=1,…,L. Получение расписания с минимальным временем решения и в этом случае является NР - трудной задачей. Один из наиболее эффективных и нетрудоемких алгоритмов организации вычислений в этом случае -- алгоритм LPT (longest-processing task first) - самая длинная задача решается первой), являющийся частным случаем алгоритма критического пути для независимых задач. Суть этого алгоритма заключается в назначении задач в порядке убывания времени решения на освобождающиеся процессоры. Сотрудником фирмы ВеllLaboratories США, Грэхемом в 1967г. был получен следующий результат:

Теорема.

При использовании алгоритма LРТ для распределения любого пакета П={Z_i} независимых задач без прерываний в системе с n идентичными процессорами справедливо:

Т (4/3-1/3n)*T_o,

где Т- время решения пакета П при распределении задач алгоритмом LРТ,

То - длина соответствующего оптимального расписания.

Очевидно, Т ? 1/n*

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

Алгоритм LPT приведен на рисунке 2.3.1.

Рисунок 2.3.1 (Алгоритм LPT)

3. РЕЗУЛЬТАТЫ ВЫПОЛНЕНИЯ ПРОГРАММЫ

В курсовой написаны три программы реализующие алгоритмы:

1. Простой алгоритм(случайное определение очереди заявок для определенного процессора)

2. Алгоритм Макнотона

3. Алгоритм LPT

Результаты работы программ представлены на рисунке 3.1

Рисунок 3.1 (Результаты работы программы)

Сравнительный анализ результатов работы алгоритмов представлен в нижеследующих таблицах (таблицах 3.1-3.6)

Для 100 заявок

Таблица 3.1 - ПРОСТОЙ АЛГОРИТМ