Имя материала: Информационные системы и технологии в экономике

Автор: Т.П. Барановская

4.3. организация планирования обработки вычислительных задач

 

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

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

При решении вычислительной задачи ЭВМ использует свои

ресурсы в объеме и последовательности, определяемых алгорит-

мом решения. К ресурсам ЭВМ относятся объем оперативной и

внешней памяти, время работы процессора, время обращения к

внешним устройствам (внешняя память, устройства отображе-

ния). Естественно, что эти ресурсы ограничены. Поэтому и тре-

буется найти наилучшую последовательность решения поступив-

ших на обработку вычислительных задач. Процесс определения

последовательности решения задач во времени называется плани-

рованием. При планировании необходимо знать, какие ресурсы и

в каком количестве требует каждая из поступивших задач. Ана-

лиз потребности задачи в ресурсах производится на основе ее

программы решения. Программа состоит, как правило, из огра-

ниченного набора процедур (по крайней мере к этому

с известными для данной ВС затратами ресурсов. После анализа

поступивших программ решения задач становится ясно, какая

задача каких ресурсов требует и в каком объеме. Критерии, ис-

пользуемые при     зависят от степени

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

Пример.

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

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

Знание матриц ресурсозатрат при выполнении программ позволяет вычислить суммарные затраты каждого из ресурсов по всем программам решения вычислительных задач, поступивших в ВС, и составить их матрицу ресурсозатрат. Обозначим поступившие в ВС программы решения задач через Зі, Зг, ■•■,3m; ty — затратыу-го ресурса на выполнение г-й задачи (г = 1,..., m; j= 1,..., п); R, R2, /?ш — ресурсы ВС. Матрица ресурсозатрат по задачам запишется в виде

 

 

Л,

«2 •

■ Rn

 

'11

h2 ■

■ hn

 

 

l22 ■

■ hn

з

 

lm2 ■

 

 

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

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

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

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

Если в процессе обработки данных используется п устройств (ресурсов) ВС, нахождение оптимальной последовательности поступающих на решение т задач, минимизирующих суммарное время обработки, потребует перебора (ті)" вариантов. Например, если в ВС поступило всего шесть заданий (т = 6), использующих всего два ресурса (п - 2), то для нахождения оптимальной последовательности после составления матрицы Т„ потребуется произвести (6!)  переборов, т.е.

1 3

518400. Если же m - 10, то потребуется порядка 10 " переборов. Ясно, что даже для ЭВМ это многовато.

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

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

 

 

*1

 

з,

'п

hi

 

hi

h\%

3(Я

'ml

lm2

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

1.         В матрице Т„ определяется tm -тіп{?ц, t2, tm2J.

2.         Из задач Зі, Зтвыбираются задачи, для которых ресурсоем-

кость хотя бы по одному устройству была равна fmin, т.е. в данном

случае выбирают задачи 3/, у которых хотя бы одна из двух ty= fm;n.

(Напомним, что / — это номер задачи,у — номер устройства, / = 1,..., т,

у = 1; 2.)

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

В начало последовательности обрабатываемых задач ставят

3, (?min, to), В КОНеЦ — 3; ( 1Л, tm ).

5.         Задачи, вставленные в последовательность обрабатываемых

задач, исключаются из матрицы Т„.

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

7.         Задачи 3,- (fmin> U2) и 3; (t-,, fmin) , полученные из новой матрицы,

ставятся в середину составленной ранее последовательности обраба-

тываемых задач и т. д.

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

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

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

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

Разнообразие методов и функций, используемых в алгоритмах организации вычислительного процесса, зависит от допустимых режимов обработки данных в ВС. В наиболее простой ВС, такой, как персональный компьютер (ПК), не требуется управление очередями заданий и планирование вычислительных работ. В ПК применяют в основном режим поэтому их операционные системы не имеют в своем составе программ диспетчирования, планировщика и супервизора. Но в более мощных ЭВМ, таких, как серверы и особенно мейнфреймы, подобные управляющие программы оказывают решающее влияние на работоспособность и надежность ВС. Например, к UNIX-серверам могут обращаться с заданиями одновременно сотни пользователей, а к мэйнфреймам типа S/390 - тысячи.

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 | 58 |