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

Содержание

Введение

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

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

2.1 Алгоритм SPT

2.2 Алгоритм RR

2.3 Алгоритм FB

2. Описание алгоритма

3. Результаты работы

4. Анализ работы программы

Заключение

Список используемых источников

Приложения

Введение

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

Цель работы - моделирование вычислительной однопроцессорной системы оперативной обработки.

Написать программу, реализующую работу процессора по обработке

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

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

с предварительной сортировкой заявок по длительности, по алгоритму SPT;

по алгоритму RR.

Обработать очереди из 100 и 1000 заявок;

- вероятность прихода заявок: 30 и 60;

разброс длительностей заявок: 0-7 и 3-5;

длительность процессорного кванта: 4;

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

Сравнить получившиеся результаты с теорией. Оценить эффективность алгоритмов. Произвести анализ работы.

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

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

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

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

с предварительной сортировкой заявок по длительности, по алгоритму SPT;

по алгоритму RR.

Обработать очереди из 100 и 1000 заявок;

- вероятность прихода заявок: 30 и 60;

- разброс длительностей заявок: 0-7 и 3-5;

- длительность процессорного кванта: 4;

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

Сравнить получившиеся результаты с теорией. Оценить эффективность алгоритмов. Произвести анализ работы.

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

2.1 Алгоритм SPT

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

ti - собственно время решения и среднее время ответа есть

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



так как l>k, а talЈ tak. Следовательно, перемещение вперед задачи с меньшим временем решения приводит к уменьшению среднего времени обслуживания. В перестановке (1, ... ,L) при условии, что t1Ј...ЈtL, нельзя сделать ни одной такой улучшающей транспозиции, а потому u* есть минимальное среднее время обслуживания и алгоритм SPT дает оптимальное решение рассматриваемой задачи.

2.2 Алгоритм RR

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

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



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

Оценим среднее время ожидания и пребывания работ в системе с циклическим планированием. Воспользуемся для этого аппаратом теории массового обслуживания. Для упрощения последующих выкладок предположим, что длительность кванта не постоянная величина, а случайная, распределенная по экспоненциальному закону с тем же средним значением q. Причем также, что на вход системы поступает простейший поток с интенсивностью l работ в единицу времени, и с вероятностями s или (1-s) работа не будет или соответственно будет завершена в текущем кванте. Из последнего предположения следует, что вероятность того, что работа будет выполнена точно за k квантов (не завершена за первые k-1 квантов и завершена в k-том варианте), описывается геометрическим распределением

Таким образом, если известны средняя трудоемкость работ Q и длительность q кванта, то среднее количество квантов, с одной стороны, равно Q/q, а с другой - полученному выше выражению, то есть

Определим среднее время ответа для работы J, требующей ровно t единиц времени обработки. Пусть m - наименьшее целое, при котором mqіt (т.е. m - число квантов, достаточное для обслуживания заявки). Рассмотрим состояние системы на момент поступления работы J. При поступлении работы J в системе в среднем находится W1 других работ. Значение N1 определяется как среднее число заявок в системе с бесприоритетным обслуживанием, на вход которой заявки поступают с интенсивностью

L=l+ls+ls2+ј+lsn+ј=l/(1-s)

(с учетом интенсивности поступления заявок на дообслуживание в последующих тактах) и обслуживаются по экспоненциальному закону со средним q. Для определения W1 требуется найти распределение вероятностей {pk} того, что в очереди будет ровно k заявок. ТогдаW1= S kpk.

Для определения pk составим систему дифференциальных уравнений Колмогорова с помощью графа переходов (m=1/q)

Здесь Si - состояние системы с i заявками в очереди (одна из них обслуживается). Тогда система уравнений имеет вид

p`i =Lpi-1 - mpi - Lpi + mpi+1,

или

p`i =Lpi-1 - (m+L)pi + mpi+1, i=1,2,...

p`0 = -Lp0 + mp1.

Кроме того, требуется соблюдение условия нормировки

Рассмотрим установившийся режим, т.е. считаем, что t®Ґ. Тогда вместо дифференциальных уравнений получаем алгебраические

Lpi-1 - (m+L)pi + mpi+1=0, i=1,2,...

- Lp0 + mp1=0,

p0 + p1 + ... + pi + ... =1.

Из второго уравнения выразим p1 через p0 :

p1 = L/m* p0 ;

подставим это значение в первое уравнение с i=1. Тогда

Делаем индуктивное предположение:



Тогда из k-го уравнения получаем

Откуда

что подтверждает индуктивное предположение. Поэтому в соответствии с условием нормировки имеем

Где

На основании полученного выражения или pk имеем



С учетом допущения об экспоненциальности распределения кванта q время дообслуживания работы J, не зависит от этого момента и в среднем равно q. Таким образом, работа будет ожидать W1q единиц времени до получения первого кванта. За время W1q и первый квант выполнения работы J в систему поступит l новых работ. Кроме того, sW1 работ из их общего числа W1 вернутся обратно в очередь на довыполнение. Поэтому в следующем цикле работа J застанет в системе W2 работ:

W2 = lW1q + lq + sW1.

Подставляя в последнее выражение ранее полученное значение W1, получаем

В общем случае аналогично получаем

Wi = l Wi-1q + lq + s Wi-1 = r/(1-r).

Среднее время ожидания для работы J, время выполнения которой составляет m квантов, равно



Здесь среднее время ожидания wm определяется как время, необходимое для обслуживания всех Wi работ, стоящих впереди работы J в каждом из m циклов обслуживания. Среднее время ответа для работы J

Um = wm +mq = mq/(1-r),

где r = lq/(1-s) = lq/(q/Q) = lQ - загрузка системы. Из выражения для времени ожидания wm видно, что время ожидания обслуживания возрастает с увеличением трудоемкости t=mq задачи. В то же время при обслуживании задач в порядке поступления без прерываний среднее время ожидания w не зависит от трудоемкости и составляет

Из последнего выражения видно, что время ожидания длинных задач (mq>Q) больше, чем при обслуживании в порядке поступления, а время ожидания коротких задач (mq<Q) - меньше времени ожидания в режиме без прерываний.

2.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,... Увеличение кванта времени на выполнение работ с большой трудоемкостью способствует сокращению числа прерываний работы процессора и числа пересылок программ между оперативной и внешней памятью.

Рассмотрим алгоритмы SPT и RR на конкретном примере.

3. Описание алгоритма

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

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

ввод значений;

заполнение очереди заявок;

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

сортировка очереди;

реализация алгоритма SPT;

реализация алгоритма RR.

Ввод значений: используются стандартные операторы ввода-вывода.

Заполнение очереди заявок: создание заявки, добавление заявки в очередь.

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

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

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

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

(Текст программы смотреть в приложении 1)

4. Результаты работы

Таблица 1.Результаты работы программы:

Опыт:	1	2	3	4	5	6	7	8
Число заявок	100	100	100	100	1000	1000	1000	1000
Вероятность прихода заявки	60	60	30	30	60	60	30	30
Длительность решения задачи	7	5	7	5	7	5	7	5
Длина короткой заявки(квант)	4	4	4	4	4	4	4	4
Сумма длин заявок	409	314	374	300	3945	3055	3945	2959
Алгоритм без сортировки: Ср.вр. преб.заявки в очереди Число тактов	4.212 417	3.222 319	4.880 488	4.202 416	4.117 4113	3.254 3251	5.085 5080	4.269 4269
Алгоритм SPT: Ср.вр. преб.заявки в очереди Число тактов	4.061 402	3.133 307	3.707 367	2.959 290	3.943 3935	3.053 3047	3.944 3936	2.961 2958
Алгоритм RR: Ср.вр. преб.короткой заявки Ср.вр. преб.длинной заявки Число тактов	2.323 6.302 402	2.112 5.000 307	2.333 6.147 367	2.020 5.000 290	2.288 5.983 3935	2.211 5.000 3047	2.261 5.986 3936	2.140 5.000 2958

(Наглядное изображение работы программы смотреть в приложении 2)

5. Анализ работы программы

Проведем анализ работы программы. Это мы можем сделать с помощью результатов работы программы (смотреть таблицу 1).

Рассмотрим каждый алгоритм в отдельности, для того чтобы проанализировать, как зависит результат работы от изменения числа заявок, вероятности прихода заявки и от длины заявки. Рассмотрим алгоритм без предварительной сортировки. По результатам работы видно, что среднее время ожидания зависит от длины заявки (например, при длине заявки 7т среднее время ожидания равно 4.212 т, а при длине заявки 5т - 3.222т) и не зависит от числа заявок (для 100 заявок среднее время ожидания - 4.212т, а для 1000 заявок - 4.117). Но от числа заявок зависит число тактов (для 100 заявок - 417т, для 1000 заявок - 4113т). А вероятность влияет на число тактов, так как происходит выполнение “нулевых” заявок или пустых тактов.

Теперь рассмотрим алгоритм SPT. Аналогично алгоритму без сортировки, длина заявки влияет на среднее время ожидания (для 7т - 4.061т, для 5т - 3.133т), а число заявок не влияет (для 100 - 4.061т, а для 1000 - 3.943т). Вероятность не влияет на число тактов и время ожидания, так как при сортировке были удалены “нулевые” заявки.

Рассмотрим алгоритм RR. Время ожидания короткой заявки зависит только от длины кванта, но так как квант имеет длину 4т для всех переборов, то время ожидания короткой заявки не изменяется. Время ожидания длинной заявки зависит от длины заявки (для 7т - 6.302т, для 5т - 5.000т(100 заявок); для 7т - 5.983,для 5т - 5.000т(1000 заявок)), т.е. время ожидания длинной заявки не зависит от числа заявок. Число тактов зависит от количества заявок.

Сравним алгоритмы между собой. Алгоритм SPT и RR дает минимальное время обслуживания и оптимальное решение рассматриваемой задачи по сравнению с алгоритмом без сортировки (для алгоритма SPТ и RR число тактов 402, а для алгоритма без сортировки - 417т; для алгоритма SPТ и RR число тактов 3047, а для алгоритма без сортировки - 3251т). При использовании алгоритма RR время ожидания длинных задач больше, чем при обслуживании в алгоритме без сортировки и алгоритме SPT (для RR - 5.983т, для SPT - 3.943т, без сортировки - 4.117т). А время ожидания коротких задач - меньше времени ожидания в алгоритме без сортировки и SPT (для RR - 2.288т, для SPT - 3.943т, без сортировки - 4.117т). Среднее время ожидания в алгоритме SPT приблизительно составляет половину сумму времени ожидания длинной заявки и времени короткой заявки.

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

Заключение

В курсовом проекте были освещены основные аспекты управления ресурсами однопроцессорных систем оперативной обработки. Работа представлена программой. В работе были описаны алгоритмы SPT и RR, приведены результаты работы программы. Произведено их сравнение: результат показал преимущество алгоритма SPT перед RR в скорости работы, и преимущество алгоритма RR перед SPT во времени обслуживания коротких заявок. В данном курсовом проекте было рассмотрено управление ресурсами вычислительных систем однопроцессорных систем оперативной обработки (алгоритм без сортировки, SPT и RR). Задача по выполнению курсового проекта по сравнению результатов работы алгоритмов без сортировки, SPT и RR была рассмотрена и выполнена.

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

Написана программа, реализующая работу процессора по обработке

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

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

с предварительной сортировкой заявок по длительности, по алгоритму SPT;

по алгоритму RR.

Обработаны очереди из 100 и 1000 заявок;

- вероятность прихода заявок: 30 и 60;

разброс длительностей заявок: 0-7 и 3-5;

длительность процессорного кванта: 4;

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

Список используемых источников

1. В.И. Ключко, В.И.Лойко, Архитектура вычислительных систем и сетей ЭВМ. Изд. КубГТУ. 2000г.-153с.

2. В.И. Лойко, Методические указания к лабораторным работам. Изд. КубГТУ. 2000г. -25с.

Приложения

Приложение 1

Листинг программы

Program Kurs;

Uses Crt;

Type

pointer=^pnt;

pnt =record

ptr:pointer;

time:integer;

end;

Var i: integer;

a,prr,pspt,ph,p1,p2,px:pointer;

l,r,N,t,t2,k,k2,v,d,s2,c:integer;

P, Dlit, Short: Integer;

Summ,Tspt,Trr:Integer;

ch:char;

{Процедура добавления заявки}

Procedure push (var px,y:pointer; l:integer);

begin

new(p1);

p1^.ptr:=nil;

if y=nil then

begin

px:=p1;

y:=p1;

y^.time:=l;

end

else

begin

y^.ptr:=p1;

y^.time:=l;

end;

y:=p1;

end;

Begin

Repeat

Clrscr;

Randomize;

{ Число тактов}

Write(' Введите число заявок (100 или 1000) ');

Readln(N);

{ Вероятность прихода заявки}

Write(' Введите вероятность прихода заявки (30% или 60%) ');

Readln(P);

{ Длительность решения задачи}

Write(' Введите длительность решения задачи (0-7) ');

Readln(Dlit);

{ Заявка считается короткой}

Writeln(' Заявка считается короткой (4) ');

{Readln(}Short:=4;{);}

{Заполнение списка заявок}

a:=nil;ph:=nil;p1:=nil;p2:=nil;prr:=nil;pspt:=nil;

v:=0;

c:=0;

Summ:=0;

{ For i:=1 to n do}

Repeat

begin

r:=random(10)+1; {Генерации вероятности прихода заявки}

If r<=(P div 10) {------------------------}

then

begin

l:=random(Dlit)+1; {Генерация длительности заявки}

push(ph,a,l); {Добавление заявки}

inc(v); {Счетчик заявок}

Summ:=Summ+l; {Сумма длинн заявок}

end

else push(ph,a,0); {Заявки нет}

c:=c+1;

end;

Until v=n;

Writeln;

Writeln(' Сумма длин всех заявок: ',Summ);

{;Алгоритм без сортировки}

t:=0;

a:=ph;

k:=0;

i:=1;

s2:=0;

d:=0;

Tspt:=0;

Repeat

If a^.time=0 {Если время заявки 0 (заявки в этот такт нет) }

then

begin

if d<i then

begin

d:=i; {Простой}

inc(s2);

inc(t)

end;

a:=a^.ptr; {Следующая заявка}

end

else

begin

if d<i then

begin

d:=d+a^.time;

inc(t,a^.time);

inc(k);

a:=a^.ptr; {Следующая заявка}

end

end;

inc(i);

Until (a^.ptr=nil) ; { Заявки кончились}

s2:=n-s2;

If k=0 then k:=1;

Writeln;

Writeln(' Среднее время пребывания заявки в очереди : ',t/k:0:4);

Writeln(' Число тактов процессора: ',d);

{;Алгоритм SPT с сортировкой}

t:=0;

a:=nil;

px:=ph;

k:=0;

i:=1;

s2:=0;

d:=0;

Tspt:=0;

repeat

if (px^.time=0) then

if (a=nil) then

begin

ph:=px^.ptr;

Dispose(px);

px:=ph;

end

else

begin

a^.ptr:=px^.ptr;

Dispose(px);

px:=a^.ptr;

end

else begin

a:=px;

px:=px^.ptr;

end;

Until (a^.ptr=nil);

a:=ph;

Repeat

inc(Tspt);

If a^.time=0 {Если время заявки 0 (заявки в этот такт нет) }

then

begin

if d<i then

begin

d:=i; {Простой}

inc(s2)

end;

a:=a^.ptr; {Следующая заявка}

end

else

begin

if d<i then

begin

d:=d+a^.time; { Считаем число тактов работы алгоритма SPT }

inc(t,a^.time);

inc(k);

a:=a^.ptr; {Следующая заявка}

end

end;

inc(i);

Until (a^.ptr=nil) ; { Заявки кончились}

s2:=n-s2;

If k=0 then k:=1;

Writeln;

Writeln(' SPT: Среднее время пребывания заявки в очереди : ',t/k:0:4);

Writeln(' Число тактов процессора: ',d);

{;Алгоритм RR}

t:=0;

t2:=0;

s2:=0;

a:=ph;

k:=0;

k2:=0;

i:=1;

d:=0;

Trr:=0;

Repeat

inc(Trr); { Считаем время работы алгоритма RR }

If a^.time=0 {Если время заявки 0 (заявки в этот такт нет) }

then

begin

if d<i then

begin

d:=i;

inc(s2)

end;

a:=a^.ptr; { Следующая заявка}

end

else

if (a^.time>0) and (a^.time<5) {Если длина заявки дольше короткой}

then

begin

if d<i then

begin

d:=d+a^.time;

inc(t,a^.time);

inc(k);

a:=a^.ptr; { Следующая заявка}

end

end

else {Отбрасываем длинную заявку в конец очереди}

begin

if d<i then

begin

d:=d+Short;

p2:=a^.ptr;

inc(t2,a^.time);

inc(k2);

r:=a^.time-Short;

repeat

a:=a^.ptr;

until a^.ptr=nil;

push(ph,a,r);

a:=p2;

end

end;

inc(i);

Until (a^.ptr=nil) ;

s2:=n-s2;

If k=0 then k:=1;

Writeln;

Writeln(' RR : Среднее время пребывания короткой заявки в очереди : ',t/k:0:4);

Writeln(' Среднее время пребывания длинной заявки в очереди : ',t2/k2:0:4);

Writeln(' Число тактов процессора: ',d);

Writeln;

Writeln('Выход? (Y-Да) ' );

Ch:=ReadKey;

Until (Ch='y') or (CH='Y') or (CH='н')or(CH='Н');

End.

Приложение 2

Результат работы программы

Результат работы программы для 100 заявок с вероятностью прихода заявки 60%, длительностью решения задачи 7т:

Результат работы программы для 100 заявок с вероятностью прихода заявки 60%, длительностью решения задачи 7т:

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