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

СОДЕРЖАНИЕ Введение

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

1.1 Общие положения

1.2 Алгоритм SPT

1.3 Алгоритм FB

2. ПРОГРАМНАЯ РЕАЛИЗАЦИЯ

2.1 Глобальные переменные и константы

2.2 Описание программы

3. Результаты работы алгоритмов и их анализ ЗАКЛЮЧЕНИЕ СПИСОК ИСПОЛЬЗУЕМОЙ ЛИТЕРАТУРЫ ПРИЛОЖЕНИЕ 1

ПРИЛОЖЕНИЕ 2

ВВЕДЕНИЕ

Компьютерные сети уже перестали быть такой редкостью, которой они были лет двадцать назад, когда их могли себе позволить только научные организации, проводящие исследования в «высоких» технологиях. Это было связанно с тем, что сами компьютеры были большого размера и стоили очень дорого. Но, а главная причина столь небольшого распространения была не в больших габаритах и не в большой стоимости, а первую очередь в отсутствии технологий и программного обеспечения способствующего быстрой передачи данных, надежности передачи и т. д. С развитием науки многие задачи были успешно решены. И в настоящие время компьютерами некого не удивишь, компьютерные сети получили широкое распространение. Компьютеры и сети стали не роскошью, а необходимым средством которое помогает сократить время обработки информации, а всемирная сеть — интернет предоставляет возможность поиска информации, общения с другими людьми в других странах, покупать товар, и т. д. Основными характеристиками любой сети является скорость передачи информации. Главными элементами сети являются серверы которые связывают удаленные компьютеры друг с другом .

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

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

1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

1.1 Общие положения Компьютерная сеть — это система обмена информацией между компьютерами. Представляет собой совокупность трех компонентов:

I. Сети передачи данных (включающей каналы передачи данных и средства коммутации)

II. Компьютеров, взаимосвязанных сетью передачи данных

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

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

1.2 Алгоритм SPT

В системах оперативной обработки в качестве основного критерия эффективности используется среднее время обслуживания заявок. Нетрудно видеть, что в случае, когда времена решения задач априори известны, минимальное среднее время ответа дает алгоритм SPT (Shortest-processing-task-first), назначающий задачи на решение в порядке убывания времени решения ti, т. е. t1? t2???tL. При этом время ответа ui для задачи zi есть

ti — собственно время решения и среднее время ответа есть Покажем, что u* действительно минимальное значение среднего времени обслуживания. Для того чтобы показать, что u* действительно минимально среди u для всех перестановок, достаточно показать, что применение к произвольной перестановке (б1,…, бL) любой парной транспозиции, меняющей местами элементы бk и бl, где tбl? tбk и l>k, может лишь уменьшить исходное значение u, соответствующее перестановке (б1,…, бL), где бi — номер задачи, назначаемой на решение i-й по порядку, i=I, L. Действительно, пусть задачи с номерами бk и б1 поменялись местами. Тогда для полученной перестановки среднее время обслуживания равно так как l>k, а tбl? tбk. Следовательно, перемещение вперед задачи с меньшим временем решения приводит к уменьшению среднего времени обслуживания. В перестановке (1, …, L) при условии, что t1??? tL, нельзя сделать ни одной такой улучшающей транспозиции, а потому u* есть минимальное среднее время обслуживания и алгоритм SPT дает оптимальное решение рассматриваемой задачи.

1.3 Алгоритм fb

Для обеспечения еще более быстрой реакции системы на короткие работы в системах оперативной обработки используются алгоритмы многоуровневого циклического планирования. Одним из таких алгоритмов является алгоритм FB (foreground-background). Принцип его работы можно проиллюстрировать следующей схемой:

Заявки на выполнение работ поступают в очередь O1. Работы, стоящие в очереди O1, получают квант процессорного времени q. Если за это время работа была выполнена, то она покидает систему. В противном случае заявка на работу переносится в очередь O2, откуда она может быть занесена в очереди O3, O4,…, On. Очереди обслуживаются в следующем порядке. Если имеется хотя бы одна заявка в очереди O1, то эта заявка непременно обслуживается. Заявки из очереди O2 обслуживаются при условии, что нет заявок в очереди O1. Аналогично заявки из очереди Om обслуживаются только в том случае, если все очереди O1,…, Om-1 пусты. Заявка, достигшая последней очереди On, остается в ней до полного завершения работы.

Применяются модификации алгоритма FB, различающиеся по величине квантов времени, предоставляемых заявкам из разных очередей. Возможно планирование на основе постоянной величины кванта или с использованием квантов переменной длительности, которая возрастает по мере увеличения номера очереди. Одна из таких модификаций — алгоритм планирования FB с учетом приоритетов работ. Работы, поступающие в систему, разделяются в зависимости от приоритетов I, …, n на n потоков l1, …, ln. Приоритеты задач относительны, т. е. поступление в систему заявки более высокого приоритета не прерывает процесс обработки менее приоритетных заявок, но при освобождении ресурса более приоритетные заявки будут назначены в первую очередь. Работы с высшим приоритетом поступают в очередь O1, а работы с низким приоритетом — в очередь On. Работам, выбираемым на обслуживание из разных очередей, выделяются кванты времени различной длительности, причем заявкам из очереди Om выделяется больший по продолжительности квант времени, чем заявкам из очереди Om-1, m=2,n.

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

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

Например, операционная система для малых ЭВМ ОСРВ обеспечивает две процедуры разделения времени — циклическое планирование и вытеснение на диск. Процедура циклического планирования через заданный интервал времени циклически перемещает указатель задач в таблице задач системы STD (System Task Directory) и объявляет значимое событие, в результате обработки которого происходит перепланирование задач. Планировщик выбирает для выполнения первую задачу из STD. Обычно интервал времени циклического планирования устанавливается равным 0.1с.

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

— задача должна быть установлена как вытесняемая;

— на диске есть более приоритетная задача, для которой нет места в основной памяти;

— задача не имеет незавершенных запросов ввода-вывода (кроме запроса ввода с терминала).

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

Приоритетность программ для систем со свопингом может назначаться в соответствии с алгоритмом Корбато. Здесь априорно принимается следующее предположение: программы с большей длиной — более трудоемкие.

Исходя из этого предположения приоритеты программам присваиваются на основе формулы

где [x] - целая часть X; Ln — длина программы в байтах;

Lq — число байтов, передаваемых между оперативной и внешней памятью за время q, равное минимальной длительности кванта.

Отношение определяет число квантов времени, необходимых для загрузки программы в оперативную память и для вывода ее из оперативной памяти. Работа с приоритетом r заносится в очередь Op. Очередям с номерами p=1, …, n выделяются кванты времени длительности где q — квант времени, выделяемый для работ из очереди O1 .

Таким образом, очередям O1, O2, O3, O4, … соответствуют кванты времени q, 2q, 4q, 8q,… Увеличение кванта времени на выполнение работ с большой трудоемкостью способствует сокращению числа прерываний работы процессора и числа пересылок программ между оперативной и внешней памятью.

2. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ

2.1 Глобальные переменные и константы программы

const

kv=4; // константа указывает размер кванта

n1=100; // констаннта указывает количество заявок в очереди

n2=1000;// констаннта указывает количество заявок в очереди

n3=10 000;// констаннта указывает количество заявок в очереди

var

a:mas;// массив в который записываются числовые характеристики по результатам работы алгоритмов

a1,s1:mas1;//массив в который записывается очередь в n1 заявок

a2,s2:mas2;// массив в который записывается очередь в n2 заявок

a3,s3:mas3;// массив в который записывается очередь в n3 заявок

i, z: integer;.// счетчики сеть сервер алгоритм данные

2,2 Описание программы В программе описываются следующие переменные: n — число элементов в очереди, изначально вводится пользователем с клавиатуры; Lmin, Lmax — переменные, определяющие длину минимальной и максимальной заявки соответственно и также вводятся с клавиатуры пользователем. переменная L типа integer определяет частоту процессора. Рабочий массив заявок Z хранит длины заявок, при этом число заявок n не должно превышать 1000.

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

Далее происходит сортировка массива заявок методом пузырька.

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

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

3. РЕЗУЛЬТАТЫ РАБОТЫ АЛГОРИТМОВ И ИХ АНАЛИЗ АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ АЛГОРИТМОВ SPT И FB

Таблица 1. Результаты работы программы при n=100 элементов

P — вероятность прихода заявки;

W1 — диапазон длительности заявки от 0 до 6;

W2 — диапазон длительности заявки от 2 до 8.

Сравним производительность алгоритмов SPT и FB, при n=100 элементов.

При вероятности прихода заявки равной 30% и при диапазоне длительности заявки от 0 до 6 сумма всех заявок алгоритма SPT равна 258, а алгоритма FB равна 259. Время обработки очереди алгоритма SPT равно 135, а алгоритма FB равно 100. Разница между средним временем ожидания двух алгоритмов составляет 1, 199.

При вероятности прихода заявки равной 30% и при диапазоне длительности заявки от 2 до 8 сумма всех заявок алгоритма SPT равна 457, а алгоритма FB равна 436. Время обработки очереди алгоритма SPT равно 167, а алгоритма FB равно 120. Разница между средним временем ожидания двух алгоритмов составляет 4, 221.

При вероятности прихода заявки равной 70% и при диапазоне длительности заявки от 0 до 6 сумма всех заявок алгоритма SPT равна 240, а алгоритма FB равна 240. Время обработки очереди алгоритма SPT равно 136, а алгоритма FB равно 100. Разница между средним временем ожидания двух алгоритмов составляет 0, 649.

При вероятности прихода заявки равной 70% и при диапазоне длительности заявки от 2 до 8 сумма всех заявок алгоритма SPT равна 440, а алгоритма FB равна 440. Время обработки очереди алгоритма SPT равно 159, а алгоритма FB равно 110. Разница между средним временем ожидания двух алгоритмов составляет 4, 098.

Из сводной таблицы видно, что наиболее производительным является алгоритм FB, так как среднее время ожидания достаточно мало по сравнению с алгоритмом SPT. Что касается времени обработки всей очереди, то алгоритм FB примерно в 1,2 раза работает быстрее, чем алгоритм SPT.

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

Таблица 2. Результаты работы программы при n=1000 элементов

При вероятности прихода заявки равной 30% и при диапазоне длительности заявки от 0 до 6 сумма всех заявок алгоритма SPT равна 2536, а алгоритма FB равна 2586. Время обработки очереди алгоритма SPT равно 1339, а алгоритма FB равно 1000. Разница между средним временем ожидания двух алгоритмов составляет 0, 875.

При вероятности прихода заявки равной 30% и при диапазоне длительности заявки от 2 до 8 сумма всех заявок алгоритма SPT равна 4436, а алгоритма FB равна 4505. Время обработки очереди алгоритма SPT равно 1645, а алгоритма FB равно 1000. Разница между средним временем ожидания двух алгоритмов составляет 4, 262.

При вероятности прихода заявки равной 70% и при диапазоне длительности заявки от 0 до 6 сумма всех заявок алгоритма SPT равна 2376, а алгоритма FB равна 2484. Время обработки очереди алгоритма SPT равно 1290, а алгоритма FB равно 1000. Разница между средним временем ожидания двух алгоритмов составляет 0,99.

При вероятности прихода заявки равной 70% и при диапазоне длительности заявки от 2 до 8 сумма всех заявок алгоритма SPT равна 4494, а алгоритма FB равна 4498. Время обработки очереди алгоритма SPT равно 1666, а алгоритма FB равно 1000. Разница между средним временем ожидания двух алгоритмов составляет 3, 472.

Несмотря на значительное увеличение количества заявок в очереди, самым производительным алгоритмом остается по-прежнему алгоритм однопроцессорной обработки FB.

Рис. 3 Соотношение суммы заявок и времени их обработки (алгоритм SPT и FB) при n=1000.

Рис. 4 Соотношение суммы заявок и времени их обработки (алгоритм SPT и FB) при n=100.

ЗАКЛЮЧЕНИЕ

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

Протестировав программы при различных значениях вероятности прихода заявок (30% и 70%), различных диапазонах размеров заявки (0−6 и 2−8), различных длинах очереди (100 и 1000 элементов) и частотой процессора 4 можно сделать вывод, что наиболее эффективным и быстродействующим алгоритмом является алгоритм FB.

ПРИЛОЖЕНИЕ, А Листинг программы

begin

if frac (x/kv)= 0 then perevod:=round (x/kv) если остаток от деления на длину кванта равен нулю, то длина заявки равна x/kv

else perevod:=trunc (x/kv)+1; а если нет, то длина заявки равна x/kv +1

end;

Procedure Rand (o, d, v:integer); начало процедуры которая заполняет очередь заявками

var

q, j: longint;

begin

randomize;

for q:=1 to n3 do цикл работает по наибольшему количеству заявок в очереди

begin

if random (100)

begin

j:=random (d);пременной присваивается кокое либо значение от 0 до d

repeat этот цикл выполняет условие, что если заявка пришла в очередь то она не нулевая, это сделанно для того, что бы не было слишком много нулевых заявок. Количество нулевых заявок в очереди равно (100-V)% от общего числа заявок

j:=random (d);

until j>=o;

эти условия неоходимы чтобы не происходило запись элементов за пределы массивов

if (q<=n1) then begin a1[q]: =j; s1[q]: =j; end;

if (q<=n2) then begin a2[q]: =j; s2[q]: =j; end;

if (q<=n3) then begin a3[q]: =j; s3[q]: =j; end;

end;

end;

end;

Procedure SPT (n, r: integer; var a4: mas); начало процедуры реализующей алгоритм SPT;n — количество заявок в очереди r — переменная указывающая необходимо сортировать массив перед абработкой, a4 — массив в который записываются результаты

var

i, j, k, sum, vra, vr: longint;счетсики и переменные в которые будут записываться результаты выполнения

begin

if (r>0)and (n=n1) then выполняется проверка на необходимость сортировки массива с количеством элементов n1

begin

Сортировка массива пузырьковым методом

for i:=1 to N do

for j:=(N-1) downto 1 do

if a1[j]>a1[j+1] then begin

k:=a1[j+1];

a1[j+1]:=a1[j];

a1[j]:=k;

end;

end;

if (r>0)and (n=n2) then выполняется проверка на необходимость сортировки массива с количеством элементов n2

begin

Сортировка массива пузырьковым методом

for i:=1 to N do

for j:=(N-1) downto 1 do

if a2[j]>a2[j+1] then begin

k:=a2[j+1];

a2[j+1]:=a2[j];

a2[j]:=k;

end;

end;

if (r>0)and (n=n3) then выполняется проверка на необходимость сортировки массива с количеством элементов n3

begin

Сортировка массива пузырьковым методом

for i:=1 to N do

for j:=(N-1) downto 1 do

if a3[j]>a3[j+1] then begin

k:=a3[j+1];

a3[j+1]:=a3[j];

a3[j]:=k;

end;

end;

Данное условие необходимо чтобы определить какой массив необходимо обрабатывать

if n=n1 then если условие выполняется то быдет обрабатывать массив а1

begin

происходит обнуление элементов

k:=0;

j:=0;

sum:=0;

vra:=0;

vr:=0;

for i:=1 to n do цикл по очереди вынимает из массива элементы которые обрабатываются

begin

sum:=sum+a1[i]; в переменную записывается сумма длин всех заявок

vra:=vra+perevod (a1[i]); в пепеменную записывается время необходимое для выполнения всей очереди

if (a1[i]<=kv) and (a1[i]>0) then происходит подсчет количества коротких заявок и времени ожидания

begin

k:=vra;

inc (j);

end;

if a1[i]=0 then inc (vr); подсчитывается прцент не прихода заявки т. е. процент нулевых заявок

end;

i:=1;

while a4[i]<>0 do с помощью этого цикла мы проходим по заявке и останавливаемся на пустом элементе куда в дальней шем будет произведена запись результатов.

begin

inc (i);

end;

a4[i]: =sum;

a4[i+1]:=vra;

a4[i+2]:=k/j;

a4[i+3]:=(vr/n1)*100;

end;

ПРИЛОЖЕНИЕ В Блок-схема алгоритма SPT

Блок-схема алгоритма FB