Главная » Ядро Linux » Алгоритм планирования – ЧАСТЬ 3

0

Функция effective_pri o ()   возвращает значение динамического приоритета задачи. Эта функция исходит из значения параметра пicе для данной  задачи  и вычисляет для этого значения надбавку  или  штраф  в диапазоне от -5 до 5, в зависимости от интерактивности задачи.  Например, задание  с высокой интерактивностью, которое имеет  значение параметра nice, равное  10, может  иметь  динамический приоритет, равный  5. И наоборот, программа со значением параметра nice, равным  10, которая достаточно  активно использует процессор,  может  иметь  динамический приоритет, равный   12. Задачи,  которые  обладают  умеренной интерактивностью,  не  получают ни надбавки, ни  штрафа, и их динамический приоритет совпадает  со значением параметраnice.

Конечно, планировщик по волшебству  не может  определить, какой  процесс  является  интерактивным. Для определения необходима некоторая эвристика, которая отражает,  является ли  процесс  ограниченным  скоростью ввода-вывода или  скоростью процессора. Наиболее выразительный показатель — сколько  времени задача находится  в приостановленном состоянии (sleep).  Если  задача проводит  большую  часть времени в приостановленном состоянии, то она ограничена вводом-выводом. Если задача больше  времени находится  в состоянии готовности к выполнению, чем в при-

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

Для  реализации такой  эвристики в ядре Linux предусмотрен изменяемый показатель  того, как  соотносится время, которое  процесс проводит в приостановленном  состоянии, со временем, которое  процесс проводит в состоянии готовности к  выполнению. Значение этого  показателя хранится в поле   sleep_av g  структуры task_struct . Диапазон значений этого  показателя лежит  от нуля  до значения MAX_SLEEP_AVG, которое  по умолчанию равно  10 мс.  Когда  задача  становится готовой к выполнению после  приостановленного состояния, значение поля  sleep_avg увеличивается на значение времени, которое  процесс провел  в приостановленном состоянии, пока  значение sleep_av g не  достигнет MAX_SLEEP_AVG. Когда  задача выполняется, то в течение  каждого  импульса таймера  (timer  tick)  значение этой  переменной уменьшается, пока оно не достигнет значения 0.

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

Расчет  значения кванта  времени, наоборот, более  прост, так как  значение динамического приоритета уже базируется на значении параметра nice и на интерактивности (эти показатели планировщик учитывает  как  наиболее важные). Поэтому продолжительность кванта  времени может  быть  просто  выражена через  значение динамического приоритета. Когда  создается новый  процесс, порожденный и родительский процессы делят  пополам оставшуюся часть  кванта  времени родительского процесса. Такой  подход  обеспечивает равнодоступность ресурсов  и предотвращает возможность получения бесконечного значения кванта  времени путем  постоянного создания порожденных процессов. Однако после  того, как квант  времени задачи  иссякает, это значение пересчитывается на основании динамического приоритета задачи.  Функция task_timeslic e ()  возвращает новое  значение кванта  времени для данного задания. Расчет  просто  сводится к масштабированию значения приоритета в диапазон значений квантов времени. Чем  больше  значение приоритета задачи, тем  большей продолжительности квант  времени получит  задание  в текущем  цикле выполнения. Максимальное значение кванта  времени равно  MAX_TIMESLICE, которое по умолчанию равно  200 мс. Даже  задания с самым  низким приоритетом получают квант  времени продолжительностью MIN_TIMESLICE, что соответствует 10 мс.

Задачи с приоритетом, используемым по умолчанию (значение параметра nice, равно О и отсутствует надбавка и штраф за интерактивность),  получают квант  времени продолжительностью 100 мс, как  показано в табл. 4.1.

Таблица 4.1 . Продолжительности квантов времени планировщика

Тип задания

Значение параметра nice

Продолжительность кванта времени

Вновь созданное                     То же, что и у родительского         Половина от родительского процесса                                      процесса

Минимальный приоритет          +19                                              5 мс (MIN_TIMESUCE) Приоритет по умолчанию          0                 100                 мс                 (DEF_TIMESLICE) Максимальный приоритет         -20                                               800 мс (MAX_TIMESLICE)

Для   интерактивных задач   планировщик  оказывает дополнительную услугу:   если задание достаточно интерактивно,  то  при   исчерпании  своего кванта времени оно будет  помещено не  в истекший массив приоритетов, а обратно в  активный массив приоритетов.  Следует вспомнить,  что  пересчет значений квантон времени производится путем перестановки активного и  истекшего массивов приоритетов: активный массив становится истекшим,  а истекший— активным. Такая процедура обеспечивает  пересчет значений квантов времени,  который масштабируется по  времени как O(1) . С  другой стороны,  это  может привести к  тому, что  интерактивное задание станет готовым к  выполнению, но  не  получит возможности выполняться,  так  как оно  "застряло" в истекшем массиве. Помещение интерактивных заданий снова в активный массив позволяет избежать такой проблемы. Следует заметить, что  это  задание  не  будет  выполняться сразу  же, а будет  запланировано на  выполнение по  кругу вместе с  другими заданиями,  которые имеют такой же  приоритет. Данную логику реализует функция  scheduler_tic k  (), которая вызывается обработчиком прерываний таймера (обсуждается в главе  10, "Таймеры и  управление временем"), как  показано ниже.

struct task_struct *task = current;

struct runqueue *rq = this_rq();

if (!–task->time_slice) {

if (!TASK_INTERACTIVE(task) || EXPIRED_STARVING(rq))

enqueue_task(task, rq->expired);

else

}

enqueue_task(task, rq->active);

Показанный код  уменьшает значение кванта времени процесса и  проверяет, не стало ли  это  значение равным нулю. Если стало, то  задание является истекшим и его  необходимо поместить в один из  массивов. Для  этого код  вначале проверяет интерактивность задания с  помощью макроса ТАSK_INTERACTIVE () .  Этот  макрос на основании  значения параметра nice рассчитывает, является ли  задание "достаточно интерактивным". Чем  меньше значение nice (чем  выше приоритет), тем  менее интерактивным должно быть  задание. Задание со  значением параметра nice,  равным 19, никогда не  может быть  достаточно интерактивным для  помещения обратно в актив-

ный  массив.  Наоборот, задание со значением nice,  равным -20, должно  очень  сильно использовать процессор,  чтобы  его не  поместили в активный массив.   Задача  со  значением nice,  используемым по умолчанию, т.е.  равным нулю, должна  быть  достаточно интерактивной,  чтобы  быть  помещенной обратно в активный массив, но  это  также отрабатывается достаточно  четко.   Следующий макрос,  EXPIRED_STARVING () , проверяет, нет ли  в истекшем массиве  процессов, особенно нуждающихся в выполнении (startving),  когда  массивы не  переключались в  течение   достаточно долгого   времени. Если  массивы давно  не  переключались, то  обратное помещение задачи  в активный массив  еще  больше  задержит   переключение,  чт о приведет к тому,  что  задачи  в истекшем   массиве   еще  больше  будут нуждаться  в  выполнении.  Если  это  не  так, то  задача  может  быть  помещена обратно в  активный массив.   В других  случаях  задача  помещается в истекший массив, что  встречается наиболее часто.

Переход в приостановленное состояние и возврат к выполнению

Приостановленное  состояние задачи   (состояние  ожидания,  заблокированное состояние, sleeping,  blocked)  представляет собой  специальное состояние задачи, в котором  задание не  выполняется.  Это  является очень  важным, так  как  в противном случае  планировщик выбирал бы  на  выполнение задания,  которые не  "хотят"  выполняться, или, хуже того, состояние ожидания должно  было  бы  быть  реализовано в  виде  цикла,  занимающего время  процессора. Задачи  могут  переходить  в  приостановленное состояние по  нескольким причинам,  но  в любом  случае—  в ожидании наступления  некоторого  события.  Событием  может   быть  ожидание  наступления некоторого момента времени,  ожидание  следующей порции  данных  при  файловом вводе-ныводе или  другое  событие  в  аппаратном  обеспечении.  Задача  также   может переходить  в  приостановленное  состояние  непроизвольным  образом,  когда  она пытается захватить   семафор  в  режиме   ядра   (эта  ситуация  рассмотрена  в  главе  9, "Средства  синхронизации в ядре").  Обычная причина перехода  в  приостановленное состояние — это  выполнение операций файлового ввода-вывода,  например задание вызывает функцию  rea d ()   для  файла,  который  необходимо считать   с диска.   Еще один  пример—  задача  может  ожидать  на  ввод  данных  с  клавиатуры. В любом  случае ядро  ведет  себя  одинаково:  задача  помечает  себя   как  находящуюся  в  приостановленном состоянии,  помещает себя  в очередь  ожидания (wail queue), удаляет  себя  из очереди   выполнения и  вызывает функцию  schedule d  для  выбора  нового  процесса на  выполнение.  Возврат   к  выполнению  (wake  up)  происходит в обратном порядке: задача  помечает себя  как  готовую  к выполнению, удаляет  себя  из очереди  ожидания и  помепгает себя  в очередь  выполнения.

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

Приостановленное  состояние  обрабатывается с  помощью очередей ожидания

(wait  queue).   Очередь   ожидания— это  просто  список процессов,  которые ожидают

наступления  некоторого  события.  Очереди  ожидания в ядре  представляются с  помощью  типа  данных  wait_queue_head_t .  Они  могут  быть  созданы статически с помощью  макроса DECLARE_WAIT_QUEUE_HEAD  ()   или  выделены динамически  с  последующей  инициализацией с  помощью  функции  init_waitqueue_hea d () .  Процессы помещают себя  в  очередь  ожидания и  устанавливают себя  в  приостановленное состояние. Когда  происходит событие, связанное с очередью  ожидания, процессы, находящиеся в этой  очереди,  возвращаются к  выполнению.  Важно  реализовать переход в приостановленное состояние и  возврат  к  выполнению  правильно,  так  чтобы избежать конкуренции  за  ресурсы   (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  () .

• Добавить себя  в  очередь  ожидания с помощью функции  ad d   wait_queu e ()  .

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

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

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

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

из цикла. Если  нет, то снова  вызывается функция schedul e ()  и повторяется проверка условия.

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

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

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

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

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

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

Функция     add_wait_que-je() помещает задачу в очередь ожидания, устанавливает состояние задачи TASK_INTERRUPTIBLE и вызывает функциюschedule() .Функцияscheduledвызываетфункцию deactivate_task() , которая удаляет задачу из очереди выполнения.

Задача готова к выполнению                              Задача не готова к выполнению

Получен сигнал,

задача устанавливается в состояние

TASK_RUNNING и выполняет обработчик сигнала

Событие, на которое ожидала задача, произошло, и функция try_to_wake_up()   устанавливает задачу в состояние TASK_RUNNING, вызывает функцию   activate_task()   и функцию schedule() .

Функция  remove_wait_quaue () удаляет задачу из очереди ожидания.

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

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

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

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

Процесс 1

Процесс 2

ПроцессЗ Процесс 4

Процесс 5

Процесс 6

Процесс 20

  load_balancer()  

Проталкивание процесса из одной очереди в другую для уменьшения дисбаланса

Процесс 1

Процесс 2

Процесс 3

Процесс 4

Процесс 5

Процесс 6

Процесс 15

Очередь выполнения процессора 1,всего

20 процессов

Очередь выполнения процессора 2, всего

15процессов

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

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

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

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

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

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

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

Далее показана функция  load_balance (), немного упрощенная,  но содержащая все цажные детали.

static int load_balance(int this_cpu, runqueue_t *this_rq,

struct sched_doraain *sd, enum idle_type idle)

{

struct sched_group *group; runqueue_t *busiest; unsigned long imbalance; int nr_moved;

spin_lock(&this_rq->lock);

group = find_busiest_group(sd,  this_cpu, &imbalance, idle);

if (!group)

goto out_balanced;

busiest = find_busiest_queue(group) ;

if (!busiest)

goto out_balanced;

nr_moved = 0;

if (busiest->nr_running > 1) {

double_lock_balance(this_rq, busiest);

nr_moved = move_tasks(this_rq, this_cpu, busiest, imbalance, sd, idle);

spin_unlock(&busiest->lock);

}

spin_unlock(&this rq->lock);

if (!nr_moved) {

sd->nr_balance_failed++;

if (unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2))  {

int wake = 0;

spin_lock(abusiest->lock);

if (!busiest->active_balance) { busiest->active_balance = 1; busiest->push_cpu = this_cpu; wake = 1;

)

} else

}

spin_unlock(&busiest->lock);

if (wake)

wake_up_process(busiest->migration_thread);

sd->nr_balance_failed = sd->cache_nice_tries;

sd->nr_balance_failed = 0;

sd->balance_interval = sd->min_interval;

return nr_moved;

out_balanced:

spin_unlock(&this_rq->lock);

if (sd->balance_interval < sd->max_interval)

sd->balance_interval *= 2;

return 0;

}

Источник: Лав,  Роберт. Разработка ядра  Linux, 2-е  издание. : Пер.  с англ.  — М.  : ООО  «И.Д.  Вильяме» 2006. — 448 с. : ил. — Парал. тит. англ.

По теме:

  • Комментарии