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

Главная

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

Производительность алгоритмов SPT и FB. Глобальные переменные и константы программы. Компьютерная сеть передачи данных. Каналы передачи данных и средства коммутации. Сетевое программное обеспечение. Распределение ресурсов однопроцессорных серверов.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

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

2.1 Глобальные переменные и константы
3. Результаты работы алгоритмов и их анализ
Компьютерные сети уже перестали быть такой редкостью, которой они были лет двадцать назад, когда их могли себе позволить только научные организации, проводящие исследования в “высоких” технологиях. Это было связанно с тем, что сами компьютеры были большого размера и стоили очень дорого. Но, а главная причина столь небольшого распространения была не в больших габаритах и не в большой стоимости, а первую очередь в отсутствии технологий и программного обеспечения способствующего быстрой передачи данных, надежности передачи и т.д. С развитием науки многие задачи были успешно решены. И в настоящие время компьютерами некого не удивишь, компьютерные сети получили широкое распространение. Компьютеры и сети стали не роскошью, а необходимым средством которое помогает сократить время обработки информации, а всемирная сеть - интернет предоставляет возможность поиска информации, общения с другими людьми в других странах, покупать товар, и т.д.. Основными характеристиками любой сети является скорость передачи информации. Главными элементами сети являются серверы которые связывают удаленные компьютеры друг с другом .
Целью данной курсовой работы является исследование алгоритмов управления ресурсами однопроцессорных серверов при оперативной обработке задач, на основе алгоритмов SPT и FB.
Для программной реализации данных алгоритмов мною выбран язык программирования Turbo Pascal. Язык Pascal частично используется в сфере высшего образования в качестве “первого языка программирования”. Благодаря широкой сфере применения и простоте использования, язык программирования Turbo Pascal получила широкое распространение, как в профессиональных, так и в любительских кругах.
Компьютерная сеть - это система обмена информацией между компьютерами. Представляет собой совокупность трех компонентов:
I. Сети передачи данных (включающей каналы передачи данных и средства коммутации)
II. Компьютеров, взаимосвязанных сетью передачи данных
III. Сетевого программного обеспечения
Любая компьютерная сеть состоит из компьютеров (клиентов), имеющих доступ к сети и серверов. Сервер - это высокопроизводительный компьютер с большим объемом внешней памяти, который обеспечивает обслуживание других компьютеров путем управления распределением дорогостоящих ресурсов совместного пользования. Связь между клиентом и сервером осуществляется методом посылания запросов, в которых указана его сущность, т.е. какую информацию необходимо найти и отправить на компьютер, который прислал этот запрос. И чем больше количество компьютеров в сети, тем более высоко производительней должен быть сервер, так в небольшой локальной сети состоящей из нескольких компьютеров роль сервера может играть один из них. А чтобы обеспечить нормальную работу сети состоящей из сотен компьютеров необходимо иметь специальный компьютер с высокой производительностью, на котором должна быть установлена специальная операционная система, которая обеспечивала бы быстрый доступ клиентов сети к информации, располагающейся на сервере. В зависимости от назначения сервера они различаются и программным обеспечение и архитектурой. При разработке сетевого программного обеспечения особое внимание уделяется алгоритмам, по которым будет происходить обработка запросов.
В данной курсовой работе будет произведен анализ двух алгоритмов распределения ресурсов однопроцессорных серверов. Основным показателем эффективности является среднее время ожидания для короткой заявки. Для более качественного анализа опыты будут проведены с различными условиями.
В системах оперативной обработки в качестве основного критерия эффективности используется среднее время обслуживания заявок. Нетрудно видеть, что в случае, когда времена решения задач априори известны, минимальное среднее время ответа дает алгоритм 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 дает оптимальное решение рассматриваемой задачи.
Для обеспечения еще более быстрой реакции системы на короткие работы в системах оперативной обработки используются алгоритмы многоуровневого циклического планирования. Одним из таких алгоритмов является алгоритм 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.1 Глобальные переменные и константы программы
kv=4; // константа указывает размер кванта
n1=100; // констаннта указывает количество заявок в очереди
n2=1000;// констаннта указывает количество заявок в очереди
n3=10000;// констаннта указывает количество заявок в очереди
a:mas;// массив в который записываются числовые характеристики по результатам работы алгоритмов
a1,s1:mas1;//массив в который записывается очередь в n1 заявок
a2,s2:mas2;// массив в который записывается очередь в n2 заявок
a3,s3:mas3;// массив в который записывается очередь в n3 заявок
В программе описываются следующие переменные: n - число элементов в очереди, изначально вводится пользователем с клавиатуры; Lmin, Lmax - переменные, определяющие длину минимальной и максимальной заявки соответственно и также вводятся с клавиатуры пользователем. переменная L типа integer определяет частоту процессора. Рабочий массив заявок Z хранит длины заявок, при этом число заявок n не должно превышать 1000.
Программа начинает свою работу с запроса о вводе входных показателей: количество заявок в очереди, тактовая частота процессора, длина минимальной и максимальной заявки.
Далее происходит сортировка массива заявок методом пузырька.
Следующим шагом программа определяет, является ли заявка короткой или длинной. Если заявка короткая, то счетчик коротки заявок увеличивается на единицe, происходит также подсчет среднего времени простоя процессора. Длинные заявки переносятся в массив k, который будет обрабатываться в последнюю очередь согласно теории составления алгоритма FB.
После того, как в массиве заявок не останется ни одной заявки, программа выведет результат на экран.
3. РЕЗУЛЬТАТЫ РАБОТЫ АЛГОРИТМОВ И ИХ АНАЛИЗ АНАЛИЗ ПРОИЗВОДИТЕЛЬНОСТИ АЛГОРИТМОВ SPT И FB
Таблица 1. Результаты работы программы при n=100 элементов
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.
if frac(x/kv)= 0 then perevod:=round(x/kv) если остаток от деления на длину кванта равен нулю, то длина заявки равна x/kv
else perevod:=trunc(x/kv)+1; а если нет, то длина заявки равна x/kv +1
Procedure Rand(o,d,v:integer); начало процедуры которая заполняет очередь заявками
for q:=1 to n3 do цикл работает по наибольшему количеству заявок в очереди
if random(100)0)and(n=n1) then выполняется проверка на необходимость сортировки массива с количеством элементов n1
Сортировка массива пузырьковым методом
if (r>0)and(n=n2) then выполняется проверка на необходимость сортировки массива с количеством элементов n2
Сортировка массива пузырьковым методом
if (r>0)and(n=n3) then выполняется проверка на необходимость сортировки массива с количеством элементов n3
Сортировка массива пузырьковым методом
Данное условие необходимо чтобы определить какой массив необходимо обрабатывать
if n=n1 then если условие выполняется то быдет обрабатывать массив а1
for i:=1 to n do цикл по очереди вынимает из массива элементы которые обрабатываются
sum:=sum+a1[i]; в переменную записывается сумма длин всех заявок
vra:=vra+perevod(a1[i]); в пепеменную записывается время необходимое для выполнения всей очереди
if (a1[i]<=kv) and(a1[i]>0) then происходит подсчет количества коротких заявок и времени ожидания
if a1[i]=0 then inc(vr); подсчитывается прцент не прихода заявки т.е. процент нулевых заявок
while a4[i]<>0 do с помощью этого цикла мы проходим по заявке и останавливаемся на пустом элементе куда в дальней шем будет произведена запись результатов.

Критерии и основные стратегии планирования процессора. Разработка моделей алгоритмов SPT (Shortest-processing-task-first) и RR (Round-Robin). Сравнительный анализ выбранных алгоритмов при различных условиях и различном количестве обрабатываемых данных. курсовая работа [179,3 K], добавлен 21.06.2013
Разработка вычислительной однопроцессорной программы, реализующей работу процессора по обработке очереди заявок переменной длины без предварительной сортировки заявок по длительности, с предварительной сортировкой заявок по длительности, по алгоритму SPT. курсовая работа [141,7 K], добавлен 21.06.2013
Устройство компьютерных сетей. Системы для передачи информации, состоящие из терминалов, серверов и коммуникационной среды. Технические, программные и информационные средства сетей. Классификация компьютерных сетей. Сетевые операционные системы. курсовая работа [3,7 M], добавлен 10.07.2014
Локальная сеть – группа связанных между собой компьютеров, серверов, принтеров: архитектура, топологии, оборудование, маршрутизаторы; протоколы передачи данных, уровни модели OSI. Сетевое администрирование; управление безопасностью; совершенствование ЛКС. дипломная работа [633,1 K], добавлен 29.06.2012
Обоснование выбора средства программирования: входная и выходная информация, требования к аппаратному и программному обеспечению. Функциональное назначение программы, её глобальные переменные и константы, внутренняя структура и руководство пользователя. курсовая работа [1,4 M], добавлен 07.09.2012
Технологии и каналы передачи данных компьютерных сетей. Коаксиальные кабельные каналы. Технические средства коммуникации, сетевое оборудование: сетевые адаптеры, повторители, разветвители, мосты, маршрутизаторы, шлюзы, их функции, типы и преимущества. реферат [26,2 K], добавлен 10.02.2012
Роль компьютерных сетей, принципы их построения. Системы построения сети Token Ring. Протоколы передачи информации, используемые топологии. Способы передачи данных, средства связи в сети. Программное обеспечение, технология развертывания и монтажа. курсовая работа [279,7 K], добавлен 11.10.2013
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .

© 2000 — 2021



Исследование алгоритмов управления ресурсами однопроцессорных серверов при оперативной обработке задач курсовая работа. Программирование, компьютеры и кибернетика.
Право Частной Собственности На Землю Курсовая Работа
Курсовая работа: Представление о неразменных деньгах
Дипломная работа по теме Модернизация компрессора установки валоповорота паровой турбины
Реферат: Решение индивидуальных трудовых споров
Курсовая работа: Проблема зрительных ощущений в общей психологии
Курсовая работа по теме Роль и значение нотариата в защите гражданских прав
Реферат: Оценка радиационной обстановки на объекте. Особенности управления объектом экономики при радиаци
Заявление На Итоговое Сочинение
Решение Задачи Контрольная Работа Вариант 2
Қалай Киінген Дұрыс Эссе
Аппараты для жарки
Реферат по теме Инвестиционные риски
Курсовая работа: Партизанское движение в Отечественной войне 1812 года
Сочинение По Картине Художник В Поле Бунина
Курсовая работа по теме Главные особенности современной естественной науки
Доклад по теме В чем уникальность планеты Земля? (У чому унікальність планети Земля?)
Лабораторная Работа На Тему Тепловое Испытание Газотурбинной Установки
Реферат: Проблема души и тела
Общая Физическая Подготовка Цели И Задачи Реферат
Курсовая работа: Понятие и особенности договора поручения
Государственное строительство в 1991-1993 гг. - Государство и право эссе
Оценка результатов инновационной деятельности (на примере ООО "Белосток") - Менеджмент и трудовые отношения курсовая работа
Теоретические основы квалификации преступлений - Государство и право контрольная работа