4.3. ОРГАНИЗАЦИЯ ПЛАНИРОВАНИЯ ОБРАБОТКИ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ
Эффективность обслуживания вычислительных задач (их программ) зависит прежде всего от среднего времени обслуживания
поэтому в вычислительной системе (и в многомашинной, и в одномашинной особенно) требуется решать проблему минимизации времени обработки поступивших в систему заданий. Иногда эта проблема трансформируется в задачу максимизации загрузки устройств ЭВМ. являющихся носителями ресурсов.
При решении вычислительной задачи ЭВМ использует свои ресурсы в объеме и последовательности, определяемых алгоритмом решения. К ресурсам ЭВМ относятся объем оперативной и внешней памяти, время работы процессора, время обращения к внешним устройствам (внешняя память, устройства отображения). Естественно, что эти ресурсы ограничены. Поэтому и требуется найти наилучшую последовательность решения поступивших на обработку вычислительных задач. Процесс определения последовательности решения задач во времени называется планированием. При планировании необходимо знать, какие ресурсы и в каком количестве требует каждая из поступивших задач. Анализ потребности задачи в ресурсах производится на основе ее программы решения. Программа состоит, как правило, из ограниченного набора процедур (по крайней мере к этому с известными для данной ВС затратами ресурсов. После анализа поступивших программ решения задач становится ясно, какая задача каких ресурсов требует и в каком объеме. Критерии, используемые при зависят от степени
ти алгоритмов решаемых задач. Крайних случаев два: порядок использования устройств ЭВМ при решении задач строго задан их алгоритмами, а порядок использования устройств ВС в задачах заранее не известен. Для первого случая приемлем критерий минимизации суммарного времени решения вычислительных задач, для второго — максимизации загрузки устройств ВС.
Пример.
Рассмотрим модель планирования вычислительного процесса при минимизации суммарного времени [21].
В вычислительной системе ресурсы чаще всего используются последовательно. Поэтому на основе матрицы Тп можно выделить после- |
Обозначим ресурсы вычислительной системы через Я1,К2,..., Яп- Каждая программа решения задачи обработки данных включает типовые процедуры из набора П], П2, ..., Пт. Тогда матрица Г ресурсозатрат, приведенных к времени, будет выглядеть так:
где Т,у — затратыу'-го ресурса при выполнении г-й процедуры, I—1,... ,т; |
Знание матриц ресурсозатрат при выполнении программ позволяет вычислить суммарные затраты каждого из ресурсов по всем программам решения вычислительных задач, поступивших в ВС, и составить их матрицу ресурсозатрат. Обозначим поступившие в ВС программы решения задач через Зь З2, ...,Зт;1у — затратыу-го ресурса на выполнение 1-й задачи (г = 1,..., т;)= 1,..., п)\ Я\, 112, ■■■, — ресурсы ВС. Матрица ресурсозатрат по задачам запишется в виде
|
довательность прохождения через обработку задач, которая минимизирует суммарное время. Одним из методов нахождения такой последовательности, т. е. планирования, является метод решения задачи Джонсона [32], относящийся к теории расписаний и дающий эффективный и строгий алгоритм. При этом учитываются следующие ограничения:
• для любого устройства ВС выполнение последующей вычислительной задачи не может начаться до окончания предыдущей;
• каждое устройство в данный момент может выполнять только одну вычислительную задачу;
• начавшееся выполнение задачи не должно прерываться до полного его
Если в процессе обработки данных используется п устройств (ресурсов) ВС, нахождение оптимальной последовательности поступающих на решение т задач, минимизирующих суммарное время обработки, потребует перебора {т\)п вариантов. Например, если в ВС поступило всего шесть заданий (т = 6), использующих всего два ресурса (п - 2), то для нахождения оптимальной последовательности после составления матрицы Т„ потребуется произвести (6!) переборов, т.е. 518400. Если же т - 10, то потребуется порядка 1013 переборов. Ясно, что даже для ЭВМ это многовато.
Алгоритм Джонсона, полученный для п = 2, требует перебора только от (т + 1) / 2 вариантов, т.е. для нашего примера (т = 6) необходимо будет проделать 21 перебор, что значительно меньше, чем 518400. При и > 2 задачу планирования по критерию минимума суммарного времени обработки сводят к задаче Джонсона путем преобразования матрицы Г,,. Например, если п = 3 (т. е. три ресурса), то производится попарное сложение первого и второго, второго и третьего столбцов и таким образом получают двухстолбцовую матрицу Тп. После преобразования следует проверить, выполняются ли вышеперечисленные условия. Если это не так, то задача планирования не имеет строгого решения и используют эвристические алгоритмы.
Для пояснения алгоритма Джонсона представим матрицу Т„ как двухстолбцовую:
Алгоритм Джонсона состоит в следующем.
1. В матрице Т„ определяется /mjn-min{?ц, /12, ..., tmi}-
2. Из задач Зь ..., 3W выбираются задачи, для которых ресурсоем- кость хотя бы по одному устройству была равна /min, т.е. в данном случае выбирают задачи 3/, у которых хотя бы одна из двух ty= /т;п. (Напомним, что i — это номер задачи,у — номер устройства, i = 1,..., т,
7 = 1; 2.)
3. Задачи группируют по минимальному времени их исполнения
на первом и втором устройствах, т.е. и
4. В начало последовательности обрабатываемых задач ставят 3, (/min, to), В конец — 3/ ( ti\, /mjn).
5. Задачи, вставленные в последовательность обрабатываемых задач, исключаются из матрицы Т„.
6. Для новой матрицы повторяются пункты 1—3.
7. Задачи 3,- (/mm, /с) и 3; (/л, fmin) , полученные из новой матрицы, ставятся в середину составленной ранее последовательности обрабатываемых задач и т. д.
В основе эвристических алгоритмов лежат процедуры выбора из поступивших задач наиболее трудоемких и расположения их в порядке убывания времени выполнения.
При планировании по критерию максимума загрузки устройств вычислительной системы матрицы ресурсоемкости преобразуются в матрицы загрузки устройств. Из этих матриц формируют по каждому устройству потоки задач, выборки из которых позволяют сформировать оптимальную последовательность задач, подлежащих обработке.
Реализация функций и алгоритмов планирования вычислительного процесса происходит с помощью управляющих программ операционной системы ВС. Программа планировщик определяет ресурсоемкость каждой поступившей на обработку задачи и располагает их в оптимальной последовательности. Подключение ресурсов в требуемых объемах к программам выполнения задач осуществляет по запросу планировщика управляющая программа супервизор, которая тоже входит в состав операционной системы.
Таким образом, одной из важнейших процедур информационного процесса обработки данных является организация вычислительного процесса, т.е. обслуживание поступающих на обработку заданий (очередей) и планирование (оптимизация последовательности) их обработки. На программно-аппаратном уровне эти функции выполняют специальные управляющие программы, являющиеся составной частью операционных систем, т. е. систем, организующих выполнение компьютером операций обработки данных.
Разнообразие методов и функций, используемых в алгоритмах организации вычислительного процесса, зависит от допустимых режимов обработки данных в ВС. В наиболее простой ВС, такой, как персональный компьютер (ПК), не требуется управление очередями заданий и планирование вычислительных работ. В ПК применяют в основном режим
поэтому их операционные системы не имеют в своем составе программ диспетчирования, планировщика и супервизора. Но в более мощных ЭВМ, таких, как серверы и особенно мейнфреймы, подобные управляющие программы оказывают решающее влияние на работоспособность и надежность ВС. Например, к и№Х- серверам могут обращаться с заданиями одновременно сотни пользователей, а к мэйнфреймам типа Б/390 - тысячи.
25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 Наверх ↑