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

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

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

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). Соль этого пула в том, чтобы не вызывать медленный 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, но этот пост и так содержит достаточно пищи для размышления, так что отложу до следующего раза.