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

0

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

Программный код  планировщика  операционной  системы Linux  содержится в файле   kernel/sched.c .  Алгоритм планирования  и  соответствующий программный код  были  существенно переработаны в те  времена,  когда  началась разработка ядер серии  2.5.  Следовательно, программный  код  планировщика является полностью новым  и  отличается от планировщиков предыдущих версий. Новый планировщик разрабатывался для  того, чтобы  удовлетворять указанным  ниже  требованиям.

• Должен быть  реализован полноценный О(1) -планировщик. Любой  алгоритм, использованный в новом планировщике, должен  завершать свою  работу  за постоянный период времени, независимо от числа  выполняющихся  процессов и других   обстоятельств.

• Должна обеспечиваться хорошая  масштабируемость для  SMP-систем.  Каждый процессор должен   иметь  свои  индивидуальные элементы  блокировок  и  свою индивидуальную очередь  выполнения.

• Должна быть  реализована улучшенная SMP-привязка  (SMP affinity).  Задания, для  выполнения на  каждом процессоре многопроцессорной  системы,  должны быть  распределены правильным образом, и, по возможности,  выполнение этих задач  должно продолжаться на  одном   и  том  же  процессоре.  Осуществлять миграцию заданий с одного  процессора на другой  необходимо  только  для  уменьшения дисбаланса между  размерами очередей выполнения  всех  процессоров.

• Должна быть  обеспечена хорошая производительность для  интерактивных приложений. Даже  при  значительной  загрузке система должна  иметь  хорошую  реакцию и немедленно планировать выполнение интерактивных задач.

• Должна быть  обеспечена равнодоступность ресурсов (fairness).   Ни  один  процесс   не  должен   ощущать  нехватку   квантов  времени  за  допустимый  период. Кроме того, ни  один  процесс не должен  получить недопустимо  большое  значение  кванта времени.

•  Должна   быть  обеспечена   оптимизация  для  наиболее   распространенного   случая,  когда  число  готовых  к  выполнению процессов   равно   1-2,  но  в то же  время должно   обеспечиваться  хорошее  масштабирование  и  на  случай   большого  числа процессоров,  на  которых   выполняется  большое   число   процессов.

Новый   планировщик  позволяет   удовлетворить   всем   этим  требованиям.

Очереди выполнения

Основная структура данных планировщика — это  очередь выполнения (runqueue). Очередь   выполнения  определена   в  файле    kernel/sched.c3      в   виде  структуры struc t      runqueue .  Она  представляет   собой  список   готовых  к  выполнению  процессов  для  данного   процессора.

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

struct runqueue {

spinlock_t lock; /* спин-блокировка для защиты этой очереди выполнения*/ unsigned long nr_rinning; /* количество задач, готовых к выполнению */ unsigned long nr_switches;    /* количество переключений контекста */ unsigned long expired timestamp; /* время последнего обмена массивами*/ unsigned long nr_uninterruptible; /* количество заданий в состоянии

непрерываемого ожидания */

unsigned long long timestamp last tick; /* последняя метка времени планировщика */

struct task_struct *curr;  /* текущее задание, выполняемое на данном

процессоре */

struct task_struct *idle;  /* холостая задача данного процессора */

struct mm_struct *prev_mm; /* поле mm_struct последнего выполняемого задания */

struct prio_array "active; /* указатель на активный массив приоритетов*/

struct prio_array ‘expired; /* указатель на истекший массив приоритетов*/

struct prio_array arrays[2]; /* массивы приоритетов */

struct task_3truct *migration_thread; /* миграционный поток для данного процессора */

struct list_head migration_queue;    /* миграционная очередь для

данного процессора */

atomic_t nr_iowait; /* количество заданий, ожидающих на ввод-вывод */

};

3 Может        возникнуть   вопрос:   почему  используется   фай л   kernel/sched.с,   а  не  заголовочный   файл include/linux/sched.h ?       Потому  что желательно  абстрагироваться  от реализации  кода планировщика  и  обеспечил ,  доступность  для  остального  кода  ядра  только  лишь  некоторых  интерфейсов.

Поскольку очередь  выполнения — это основная структура  данных  планировщика, существует  группа  макросов, которые используются для доступа  к определенным очередям выполнения. Макрос cpu_rq  (processor )  возвращает указатель  на очередь выполнения, связанную с процессором, имеющим заданный номер.  Аналогично макрос  this_r q ()  возвращает указатель  на очередь, связанную с текущим процессором. И наконец, макрос  task_rq(task ) возвращает указатель  на очередь, в которой находится соответствующее задание.

Перед тем как производить манипуляции с очередью  выполнения, ее необходимо заблокировать (блокировки подробно рассматриваются в главе 8, "Введение  в синхронизацию выполнения кода ядра"). Так как очередь выполнения уникальна для каждого процессора, процессору редко  необходимо блокировать очередь  выполнения другого процессора (однако, как будет показано далее, такое все же иногда  случается). Блокировка очереди  выполнения  позволяет запретить внесение любых изменений в структуру данных  очереди, пока  процессор, удерживающий блокировку, выполняет операции чтения  или  записи полей  этой  структуры.  Наиболее часто  встречается ситуация, когда необходимо заблокировать очередь  выполнения, в которой выполняется текущее  задание. В этом  случае  используются функции tapk_rq_loc k ()  и task_rq_unlock() , как показано ниже.

struct runqueue *rq;

unsigned long flags;

rq = task_rq_lock(task, &flags);

/* здесь можно производить манипуляции с очередью выполнения */

task_rq_unlock (rq, &flags);

Альтернативными функциями  выступают функция this_rq_loc k (), которая позволяет  заблокировать текущую  очередь  выполнения, и функция rq     unlock (struc t runqueue   *rq) , позволяющая разблокировать указанную в аргументе  очередь.

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

/* для того, чтобы заблокировать … */

if (rql < rq2) ( spin_lock(s,rql->lock] ; spin_lock(Srq2->lock);

} else (

spin_lock(Srq2->lock)  ;

spin_lock(&rql->lock)

}

/* здесь можно манипулировать обеими очередями … */

/• для того, чтобы разблокировать … */ spin_unlock(brql->lock); spin_unlock(&rq2->lock);

С помощью функций double_rq_lock () и double_rq_unlock()указанные шаги можно выполнить автоматически. При этом получаем следующее.

double_rq_lock(rql, rq2);

/* здесь можно манипулировать обеими очередями …*/

double_rq_unlock(rql, rq2) ;

Рассмотрим небольшой пример, который показывает,  почему важен порядок захвата  блокировок.  Вопрос взаимных блокировок обсуждается в  главах 8,  "Введение в синхронизацию выполнения кода  ядра"  и 9, "Средства синхронизации в ядре". Эта проблема касается не  только очередей выполнения: вложенные блокировки должны всегда захватываться в одном и  том  же  порядке. Спин-блокировки  используются для предотвращения манипуляций с очередями выполнения несколькими задачами одновременно. Принцип работы этих  блокировок аналогичен ключу, с помощью которого  открывают дверь. Первое задание, которое подошло к двери, захватывает ключ, входит в дверь и  закрывает ее  с другой стороны.  Если другое   задание  подходит к двери и  определяет, что  дверь закрыта (потому что  за  дверью находится первое задание), то  оно  должно остановиться и  подождать, пока первое задание на  выйдет и не  возвратит ключ. Ожидание называется  спиннингом (вращением, spinning), так как  на самом деле  задание постоянно выполняет цикл, периодически проверяя, не  возвращен ли  ключ. Теперь рассмотрим, что  будет, если одно задание пытается сначала заблокировать первую очередь выполнения,  а затем вторую, в то время как  другое  задание  пытается сначала заблокировать вторую очередь, а затем — первую. Допустим, что  первое задание успешно захватило блокировку первой очереди, в то  время как второе задание захватило блокировку второй очереди. После этого первое задание пытается заблокировать вторую очередь, а  второе задание — первую. Ни  одно из заданий никогда не  добьется успеха, так  как  другое   задание уже  захватило эту  блокировку. Оба  задания будут  ожидать друг  друга  вечно. Так  же  как   в тупике дороги создается блокировка движения, так  и  неправильный  порядок захвата блокировок приводит к тому, что  задания начинают ожидать друг друга  вечно, и тоже  возникает тупиковая ситуация, которая еще  называется взаимоблокировкой. Если оба  задания захватывают блокировки  в  одном и  том  же  порядке, то  рассмотренной ситуации произойти не  может. В главах 8 и 9 представлено полное описание блокировок.

Массивы приоритетов

Каждая очередь выполнения содержит два массива приоритетов (priority arrays): актинный и  истекший. Массивы  приоритетов определены в  файле  kernel/sched. c в виде  описания struc t    prio_array .  Массивы приоритетов — это  структуры данных, которые обеспечивают 0(1)-планирование. Каждый массив приоритетов содержит  для  каждого значения приоритета одну  очередь процессов,  готовых к  выполнению. Массив приоритетов также содержит битовую маску приоритетов (priority bitmap), используемую для  эффективного поиска готового к выполнению задания, у которого значение приоритета является наибольшим в системе.

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

По теме:

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