Протокол передачи кадров

1. Постановка задачи

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

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

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

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

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

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

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

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

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

Оперативная память объемом не меньше 8 Мбайт для Windows 95 или 16 Мбайт для Windows 98.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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, ½*(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, в оптимальном расписании ложно.

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*

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

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

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]

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]

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.

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