Диспетчеризация в мультипроцессорной системе

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

● Алгоритм разделения времени

Простейший алгоритм диспетчеризации процессов (или потоков) состоит в поддержании единой очереди готовых потоков (возможно с различными приоритетами).

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

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

● Алгоритм родственного планирования.

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

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

Двухуровневое планирование обладает тремя преимуществами

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

○ Во-вторых, двухуровневое планирование по возможности использует преимущество родственности кэша.

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

● Совместное использование пространства (процессоров).

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

Планирование нескольких потоков на нескольких центральных процессорах называется совместным использованием пространства или разделением пространства.

Простейший алгоритм разделения пространства работает следующим образом.

○ Создается группа связанных потоков.

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

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

○ Если процессоров недостаточно, ни один из потоков не запускается, пока не освободится достаточное количество центральных процессоров.

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

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

Периодически должны приниматься решения о планировании процессов. В однопроцессорных системах для пакетного планирования применяется хорошо известный алгоритм «кратчайшее задание первое». Подобный алгоритм для мультипроцессора представляет собой выбор процесса, для которого требуется наименьшее количество циклов процессора, то есть процесса, чье произведение числа центральных процессоров на время работы минимально. Однако на практике эта информация редко бывает доступна, поэтому применение такого алгоритма затруднительно. Действительно, исследования показали, что придумать что-либо лучше простого обслуживания заданий в порядке их поступления трудно.

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

Один из способов управления степенью распараллеливания заключается в наличии центрального сервера, ведущего учет работающих и желающих работать процессов, а также минимального и максимального количества требующихся для них центральных процессоров. Периодически центральный сервер опрашивает каждый центральный процессор, чтобы узнать, сколько центральных процессоров он может использовать. Затем он увеличивает или уменьшает количество процессов или потоков, стараясь добиться соответствия числу доступных процессоров. Например, на web-сервере могут параллельно работать 1, 2, 5, 10, 20 или любое другое количество потоков. Если на нем в настоящий момент работает 10 потоков и вдруг спрос на центральные процессоры повышается, то ему могут приказать сократить число своих потоков до 5. Поэтому, когда 5 потоков закончат свою работу, они не получают новую работу, а завершаются. Такая схема обеспечивает динамическое изменение размеров групп процессоров, чтобы добиться лучшего соответствия текущей нагрузке.

● Бригадное планирование.

Множество потоков процесса распределяются для одновременного выполнения на множестве процессоров, по одному потоку на процессор.

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

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

Чтобы понять, какие возможны проблемы при независимом планировании потоков процесса (или процессов задания), рассмотрим систему с потоками А_о и А₁, принадлежащими процессу А, и потоками В_о и В₁, принадлежащими процессу В. Потоки А_о и В_о работают в режиме разделения времени на центральном процессоре 0, а потоки А₁ и В₁ - на процессоре 1. Потокам А_о и А₁ нужно часто обмениваться информацией. Общение потоков выглядит следующим образом. Поток А_о посылает потоку А₁ сообщение, после чего поток А₁ отправляет потоку А_о ответ и т. д. Предположим, что потоки А_о и В_о, начали выполняться первыми. В интервале времени 0 поток А_о посылает потоку А₁ запрос, но поток А₁ не получает его до тех пор, пока не будет запущен в интервале времени 1, начинающемся через 100 мс. Он немедленно отправляет ответ, но поток А_о не получает ответа, пока его снова не запустят в момент времени 200 мс. В результате за 200 мс мы получаем всего одну пару запрос-ответ, что не слишком хорошо. Решением данной проблемы является так называемое бригадное планирование, представляющее собой развитие идеи совместного планирования.

Бригадное планирование состоит из трех частей:

● Группы связанных потоков планируются как одно целое, бригада.

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

● Все члены бригады начинают и завершают свои временные интервалы (кванты времени) одновременно.

Бригадное планирование работает благодаря синхронности работы всех центральных процессоров.

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