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

ВВЕДЕНИЕ

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

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

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

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

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

Для каждого из алгоритмов необходимо:

- провести распределение задач на процессоры по временам их решения;

- вычислить показатели эффективности;

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

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

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

1. Количество процессоров в системе;

2. Число задач в пакете;

3. Времена решения задач.

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

1. Данные о распределение задач на процессоры;

2. Простой процессора;

3. Длина оптимального расписания.

Эти данные должны выдаваться для каждого рассматриваемого метода.

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

2 СВЕДЕНИЯ ИЗ ТЕОРИИ

2.1 Мультипроцессорная обработка

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

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

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

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

В наши дни становится общепринятым введение в ОС функций поддержки мультипроцессорной обработки данных. Такие функции имеются во всех популярных ОС, таких как Sun Solaris 2.x, Santa Crus Operations Open Server 3.x, IBM OS/2, Microsoft Windows NT и Novell NetWare, начиная с 4.1.

2.2 Системы пакетной обработки

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

Для достижения этой цели в системах пакетной обработки используется следующая схема функционирования: в начале работы формируется пакет заданий, каждое задание содержит требование к системным ресурсам; из этого пакета заданий формируется мультипрограммная смесь, то есть множество одновременно выполняемых задач. Для одновременного выполнения выбираются задачи, предъявляющие разные требования к ресурсам, так, чтобы обеспечивалась сбалансированная загрузка всех устройств вычислительной машины. Например, в мультипрограммной смеси желательно одновременное присутствие вычислительных задач и задач с интенсивным вводом-выводом. Таким образом, выбор нового задания из пакета заданий зависит от внутренней ситуации, складывающейся в системе, то есть выбирается «выгодное» задание. Следовательно, в вычислительных системах, работающих под управлением пакетных ОС, невозможно гарантировать выполнение того или иного задания в течение определенного периода времени.

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

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

Рис. 1

Очевидно, что наилучший в смысле минимизации общего времени решения задач - вариант с, для которого время Т решения пакета задач совпадает с соответствующим оптимальным значением Т0 и в данном случае равно величине ? = max {max ti, l/n*?ti }

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

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

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

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

Пример

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

? = max {5, 1/2*(5+4+3+2) } =7.

И расписание, полученное в соответствии с алгоритмом Макнотона,

имеет следующий вид:



Рис. 2

В данном случае число прерываний равно единице.

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

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

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

Рис. 3

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

2.4 Алгоритм LPT

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

Теорема.

При использовании алгоритма LPT для распределения любого пакета П={Zi}, где i=1,…,L, независимых задач без прерываний в системе с n идентичными процессорами справедливо: Т ? (4/3-1/3n)*Т0, где Т- время решения пакета П при распределении задач алгоритмом LPT.

Очевидно, что

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

3 СОЗДАНИЕ ПРОГРАММЫ

3.1 Требования к программе

Программа должна:

· произвести распределение задач на процессоры системы в соответствии с исследуемым алгоритмом;

· вычислить показатели работы алгоритмов;

· вывести результаты в понятной и удобной форме.

3.2 Процедуры и функции программы

Программа разработана в среде Delphi 7.

Procedure Maknotona - процедура реализации алгоритма Макнотона при пакетной обработке задач с прерываниями.

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

Procedure SortBubble - процедура пузырьковой сортировки времен решения задач по убыванию.

Вычисления осуществляются с помощью нажатия на кнопку «Начать». Далее происходит обработка процедуры procedure TForm1.Button1Click, с помощью которой производится ввод данных в массив времён решения задач, а также запускаются основные вычислительные процедуры. Данные заносятся в массив генератором случайных чисел, запускаемым функцией random. Данная функция позволяет получать числа в промежутке от 0 до введенного параметра. Так как необходимо, чтобы время решения было больше нуля, увеличиваем левую границу промежутка на единицу.

В приложении использованы компоненты для вывода результатов работы программы: LabeledEdit и Memo. Компонент LabeledEdit предназначается для вывода времени решения каждой задачи, а Memo - для вывода распределения задач по процессорам и отображения показателей эффективности работы алгоритмов.

3.3 Результаты работы программы

Упорядоченные по убыванию времена решения задач отображены в четырех компонентах LabeledEdit для каждой задачи (Рис. 4).

Рис. 4

Результаты вычислений представлены в двух компонентах Memo. Один предназначен для алгоритма Макнотона (Рис. 5), а другой - для алгоритма LPT (Рис. 6). Для каждого процессора выведены задачи с временами решения. Указывается время простоя процессора и длина оптимального расписания.



Рис. 5

Рис. 6

На форме размещены также кнопки «Начать» и Close. Нажатие на первую из них приводит к выполнению процедуры procedure TForm1.Button1Click, а нажатие на вторую - к закрытию приложения. Рис. 7

3.4 Руководство пользователя

При запуске приложения появляется окно программы с названием «Алгоритмы Макнотона и LPT». Для начала вычислений нужно нажать кнопку «Начать». При этом в четырех верхних окнах появятся упорядоченные времена решения задач, а в двух нижних - результаты вычислений. Чтобы заново сгенерировать времена нужно повторно нажать на кнопку «Начать». Для выхода необходимо использовать кнопку Close. Данный компонент по умолчанию включает в себя функцию закрытия окна.

заключение

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

В процессе работы было разработано приложение в среде Delphi 7. Очевидные преимущества по сравнению с Turbo Pascal, позволили создать простую для понимания визуально оформленную программу.

Исследование алгоритма Макнотона и LPT показало, что в большинстве случаев длина оптимального расписания меньше у алгоритма Макнотона. Однако в реальном применении алгоритм с прерываниями имеет свои недостатки, связанные с тратой времени процессора на обработку прерываний, которых нет при использовании алгоритма LPT.

литература

1. Автоматизированные информационные технологии в экономике: Учебник для вузов /М.И Семенов, И.Т. Трубилин, В.И. Лойко, Т.П. Барановская. - М.: Финансы и статистика, 2002.

2. Семенов М.И, Лойко В.И., Барановская Т.П. Компьютерные системы и сети: Уч. пособие. - Краснодар: КубГАУ, 2002

3. В.В.Фаронов « Турбо Паскаль. Начальный курс», Москва, «Нолидж», 2000г.

4. Шнитман В. Современные высокопроизводительные компьютеры. Центр Информационных Технологий, 1998. http:// www.citmgu.ru.

5. http://www. algolist.manual.ru

Приложение 1. БЛОК-СХЕМА

Процедура Макнотона

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



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

Процедура LPT

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

Процедура SortBubble

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

Приложение 2. ЛИСТИНГ ПРОГРАММЫ

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, ExtCtrls, Buttons;

const L=4; n=3;

type

TForm1 = class(TForm)

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

Label4: TLabel;

Label5: TLabel;

LabeledEdit1: TLabeledEdit;

LabeledEdit2: TLabeledEdit;

LabeledEdit3: TLabeledEdit;

LabeledEdit4: TLabeledEdit;

Button1: TButton;

BitBtn1: TBitBtn;

Memo1: TMemo;

Memo2: TMemo;

procedure Button1Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

a:array [1..L] of integer;

i:integer;

implementation

{$R *.dfm}

procedure SortBubble(var x:array of integer;n:integer);

var buf,i,j:integer;

begin

for i:=1 to n-1 do

for j:=4 downto i do

if x[j-1]<x[j] then begin

buf:=x[j-1];

x[j-1]:=x[j];

x[j]:=buf;

end;

Form1.LabeledEdit1.Text:=inttostr(a[1]);

Form1.LabeledEdit2.Text:=inttostr(a[2]);

Form1.LabeledEdit3.Text:=inttostr(a[3]);

Form1.LabeledEdit4.Text:=inttostr(a[4]);

end;

procedure Maknotona(x:array of integer);

var i,p:integer;

max,buf,buf_1:integer;

begin

max:=0;

for i:=0 to L-1 do max:=max+x[i];

if (max mod n) <> 0 then

max:=1+(max div n)

else

max:=max div n;

if max<x[0] then max:=x[0];

i:=0;

for p:=1 to n do begin

buf:=max;

Form1.Memo1.Lines.Add('Процессор '+inttostr(p));

while (buf>0) do begin

buf_1:=buf;

buf:=buf-x[i];

if (x[i]-buf_1<0)

then

Form1.Memo1.Lines.Add(inttostr(i+1)+' задача='+inttostr(x[i]))

else

Form1.Memo1.Lines.Add(inttostr(i+1)+' задача='+inttostr(buf_1));

x[i]:=x[i]-buf_1;

inc(i);

if i>L-1 then break;

end;

if x[i-1]>0 then dec(i);

if i>l-1 then break;

Form1.Memo1.Lines.Add('');

end;

Form1.Memo1.Lines.Add('');

if p<4 then Form1.Memo1.Lines.Add('Процессор '+inttostr(p)+' стоит '+ inttostr(buf)+' ');

Form1.Memo1.Lines.Add('');

Form1.Memo1.Lines.Add('Длина оптимального расписания '+inttostr(max));

end;

procedure LPT(x:array of integer);

var i,j,max:integer;

begin

j:=0;

max:=x[0];

if (x[n]+x[n-1])>max then

max:=x[n]+x[n-1];

for i:=1 to n do

begin

Form1.Memo2.Lines.Add('Процессор '+inttostr(i));

Form1.Memo2.Lines.Add(inttostr(i)+' задача='+inttostr(x[j]));

if i=n then

begin

Form1.Memo2.Lines.Add('4 задача='+inttostr(x[n]));

Form1.Memo2.Lines.Add('Процессор стоит '+inttostr(max-(x[n]+x[n-1])));

end

else

Form1.Memo2.Lines.Add('Процессор стоит '+inttostr(max-x[j]));

Form1.Memo2.Lines.Add('');

inc(j);

end;

Form1.Memo2.Lines.Add('Длина оптимального расписания '+inttostr(max));

end;

procedure TForm1.Button1Click(Sender: TObject);

begin

Memo1.Clear;

Memo2.Clear;

for i:=1 to L do

a[i]:=1+random(8);

SortBubble(a,L);

Maknotona(a);

LPT(a);

end;

procedure TForm1.FormCreate(Sender: TObject);

begin

Memo1.Clear;

Memo2.Clear;

end;

end.

Размещено на Allbest.ru