4.3. ОРГАНИЗАЦИЯ ПЛАНИРОВАНИЯ ОБРАБОТКИ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ

Эффективность обслуживания вычислительных задач (их про­грамм) зависит прежде всего от среднего времени обслуживания

поэтому в вычислительной системе (и в многомашин­ной, и в одномашинной особенно) требуется решать проблему минимизации времени обработки поступивших в систему зада­ний. Иногда эта проблема трансформируется в задачу макси­мизации загрузки устройств ЭВМ. являющихся носителями ре­сурсов.

При решении вычислительной задачи ЭВМ использует свои ресурсы в объеме и последовательности, определяемых алгорит­мом решения. К ресурсам ЭВМ относятся объем оперативной и внешней памяти, время работы процессора, время обращения к внешним устройствам (внешняя память, устройства отображе­ния). Естественно, что эти ресурсы ограничены. Поэтому и тре­буется найти наилучшую последовательность решения поступив­ших на обработку вычислительных задач. Процесс определения последовательности решения задач во времени называется плани­рованием. При планировании необходимо знать, какие ресурсы и в каком количестве требует каждая из поступивших задач. Ана­лиз потребности задачи в ресурсах производится на основе ее программы решения. Программа состоит, как правило, из огра­ниченного набора процедур (по крайней мере к этому с известными для данной ВС затратами ресурсов. После анализа поступивших программ решения задач становится ясно, какая задача каких ресурсов требует и в каком объеме. Критерии, ис­пользуемые при        зависят от степени

ти алгоритмов решаемых задач. Крайних случаев два: порядок использования устройств ЭВМ при решении задач строго задан их алгоритмами, а порядок использования устройств ВС в зада­чах заранее не известен. Для первого случая приемлем критерий минимизации суммарного времени решения вычислительных за­дач, для второго — максимизации загрузки устройств ВС.

Пример.

Рассмотрим модель планирования вычислительного процесса при минимизации суммарного времени [21].

Обозначим ресурсы вычислительной системы через Я1,К2,..., Я_п- Каждая программа решения задачи обработки данных включает типо­вые процедуры из набора П], П2, ..., П_т. Тогда матрица Г ресурсозат­рат, приведенных к времени, будет выглядеть так:

Знание матриц ресурсозатрат при выполнении программ позволя­ет вычислить суммарные затраты каждого из ресурсов по всем про­граммам решения вычислительных задач, поступивших в ВС, и соста­вить их матрицу ресурсозатрат. Обозначим поступившие в ВС про­граммы решения задач через Зь З2, ...,З_т;1у — затратыу-го ресурса на выполнение 1-й задачи (г = 1,..., т;)= 1,..., п)\ Я\, 112, ■■■, — ресурсы ВС. Матрица ресурсозатрат по задачам запишется в виде

 

 

довательность прохождения через обработку задач, которая миними­зирует суммарное время. Одним из методов нахождения такой после­довательности, т. е. планирования, является метод решения задачи Джонсона [32], относящийся к теории расписаний и дающий эффектив­ный и строгий алгоритм. При этом учитываются следующие ограни­чения:

•       для любого устройства ВС выполнение последующей вычисли­тельной задачи не может начаться до окончания предыдущей;

•       каждое устройство в данный момент может выполнять только одну вычислительную задачу;

•       начавшееся выполнение задачи не должно прерываться до пол­ного его

Если в процессе обработки данных используется п устройств (ре­сурсов) ВС, нахождение оптимальной последовательности поступаю­щих на решение т задач, минимизирующих суммарное время обра­ботки, потребует перебора {т\)^п вариантов. Например, если в ВС по­ступило всего шесть заданий (т = 6), использующих всего два ресурса (п - 2), то для нахождения оптимальной последовательности после со­ставления матрицы Т„ потребуется произвести (6!) переборов, т.е. 518400. Если же т - 10, то потребуется порядка 10¹³ переборов. Ясно, что даже для ЭВМ это многовато.

Алгоритм Джонсона, полученный для п = 2, требует перебора толь­ко от (т + 1) / 2 вариантов, т.е. для нашего примера (т = 6) необходимо будет проделать 21 перебор, что значительно меньше, чем 518400. При и > 2 задачу планирования по критерию минимума суммарного време­ни обработки сводят к задаче Джонсона путем преобразования матри­цы Г,,. Например, если п = 3 (т. е. три ресурса), то производится попар­ное сложение первого и второго, второго и третьего столбцов и таким образом получают двухстолбцовую матрицу Т_п. После преобразова­ния следует проверить, выполняются ли вышеперечисленные условия. Если это не так, то задача планирования не имеет строгого решения и используют эвристические алгоритмы.

Для пояснения алгоритма Джонсона представим матрицу Т„ как двухстолбцовую:

Алгоритм Джонсона состоит в следующем.

1.    В матрице Т„ определяется /_mj_n-min{?ц, /12, ..., t_mi}-

2.     Из задач Зь ..., 3_W выбираются задачи, для которых ресурсоем- кость хотя бы по одному устройству была равна /min, т.е. в данном случае выбирают задачи 3/, у которых хотя бы одна из двух ty= /_т;_п. (Напомним, что i — это номер задачи,у — номер устройства, i = 1,..., т,

7 = 1; 2.)

3.     Задачи группируют по минимальному времени их исполнения

на первом и втором устройствах, т.е.    и

4.     В начало последовательности обрабатываемых задач ставят 3, (/min, to), В конец — 3/ ( ti\, /_mj_n).

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

6.    Для новой матрицы повторяются пункты 1—3.

7.     Задачи 3,- (/mm, /с) и 3; (/л, f_mi_n) , полученные из новой матрицы, ставятся в середину составленной ранее последовательности обраба­тываемых задач и т. д.

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

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

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

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

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

поэтому их операционные системы не имеют в своем составе про­грамм диспетчирования, планировщика и супервизора. Но в бо­лее мощных ЭВМ, таких, как серверы и особенно мейнфреймы, подобные управляющие программы оказывают решающее влия­ние на работоспособность и надежность ВС. Например, к и№Х- серверам могут обращаться с заданиями одновременно сотни пользователей, а к мэйнфреймам типа Б/390 - тысячи.