Linux Kernel (Ядро линукса) (часть 1)

Алгоритм планирования

Алгоритм планирования, применявшийся в ранних версиях Linux, был довольно прост и прямолинеен. При каждом переключении процессов ядро просматривало список выполняемых процессов, вычисляло их приоритеты и выбирало "наилучший" процесс. Основной недостаток такого алгоритма заключается в том, что время, потраченное на выбор процесса, зависит от количества выполняемых процессов. Алгоритм оказывается слишком дорогим (то есть расходует слишком много времени) в системах типа high-end, где выполняются тысячи процессов.

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

Планировщику всегда удается найти процесс, который следует выполнить. Всегда существует, по меньшей мере, один выполняемый процесс — процесс swapper, который имеет идентификатор, равный 0, и выполняется лишь тогда, когда процессор не может выполнить другие процессы. каждый процессор в многопроцессорной системе имеет свой процесс swapper с идентификатором, равным нулю.

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

- sched fifo— процесс, работающий в реальном времени по принципу "первым вошел — первым вышел". Когда планировщик предоставляет процессор такому процессу, он оставляет дескриптор процесса на том же месте в очереди на выполнение. При отсутствии других выполняемых процессов реального времени с более высоким приоритетом данный процесс продолжает пользоваться процессором, сколько ему нужно, даже если имеются выполняемые процессы реального времени с тем же приоритетом;
- sched rr — процесс, работающий в реальном времени по круговому принципу. Когда планировщик предоставляет процессор такому процессу, он переносит дескриптор процесса в конец очереди на выполнение. Эта политика обеспечивает справедливое распределение времени процессора между всеми процессами реального времени, принадлежащими к классу sched rr и имеющими одинаковый приоритет;
- sched normal — обычный процесс, работающий в режиме разделения времени.

Алгоритм планирования ведет себя по-разному в зависимости от того, является ли процесс обычным или процессом реального времени.