Задачи и способы планирования работ

Выполнения работ

Планирование по критерию минимума суммарного времени

Детерминированное планирование

Рисунок 2.3 - Методы планирования

Методы планирования

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

,

где – емкость памяти, требуемая i-й работе.

– время занятия работой i устройства j.

L – число одновременных работ.

J₁…J_n – работа (процесс).

Q_n – заданный объем памяти.

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

Параметры ресурсов и работ.Ресурсы ВС — памяти и устрой­ства — задаются следующим образом. Память характе­ризуется емкостью, а устройство — быстро­действием (производительностью), определяемым средним числом операций, выполняемых за единицу времени. Внешнее запоминающее устройство содержит в себе два ресурса: память определенной емкости и производительность, определяемую средним числом передач информации в единицу времени и скоростью передачи информации. Таким образом, ВС обладает совокупностью ресурсов F₀, F₁, ..., F_N, где F₀ — ресурс памяти, F₁, ..., F_N - ресурсы устройств.

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

Потребность работ J₁ ..., J_M в ресурсах памяти F₀ и устройств F₁, ..., F_N будем ха­рактеризовать матрицей

M F₁ F₂ F_N

J₁ m₁ t₁₁ t₁₂ . . . t_1N

J₂ m₂ t₂₁ t₂₂ . . . t_2N (1)

T = ( m_i, t_ij) = .........................................

J_M m_M t_M1 t_M2 . . . t_MN

Элемент τ_ij (ϊ=1, ..., Μ j= 1, .., Ν) характеризует потребность работы J_ί в ресурсе устройства F_j.(j=1...N). Значение τ_ij определяет число единиц времени, необходимых для выполнения работы J_ί на этом устрой­стве.

Элемент m_i характеризует потребность работы J_i в ресурсе памяти M. Значение m_i задает количество единиц информации, которые должны быть размещены в памяти M при выполнении ра­боты J_ί.

Матрицу (1) будем называть матрицей трудоемкости работ, имея в виду, что она характеризует потребность работ не только во времени, но и в памяти, т. е. характеризует как трудоемкость, так и сложность работ.

Порядок использования ресурсов — это очередность работы устройств при выполнении каждой из работ. Например, пусть систе­ма состоит из устройства ввода F₁ процессора F₂ , и устройства вывода F₃ . Порядок использования ресурсов может быть следующим. Работа сначала выполняется на устройстве F₁, при этом устройства F₂ и F₃ не используются. Затем работа выполняется только с использованием устройства F₂ и завершается на устройстве F₃. Если порядок использования устройств априорно определить невозможно, то говорят, что ресурсы используются в случайном порядке.

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

Итак, задача планирования состоит в следующем. Исходя из заданных ресурсов M, F₁, ..., F_N, системы, матрицы трудоемкости работ (1), требуется построить план (расписание), т. е. определить оптимальный порядок выполнения работ во времени.

Планирование вычислительного процесса может иметь целью минимизацию суммарного времени выполнения работ (времени вы­полнения пакета работ). Эта цель достигается путем совмещения работы устройств ВС во времени: чем больше во времени совмещена работа отдельных устройств, тем меньшее время будет затрачено на выпол­нение пакета задач. Чтобы решить задачу планирования в такой постановке, необходимо располагать информацией о трудоемкости каждой работы и порядке использования ресурсов системы каждой работой. Трудоемкость работы будем представлять матрицей (1), величины τ_ij в которой определяются априорно известными детер­минированными значениями. Простые алгоритмы планирования работ по критерию минимума суммарного времени выполнения работ могут быть построены в предположении, что все работы используют ресурсы системы в одинаковом порядке. Здесь будут рассматриваться алгоритмы планирования, предполагающие следующий порядок прохождения задач: 1) ввод, обработка; 2) ввод, обработка и вывод. При этом рассматривается слу­чай, когда на каждой фазе выполнения работ используется лишь один ресурс.

Рис.2.4. Двухфазная модель выполнения работ

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