Пишу игрушечную ОС (доступнее о планировщике)

Отсутствие комментариев к двум моим предыдущим постам, несмотря на большое число лайков, привели меня к выводу, что подавляющее большинство ничего не поняло. Просто, будучи давно погружённым в тему, я проявил невнимательность к своему читателю. Моя вина, буду исправляться. Поговорим о планировании доступным языком.

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

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

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

Переключение потоков в вытесняющем планировщике инициируется прерыванием по таймеру. Каждый заданный период времени выполнение кода приостанавливается, и управление передаётся обработчику прерывания. Этот обработчик решает, продолжать ли текущему потоку работать до следующего периода, или же передать управление другому потоку.

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

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

В toy это делается так:

DEFINE_ISR(timer, 0) {
  ...
  thrd->context = *stack_frame; // сохраняем текущий контекст в структуре thread_data
  update_priority_quantum(thrd); // вычисляем новый квант и приоритет потока
  ...
  prio = &cpud->priorities[cpud->current_priority = highest]; // работает с наивысшим текущим приоритетом
  struct thread_data *thrd2 = prio->active_tail; // берём из очереди наивысшего приоритета первый поток
  if (thrd2 != thrd) { // если старый и новый - не один и тот же поток
    *stack_frame = thrd2->context; // устанавливаем контекст из нового потока 
    wrmsr(MSR_FS_BASE, (uint64_t)thrd2);
  }
  ...
}

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

Важно понимать, что код SMP-планировщика работает в каждом логическом процессоре. Т.е. в каждом из них генерируются прерывания по таймеру, переключающие контексты потоков. Итак, потоки распределены между имеющимися логическими процессорами (балансировка их загрузки — отдельная нетривиальная задача). В современных x86-системах наряду со старым программируемым таймером поддерживаются, так называемые, local APIC таймеры. Главное их преимущество заключается в том, что каждый логический процессор имеет свой независимый local APIC таймер. Поэтому, именно эти таймеры удобно использовать для планирования. Код работы с APIC таймером в toy можно посмотреть здесь.

Может возникнуть ошибочное впечатление, что поскольку каждый логический процессор планирует собственные потоки, то нет необходимости в синхронизации. На самом деле, потоки не привязаны жёстко к одному процессору, а могут мигрировать (как при балансировке загрузки, так и явно, по инициативе другого потока). Например, в toy один поток может приостановить второй, и запустить его на другом процессоре. Соответственно, появляется необходимость в защите совместно используемых данных.

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

Основным примитивом синхронизации, основанным на активном ожидании, является спинлок. В современных системах спинлоки базируется на атомарных инструкциях. Для x86 это xchg, lock cmpxchg, и другие. Главная задача таких инструкций — атомарно прочесть и изменить ячейку памяти. Реализация базовых захвата и освобождения спинлока в toy:

struct spinlock {
  volatile uint8_t busy;
};

static inline void create_spinlock(struct spinlock *lock) {
  lock->busy = false;
}

// zero tries means (practically) forever
static inline bool acquire_spinlock_int(struct spinlock *lock,
                                        uint64_t tries) {
  uint8_t al;
  do ASMV("mov $1, %%al\nxchgb %%al, %0" : "+m"(lock->busy), "=&a"(al));
  while (al && --tries);
  return !al;
}

static inline void release_spinlock_int(struct spinlock *lock) {
  ASMV("xorb %%al, %%al\nxchgb %%al, %0" : "+m"(lock->busy) : : "al");
}

На сегодня всё.