Пишу игрушечную ОС (о реализации мьютекса)

Продолжаю блог о разработке игрушечной ОС (предыдущие посты: раз ^[1], два ^[2], три ^[3]). Сделав паузу в кодировании (майские праздники, всё-таки), продолжаю работу. Только что набросал сканирование PCI-шины. Эта штука понадобится для работы с SATA-контроллером: следующее, что хочу сделать — это простенький драйвер диска. Он позволит поэкспериментировать с проецированием постоянной памяти на адресное пространство (своппинг, доведённый до логического конца). А пока хотел бы описать реализацию мьютекса.

Для реализации мьютекса (определён и реализован в src/sync.h ^[4] и src/sync.c ^[5]) нет необходимости в модификации существующего планировщика, описанного в двух предыдущих постах. Мьютекс может быть построен на базе всего двух его функций: pause_thread и resume_thread (см. src/schedule.h ^[6]).

struct mutex {
  struct __mutex_node *head, *tail;
  struct spinlock mlock, ilock;
};

static inline void create_mutex(struct mutex *mutex) {
  mutex->head = mutex->tail = NULL;
  create_spinlock(&mutex->mlock);
  create_spinlock(&mutex->ilock);
}

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

Итак, как это работает? Когда поток пытается получить мьютекс, он пробует захватить mlock, делая N попыток. Если это у него получается, то мьютекс захвачен. В противном случае он должен безопасно (т.е. через ilock) добавить себя в очередь ожидающих потоков и уснуть.

static inline err_code acquire_mutex(struct mutex *mutex) {
  extern err_code __sleep_in_mutex(struct mutex *mutex);
  if (!acquire_spinlock_int(&mutex->mlock, 1000))
    return __sleep_in_mutex(mutex);
  return ERR_NONE;
}

struct __mutex_node {
  struct __mutex_node *next;
  thread_id id;
};

INTERNAL err_code __sleep_in_mutex(struct mutex *mutex) {
  struct __mutex_node *node = NULL;
  bool acquired;

  acquire_spinlock(&mutex->ilock, 0);
  acquired = acquire_spinlock_int(&mutex->mlock, 1);
  if (!acquired) {
    node = alloc_block(&mutex_node_pool);
    if (node) {
      node->next = NULL;
      node->id = get_thread();
      if (mutex->head)
        mutex->head->next = node;
      mutex->head = node;
      if (!mutex->tail)
        mutex->tail = node;
      pause_this_thread(&mutex->ilock);
    }
  }
  if (!node)
    release_spinlock(&mutex->ilock);

  return (acquired || node) ? ERR_NONE : ERR_OUT_OF_MEMORY;
}

Вышеприведённый код нуждается в некоторых пояснениях:

1. Функция acquire_spinlock_int аналогична acquire_mutex за исключением того, что она не отключает прерывания до момента освобождения спинлока. Захватывая mlock, мы не хотим отключать прерывания — владение мьютексом может быть долгим. Другое дело, когда мы, захватывая ilock, хотим добавить поток в очередь — эта операция должна быть как можно более быстрой.

Следующая строка функции __sleep_in_mutex на первый взгляд бессмысленна:

 acquired = acquire_spinlock_int(&mutex->mlock, 1);

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

2. Функции alloc_block и free_block относятся к пулу заранее выделенных блоков памяти фиксированного размера (см. src/memory.h ^[7]). Соль этого пула в том, чтобы не вызывать медленный malloc всякий раз, когда нам нужен блок (в данном случае struct __mutex_node). Кстати, этот пул у меня пока без реализации (только заглушка, напрямую вызывающая malloc), как и сам malloc. Если у кого возникнет непреодолимое желание реализовать первый или портировать второй — пишите.

3. Зачем делать N попыток захватить mlock, если можно уснуть после первой попытки? Можно, просто это не очень эффективно. Время переключения контекста существенно выше одной попытки получить спинлок. Поэтому рационально сделать N попыток (в коде 1000, взято с потолка; в будущем нужно провести практические замеры, вывести и обосновать более разумный N), прежде чем усыпать.

При освобождении мьютекса хозяин захватывает ilock, после чего проверяет наличие в очереди ждущих потоков. Если поток найден, то он просыпается, становясь новым хозяином мьютекса. Если ожидающих потоков нет, то хозяин возвращает mlock и выходит.

static inline void release_mutex(struct mutex *mutex) {
  extern void __awake_in_mutex(struct mutex *mutex);
  acquire_spinlock(&mutex->ilock, 0);
  if (mutex->tail)
    __awake_in_mutex(mutex);
  else
    release_spinlock_int(&mutex->mlock);
  release_spinlock(&mutex->ilock);
}

INTERNAL void __awake_in_mutex(struct mutex *mutex) {
  struct __mutex_node *node;
  err_code err;

  do {
    node = mutex->tail;
    mutex->tail = node->next;
    if (mutex->head == node)
      mutex->head = NULL;
    err = resume_thread(node->id);
    free_block(&mutex_node_pool, node);
  }
  while (mutex->tail && err);

  if (!mutex->tail)
    release_spinlock_int(&mutex->mlock);
}

Хотел, было, ещё рассказать о реализации функции sleep, но этот пост и так содержит достаточно пищи для размышления, так что отложу до следующего раза.

P.S. Если найдёте ошибки в коде — обязательно пишите.

Автор: ababo

Источник ^[8]