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

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

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

МИНИСТЕРСТВО СЕЛЬСКОГО ХОЗЯЙСТВА РОССИЙСКОЙ ФЕДЕРАЦИИ

КУБАНСКИЙ ГОСУДАРСТВЕННЫЙ АГРАРНЫЙ УНИВЕРСИТЕТ

Факультет прикладной информатики

Кафедра компьютерных технологий и систем

Курсовая работа

по дисциплине

"Вычислительные системы, сети и телекоммуникации"

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

Исполнитель: Чигиринов Р. В.

факультет «Прикладная информатика», учебная группа ПИЭ-33

Руководитель: Ткаченко В. В.

Краснодар - 2007

СОДЕРЖАНИЕ

Введение

1. Управление процессами

1.1 Понятие Процесса. Состояния процесса

1.2 Планирование процессов. Понятие очереди

2. Планирование процессора

2.1 Критерии планирования процессора9

2.2 Стратегии планирования процессора10

2.2.1 Первый пришел - первый обслуживается FIFO. First come - First served (FCFS)

2.2.2 Стратегия SJF (Shortest job first)

2.2.3 Приоритетное планирование

2.2.4 “Карусельная” стратегия планирования. RR (Round Robin).

2.2.5 Планирование с использованием многоуровневой очереди.(Multilevel queue scheduling)

2.2.6. Программирование с использованием многоуровневой очереди с обратными связями (multilevel feedback queue sheduling)

3. Алгоритмизация и программирование методов «RR» и «SPT»

3.1 Алгоритм стратегии планирования SPT (Shortest-processing-task-first.)

3.2 Программная реализация метода SPT (Shortest-processing-task-first.)

3.3 Алгоритм стратегии планирования . RR (Round Robin)

3.4 Программная реализация метода RR (Round Robin)

3.5 Результаты расчетов и их сопоставление

Заключение

Список используемой литературы

Приложение

Введение

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

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

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

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

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

- постановка процессов в очередь готовых к выполнению;

- управление очередью готовых процессов;

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

Планирование процессов включает в себя решение следующих задач:

- определение момента времени для смены выполняемого процесса;

- выбор процесса на выполнение из очереди готовых процессов.

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

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

В курсовой работе будут разработаны модели алгоритмов SPT (Shortest-processing-task-first) и RR (Round-Robin). Также будет проведен сравнительный анализ выбранных алгоритмов при различных условиях и различном количестве обрабатываемых данных.

1. Управление процессами

1.1 Понятие Процесса. Состояния процесса.

Не следует смешивать понятия процесс и программа. Программа - это план действий, а процесс - само действие. Понятие процесс включает:

1. программный код;

2. данные;

3. содержимое стека;

4. содержимое адресного и других регистров CPU.

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

Различают следующие состояния процесса:

1. новый (new, процесс только что создан);

2. выполняемый (running, команды программы выполняются в CPU);

3. ожидающий (waiting, процесс ожидает завершения некоторого события, чаще всего операции ввода - вывода);

4. готовый (ready, процесс ожидает освобождения CPU);

5. завершенный (terminated, процесс завершил свою работу).

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

1.2 Планирование процессов. Понятие очереди

Система управления процессами обеспечивает прохождение процесса через компьютер. В зависимости от состояния процесса ему должен быть предоставлен тот или иной ресурс, например, «новый» процесс необходимо разместить в основной памяти, следовательно, ему необходимо выделить часть адресного пространства. Процессу в состоянии «готовый» должно быть предоставлено процессорное время. «Выполняемый» процесс может потребовать оборудование ввода-вывода и доступ к файлу.

Распределение процессов между имеющимися ресурсами носит название планирование процессов. Одним из методом планирования процессов, ориентированных на эффективную загрузку ресурсов, является метод очередей ресурсов. Новые процессы находятся во входной очереди, часто называемой очередью работ - заданий (job queue).

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

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

Процесс в состоянии ожидания завершения операции ввода - вывода находится в одной из очередей к оборудованию ввода - вывода, которое носит название devices queue.

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

(scheduler) Операционная система, обеспечивающая режим мультипрограммирования, обычно включает два планировщика -- долгосрочный

(long term scheduler) и краткосрочный (short term scheduler/CPU scheduler).

Основное отличие между долгосрочным и краткосрочным планировщиками заключается в частоте запуска, например: краткосрочный планировщик может запускаться каждые 100 мс, долгосрочный -- один раз за несколько минут.

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

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

Краткосрочный планировщик решает, какой из процессов, находящихся в очереди готовых процессов, должен быть передан на выполнение в CPU. В некоторых операционных системах долгосрочный планировщик может отсутствовать. Например, в системах разделения времени (time sharing system), каждый новый процесс сразу же помещается в основную память.

1.3 Взаимодействие процессов. Пользовательский уровень

Совместно выполняемые процессы могут быть либо независимыми (independed processes), либо взаимодействующими (cooperating processes).

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

Взаимодействие процессов удобно рассматривать в схеме производитель - потребитель (produces - consumer). Например, программа вывода на печать, производит последовательность символов, которые потребляются драйвером принтера или компилятор производит ассемблерный текст, который затем потребляется ассемблером.

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

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

- буфер заполнен; ожидает процесс - производитель;

- буфер пуст; ожидает процесс - потребитель.

Буфер представлен в виде циклически связанного массива адресуемых элементов с двумя указателями - in, out. Указатель in содержит номер первого свободного элемента буфера, а out - первого занятого элемента буфера.

1. Пуст. in=out. Очевидно, что буфер пуст в том случае, если выполняется это условие.

2. Буфер будет полностью заполнен, если выполняется условие (in+1) mod n = out.

Процесс - производитель должен выполнять процедуру записи в буфер типа

Repeat

- продуцируется очередной элемент в Next p;

- while (in+1) mod n = out do no_op; buffer (in):=next p; in:=(in+1) mod n; until false.

Где next p - локальная переменная процесса - производителя, в которой хранится очередной продуцируемый элемент no_op - пустой оператор.

Процесс - потребитель должен выполнять процедуру чтения из буфера типа:

Repeat while in out do no_op; next p := buffer (out); out:=(out+1) mod n;

- потребляется очередной элемент из Next с;

until false.

2. Планирование процессора

Краткосрочный планировщик выбирает процессы из очереди готовых процессов и передает их на выполнение в CPU.

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

2.1 Критерии планирования процессора

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

1. утилизация CPU (использование) CPU utilization. утилизация CPU теоретически может находиться в пределах от 0 до 100%. В реальных системах утилизация CPU колеблется в пределах 40% для легко загруженного CPU, 90% для тяжело загруженного CPU.

2. пропускная способность CPU throughput. Пропускная способность CPU может измеряться количеством процессов, которые выполняются в единицу времени.

3. время оборота (turnaround time) для некоторых процессов важным критерием является полное время выполнения, то есть интервал от момента появления процесса во входной очереди до момента его завершения. Это время названо временем оборота и включает время ожидания во входной очереди, время ожидания в очереди готовых процессов, время ожидания в очередях к оборудованию, время выполнения в процессоре и время ввода - вывода.

4. время ожидания (waiting time). под временем ожидания понимается суммарное время нахождения процесса в очереди готовых процессов.

5. время отклика (response time) для сугубо интерактивных программ важным показателем является время отклика или время, прошедшее от момента попадания процесса во входную очередь до момента первого обращения к терминалу.

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

В ряде случаев используются сложные критерии, например так называемый минимаксный критерий, то есть вместо простого критерия минимум среднего времени отклика используется следующий -- минимум максимального времени отклика.

2.2 Стратегии планирования процессора

2.2.1 Первый пришел - первый обслуживается FIFO. First come - First served (FCFS)

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

Когда процесс попадает в очередь готовых процессов, process control block присоединяется к хвосту очереди.

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

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

2.2.2 Стратегия SJF (Shortest job first).

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

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

2.2.3 Приоритетное планирование

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

Стратегия приоритетного планирования - это стратегия, предполагающая, что каждому процессу приписывается приоритет, определяющий очередность предоставления ему CPU.

Приоритет -- это целое положительное число, находящееся в некотором диапазоне, например от 0 до 7, от 0 до 4095. Будем считать, что чем меньше значение числа, тем выше приоритет процесса.

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

Внутренние факторы:

1. требования к памяти

2. количество открытых файлов

3. отношение среднего времени ввода - вывода к среднему времени CPU и так далее.

Внешние факторы:

1. важность процесса

2. тип и величина файлов, используемых для оплаты

3. отделение, выполняющее работы и так далее

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

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

Известен случай, когда в 1973 году в Массачусетском технологическом институте MIT при остановке компьютера IBM 7094 в очереди готовых процессов были обнаружены процессы, представленные в 1967 и все еще не выполненные.

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

2.2.4 “Карусельная” стратегия планирования. RR (Round Robin)

Round Robin стратегия применяется в системах разделения времени.

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

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

Рассмотрим суть стратегии на примере:

Пусть имеются 3 процесса П1(24 мс), П2(3 мс), П3(3 мс). Выделенный квант времени q=4 мс.

Соответственно Round Robin стратегия для этого случая имеет вид:

|П1 |П2 |П3 |П1 |П1 |П1 |П1 |П1 |

|WT1=0 мс |7 |10 |14 |18 |22 |26 |30 |.

Свойства Round Robin стратегии сильно зависят от величины временного кванта q. Чем больше временной квант, тем дольше Round Robin стратегия приближается к FCFS стратегии. (для рассмотренного примера, если q>24 мс, то ->FCFS.) При очень малых значениях временного кванта Round Robin стратегия называют разделением процессора -- processor sharing. Теоретически это означает, что каждый из N процессов работает со своим собственным процессором, производительность процессора равна 1/N от производительности физического процессора.

2.2.5 Планирование с использованием многоуровневой очереди (Multilevel queue scheduling)

Эта стратегия разработана для ситуации, когдла процессы могут быть легко классифицированны на несколько групп, например, часто процессы разделяют на две группы: интерактивные (процессы переднего плана) и пакетные (фоновые).

Интерактивные и пакетные процессы имеют различные требования к краткосрочному планировщику, например по отношению ко времени отклика.

Стратегия многоуровневой очереди разделяет очередь готовых процессов на несколько очередей, в каждой из которых находятся процессы с одинаковыми свойствами, и каждый из которых может планироваться индивидуальной стратегией, например Round Robin стратегия для интерактивных процессов и FCFS для пакетных процессов.

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

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

2.2.6 Программирование с использованием многоуровневой очереди с обратными связями (multilevel feedback queue sheduling)

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

Процессы первоначально попадают в очередь 0, где каждому из них предоставляется квант времени, равный 8 мс. Те процессы, которые не успели выполниться в течение этого времени, перемещаются в очередь 1. Процессы из очереди 1 начинают обрабатываться только тогда, когда очередь 0 становиться пустой. Те процессы, которые не выполнились в очереди 1 (q=16 мс) перемещаются в очередь 2. Процессы из очереди 2 будут обрабатываться только в том случае, если становятся пустыми очереди 0 и 1.

Рассмотренная стратегия является наиболее универсальной и сочетает в себе свойства всех рассмотренных раньше стратегий.

1. FCFS

2. SJF

3. приоритетная

4. Round Robin

5. многоуровневая очередь.

3. Алгоритмизация и программирование методов «RR» и «SPT»

3.1 Алгоритм стратегии планирования SPT (Shortest-processing-task-first.)

процессор планирование алгоритм

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

ui=, где - время ожидания, ti - собственно время решения и среднее время ответа есть u*=.

u* действительно минимальное значение среднего времени обслуживания. Для того чтобы показать, что u* действительно минимально среди u для всех перестановок, достаточно показать, что применение к произвольной перестановке (a1,...,aL) любой парной транспозиции, меняющей местами элементы ak и al, где tal<tak и l>k, может лишь уменьшить исходное значение u, соответствующее перестановке (a1,...,aL), где ai - номер задачи, назначаемой на решение i-й по порядку, i=I,L

3.2 Программная реализация метода SPT (Shortest-processing-task-first)

Алгоритм SPT используется, когда времена решения задач (процессов) известны. Для этого, перед непосредственным решением, он сначала производит сортировку задач в порядке возрастания.

Этот первый этап сортировки можно изобразить в виде блок-схемы на рисунке 1.

Рисунок 1.

Данный алгоритм можно объяснить следующим образом:

i-й элемент с конца (в нашем случае процесс с заранее известным временем решения) сравнивается с перед ним стоящим i-1 элементом. Если i-й меньше i-1 элемента, то они меняется местами. Все элементы сравниваются с перед ним стоящими, после чего все начинается сначала, и так n раз до полного упорядочивания.

Программно это выглядит так:

for j:=1 to n do

for i:=n downto 1 do

begin

if B[i]<B[i-1] then

begin

jm:=B[i-1];

B1[i-1]:=B1[i];

B1[i]:=jm;

end;

end;

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

Его можно изобразить в виде блок-схемы, которая изображена на рисунке 2:

Рисунок 2.

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

Среднее время определяется как отношение полного времени на количество заявок.

Программно это выглядит следующим образом:

for i:=1 to n do

begin

for j:=1 to i do

begin

jm:=jm+B[j];

if (B[j]<=dl)and(B[j]<>0) then

vk1:=vk1+B[j];

end;

end;

u:=jm/n;

vkv1:=vk1/n;

3.3 Алгоритм стратегии планирования . RR (Round Robin)

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

Простейшее правило планирования работ, обеспечивающее выполнение указанного требования, задается алгоритмом циклического обслуживания, или, иначе, алгоритмом RR (Round-Robin). Работа алгоритма показана на рисунке 3.

Рисунок 3.

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

3.4 Программная реализация метода RR (Round Robin)

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

Изобразим данный алгоритм в виде блок-схемы на рисунке 4:

Рисунок 4.

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

Среднее время определяем как отношение полного времени на количество заявок.

Данный алгоритм в программном виде будет выглядеть следующим образом:

for n1:=1 to m do

begin

for i:=1 to n do

for j:=1 to i do

begin

jm:=jm+B[j,1];

if (B[j,1]<=dl)and(B[j,1]<>0) then

vk2:=vk2+B[j,1];

end;

for j:=1 to n do

if B[j,1]>q then

B[j,1]:=B[j,1]-q

else

B[j,1]:=0;

end;

u:=jm/n;

vkv2:=vk2/n;

3.5 Результаты расчетов и их сопоставление

Для проверки работы алгоритмов была создана программа, эмитирующая их работу. Окно программы изображено на рисунке 5.

Рисунок 5.

Листинг программы представлен в приложении.

Для эмуляции прихода заявок используется массив, элементами которого являются времена, необходимые для выполнения поступающих заявок. Для сравнения эффективности рассматриваются массивы в 100, 1000 и 10000 элементов.

Анализ численных результатов целесообразно представить в виде таблиц.

Обработаем очередь из 100, 1000, 10000 заявок, где будут даны следующие данные: вероятность прихода заявок - 70; разброс длительностей заявок - от 0 до 6; длительность процессорного кванта - 4. Результаты представим в таблице 1.

Таблица 1 - Показатели эффективности работы алгоритмов RR и SPT.

Количество заявок	Алгоритм	Среднее время обслуживания	Время ожидания короткой заявки
100	SPT	29,79	14,95
	RR	100,2	32,96
1000	SPT	437,042	154,62
	RR	1124,235	288,455
10000	SPT	4565,047	1476,7
	RR	12178,42	3058,944

Обработаем очередь из 100, 1000, 10000 заявок, где будут даны следующие данные: вероятность прихода заявок - 30; разброс длительностей заявок - от 2 до 8; длительность процессорного кванта - 4. Результаты представим в таблице 2.

Таблица 2 - Показатели эффективности работы алгоритмов RR и SPT.

Количество заявок	Алгоритм	Среднее время обслуживания	Время ожидания короткой заявки
100	SPT	18,47	8,77
	RR	107,15	32,18
1000	SPT	170,051	48,43
	RR	963,071	233,375
10000	SPT	1755,5012	530,0827
	RR	9663,7024	2332,0272

Из результатов расчета видно, что алгоритм SPT действует эффективнее, чем RR. Это связано с тем, что алгоритм SPT заранее знает какой процесс по длительности ему придется обрабатывать и все эти процессы строит в порядке возрастания времени решения. Алгорит RR не знает какой процесс попадет ему на выполнение и в связи с этим обрабатывает все заявки без предварительной сортировки.

Заключение

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

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

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

Список используемой литературы

Вирт Н. «Алгоритмы и структуры данных», Москва: Мир, 1989 г. - 360 с.

Лойко В.И. «Структуры и алгоритмы обработки данных. Учебное пособие» Краснодар: КГАУ, 2000г. - 210 с.

Пономарев В. А. «Самоучитель Delphi 7 Studio» - СПб.: БХВ-Петербург, 2003. - 512 с.

Райли Д. «Абстракция и структуры данных. Вводный курс» Москва: Мир, 1993. - 320 с.

Меженный О. А. «TURBO PASCAL» - Москва: Диалектика, 2001г. - 446 с.

Хусаинов Б.С. Структуры и алгоритмы обработки данных. Учеб. пособие . - Москва: Финансы и Статистика, 2004г. -235 с.

Приложение.

unit Unit1;

interface

uses

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

Dialogs, Grids, StdCtrls;

type

TForm1 = class(TForm)

Edit1: TEdit;

Label1: TLabel;

Button1: TButton;

Button2: TButton;

StringGrid2: TStringGrid;

Label2: TLabel;

Edit2: TEdit;

Label4: TLabel;

Button3: TButton;

Button4: TButton;

Button5: TButton;

Label5: TLabel;

Edit3: TEdit;

Edit4: TEdit;

Button6: TButton;

Edit5: TEdit;

Button7: TButton;

Label3: TLabel;

Button8: TButton;

Button9: TButton;

Edit6: TEdit;

Label6: TLabel;

Label7: TLabel;

Edit7: TEdit;

Label8: TLabel;

Edit8: TEdit;

Label9: TLabel;

Edit9: TEdit;

Edit10: TEdit;

Label10: TLabel;

Button10: TButton;

StringGrid1: TStringGrid;

Edit11: TEdit;

procedure FormCreate(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure Button3Click(Sender: TObject);

procedure Button4Click(Sender: TObject);

procedure Button5Click(Sender: TObject);

procedure Button9Click(Sender: TObject);

procedure Button6Click(Sender: TObject);

procedure Edit10Change(Sender: TObject);

procedure Button8Click(Sender: TObject);

procedure Button10Click(Sender: TObject);

procedure Button7Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

const nmax=10000;

type

mas1=array[1..nmax,1..1] of extended;

mas2=array[1..nmax,1..1] of integer;

var

Form1: TForm1;

A: mas1;

B,B1: mas2;

dl,n,i,j,jm,k,q,sto,r:integer;

dl1,dl2,m,sum1,n1,n2,vk1,vk2: integer;

sum,L,qr,trud,p,w,u,n3,vkv1,vkv2 :extended;

implementation

{$R *.dfm}

procedure TForm1.FormCreate(Sender: TObject);

begin

n:=5;

q:=1;

r:=70;

sum:=0;

dl:=1;

dl1:=1;

dl2:=5;

edit1.text:=floatToStr(n);

edit2.text:=floatToStr(q);

edit3.text:=floatToStr(r);

edit5.text:=floatToStr(dl1);

edit6.text:=floatToStr(sum);

edit10.text:=floatToStr(dl);

edit11.text:=floatToStr(dl2);

stringGrid1.ColCount:=n+1;

//stringGrid1.RowCount:=n+1;

stringGrid2.ColCount:=n+1;

//stringGrid2.RowCount:=n+1;

stringgrid1.Cells[0,0]:='Массив:';

stringgrid2.Cells[0,0]:='Отсортированные:';

stringgrid1.Cells[0,1]:='Время';

stringgrid2.Cells[0,1]:='Время';

for i:=1 to n do

begin

//stringgrid1.Cells[0,i]:='i='+intToStr(i);

stringgrid1.Cells[i,0]:='Заявка '+intToStr(i);

//stringgrid2.Cells[0,i]:='i='+intToStr(i);

stringgrid2.Cells[i,0]:='Заявка '+intToStr(i);

end;

end;

procedure TForm1.Button1Click(Sender: TObject);

begin

n:=strtoint(edit1.Text);

stringGrid1.ColCount:=n+1;

//stringGrid1.RowCount:=n+1;

stringGrid2.ColCount:=n+1;

//stringGrid2.RowCount:=n+1;

for i:=1 to n do

begin

//stringgrid1.Cells[0,i]:='i='+inttostr(i);

stringgrid1.Cells[i,0]:='Заявка '+inttostr(i);

stringgrid2.Cells[i,0]:='Заявка '+inttostr(i);

end;

end;

procedure TForm1.Button2Click(Sender: TObject);

begin

jm:=0; vk1:=0; n1:=0;

for i:=1 to n do

begin

A[i,1]:=strtoFloat(stringgrid1.Cells[i,1]);

B1[i,1]:=Trunc(A[i,1]);

// sum1:=sum1+B1[i,1];

end;

for j:=1 to n do

for i:=n downto 1 do

begin

if B1[i,1]<B1[i-1,1] then

begin

jm:=B1[i-1,1];

B1[i-1,1]:=B1[i,1];

B1[i,1]:=jm;

end;

end; jm:=0;

//edit7.text:=floatToStr(B1[1,1])

for i:=1 to n do

stringGrid2.Cells[i,1]:=floatToStrf(B1[i,1],fffixed,6,0);

for i:=1 to n do

begin

for j:=1 to i do

begin

jm:=jm+B1[j,1];

if (B1[j,1]<=dl)and(B1[j,1]<>0) then

vk1:=vk1+B1[j,1];

end;

//if (B1[j,1]<=dl)and(B1[j,1]<>0) then inc(n1);

end;

u:=jm/n;

vkv1:=vk1/n;

edit8.text:=floatToStr(u);

edit4.text:=floatToStr(vkv1);

end;

procedure TForm1.Button3Click(Sender: TObject);

begin

q:=strtoint(edit2.Text);

end;

procedure TForm1.Button4Click(Sender: TObject);

begin

close();

end;

procedure TForm1.Button5Click(Sender: TObject);

begin

for i:=1 to n do

begin

sto:=random(99)+1;

if sto>r then

B[i,1]:=0

else

B[i,1]:=random(dl2-dl1+1)+dl1;

A[i,1]:=B[i,1];

stringGrid1.Cells[i,1]:=floatToStrf(B[i,1],fffixed,6,0);

end;

end;

procedure TForm1.Button9Click(Sender: TObject);

begin

sum:=0;

for i:=1 to n do

sum:=sum+A[i,1];

edit6.text:=floatToStr(sum);

end;

procedure TForm1.Button6Click(Sender: TObject);

begin

r:=strtoint(edit3.Text);

end;

procedure TForm1.Edit10Change(Sender: TObject);

begin

dl:=strtoint(edit10.Text);

end;

procedure TForm1.Button8Click(Sender: TObject);

begin

sum1:=0; n2:=0;

for i:=1 to n do

begin

A[i,1]:=strtoFloat(stringgrid1.Cells[i,1]);

B[i,1]:=Trunc(A[i,1]);

sum1:=sum1+B[i,1];

end;

//for j:=1 to n do

// if (B[j,1]<=dl)and(B[j,1]<>0) then inc(n2);

m:=B[1,1] ;

for i:=1 to n do

if B[i,1]>m then

m:=B[i,1];

m:=(m div q);

if (m mod q)<>0 then inc(m);

if m=0 then inc(m);

jm:=0; vk2:=0;

for n1:=1 to m do

begin

for i:=1 to n do

for j:=1 to i do

begin

jm:=jm+B[j,1];

if (B[j,1]<=dl)and(B[j,1]<>0) then

vk2:=vk2+B[j,1];

end;

for j:=1 to n do

if B[j,1]>q then

B[j,1]:=B[j,1]-q

else

B[j,1]:=0;

end;

u:=jm/n;

vkv2:=vk2/n;

edit9.text:=floatToStr(u);

edit7.text:=floatToStr(vkv2);

end;

procedure TForm1.Button10Click(Sender: TObject);

begin

dl:=strtoint(edit10.Text);

end;

procedure TForm1.Button7Click(Sender: TObject);

begin

dl1:=strtoint(edit5.Text);

dl2:=strtoint(edit11.Text);

end;

end.

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