ОРГАНИЗАЦИЯ ПЛАНИРОВАНИЯ ОБРАБОТКИ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ
Эффективность обслуживания вычислительных задач (их программ) зависит прежде всего от среднего времени обслуживания
tQбел =— , поэтому в вычислительной системе (и в многомашинной, и в одномашинной особенно) требуется решать проблему минимизации времени обработки поступивших в систему заданий.
Иногда эта проблема трансформируется в задачу максимизации загрузки устройств ЭВМ. являющихся носителями ресурсов.При решении вычислительной задачи ЭВМ использует свои ресурсы в объеме и последовательности, определяемых алгоритмом решения. К ресурсам ЭВМ относятся объем оперативной и внешней памяти, время работы процессора, время обращения к внешним устройствам (внешняя память, устройства отображения). Естественно, что эти ресурсы ограничены. Поэтому и требуется найти наилучшую последовательность решения поступивших на обработку вычислительных задач. Процесс определения последовательности решения задач во времени называется планированием. При планировании необходимо знать, какие ресурсы и в каком количестве требует каждая из поступивших задач. Анализ потребности задачи в ресурсах производится на основе ее программы решения. Программа состоит, как правило, из ограниченного набора процедур (по крайней мере к этому стремятся) с известными для данной ВС затратами ресурсов. После анализа поступивших программ решения задач становится ясно, какая задача каких ресурсов требует и в каком объеме. Критерии, используемые при планировании, зависят от степени определенное- ти алгоритмов решаемых задач. Крайних случаев два: порядок использования устройств ЭВМ при решении задач строго задан их алгоритмами, а порядок использования устройств ВС в задачах заранее не известен. Для первого случая приемлем критерий минимизации суммарного времени решения вычислительных задач, для второго — максимизации загрузки устройств ВС.
Пример.
Рассмотрим модель планирования вычислительного процесса при минимизации суммарного времени [21].
Обозначим ресурсы вычислительной системы через Ri, Ri,-.-, Rn. Каждая программа решения задачи обработки данных включает типовые процедуры из набора Пі, Пг, ..., Пт. Тогда матрица Г ресурсозатрат, приведенных к времени, будет выглядеть так:
где Т,у — затраты у-го ресурса при выполнении і'-й процедуры, і—1,... ,т;
Знание матриц ресурсозатрат при выполнении программ позволяет вычислить суммарные затраты каждого из ресурсов по всем программам решения вычислительных задач, поступивших в ВС, и составить их матрицу ресурсозатрат. Обозначим поступившие в ВС программы решения задач через Зі, З2, ty — затраты]-го ресурса на
В вычислительной системе ресурсы чаще всего используются последовательно. Поэтому на основе матрицы Тп можно выделить после-
выполнение ґ-й задачи (г = 1,..., т; j= 1,..., п)\ R\, R2, . Rm — ресурсы ВС. Матрица ресурсозатрат по задачам запишется в виде
довательность прохождения через обработку задач, которая минимизирует суммарное время. Одним из методов нахождения такой последовательности, т. е. планирования, является метод решения задачи Джонсона [32], относящийся к теории расписаний и дающий эффективный и строгий алгоритм. При этом учитываются следующие ограничения:
- для любого устройства ВС выполнение последующей вычислительной задачи не может начаться до окончания предыдущей;
- каждое устройство в данный момент может выполнять только одну вычислительную задачу;
- начавшееся выполнение задачи не должно прерываться до полного его завершения.
Если в процессе обработки данных используется п устройств (ресурсов) ВС, нахождение оптимальной последовательности поступающих на решение т задач, минимизирующих суммарное время обработки, потребует перебора (га!)” вариантов.
Например, если в ВС поступило всего шесть заданий (ш = 6), использующих всего два ресурса (п - 2), то для нахождения оптимальной последовательности после составления матрицы Т„ потребуется произвести (6!) переборов, т.е. 518400. Если же m - 10, то потребуется порядка 1013 переборов. Ясно, что даже для ЭВМ это многовато.Алгоритм Джонсона, полученный для п = 2, требует перебора только от (т + 1) / 2 вариантов, т.е. для нашего примера (т = 6) необходимо будет проделать 21 перебор, что значительно меньше, чем 518400. При и gt; 2 задачу планирования по критерию минимума суммарного времени обработки сводят к задаче Джонсона путем преобразования матрицы Т„. Например, если п = 3 (т. е. три ресурса), то производится попарное сложение первого и второго, второго и третьего столбцов и таким образом получают двухстолбцовую матрицу Тп. После преобразования следует проверить, выполняются ли вышеперечисленные условия. Если это не так, то задача планирования не имеет строгого решения и используют эвристические алгоритмы.
Для пояснения алгоритма Джонсона представим матрицу Т„ как двухстолбцовую:
Алгоритм Джонсона состоит в следующем.
- В матрице Т„ определяется /mjn-min{fи, tn, •••, Wb
- Из задачі, ..., 3mвыбираются задачи, для которых ресурсоем- кость хотя бы по одному устройству была равна іщіп, т.е. в данном случае выбирают задачи 3/, у которых хотя бы одна из двух ty= fmin. (Напомним, что і — это номер задачи,у — номер устройства, і = 1,..., т,
j = 1; 2.)
- Задачи группируют по минимальному времени их исполнения tmm на первом и втором устройствах, т.е. 3,- (/minfa) и 3,- (til, ?min)-
- В начало последовательности обрабатываемых задач ставят З, (бшпgt; to), В КОНЄЦ — 3/ ( tn, tmm)-
- Задачи, вставленные в последовательность обрабатываемых задач, исключаются из матрицы Т„.
- Для новой матрицы повторяются пункты 1—3.
- Задачи 3,- (tmin, fa) и 3; (1ц, fmin) , полученные из новой матрицы, ставятся в середину составленной ранее последовательности обрабатываемых задач и т. д.
В основе эвристических алгоритмов лежат процедуры выбора из поступивших задач наиболее трудоемких и расположения их в порядке убывания времени выполнения.
При планировании по критерию максимума загрузки устройств вычислительной системы матрицы ресурсоемкости преобразуются в матрицы загрузки устройств. Из этих матриц формируют по каждому устройству потоки задач, выборки из которых позволяют сформировать оптимальную последовательность задач, подлежащих обработке.
Реализация функций и алгоритмов планирования вычислительного процесса происходит с помощью управляющих программ операционной системы ВС. Программа планировщик определяет ресурсоемкость каждой поступившей на обработку задачи и располагает их в оптимальной последовательности. Подключение ресурсов в требуемый объемах к программам выполнения задач осуществляет по запросу планировщика управляющая программа супервизор, которая тоже входит в состав операционной системы.
Таким образом, одной из важнейших процедур информационного процесса обработки данных является организация вычислительного процесса, т.е. обслуживание поступающих на обработку заданий (очередей) и планирование (оптимизация последовательности) их обработки. На программно-аппаратном уровне эти функции выполняют специальные управляющие программы, являющиеся составной частью операционных систем, т. е. систем, организующих выполнение компьютером операций обработки данных.
Разнообразие методов и функций, используемых в алгоритмах организации вычислительного процесса, зависит от допустимых режимов обработки данных в ВС. В наиболее простой ВС, такой, как персональный компьютер (ПК), не требуется управление очередями заданий и планирование вычислительных работ. В ПК применяют в основном однопрограммный режим работы, поэтому их операционные системы не имеют в своем составе программ диспетчирования, планировщика и супервизора. Но в более мощных ЭВМ, таких, как серверы и особенно мейнфреймы, подобные управляющие программы оказывают решающее влияние на работоспособность и надежность ВС. Например, к UNIX- серверам могут обращаться с заданиями одновременно сотни пользователей, а к мэйнфреймам типа S/390 - тысячи.