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

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

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

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

где m- количество задач в пакете; n- количество устройств системы; элемент матрицы, характеризующей потребность i-й задачи в j-м ресурсе. При этом, если задача выполняется без использования ресурса, то =0; если ресурс является не памятью, то значение определяет количество единиц информации i- й задачи, которые необходимо разместить в памяти; если ресурс является не памятью, то определяет число единиц времени, необходимых для выполнения i- й задачи на j-м устройстве.

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

.

Следовательно, доля времени, в течение которого j – е устройство будет загружено i- й задачей, при условии, что система выполняет только i-ю задачу, определяется значением

для ;

Преобразовав элементы матрицы трудоемкости в соответствии с последней формулой, получим матрицу загрузки устройств задачами

(11.1)

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

1. Пакет задачи делится на потоки, каждый из которых состоит из задач, в максимальной степени загружающих отдельные устройства ВС, т.е. i - я задача относится к j - му потоку, если , для всех к=j . Каждая задача приписывается единственному потоку задач.

2 . В начальный момент времени, когда начинается обработка пакета, из потоков Р_j( j = 1, n) забирается по одной задаче, образующих начальную рабочую смесь. При этом должно проверяться условие

,

где Е- емкость памяти ВС, отводимая под задачи; E_i- емкость задачи, включенной в рабочую смесь; а.,...,w - номера задач, включенных в смесь.

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

Рассмотрим процесс планирования вычислительного процесса на примере задач, заданных следующей матрицей трудоемкости:

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

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

Построим матрицу загрузки устройств. Коэффициенты загрузки устройств вычисляются по (11.1). Коэффициент загрузки оперативной памяти , определяющий долю ёмкости памяти, требуемую для размещения i-й задачи.

Коэффициент загрузки, вычисленный с точностью одного знака после запятой, приведен в табл. 11.4, используя которую распределим работы по потокам Р₁ , Р_2, Р₃. Задача 1 создает наибольшую загрузку для устройства вывода J=3 и, следовательно, должна быть отнесена к потоку Р₃; задача 2 создает наибольшую загрузку для процессора J=2 и выделяется в поток P₂; задача 3 создает наибольшую загрузку для устройства вывода, следовательно, выделяется в поток P₃ и т.д. Окончательно получаем

Р₁₌{5, 7, 9} ; Р₂ ={3,4,6} ; Р₃= {1, 3, 8}.

Таблица 11.4 ^ • Г>6
Номер задачи
I	8	0	0,4	0,6	0.3
2	II	0,2	0,7	0,1	0,2
3	II	0,1	0,1	0,8	0,4 \
4	20	0,3	0,5	0,2	0,4
5	7	0,6	0,4	0	0,4
6	18	0,3	0.6	0,1	0,6
7	12	0,6	0,2	0,2	0,4
8	II	0,3	0,2	0,5	0,3
9	15	0,5	0,3	0,2	0,6

На рис. 11.5, а представлены диаграммы работы устройств:

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

Суммарная загрузка Е^* оперативной памяти представлена диаграммой рис. 11.5, б. Вертикальные линии отмечают моменты перерастания памяти. Слева от вертикальной линии указывается номер завершенной задачи, которая освобождает память, справа – номер следующей задачи, включенной в смесь и память. В момент времени t=0 в память загружаются задачи 5,2,1из потоков Р1, р2,Р3, которые совместно занимают 0,9 емкости памяти. Смесь не может быть пополнена другой задачей, поскольку свободная часть памяти имеет недостаточную емкость. Эта смесь выполняется до момента t= 7, в который заканчивается выполнение задачи 5. На ее место загружается задача 7 из того же потока Р1, что и задача 5. Новая смесь задач выполняется до момента t=16, которому соответствует завершение задачи 2. При этом освобождается 0.2 емкости памяти. Емкость свободной памяти на момент завершения этой работы составляет 0,3 Е. Поскольку задача 2 относится к потоку Р2, то для обеспечения максимальной загрузки следовало бы включить в смесь задачу 4 или 6. Но задачи 4 и 6 не могут быть размещены в памяти, поскольку требуют 0,4 Е и 0,6 Е памяти, и смесь пополняется задачей 8, которая может быть размещена в памяти.

Данный пример иллюстрирует также, насколько существенны для процесса планирования ограничения со стороны емкости памяти. Анализ полученного плана показывает, что среднее число параллельно работающих устройств равно 1,6 при средней загрузке оперативной памяти 0,88; общее время решения задач пакета составляет всего 69 единиц времени, в то время как решение задач однопрограммном режиме потребовало бы 113 единиц времени.

Рис. 11.5. Диаграмма работы устройств