I am writing a toy OS (about mutex implementation)

I continue the blog about the development of a toy OS (previous posts: one , two , three ). Having paused in coding (May holidays, after all), I continue to work. Just sketched a PCI bus scan. This thing is needed to work with the SATA controller: the next thing I want to do is a simple disk driver. It will allow to experiment with the projection of permanent memory to the address space (swapping, brought to a logical end). For now I would like to describe the implementation of the mutex.



To implement the mutex (defined and implemented in src / sync.h and src / sync.c ), there is no need to modify the existing scheduler described in the two previous posts. A mutex can be built on the basis of only two of its functions: start and pause a thread (see 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); } 

My implementation of the mutex involves two spinlock and a queue of sleeping threads. The first spinlock (mlock) is responsible for accessing the protected mutex resource, i.e. it is captured if and only if the mutex is captured. The second spinlock (ilock) protects the queue of waiting threads from simultaneous modification.



So how does it work? When a thread tries to get a mutex, it tries to capture mlock, making N attempts. If it succeeds, the mutex is captured. Otherwise, it should safely (i.e. via ilock) add itself to the queue of waiting threads and fall asleep.

')

 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; } 

The above code needs some explanation:



1. The acquire_spinlock_int function is similar to acquire_spinlock, except that it does not disable interrupts until the spinlock is released. When capturing mlock, we don’t want to disable interrupts - possession of a mutex can be long. Another thing is when, capturing ilock, we want to add a stream to the queue — this operation must be fast.



2. The following line of the function __sleep_in_mutex is at first glance meaningless:

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

In fact, why re-try to grab the spinlock when we have failed? Then, between the first attempt and the capture of ilock, the owner of the mutex can return it, and only later our thread will receive a planning quantum. Without another attempt, we will add ourselves to the queue and put them to sleep forever. Therefore, it is important to check again after the capture of ilock (the owner of the mutex will return to it when returning).



3. The functions alloc_block and free_block relate to a pool of pre-allocated fixed-size memory blocks (see src / memory.h ). The salt of this pool is not to call a slow malloc whenever we need a block (in this case, struct __mutex_node). By the way, I still have this pool without implementation (only a stub that directly calls malloc), just like malloc itself. If anyone has an overwhelming desire to realize the first or to port the second - write.



4. Why make N attempts to capture mlock if you can fall asleep after the first attempt? You can, it just is not very effective. The context switching time is significantly higher than one attempt to get a spinlock. Therefore, it is rational to make N attempts (in code 1000, taken from the ceiling; in the future, it is necessary to take practical measurements, derive and substantiate a more reasonable N) before putting it to sleep.



5. The code uses a modified version of pause_thread: pause_this_thread. In addition to putting the current stream to sleep, it atomically (in an interrupt) releases the spinlock passed to it.



When releasing a mutex, the host captures ilock, and then checks for waiting threads in the queue. If a thread is found, then it wakes up, becoming the new owner of the mutex. If there are no waiting threads, then the host returns mlock and exits.

 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); } 

I wanted to, it was still to talk about the implementation of the sleep function, but this post already contains enough food for thought, so I will postpone it until the next time.



PS If you find errors in the code - be sure to write.