От шедулера к планировщику
См. две другие статьи этой группы — Делаем многозадачность и Преемптивность: как отнять процессор.
Сразу просьба к строгим читателям. Если вы не поняли какой-либо термин из применённых — спросите, я подскажу, что я имел в виду. А если вам нравится другое написание или перевод этого термина — укажите его в комментарии. Я применяю те, которые нравятся мне.
Итак, в прошлых статьях описан механизм реализации многозадачности за вычетом планировщика, он же шедулер, он же скедулер, он же Васька меченый, сорри, заговариваюсь я с этими терминами…
Как я уже говорил, шедулер — это просто функция, которая отвечает на вопрос: какую нить и на сколько времени поставить на процессор.
Кстати, в SMP системе шедулер ничем не отличается от однопроцессорного. Вообще, чтобы проще понимать структуру взаимодействия сущностей на одном и нескольких процессорах, проще всего представить себе следующую модель: для каждого процессора есть нить «простоя» (которая работает, если вообще больше некому и просто останавливае процессор до прерывания), которая постоянно пытается «отдать» процессор (которым она как бы владеет) другим нитям, выбирая нить с помощью шедулера.
Говоря о шедулере нельзя не сказать о приоритетах.
Приоритет — свойство нити (или процесса) влияющее на конкуренцию этой нити с другими нитями за процессор.
Приоритет обычно описывается парой <класс приоритета, значение приоритета внутри класса>.
На сегодня сформировалась довольно чёткая схема реализации приоритетов. Приоритеты нитей делятся на три класса:
- Реальное время: нити такого класса всегда вытесняют с процессора нити других классов так быстро, как это возможно, и никогда не снимаются с процессора кроме как по наличию нити с более высоким приоритетом реального времени. То есть — такие нити сами должны решать, когда им больше не нужен процессор.
- Разделение времени: нити такого класса всегда вытесняют с процессора нити класса idle, между собой нити разделения времени конкурируют мягко. Две нити такого класса с разными значениями приоритета будут получать разный процент процессорного времени, но обязательно будут его получать, даже если значения приоритетов различаются предельным образом.
- Idle класс: нити такого класса получают процессор только если нет готовых к исполнению нитей других классов, «на сдачу». Лично я не вижу смысла в значении приоритета внутри класса idle. Хотя так тоже бывает.
Кстати. Говорят, Кернигана как-то спросили, что бы он сделал иначе, если бы писал Юникс заново. «Написал бы creat как create», — ответил мэтр. Я бы добавил к списку исправлений ещё мешок несуразностей, начиная с nice — понятие приоритета в Юниксе почему-то первёрнуто. Чем nice меньше, тем приоритет выше.
Мы в данной статье будем придерживаться более человеколюбивой шкалы: выше численное значение = больше процессора.
Кому-то, наверное, уже хочется заглянуть в код. Вот он:
Исходный текст Фантомовского шедулера.
И вот уже трещат морозы
И серебрятся средь полей…
(Читатель ждет уж рифмы розы;
На, вот возьми ее скорей!)
Кстати о Пушкине. Я категорически не претендую на какие-то сакральные знания в области написания планировщиков. Приведённый пример — сермяжная и банальная, хотя и вполне разумная реализация. Тем не менее, написание хорошего шедулера — очень серьёзная научная задача, про это диссертации пишут, и если речь заходит про настоящее реальное время — всё становится совсем серьёзно. В этой статье я затрагиваю только основы. В нашей стране есть специалисты, которые по этой теме знают примерно на три порядка больше, чем ваш покорный слуга.
За сим — продолжим.
Достаточно традиционная реализация шедулера предполагает наличие так называемой run queue — очереди нитей, готовых к исполнению. Вообще-то это не обязательно очередь, и если и очередь — то, обычно, множество очередей, относящихся к разным классам, а иногда и уровням приоритетов.
Конкретно в Фантоме это три очереди, согласно классам:
/** Idle prio threads */
static queue_head_t runq_idle = {0,0};
/** Normal prio threads */
static queue_head_t runq_norm = {0,0};
/** Realtime prio threads */
static queue_head_t runq_rt = {0,0};
В целом нить по отношению к процессору может находиться в трёх состояниях:
- Заблокирована. Не находится на процессоре, не может быть на него поставлена. Отсутствует в какой-либо run queue.
- Исполняется. Отсутствует в какой-либо run queue.
- Может исполняться. Присутствует в какой-либо run queue.
То есть, в run queue находятся нити, которые хотели бы попасть на процессор.
Отсюда работа планировщика сводится к тому, чтобы:
- Определиться с тем, нить какого класса приоритета сейчас будем запускать. Это просто — проверить, не пуста ли очередь realtime — если не пуста, то мы запускаем нить realtime, проверить очередь нормальных приоритетов — если не пуста, то запускаем нормальную нить. Иначе — запускаем idle нить. Если и таких нет, отмечаем, что процессор idle и уходим в нить «вечного» сна.
- Если определились с приоритетом — выбрать правильную нить для исполнения в данном приоритете.
- Назначить нити временной интервал для исполнения.
В целом реализация довольно банальна. Начнём с реального времени. Наивная реализация сортирует имеющиеся нити и запускает нить с максимальным численным значением приоритета. Временной интервал не назначается, так как для нитей с приоритетом реального времени он и не проверяется.
// Have some realtime?
if( !queue_empty(&runq_rt) )
{
int maxprio = -1;
phantom_thread_t *best = 0;
phantom_thread_t *it = 0;
queue_iterate(&runq_rt, it, phantom_thread_t *, runq_chain)
{
if( it->thread_flags & THREAD_FLAG_NOSCHEDULE ) continue;
if( ((int)it->priority) > maxprio )
{
maxprio = it->priority;
best = it;
}
}
if( best )
{
assert(t_is_runnable(best));
return best;
}
}
Очевидная доработка кода заключается в том, чтобы не сортировать все нити в шедулере, а вставлять нить в очередь в порядке убывания численного приоритета. Тогда планировщику достаточно просто вынуть из очереди первую нить и её запустить.
Теперь нити с приоритетом класса разделения времени — то есть, обычные нити, мягко конкурирующие за процессор.
Здесь надо отметить, что переменная ticks_left в структуре состояния нити определяет, сколько 10 мсек интервалов нить продержится на процессоре.
Сначала рассмотрим, что делает функция t_assign_time ():
it->ticks_left = NORM_TICKS + it->priority;
Она проверяет, что все нити истратили свои ticks_left, и если да — назначает им новые ticks_left — тем, у кого приоритет больше — даёт больше процессорного времени.
Что делает сам планировщик? Выбирает нить с максимальным приоритетом и с ненулевым остатком процессорного времени, её и запускает:
// Have normal one?
if( !queue_empty(&runq_norm) )
{
// If no normal thread has ticks left, reassign
// ticks and retry
do {
unsigned int maxprio = 0; // NB! not a negative number!
phantom_thread_t *best = 0;
phantom_thread_t *it = 0;
queue_iterate(&runq_norm, it, phantom_thread_t *, runq_chain)
{
if( it->thread_flags & THREAD_FLAG_NOSCHEDULE ) continue;
if( (it->priority > maxprio) && (it->ticks_left > 0) )
{
maxprio = it->priority;
best = it;
}
}
if( best )
{
return best;
}
} while(t_assign_time());
}
Когда все остатки у всех нитей кончились — просит t_assign_time () назначить нитям новые остатки.
Вообще-то, сортировка здесь относительно избыточна. Достаточно просто добавлять нити в конец очереди, а выбирать из начала — fair enough. Вообще, сортировать все нити — очевидно плохо, не делайте так. Я тоже этот кусок перепишу более оптимальным образом, например, так как уже описал выше, для realtime.
Кстати, при чтении кода планировщика надо учитывать, что нити не всегда «съедают» свой квант времени — нить может заблокироваться на примитиве синхронизации и часть времени простоять не по своей воле. Этим и обусловлена сортировка: если приоритет нити высок, то нить после разблокирования вернётся на процессор раньше, чем доработают все остальные нити.
Хорошо, перейдём к idle priority class. Мы попадём сюда только если в предыдущих классах все нити спят или отсутствуют.
// Have idle one?
ret = (phantom_thread_t *)queue_first(&runq_idle);
if( ret )
{
if( ret->thread_flags & THREAD_FLAG_NOSCHEDULE )
goto idle_retry;
// Just take first. Switched off thread will become
// last on runq, so all idle threads will run in cycle
ret->ticks_left = NORM_TICKS;
return ret;
}
else
goto idle_no;
Здесь всё просто — берём первую попавшуюся, запускаем на стандартное время. Поскольку при снятии с процессора она попадёт в конец очереди runq_idle, все такие нити будут запускаться по кругу.
Наконец, если вообще ничего не нашлось, у нас есть специальная idlest thread на этот случай.
STAT_INC_CNT(STAT_CNT_THREAD_IDLE);
percpu_idle_status[GET_CPU_ID()] = 1; // idle
return GET_IDLEST_THREAD(); // No real thread is ready to run
Она у каждого процессора своя просто потому, что одну нить нельзя запустить дважды. Проста как мычание:
while(1)
{
hal_sti();
hal_wait_for_interrupt();
}
Почти всё.
Что здесь не учтено.
Interactive thread prio boost: обычно планировщики увеличивают фактический приоритет нитям, которые замечены во вводе-выводе с консоли или другой сущности, за которой, потенциально, прячется интерактивный юзер. Это повышает перцептивную реактивность системы — «операционка меньше тупит» с точки зрения человека. И наоборот — если нить «доедает» свой таймслайс до конца, и делает это стабильно, ей немного понижают приоритет, считая её чисто вычислительной. С той же целью — повысить реактивность системы.
Это, конечно, касается только нитей с обычным классом приоритетов — никто и никогда не трогает приоритеты реального времени.
Планирование реального времени с гарантией доли процессора. Строгие системы реального времени имеют жёсткий план, в рамках которого нить или группа нитей может получать чётко оговоренное количество процессорного времени.
Инверсия приоритетов.
Предположим, у нас есть страшно важная нить R с максимальным приоритетом реального времени, и нить I с приоритетом класса idle, которая занимается несущественной ерундой. А так же обычная нить U, которая работает с юзером — читает команды с консоли. Шелл, например.
Юзер бездействует, ждёт ввода-вывода и нить U.
Нить I получает процессор, решает поделать свою ерунду и хочет для этого выделить себе немного памяти. Функция выделения памяти ядра запирает глобальный мьютекс и начинает выделять. Работая на idle prio, очевидно.
В этот момент просыпается ото сна нить R, которой пора скорректировать положение стержня поглотителя активной зоны реактора. И тоже хочет немного памяти.
(Давайте не будем привередничать и спрашивать, что U и R делают на одной машине — U может быть сервером статистики по TCP, например.)
Естественно, R забирает процессор у I, но упирается в глобальный мьютекс при выделении памяти, и останавливается.
Тут бы I продолжить работу, но юзер набирает команду, и U принимается за работу, отбирая процессор у I. Теперь, внезапно, высокоприоритетная нить реального времени R ждёт окончания работы нити U, и реактор взрывается к чертям.
Для того, чтобы это не случалось, делают то, что у меня в Фантоме пока не сделано — инверсию приоритетов.
Она формулируется так: если нить более высокого приоритета заблокирована на ресурсе, занятом нитью низкого приоритета, вторая нить получает на время такой блокировки приоритет первой нити.
То есть, в нашем примере, нить I на время блокировки мьютекса выделения памяти должна была получить приоритет реального времени от нити R, вытеснить к чертям нить U и доделать то, что блокирует нить R. После разблокировки мьютекса её приоритет должен понизиться обратно до idle и процессор перейдёт к R, как и должно быть.
Вот теперь, наверное, всё. :)
