Л а б о р а т о р н а я р а б о т а 7

ПЛАНИРОВАНИЕ РАБОТ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ

Цель работы: освоение простейших алгоритмов планирования выполнения работ на заданном наборе ресурсов вычислительной системы.

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

Потребность работ J₁,J₂,...,J_m в ресурсах F₁,F₂,...,F_n характеризуется матрицей трудоемкости работ

		F1	F2	. . .	Fn
	J1	t11	t12	. . .	t1n
	J2	t21	t22	. . .	t2n
T = [ tij ] =	. . .	. . .	. . .	. . .	. . .
	Jm	tm1	tm2	. . .	tmn

где t_ij - означает потребность работы J_i в ресурсе F_j.

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

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

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

Поэтому следует учитывать дополнительные факторы, основные из которых следующие:

- степень детерменированности характеристик работ и порядка их поступления в вычислительную систему;

- затраты времени на выполнение алгоритма высокоэффективного планирования.

Если характеристики работ и время их поступления известны с высокой точностью, то следует воспользоваться результатами прикладной математической дисциплины известной под названием теория расписаний [1]. Но обычно, за редким исключением, оптимальное расписанием может быть найдено только методом полного перебора, так как данный класс задач относится к комбинаторным задачам. Даже при небольшом числе работ полный перебор всех вариантов расписания требует больших затрат машинного времени.

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

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

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

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

Трудоемкости внешних устройств и процессора заданы в некоторых единицах времени, допустим в секундах, а потребность в ОЗУ характеризуется числом условных страниц. Причем общий объем ОЗУ равен тридцатидвум страницам и категорически не может быть превышен.

В дальнейшем для примеров будет использоваться матрица трудоемкости вида

		F1	F2	CPU	F3	MEM
	J1
	J2
Т =	J3						( 1 )
	J4
	J5

Т Р У Д О Е М К О С Т Ь В Ы П О Л Н Е Н И Я Р А Б О Т

Таблица 4.1

Номер варианта	УВВ F1, сек	УВВ F2, сек	Процессор CPU, сек	УВВ F3, сек	ОЗУ, страниц

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

1. Планирование работ на основе двухфазной модели

вычислительной системы

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

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

		F1	F2
	J1
	J2
T =	J3			( 2 )
	J4
	J5

Обозначим продолжительности выполнения работ J₁,J₂,...,J_m в первой фазе через t₁₁,t₂₁,...,t_m1, а во второй фазе - t₁₂,t₂₂,...,t_m2 соответственно.

Алгоритм оптимального планирования в такой постановке состоит из следующих этапов:

1.1. Отметим начало очереди работ позицией a = 1 и конец очереди - позициеей b = m.

1.2. В матрице трудоемкости находится минимальное значение t = min( t₁₁,t₁₂,...,t_m1,t_m2 ).

1.3. Выделяются работы J_k,...,J_n, для которых t_ij = t ( i = k,...,n; j = 1,2 ).

1.4. Если выделена единственная работа J_k, то при t_k1 = t, она ставится в начало очереди, опредеяемой позицией a, а при t_k2 = t - в конец очереди в позицию b. Затем выполняется пункт 1.7.

1.5. Если выделено несколько работ J_k,...,J_n, то они разделяются на две группы:

а) c одинаковыми временами выполнения в первой фазе t_k1,...,t_n1, равными t;

b) c одинаковыми временами выполнения во второй фазе t_k2,...,t_n2, равными t.

1.6. Работы из первой группы заносятся в начало очереди с позиций a, a+1, ... в порядке увеличения значений t_i2, ..., t_j2. Работы из второй группы заносятся в конец очереди в позиции b, b-1, ... в порядке увеличения значений t_i1,...,t_j1.

1.7. После включения работы в начало или конец очереди работа вычеркивается из матрицы трудоемкости и переменной a или b присваивается новое значение a = a + 1 или b = b - 1.

1.8. Процесс продолжается из пункта 1.2 до распределения всех работ по позициям очереди.

Для матрицы трудоемкости ( 2 ) в соответствии с вышеизложенным алгоритмом планирование работ выполняется следующим образом:

1.1. Присваиваем a = 1 и b = 5.

1.2. Находим минимальное значение t = 3 матрице трудоемкости.

1.3. Выбираем работы, для которых t_ij = t = 3:

	F1	F2
J3

1.4. Так как выделена единственная работа с минимальным значением t из второй фазы, то она ставится в конец очереди и b = 4.

1.5. Вычеркиваем упорядоченные работы из матрицы трудоемкости ( 2 ) и получим следующую матрицу трудоемкости:

		F1	F2
	J1
	J2
T =	J4
	J5

1.6.В новой матрице трудоемкости находим минимальное значение t = 4.

1.7.Выбираем работы, для которых t_ij = t = 4:

	F1	F2
J5

1.8.Так как выделена единственная работа с минимальным значением t из второй фазы, то она ставится в конец очереди и b = 3.

1.9.Получаем новую матрицу трудоемкости путем вычеркивания упорядоченных работ:

		F1	F2
	J1
T =	J2
	J4

1.10. Повторяя предыдущее, опредеяем, что работа J2 ставится в конец очереди и b = 3. Следующая матрица трудоемкости имеет вид

		F1	F2
	J1
T =	J4

1.11. Находим в последней матрице минимальное значение t = 11.

1.12. Выбираем единственную работу, для которой t_ij = t = 11

		F1	F2
T =	J4

1.13. Ставим выделенную работу в начало очереди, так как минимальное значение t соответствует первой фазе и a = 2.

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

J4	J1	J2	J5	J3

Диаграмма выполнения этих работ представлена на рис.4.1, откуда следует, что весь пакет выполняется за 65 единиц времени. Несложно убедиться, что пропуск пакета в порядке противоположном оптимальному расписанию потребует 84 единицы времени.

Диаграмма выполнения двухфазной модели по расписанию

t

4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64

F₁

J₄ J₁ J₂ J₅ J₃

® t

F₂

J₄ J₁ J₂ J₅ J₃

® t

Рис.4.1

Диаграмма выполнения трехфазной модели по расписанию

t

4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64

F₁

J₁ J₄ J₂ J₅ J₃

® t

CPU

J₁ J₄ J₂ J₅ J₃

® t

F₂

J₁ J₄ J₂ J₅ J₃

® t

Рис.4.2

2. Планирование работ на основе

трехфазной модели вычислительной системы

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

		F1	CPU	F3
	J1
	J2
T =	J3				( 3 )
	J4
	J5

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

min( t_i1 ) >= max( t_j2 );

^{i j}

( 4 )

min( t_i3 ) >= max( t_j2 ),

^{i j}

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

Для матрицы трудоемкости ( 3 ) имеем:

min( t_i1 ) = 7; max( t_j2 ) = 10; min( t_i3 ) = 1,

^{i j i}

т.е. ограничение ( 4 ) не выполняется.

Наиболее простой из эвристических алгоритмов планирования для трехфазных моделей вычислительной системы включает следующие пункты:

2.1. Определяется номер строки фазы k с наибольшей суммарной продолжительностью работ, т.е.

_m

max ( å t_ik ) .

^{k i=1}

2.2. Если k = 1, то работы запускаются в порядке убывания величин t_i2 + t_i3.

2.3. Если k = 3, то работы запускаются в порядке возрастания величин t_i1 + t_i2.

2.4. Если k = 2, то работы упорядочиваются на основе алгоритма двухфазного планирования при исключениии второго столбца из матрицы трудоемкости.

Для матрицы трудоемкости ( 3 ) получим:

t_i1 = 55; t_i2 = 26; t_i3 = 24, ( 5 )

т.е. наибольшую суммарную продолжительность работ имеет фаза ввода информации. В соответствии с пунктом 2.2 работы следует запустить в порядке убывания величин t_i2 + t_i3. План пропуска программ будет следующий:

J1	J2	J3	J4	J5

Диаграмма выполнения работ по этому расписанию изображена на рис 4.2. Из рисунка видно, что время выполнения всего пакета программ при выбранном расписании равно 58 сек. На рис. 4.3 приведена диаграмма выполнения этого же пакета в соответствии с матрицей трудоемкости ( 3 ). Из анализа следует, что эвристический алгоритм планирования дает выигрыш в семь единиц времени.

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

Эта же идея заложена в алгоритм нахождения минимально возможного времени выполнения пакета программ Т₀, которое необходимо для оценки эффективности эвристических методов планирования работ в любых моделях. Обозначим через Т₂ максимальную суммарную продолжительность выполнения из всех фаз матрицы трудоемкости, т.е.

_m

T₂ = max ( å t_ik ). ( 6 )

^{k i=1}

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

Т1 =

{

0, при k = 1;   k-1 min ( å tij ), при k = 1. i i=1

Длительность конечного этапа выполнения всех работ из пакета может быть определена по выражению

Т3 =

{

0, при k = m;   m min ( å tij ), при k = 1. i i=k+1

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

T₀ = T₁ + T₂ + T₃.

Диаграмма выполнения трехфазной модели по исходной

матрице трудоемкости

t

4 8 12 16 20 24 28 32 36 40 44 48 52 56 60 64

F₁

J₁ J₂ J₃ J₄ J₅

® t

CPU

J₁ J₂ J₃ J₄ J₅

® t

F₃

J₁ J₂ J₃ J₄ J₅

® t

Рис.4.3

Для матрицы трудоемкости ( 3 ) из ( 6 ) имеем, что Т₂ = 55, а наиболее трудоемкая фаза k = 1. Отсюда получаем, что Т₁ = 0. Из матрицы ( 3 ) простым перебором находим, что Т₃ = t₃₂ + t₃₃ = 3. Таким образом Т₀ = T₁ + T₂ + T₃ = 58, т.е. эвристический алгоритм позволил найти одно из квазиоптимальных расписаний для трехфазной модели.

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

t_i1 = 28; t_i2 = 27; t_i3 = 26; t_i4 =26.

Таким образом

T₂ = 28; k = 1; T₁ = 0; T₃ = 6 ( для работы J );

T₀ = 0 + 28 + 6 = 34.

Отсюда следует, что работу J3 необходимо запускать последней. Это уже позволяет снизить количество вариантов перебора для определения позиции в очереди для остальных работ. В нашем случае общее количество вариантов расписаний равно n! = 5! = 120. Определение позиции одной работы снижает число вариантов до значения ( n - 1 )! = 4! = 24.

3. Планирование по критерию максимальной загрузки

устройст вычислительной системы

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

3.1. По матрице трудоемкости вычисляется время выполнения T_i работы J_i:

_n

T_i =å t_ij.

^j=1

Тогда доля времени j-го устройства в выполнении i-й работы определяется значением

r_ij = t_ij / T_i ,

которое можно рассматривать как коэффициент загрузки j-го устройства со стороны i-й программы. Для ОЗУ коэффициент загрузки со стороны работы J_i равен отношению количества страниц, занимаемых работой J_i, к общему объему страниц в ОЗУ.

Из матрицы трудоемкости ( 1 ) на основании вышеописанных правил при общем объеме ОЗУ в 32 страницы получим следующую матрицу загрузки

		F1	F2	CPU	F3	MEM
	J1	.21	.24	.26	.29	.37
	J2	.32	.27	.23	.18	.47
R =	J3	.40	.30	.20	.10	.31	( 7 )
	J4	.19	.23	.27	.31	.60
	J5	.37	.27	.18	.18	.32

3.2. Каждая работа из пакета помещается в один из потоков, каждый из которых в максимальной степени загружает отдельные устройства вычислительной системы. Работа J_i помещается в поток P_j если

r_ij = max ( r_kj ) ,

^k

т.е. работа J_i имеет наибольший коэффициент загрузки для j-го устройства системы.

В нашем примере из матрицы загрузки ( 7 ) имеем:

P₁ = { J₂, J₃, J₅ };

P₂ = { };

P₃ = { };

P₄ = { J₁, J₄ }.

Из-за малого количества работ в пакете или неудачного подбора пакета потоки Р2 и Р3 оказались пустыми. Для увеличения загрузки вычислительной системы поместим в эти потоки работы с максимальной загрузкой указанных потоков, удалив эти работы из других потоков:

P₁ = { J₂,, J₅ };

P₂ = { J₃ };

P₃ = { J₄ };

P₄ = { J₁ }.

3.3. Совокупность работ, выполняемых совместно, называется смесью работ. Первоначально смесь составляется путем выборки работ из всех потоков по одной. При этом следует учитывать ограничения со стороны емкости ОЗУ.

3.4. В момент окончания работы J_i из смеси в последнюю следует попытаться поместить очередную работу из того потока, к которому принадлежала работа J_i. Это позволит поддерживать на высоком уровне загрузку того устройства, которое наиболее интенсивно использовалось только что выполненной работой. При назначении очередной работы на выполнение необходимо учитывать ограничения со стороны емкости ОЗУ. Если очередную работу из потока нельзя запустить из-за превышения емкости ОЗУ, то выбирается следующая работа из этого же пакета. Если это не удается, то берется работа из другого потока. Этот пункт выполняется до окончания всех работ из пакета.

Попытаемся составить смесь из работ, представляющих все потоки, т.е. включим в смесь работы J₂,J₃,J₄,J₁. Но при этом коэффициент загрузки ОЗУ оказывается равным

0.47 + 0.31 + 0.60 + 0.37 = 1.75,

т.е. при такой смеси ОЗУ перегружено. Элементарный перебор показывает, что одновременно в работу можно запустить только три работы - J₁,J₃,J₅. При этом коэффициент использования ОЗУ будет равен

0.37 + 0.31 + 0.47 = 1.0.

Одна из возможных диаграмм процесса выполнения работ приведена на рис.4.4. В момент времени t₁ = 38 будет завершена работа J₁. Но ни одну из оставшихся работ запустить нельзя из-за нехватки объема ОЗУ. В момент времени t₂ = 39 сек завершается выполнение работы J₃. В смесь работ может быть помещена любая из оставшихся работ - J₂ или J₄. Запускаем работу J₄, т.к. она имеет большее время выполнения последней фазы, чем работа J₂. В момент времени t₃ = 41 сек будет завершена работа J₅, но запустить последнюю работу J₂ нельзя из-за ограничения со стороны оперативной памяти. Это будет продолжаться до момента времени t₄ = 65, когда будет завершена работа J₄. В этот момент времени можно запустить работу J₂ и вся работа будет выполнена за 87 сек.

На рис 4.5 приведена диаграмма процесса выполнения работ,когда первыми в смесь помещены работы J₂,J₁. В момент времени t₁ = 22 сек будет завершена работа J₂ и может быть запущена работа J₅ из этого же потока. В связи с тем, что ОЗУ после этого свободно, помещаем в смесь в этот же момент времени и работу J₃. В момент времени t₂ = 45 завершается работа J₁, но последняя работа J4 запущена быть не может из-за нехватки объема ОЗУ. Работа J₄ запускается в момент времени t₃ = 47 cек после завершения работы J₅. Весь пакет будет выполнен за 73 сек.

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

Диаграмма выполнения четырехфазной модели по расписанию

® t