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

Продолжаю вести блог о разработке игрушечной ОС.

В прошлом посте я писал о том, как добиться возможности реализовывать на C обработчики прерываний. Теперь, пользуясь написанными ранее макросами, можно реализовать простой SMP-планировщик. Он будет предоставлять минимально возможный функционал, на базе которого в будущем нужно будет возводить различные надстройки, в частности, примитивы синхронизации (например, мьютекс). Опять же, красивая модульная структура не способствует высокой производительности, но красота, как известно, спасёт мир, так что отдадим ей предпочтение.

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

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

Итак, вышеперечисленные требования вылились у меня в следующий интерфейс планировщика:

// IN fields should be set before calling attach_thread
struct thread_data {
  INTERNAL uint64_t magic;
  INTERNAL struct thread_data *prev, *next, *all_prev, *all_next;
  IN struct int_stack_frame context;
  IN uint8_t *stack;
  IN size_t stack_size; // size available to thread: stack_size - 8
  IN uint64_t affinity[THREAD_AFFINITY_SIZE];
  OUT uint64_t output;
  OUT uint64_t run_time;
  IN uint8_t priority;
  INTERNAL uint8_t real_priority;
  INTERNAL uint16_t quantum;
  INTERNAL uint8_t cpu;
  INTERNAL uint8_t state: 2;
  IN uint8_t fixed_priority : 1;
};

typedef uint64_t thread_id;
typedef uint64_t (*thread_proc)(uint64_t input);

// set stack and stack_size fields before calling this function
err_code set_thread_context(struct thread_data *thread, thread_proc proc,
                            uint64_t input);

// attached thread becomes paused; thread should not reside in stack!
err_code attach_thread(struct thread_data *thread, thread_id *id);
err_code detach_thread(thread_id id, struct thread_data **thread);

err_code resume_thread(thread_id id);
err_code pause_thread(thread_id id);
err_code stop_thread(thread_id id, uint64_t output);

thread_id get_thread(void);

Вот пример кода, запускающего новый поток:

static uint64_t thread_proc(uint64_t input) {
  // do some work
  return output;
}

#define STACK_SIZE 0x1000

static void start_thread(void) {
  thread_id id;
  struct thread_data *thrd;

  struct thread_data *thrd = kmalloc(sizeof(*thrd)+STACK_SIZE);
  if (!thrd) {
    LOG_ERROR("Failed to allocate memory");
    return;
  }

  memset(thrd, 0, sizeof(*thrd));
  thrd->stack = (uint8_t*)(thrd + 1);
  thrd->stack_size = STACK_SIZE;
  thrd->affinity[0] = 1; // will run on first CPU only
  thrd->priority = 3;
  thrd->fixed_priority = true;
  set_thread_context(thrd, thread_proc, 0);

  if (attach_thread(thrd, &id) != ERR_NONE) {
    LOG_ERROR("Failed to attach thread");
    return;
  }

  if (resume_thread(id) != ERR_NONE) {
    LOG_ERROR("Failed to resume thread");
    return;
  }

Теперь самое время заглянуть под капот.

Наш планировщик состоит из следующих частей:
1. Список всех добавленных потоков. Защищён собственным спинлоком.
2. Список неактивных потоков. К неактивным потокам относятся приостановленные и завершённые потоки. Защищён собственным спинлоком.
3. Рабочая область CPU (по одной на каждый логический процессор). Она содержит очереди приоритетов, а также специальную структуру задачи (о ней пойдёт речь позже). Рабочая область CPU также защищена собственным спинлоком.

Рассмотрим работу планировщика на примере запуска нового потока. Прежде всего, захватывается спинлок списка неактивных потоков (будем извлекать из него элемент). Этот спинлок не только защищает список от несогласованной модификации разными потоками, но и отключает прерывания, обеспечивая атомарность операции на данном процессоре. После извлечения потока ищется процессор с наименьшим числом планируемых потоков (из разрешённых в affinity) – простой вариант балансировки нагрузки.

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

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

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

Несколько сумбурное изложение, многие вещи остались за кадром, но на сегодня хватит. Если у кого будут вопросы — опишу подробнее в комментариях. И да, всегда можно почитать исходники.

Автор: ababo

Источник