Работа планировщика заключается в разделении CPU между несколькими процессами. Реализация планировщика размещена в файле kernel/sched.c. Соответствующий заголовочный файл include/linux/sched.h подключается (прямо или косвенно) фактически к каждому файлу с исходным текстом ядра.
Поля task_struct, которые используются планировщиком:
p->need_resched: это поле устанавливается если schedule() должна быть вызвана при 'первом удобном случае'.
p->counter: число тактов системных часов, оставшихся до окончания выделенного кванта времени, уменьшается по таймеру. Когда значение этого поля становится меньше либо равно нулю, то в него записывается ноль и взводится флаг p->need_resched. Иногда это поле называют "динамическим приоритетом" ('dynamic priority') процесса потому как он может меняться..
p->priority: статический приоритет процесса, может изменяться только через системные вызовы, такие как nice(2), POSIX.1b sched_setparam(2) или 4.4BSD/SVR4 setpriority(2).
p->rt_priority: приоритет реального времени (realtime priority)
p->policy: политика планирования, определяет класс планирования задачи. Класс планирования может быть изменен системным вызовом sched_setscheduler(2). Допустимые значения: SCHED_OTHER (традиционные процессы UNIX), SCHED_FIFO (процессы реального времени POSIX.1b FIFO) и SCHED_RR (процессы реального времени POSIX round-robin). Допускается комбинирование любого из этих значений с SCHED_YIELD по ИЛИ (OR) чтобы показать, что процесс решил уступить CPU, например при вызове sched_yield(2). Процесс реального времени FIFO будет работать до тех пор, пока не:
a) запросит выполнение блоковой операции ввода/вывода,
b) явно не отдаст CPU или
c) будет вытеснен другим процессом реального времени с более высоким приоритетом (значение в p->rt_priority).
SCHED_RR то же самое, что и SCHED_FIFO, за исключением того, что по истечении выделенного кванта времени, процесс помещается в конец очереди runqueue.
Алгоритм планировщика достаточно прост, несмотря на очевидную сложность функции schedule(). Сложность функции объясняется реализацией трех алгоритмов планирования, а так же из-за учета особенностей SMP (мультипроцессорной обработки).
Бесполезные, на первый взгляд, операторы goto в коде schedule() используются с целью генерации более оптимального (для i386) кода. Планировщик для ядра 2.4 (как и в более ранних версиях) был полностью переписан, поэтому дальнейшее обсуждение не относится к ядрам версии 2.2 и ниже.
Разберем код функции подробнее:
Если current->active_mm == NULL, то значит что-то не так. Любой процесс, даже поток ядра (для которого current->mm == NULL), всегда должен иметь p->active_mm.
Если что либо планируется сделать с очередью tq_scheduler, то делать это надо здесь. Механизм очередей позволяет отложить выполнение отдельных функций на некоторое время. Этой теме будет уделено больше внимания несколько позднее.
Локальным переменным prev и this_cpu присваиваются значения current (текущая задача) и CPU текущей задачи соответственно.
Проверяется контекст вызова schedule(). Если функция вызвана из обработчика прерываний (по ошибке), то ядро "впадает в панику".
Освобождается глобальная блокировка ядра.
Если надлежить выполнить что-то, работающее через "мягкие" прерывания, то сделать это надо сейчас.
Устанавливается указатель struct schedule_data *sched_data на область данных планирования для заданного CPU, которая содержит значение TSC для last_schedule и указатель на последнюю запланированную задачу (task_struct) (TODO: sched_data используется только для мультипроцессорных систем, зачем тогда init_idle() инициализирует ее и для однопроцессорной системы?).
"Запирается" runqueue_lock. Обратите внимание на вызов spin_lock_irq(), который используется ввиду того, что в schedule() прерывания всегда разрешены. Поэтому, при "отпирании" runqueue_lock, достаточно будет вновь разрешить их, вместо сохранения/восстановления регистра флагов (вариант spin_lock_irqsave/restore).
task state machine: если задача находится в состоянии TASK_RUNNING, то она остается в этом состоянии; если задача находится в состоянии TASK_INTERRUPTIBLE и для нее поступили сигналы, то она переводится в состояние TASK_RUNNING. В любом другом случае задача удаляется из очереди runqueue.
Указатель next ( лучший кандидат) устанавливается на фоновую задачу для данного CPU. Признак goodness для этого кандидата устанавливается в очень малое значение (-1000), в надежде на то, что найдется более лучший претендент.
если задача prev (текущая) находится в состоянии TASK_RUNNING, то значение goodness принимает значение goodness задачи и она (задача) помечается как кандидат, лучший чем задача idle.
Далее начинается проверка очереди runqueue, признак goodness каждого процесса сравнивается с текущим. Конкуренцию выигрывает процесс с более высоким goodness. Необходимо уточнить концепцию "может быть намечена на этом CPU": на однопроцессорной системе любой процесс из очереди runqueue может быть запланирован; на многопроцессорной системе, только тот, который не запущен на другом CPU, может быть запланирован для этого процессора. Признак goodness определяется функцией goodness(), которая для процессов реального времени возвращает их goodness очень высоким (1000 + p->rt_priority), значение больше 1000 гарантирует, что не найдется такого процесса SCHED_OTHER, который выиграл бы конкуренцию; таким образом конкуренция идет только между процессами реального времени, которую выигрывает процесс с более высоким p->rt_priority. Функция goodness() возвращает 0 для процессов, у которых истек выделенный квант времени (p->counter). Для процессов не реального времени значение goodness устанавливается равным p->counter - таким способом понижается вероятность захвата процессора задачей, которая уже получала его на некоторое время, т.е. интерактивные процессы получают преимущество перед продолжительными вычислительными процессами. Далее, реализуя принцип "cpu affinity", вес задачи, исполнявшейся на этом же процессоре, увеличивается на константу PROC_CHANGE_PENALTY, что дает небольшое преимущество перед другими процессами. Дополнительное преимущество придается и процессам, у которых mm указывает на текущий active_mm или не имееющим пользовательского адресного пространства, т.е. потокам ядра.
если текущее значение goodness получается равным 0, то производится просмотр всего списка процессов (не только runqueue!) и производится перерасчет динамических приоритетов следуя простому алгоритму:
Следует отметить, что перед выполнением цикла перерасчета сбрасывается runqueue_lock, поскольку цикл может занять довольно продолжительное время, в течение которого schedule() может быть вызвана другим процессором, в результате чего может быть найдена задача с goodness достаточным для запуска на этом процессоре. По общему признанию это выглядит несколько непоследовательным, потому что в то время как один процессор отбирает задачи с наивысшим goodness, другой вынужден производить перерасчет динамических приоритетов.
В этой точке next указывает на задачу, которая должна быть запланирована, далее в next->has_cpu заносится 1 и в next->processor заносится значение this_cpu. Блокировка runqueue_lock
может быть снята.
Если происходит возврат к предыдущей задаче (next == prev) то просто повторно устанавливается блокировка ядра и производится возврат, т.е. минуя аппаратный уровень (регистры, стек и т.п.) и настройки VM (переключение каталога страницы, пересчет active_mm и т.п.).
Макрос switch_to() является платформо-зависимым. На i386 это имеет отношение к:
a) обработке FPU (Floating Point Unit - арифметический сопроцессор)
