Алгоритм планирования вычислительного процесса вс, работающей в режиме однопрограммной пакетной обработки

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

Рассмотрим алгоритм планирования вычислительного процесса для случая ВС с одним центральным процессором. Дано n задач, образующих пакет, поступающий для реализации на вход ВС. Для каждой задачи известно: t_j- время выполнения j - й задачи; С_j- время, к которому должна быть выполнена j - я задача, или срок выполнения этой задачи.

При рассмотрении этого алгоритма предполагаем следующее:

1) время выполнения каждой задачи не зависит от порядка их выполнения и известно до начала процесса выполнения;

2) все задачи имеют равный приоритет;

3) центральный процессор ВС не может выполнять одновременно более одного задания.

За критерий при выборе оптимальной очередности решения задач пакета примем минимальное суммарное отклонение фактического времени каждой j - и задачи от заданного срокa решения С_j

Пусть имеем последовательность задач S_j (j =1, 2, …, n).

Рассмотрим разность между фактическим временем решения задачи и заданным сроком ее решения.

Для задачи, выполняемой

в первую очередь

вo вторую очередь

в третью очередь

в r – ю очередь

При j-я задача выполняется в срок;

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

Следовательно, задача состоит в определении такой последовательности решения задач пакета, которая минимизирует .Очевидно, что всех возможных последовательностей будет п!

Возможны следующие варианты организации вычислительного процесса:

1) Решение всех задач не выполняется в срок при любой последовательности выполнения, т.е. t_j –с_j > 0 для всех j . Тогда выражение для критерия минимального отклонения можно записать в виде

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

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

Такую последовательность получим, выполняя задачи в порядке уменьшения времени их решения;

3) В общем случае часть задач не решается в срок при любой очередности, а остальные задачи решаются в срок при любой очередности .

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

т.е. кроме задач, которые выполняются в срок при любой последовательности решения.

Задачам, для которых это условие не выполняется, необходимо присвоить номера в оптимальной последовательности в порядке увеличения

Оставшимся задачам присваиваются очередные номера оптимальной последовательности в порядке уменьшения времени решения этих задач.

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

Таблица 11.1

Номер задачи j	Время решения	Срок выполнения j й-задачи cj	Время завершения	Отклонение
I	4	21	4	- 17
2	7	30	11	- 19
3	10	37	21	- 16
4	2	3	23	20
5	3	2	26	24
6	10	38	36	- 2

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

Для задач 3 и 6 условие

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

Для задач 1, 2, 4, 5 составляем оптимальную последовательность в порядке возрастания величины .

Для задач 3 и 6 очередность решения устанавливаем в порядке уменьшения времени их реализации .

Выполним расчеты в рабочей табл. 11.2.

Таблица 11.2
j	tj	Cj	tj- Cj		Место в оптимальной последовательности
1	4	21	-17	21	3
2	7	30	-23	30	4
3	10	37	-27	37	6
4	2	3	- 1	3	1
5	3	2	1	4	2
6	10	38	-28	38	5

Полученную упорядоченную последовательность реализации задач сведем в табл. 11.3, аналогичную по форме табл. 11.1, и проведем сравнительный анализ результатов.

Таблица 11.3
Номер задачи j	Время решения tj	Срок выполнения j-й задачи - Cj	Время завершения	Отклонение
I	2	3	2	- 1
2	3	2	5	3
3	4	21	9	-12
4	7	30	16	-14
5	10	38	26	-12
6	10	37	36	- 1

В заданной последовательности реализации задач (см.табл.11.1) две из них были бы выполнены с общим опозданием на 44 единицы времени. В новой последовательности реализации задач только одна из них будет выполнена с опозданием на 3 единицы.