Разработка ядра Linux - Роберт Лав

Приостановленное состояние обрабатывается с помощью очередей ожидания (wait queue). Очередь ожидания — это просто список процессов, которые ожидают наступления некоторого события. Очереди ожидания в ядре представляются с помощью типа данных wait_queue_head_t. Они могут быть созданы статически с помощью макроса DECLARE_WAIT_QUEUE_HEAD() или выделены динамически с последующей инициализацией с помощью функции init_waitqueue_head(). Процессы помещают себя в очередь ожидания и устанавливают себя в приостановленное состояние. Когда происходит событие, связанное с очередью ожидания, процессы, находящиеся в этой очереди, возвращаются к выполнению. Важно реализовать переход в приостановленное состояние и возврат к выполнению правильно, так чтобы избежать конкуренции за ресурсы (race).

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

/* пусть q — это очередь ожидания (созданная в другом месте) ,

где мы хотим находиться в приостановленном состоянии */

DECLARE_WAITQUEUE(wait, current);

add_wait_queue(q, &wait);

set_current_state(TASK_INTERRUPTIBLE); /* или TASK_UNINTERRUPTIBLE */

/* переменная condition характеризует наступление события,

   которого мы ожидаем */

while (!condition)

 schedule();

set_current_state(TASK_RUNNING);

remove_wait_queue(q, &wait);

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

• Создать элемент очереди ожидания с помощью макроса DECLARE_WAITQUEUE().

• Добавить себя в очередь ожидания с помощью функции add_wait_queue(). С помощью этой очереди ожидания процесс будет возвращен в состояние готовности к выполнению, когда условие, на выполнение которого ожидает процесс, будет выполнено. Конечно, для этого где-то в другом месте должен быть код, который вызывает функцию wake_up() для данной очереди, когда произойдет соответствующее событие.

• Изменить состояние процесса в значение TASK_INTERRUPTIBLE или TASK_UNINTERRUPTIBLE.

• Проверить, не выполнилось ли ожидаемое условие. Если выполнилось, то больше нет необходимости переходить в приостановленное состояние. Если нет, то вызвать функцию schedule().

• Когда задача становится готовой к выполнению, она снова проверяет выполнение ожидаемого условия. Если условие выполнено, то производится выход из цикла. Если нет, то снова вызывается функция schedule() и повторяется проверка условия.

• Когда условие выполнено, задача может установить свое состояние в значение TASK_RUNNING и удалить себя из очереди ожидания с помощью функции remove_wait_queue().

Если условие выполнится перед тем, как задача переходит в приостановленное состояние, то цикл прервется и задача не перейдет в приостановленное состояние по ошибке. Следует заметить, что во время выполнения тела цикла код ядра часто может выполнять и другие задачи. Например, перед выполнением функции schedule() может возникнуть необходимость освободить некоторые блокировки и захватить их снова после возврата из этой функции; если процессу был доставлен сигнал, то необходимо возвратить значение -ERESTARTSYS; может возникнуть необходимость отреагировать на некоторые другие события.

Возврат к выполнению (wake up) производится с помощью функции wake_up(), которая возвращает все задачи, ожидающие в данной очереди, в состояние готовности к выполнению. Вначале вызывается функция try_to_wake_up(), которая устанавливает поле состояния задачи в значение TASK_RUNNING, далее вызывается функция activate_task() для добавления задачи в очередь выполнения и устанавливается флаг need_resched в ненулевое значение, если приоритет задачи, которая возвращается к выполнению, больше приоритета текущей задачи. Код, который отвечает за наступление некоторого события, обычно вызывает функцию wake_up() после того, как это событие произошло. Например, после того как данные прочитаны с жесткого диска, подсистема VFS вызывает функцию wake_up() для очереди ожидания, которая содержит все процессы, ожидающие поступления данных.

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

Рис. 4.3. Переход в приостановленное состояние (sleeping) и возврат к выполнению (wake up)

Балансировка нагрузки

Как уже рассказывалось ранее, планировщик операционной системы Linux реализует отдельные очереди выполнения и блокировки для каждого процессора в симметричной многопроцессорной системе. Это означает, что каждый процессор поддерживает свой список процессов и выполняет алгоритм планирования только для заданий из этого списка. Система планирования, таким образом, является уникальной для каждого процессора. Тогда каким же образом планировщик обеспечивает какую-либо глобальную стратегию планирования для многопроцессорных систем? Что будет, если нарушится балансировка очередей выполнения, скажем, в очереди выполнения одного процессора будет находиться пять процессов, а в очереди другого — всего один? Решение этой проблемы выполняется системой балансировки нагрузки, которая работает с целью гарантировать, что все очереди выполнения будут сбалансированными. Система балансировки нагрузки сравнивает очередь выполнения текущего процессора с другими очередями выполнения в системе.

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

Система балансировки нагрузки реализована в файле kernel/sched.c в виде функции load_balance(). Эта функция вызывается в двух случаях. Она вызывается функцией schedule(), когда текущая очередь выполнения пуста. Она также вызывается по таймеру с периодом в 1 мс, когда система не загружена, и каждые 200 мс в другом случае. В однопроцессорной системе функция load_balance() не вызывается никогда, в действительности она даже не компилируется в исполняемый образ ядра, питому что в системе только одна очередь выполнения и никакой балансировки не нужно.

Функция балансировки нагрузки вызывается при заблокированной очереди выполнения текущего процессора, прерывания при этом также запрещены, чтобы защитить очередь выполнения от конкурирующего доступа. В том случае, когда функция load_balance() вызывается из функции schedule(), цель ее вызова вполне ясна, потому что текущая очередь выполнения пуста и нахождение процессов в других очередях с последующим их проталкиванием в текущую очередь позволяет получить преимущества. Когда система балансировки нагрузки активизируется посредством таймера, то ее задача может быть не так очевидна. В данном случае это необходимо для устранения любого дисбаланса между очередями выполнения, чтобы поддерживать их в почти одинаковом состоянии, как показано на рис. 4.4.

Рис. 4.4. Система балансировки нагрузки

Функция load_balance() и связанные с ней функции сравнительно большие и сложные, хотя шаги, которые они предпринимают, достаточно ясны.

• Функция load_balance() вызывает функцию find_busiest_queue() для определения наиболее загруженной очереди выполнения. Другими словами — очередь с наибольшим количеством процессов в ней. Если нет очереди выполнения, количество процессов в которой на 25% больше, чем в дайной очереди, то функция find_busiest_queue() возвращает значение NULL и происходит возврат из функции load_balance(). В другом случае возвращается указатель на самую загруженную очередь.

• Функция load_balance() принимает решение о том, из какого массива приоритетов самой загруженной очереди будут проталкиваться процессы. Истекший массив является более предпочтительным, так как содержащиеся в нем задачи не выполнялись достаточно долгое время и, скорее всего, не находятся в кэше процессора (т.е. не активны в кэше, not "cache hot"). Если истекший массив приоритетов пуст, то ничего не остается, как использовать активный массив.