Управление ресурсами однопроцессорных систем оперативной обработки
Алгоритм SPT
В системах оперативной обработки в качестве основного критерия эффективности используется средне время обслуживания заявок. Нетрудно видеть, что в случае, когда времена решения задач априори известны, минимальное среднее время ответа дает алгоритм SPT (Shortest-processing-task-first), назначающий задачи на решение в порядке убывания времени решения ti, т.е. t1 £ t2 £...£ tL [28]. При этом время ответа ui для задачи zi есть
ui= S tj, где S tj- времяожидания, ti- собственно время решения и среднее время ответа есть 
.
Алгоритм RR
В реальных системах оперативной обработки априорная информация о временах решения задач, как правило, отсутствует. Чтобы воспользоваться принципами планирования на основе алгоритма SPT, в систему вводятся средства, обеспечивающие выявление коротких и длинных работ непосредственно в ходе вычислительного процесса.
Простейшее правило планирования работ, обеспечивающее выполнение указанного требования, задается алгоритмом циклического обслуживания, или, иначе, алгоритмом RR (Round–Robin). Работа алгоритма иллюстрируется рисунком 3.32.
Рис.3.32. Иллюстрация алгоритма RR
Заявки на выполнение работ поступают с интенсивностью l в очередь O, откуда они выбираются и исполняются процессором Пр. Для обслуживания отдельной заявки отводится постоянный квант времени q, достаточный для выполнения нескольких тысяч операций. Если работа была выполнена за время q, она покидает систему. В противном случае она вновь поступает в конец очереди и ожидает предоставления ей очередного кванта процессорного времени.
Алгоритм FB
Для обеспечения еще более быстрой реакции системы на короткие работы в системах оперативной обработки используются алгоритмы многоуровневого циклического планирования. Одним из таких алгоритмов является алгоритм FB (foreground-background). Принцип его работы можно проиллюстрировать следующей схемой (3.34):
Рис. 3.34. Иллюстрация алгоритма FB
Заявки на выполнение работ поступают в очередь 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 выделяются кванты времени длительности
qp=2p-1q,
где q – квант времени, выделяемый для работ из очереди O1 .
Таким образом, очередям O1, O2, O3, O4,... соответствуют кванты времени q,2q,4q,8q,... Увеличение кванта времени на выполнение работ с большой трудоемкостью способствует сокращению числа прерываний работы процессора и числа пересылок программ между оперативной и внешней памятью.
Планирование вычислительного процесса
