<<
>>

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 - тысячи.

<< | >>
Источник: Т.П. Барановская, В.И. Лойко, М.И. Семенов, А.И. Трубилин. Информационные системы и технологии в экономике: Учебник. - 2-е изд., доп. и перераб. Под ред. В.И. Лойко. - М.: Финансы и статистика, - 416 с: ил.. 2005

Еще по теме 4.3. ОРГАНИЗАЦИЯ ПЛАНИРОВАНИЯ ОБРАБОТКИ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ:

  1. 14.2. Диспетчеризация и планирование вычислительных задач
  2. 4.6. УПРАВЛЕНИЕ РЕСУРСАМИ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ 4.6.1. ОДНОПРОЦЕССОРНЫЕ СИСТЕМЫ ОПЕРАТИВНОЙ ОБРАБОТКИ
  3. 4.2.ОРГАНИЗАЦИЯОБСЛУЖИВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ ЗАДАЧ
  4. 10.2. Частные методики решения вычислительных задач
  5. 4.1. ОРГАНИЗАЦИЯ ВЫЧИСЛИТЕЛЬНОГО ПРОЦЕССА
  6. 1.4.2. Особенности оперативных постановок информационных, вычислительных задач и их комплексов
  7. 3.2. Типовая структура технологического процесса обработки информации при решении экономических задач
  8. 4.6.2. МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ ПРИ ОБРАБОТКЕ ПАКЕТОВ ЗАДАЧ С ПРЕРЫВАНИЯМИ
  9. 4.6.3. МНОГОПРОЦЕССОРНЫЕ СИСТЕМЫ ПРИ ОБРАБОТКЕ ПАКЕТОВ НЕЗАВИСИМЫХ ЗАДАЧ БЕЗ ПРЕРЫВАНИЙ
  10. 4.5. НЕТРАДИЦИОННАЯ ОБРАБОТКА ДАННЫХ 4.5.1. ПАРАЛЛЕЛЬНАЯ ОБРАБОТКА
  11. Содержание финансового планирования. Основные задачи и этапы планирования
  12. 2. ПРЕДМЕТ ПЛАНИРОВАНИЯ. СУЩНОСТЬ И СТРУКТУРА ОБЪЕКТОВ ПЛАНИРОВАНИЯ В ОРГАНИЗАЦИИ
  13. Финансовое планирование. Содержание и задачи финансового планирования. Виды финансовых планов
  14. § 1. Задачи и принципы планирования капитальных вложений
  15. 5.1.1. Цель и задачи внутрифирменного планирования
  16. 7.2. Информационно-вычислительная сеть ФСГС РФ
  17. 99. Задачи инвестиционного планирования
  18. 20.1. ЦЕЛИ И ЗАДАЧИ ФИНАНСОВОГО ПЛАНИРОВАНИЯ