Планировщик операционной системы мультипроцессора призван решать две следующие основные задачи планирования процессов:
Способ решения этих задач существенно зависит от того, независимы или зависимы (связаны друг с другом) процессы.
Планирование независимых процессов.
Основным алгоритмом планирования независимых процессов является алгоритм планирования процессов с использованием очередей заданий. Идея подхода состоит в следующем. Все готовые к исполнению процессы помещаются в очередь заданий. Освободившийся процессор получает готовый к исполнению процесс из этой очереди. По мере обработки данных появляются новые готовые к исполнению процессы, которые помещаются в очередь заданий. При наличии нескольких готовых к исполнению процессов возникает проблема формирования правил выделения процессов из очереди.
Процесс в системе может находиться в следующих основных состояниях:
Все процессы в состоянии «готов к исполнению» образуют либо единую очередь к процессорам, упорядоченную по приоритетам процессов, либо образуют несколько очередей для процессов с разными приоритетами (например, в транспьютерах – очередь процессов с высоким приоритетом и с обычным приоритетом).
Переключение процессоров с процесса на процесс заключается в выборе самого приоритетного процесса из очереди (этот процесс находится в начале очереди). Смена процессов может вызываться исчерпанием кванта времени, отведенного под непрерывное выполнение текущего процесса, или переходом процесса в состояние "ожидает".
Если одновременно освободятся два процессора, то они могут выбрать для исполнения один и тот же процесс. Для предотвращения такой ситуации необходим специальный механизм, который можно построить, например, на основе семафоров.
Изложенную схему планирования иллюстрирует Рис. 1, где а) – исходное состояние системы; б) – состояние после завершения работы процесса и освобождения процессора (из очереди процессов с высшим приоритетом выбран первый процесс и назначен на выполнение процессору ).
Рис. 1.  К планированию независимых процессов. а)Исходное состояние. б)Состояние после освобождения процессора P4.
Рассмотренная схема планирования позволяет, во-первых, обеспечить процессорам режим разделения времени и, во-вторых, позволяет автоматически балансировать загрузку процессоров системы, т.е. исключает ситуацию, когда один из процессоров простаивает, в то время как другие процессоры перегружены.
Недостатком данной схемы планирования является возможная конкуренция процессов при доступе к указанным очередям.
Кроме того, такая схема планирования не учитывает следующее обстоятельство. Если некоторый процесс достаточно долгое время работал на процессоре , то кэш-память этого процессора содержит, как правило, много данных процесса . Поэтому после прерывания по той или иной причине процесса , его целесообразно было бы запустить опять на процессоре (поскольку его кэш-память может еще содержать необходимую процессу информацию). Некоторые операционные системы мультипроцессоров выполняют планирование с учетом данного обстоятельства. Однако при этом усложняется решение проблемы балансировки загрузки процессоров.
Производительность мультипроцессора может уменьшить также переключение на другой процесс в тот момент, когда текущий процесс выполняет критическую секцию, а другие процессы ожидают входа в критическую секцию. Поскольку критические секции малы, вероятность такого прерывания невысока. Однако если это прерывание имеет место, потери могут быть существенны. Для борьбы с деградацией производительности мультипроцессора, обусловленной этой причиной, ОС может запрещать выбор активных процессов, ожидающих входа в критическую секцию, до тех пор, пока вход в секцию не освободится.
Рассмотрим в качестве примера механизм планирования независимых процессов в ОС UNIX. Готовые к выполнению процессы выстраиваются в очередь к процессору в порядке уменьшения своих приоритетов. Если некоторый процесс отработал свой квант процессорного времени, но при этом остался готовым к выполнению, то он становится в очередь к процессору впереди любого процесса с более низким приоритетом, но вслед за любым процессом, обладающим тем же приоритетом. Если некоторый процесс становится активным, то он также ставится в очередь вслед за процессом, обладающим тем же приоритетом.
В ОС UNIX используются динамические и статические приоритеты. Каждый процесс при своем образовании получает от ОС некоторый статический приоритет. Все процессы с динамическим приоритетом не ниже некоторого порогового уровня участвуют в конкуренции за процессор (по схеме, описанной выше). Каждый раз, когда процесс успешно отрабатывает свой квант процессорного времени, его динамический приоритет уменьшается на величину, которая зависит от его статического приоритета. Если значение динамического приоритета процесса достигает некоторого нижнего предела, он перемещается во внешнюю память (свопинг) и больше не конкурирует за процессор.
Приоритет процесса, который перемещен во внешнюю память, постепенно повышается, давая, в конце концов, этому процессу возможность вновь вернуться в основную память и принять участие в конкуренции за процессор (когда его приоритет превысит некоторый пороговый уровень).
Планирование зависимых процессов.
Простейший алгоритм планирования связанных процессов состоит в статическом разбиении множества процессоров на несколько подмножеств и назначении каждому из них своей группы связанных процессов. Положим, например, что имеется четыре группы связанных процессов , , , . Тогда в соответствии с рассматриваемым алгоритмом планирования процессы должны быть назначены первому подмножеству процессоров , процессы - второму подмножеству процессоров , и т.д. (см. рис. 2).
Рис. 2.  К планированию зависимых процессов.
Если в системе появляется новая группа связанных процессов, то операционная система проверяет, имеются ли свободные процессоры по числу процессов в этой группе. Если имеется достаточное количество свободных процессоров, то каждому процессу выделяется свой процессор и все процессы запускаются. В противном случае – ни один из процессов этой группы не запускается до появления достаточного количества свободных процессоров. Если один из выполняемых процессов по той или иной причине блокируется, соответствующий процессор не освобождается. Процессор освобождается и поступает в пул свободных процессоров только после завершения назначенного ему процесса.
Если в системе имеется несколько групп готовых к выполнению процессов, то выбирается первая из этих групп, для которой достаточно свободных процессоров.
Достоинством простейшего алгоритма планирования состоит в снижении накладных расходов на переключение контекста. Недостаток состоит в потерях времени процессоров на блокировки.
Развитием простейшего алгоритма планирования связанных процессов является алгоритм совместного планирования связанных процессов. В этом случае группы связанных процессов также планируются как одно целое, однако выполняются в режиме разделения времени процессоров. В начале каждого кванта времени производится перепланирование всех процессов.