Рассмотрим систему, содержащую 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*

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

3. Результаты выполнения программы

Для 100 заявок

Простой алгоритм

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

Алгоритм LPT

Для 1000 заявок

Простой алгоритм

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

Алгоритм LPT

4. Исследования полученных результатов

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

Заключение

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

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

Также мною были получены практические навыки в программировании на алгоритмическом языке высокого уровня Turbo Pascal 7.0.

Список источников

1. Каган Б.М. Электронные вычислительные машины и системы. - М.: Энергоатомиздат, 1991.

2. Методы управлния ресурсами вычислительных систем: Учебное пособие/П.П. Кравченко, А.Г. Чефранов; Таганрог. Радиотехн. ин-т. Таганрог, 1991.

3. Основы теории вычислительных систем/С.А. Майоров, Г.И. Новиков, Т.И. Алиев и др. - М.: Высшая школа, 1987.

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

5. Советов Б.Я. Информационная технология: Учеб. Для вузов по спец. «Автоматизир. системы обработки информ. и упр.». - М.: Высш. шк., 1994.

Приложение 1

program odin;

uses crt; {подключение модуля}

var

i, n, r, g, f, lm, ln, z, p, max, j, lmax, t:integer; {инициализация целочисленных переменных}

k: array [1..10] of integer; {резервирование массива целых чисел}

tc:real; {инициализация дробной переменной}

{-начало исполняемой части программы-}

begin

clrscr; {очистка экрана}

Writeln ('введите количество заявок');

{-вводим с клавиатуры необходимую информацию-}

readln(n);

writeln ('введите количество процессоров');

readln(p);

writeln ('введите минимальную длину заявки');

readln(ln);

writeln ('введите максимальную длину заявки');

readln(lm);

for i:=1 to n do

begin

f:=random (lm-ln+1); {генерируем случайным образом длину заявки}

r:=f+ln;

g:=random(p); {случайным образом выбираем номер процессора,

который будет обрабатываь данную заявку}

z:=g+1;

k[z]:=r+k[z]; {создание очереди заявок для определенного процессора}

end;

max:=k[1]; {принимаем за max время работы первого процессора}

for j:=1 to p do

{-находим реальное максимальное время обработки-}

begin

lmax:=lmax+k[j]; {находим сумму длин всего набора}

if max<k[j] then

max:=k[j];

end;

for j:=1 to p do

t:=t+max-k[j]; {находим сумму времени простоя процессоров}

tc:=t/p; {среднее время простоя процессоров}

{-вывод на экран необходимых данных-}

writeln (lmax, 'сумма длин заявок ', max, 'время работы процессора ', tc, 'время простоя');

readln;

end.

Приложение 2

program dva;

uses {подключение модуля}

crt;

var

n, lmax, ln, lm, i, j, t, p:integer; {инициализация целочисленных переменных}

r: array [1..1000] of integer; {резервирование массива целых чисел}

f, s, max, tc:real; {инициализация дробных переменных}

begin

clrscr; {очистка экрана}

{-блок ввода с клавиатуры необходимых данных-}

writeln ('введите количество заявок');

readln(n);

writeln ('введите количество процессоров');

readln(p);

writeln ('введите минимальную длину заявки');

readln(ln);

writeln ('введите максимальную длину заявки');

readln(lm);

for i:=1 to n do

begin

r[i]:=random (lm-ln+1)+ln; {генерация случайным образом длин заявок}

lmax:=lmax+r[i]; {нахождение суммы длин заявок}

end;

{-сортировка массива заявок по убыванию-}

for i:=2 to n do

begin

for j:=n downto i do

begin

if r [j-1]<r[j] then

begin

t:=r [j-1];

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

r[j]:=t;

end;

end;

end;

f:=lmax/p;

if f>lm then {выбор оптимального времени решения пакета задач}

begin

if (lmax mod p)<>0 then

s:=(lmax div p)+1 {в случае нецелого деления максимального

времени работы на количество процессоров, добавляем такт времени}

else

s:=lmax/p;

tc:=(p*s-lmax)/p; {находим среднее время простоя процессоров}

max:=s; {находим время обработки пакета задач}

end else

begin

tc:=(p*lm-lmax)/p; {среднее время простоя при оптимальном времени решения пакета задач}

max:=lm; {время обработки задач}

end;

{-выводим на экран необходимых даннных-}

writeln (lmax, 'сумма длин заявок ', max, 'время работы процессора ', tc, 'среднее время простоя');

readln; end.

Приложение 3

program tri;

uses

crt; {подключение модуля}

var

n, maxt, l, k, y, t, f, w, p, ln, lm, s, e, lmax, j, i:integer; {инициализация целочисленных переменных}

z, r: array [1..1000] of integer; {резервирование двух массивов}

tc:real; {инициализация дробной переменной}

begin

{-начало исполняемой части программы-}

clrscr; {очистка экрана}

{-вводим с клавиатуры необходимую информацию-}

writeln (' введите количество заявок');

readln(n);

writeln ('введите количество процессоров');

readln(p);

writeln('');

readln(ln);

writeln ('введите минимальную длину заявок');

readln(lm);

for i:=1 to n do

begin

r[i]:=random (lm-ln+1)+ln; {генерируем случайным образом массив заявок}

k:=k+r[i]; {находим сумму длин заявок}

end;

{-сортируем массив заявок по убыванию-}

for i:=1 to n do

begin

for j:=1 to n do

begin

if r[j]<r[i] then

begin

t:=r[i];

r[i]:=r[j];

r[j]:=t;

end;

end;

end;

{-цикл обработки заявок-}

repeat

for w:=1 to p do

begin

if e=n then break; {выход их цикла если все заявки обработаны}

if z[w]=0 then {если заявка обработана полностью,

то приступаем к обработке следующей заявки}

begin e:=e+1; {счетчик обработанных заявок}

z[w]:=r[e]; {выбор очередной обрабатываемой заявки}

end;

end;

l:=p; {присваиваем значение количества процессоров}

i:=0; {счетчик цикла}

repeat

if e=n then

begin

f:=f+1; {находим время работы процессора}

break; {выход из цикла, если обработаны все заявки}

end;

i:=i+1; {переход к очередной заявке}

z[i]:=z[i] - 1; {обработка части заявки за один такт процессорного времени}

l:=l-1; {счетчик цикла с постусловием}

until (l=0); {если каждый процесс отработал один такт, то цикл завершается}

f:=f+1; {время работы процессора}

until (e=n); {если все заявки обработаны, то цикл завершается}

maxt:=z[1]; {принимаем время работы первого процессора за максимальное}

for i:=1 to p do

begin

{реальное максимальное время работы одного процессора}

if z[i]>maxt then maxt:=z[i];

end;

f:=f+maxt-2;

{-находим суммарное время простоя процессоров-}

for i:=1 to p do s:=s+maxt-z[i];

tc:=s/p; {среднее время простоя процессоров}

{выводим полученные данные на экран}

writeln (k, 'сумма длин заявок ', f, ' время работы процессора ', tc, ' среднее время простоя ');

readln;

end.

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

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