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

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

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

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

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

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

В зависимости от приоритета потоку назначается некоторый квант времени. Например, пусть таймер генерирует прерывания каждую миллисекунду. Тогда поток, которому назначен квант 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");
}

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