Планирование исполнения процессов

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

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

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

FIFO - очередь задач (First In, First Out)

LIFO - очередь задач (стек) (Last In, First Out)

Варианты LIFO и FIFO иллюстрируют статическое планирование исполнения процессов в однопроцессорной системе под управлением операционной системы с монопольным доступом к процессору (операционная система без вытеснения процесса).

Круговое обслуживание задач на базе FIFO очереди

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

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

3.1 Work stealing

Можно выделить два подхода к планированию исполнения процессов в многопроцессорных системах:

Ниже описывается алгоритм, который используется в планировщике библиотеки PFX, и в основе которого лежит идея заимствования работ (work stealing, коротко WS).

Идея WS-планирования заключается в том, что каждый процессор имеет собственный пул потоков, которые он должен исполнить. При наличии в пуле потоков, процессор изымает один из потоков и начинает исполнять его. Как только пул процессора оказывается пуст, процессор становиться "вором" и крадет (steal) потоки из пулов других процессоров.

Пул потоков процессора представляет собой двустороннюю очередь (часто называемую WS-deque). Для того чтобы начать исполнять следующий поток из пула, процессор извлекает поток с одной стороны очереди - будем называть этот конец очереди bottom. После извлечения потока, процессор исполняет поток до тех пор, пока поток не завершится или исполнение потока не будет блокировано каким-то внешним событием. В этом случае процессор извлекает новый поток из bottom, а блокированный поток помещает назад в bottom. Таким образом, пока очередь не пуста, процессор работает с ней по принципу LIFO (по принципу стека).

В том случае, когда в очереди процессора нет потоков, он произвольно выбирает другой процессор и извлекает из очереди этого процессора поток с противоположной от bottom стороны (назовем ее top ). Если же очередь другого процессора также пуста, то процессор-вор ищет другую "жертву".

Дополнительные сведения о планировании исполнения процессов будут приведены в лекции 5.

Семинарское занятие № 3. Пользовательские расширения Parallel.For

Конструкция Parallel.For, реализованная в PFX, является, по сути, параллельным аналогом последовательного цикла for перебора в некотором диапазоне чисел. Однако, конструкция цикла for в языке C# не ограничена только перебором чисел из определенного диапазона - она также поддерживает произвольные выражения для инициализации цикла, условия окончания и обновления индекса:

for(var i = init(); cond(i); i = upd(i)) { Use(i); }

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

public static void ParallelFor<T> ( 
    Func<T> init, Func<T,bool> cond, Func<T,T> upd, Action<T> body) 
{ 
    Parallel.ForEach(Iterate(init, cond, upd), body);  
} 

private static IEnumerable<T> Iterate<T> ( 
    Func<T> init, Func<T,bool> cond, Func<T,T> upd) 
{ 
    for(var i=init(); cond(i); i = upd(i)) yield return i; 
}

Можно видеть, что здесь создана некоторая версия конструкции Parallel.For, которая поддерживает произвольные выражения для инициализации цикла, условия окончания и обновления индекса. Другими словами, здесь представлена параллельная версия C#-итератора.

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

for(Node n = list; n != null; n = n.Next) 
{ 
    Process(n); 
}

Параллельная версия на основе введенной нами выше конструкции выглядит так:

ParallelFor(() => list, n => n != null, n => n.Next, n => 
{ 
    Process(n); 
});

Изучение и анализ примеров

В и приведены описания и приложены исходные коды параллельных программ быстрого преобразования Фурье (БПФ) и теста RandomAccess. Рассмотрите применение в них конструкций Paralell.For, а также возможность их замены на более высокоуровневые аналоги по типу тех, которые описаны в разделе 1 данного семинарского занятия. Кроме того, посредством запуска этих примеров на различном количестве процессоров, оцените эффективность данных реализаций БПФ и RandomAccess и выявите возможные проблемы с производительностью этих приложений.