I am writing a toy OS (about the implementation of the mutex)


    I continue the blog about developing a toy OS (previous posts: one , two , three ). After pausing the coding (May holidays, after all), I continue to work. Just sketched a scan of the PCI bus. This thing will be needed to work with the SATA controller: the next thing I want to do is a simple disk driver. It will allow you to experiment with the projection of read-only memory onto the address space (swapping brought to its logical end). In the meantime, I would like to describe the implementation of the mutex.

    To implement a mutex (defined and implemented in src / sync.h and src / sync.c) There is no need to modify the existing scheduler described in two previous posts. A mutex can be built on the basis of only two of its functions: start and pause a stream (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 mutex implementation involves two spinlocks and a queue of sleeping threads. The first spinlock (mlock) is responsible for access to the protected mutex resource, i.e. it is captured if and only if the mutex itself 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 he succeeds, then 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 - ownership of a mutex can be long. Another thing is when we, capturing ilock, want to add a thread to the queue - this operation should be quick.

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

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

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

    3. The alloc_block and free_block functions refer to a pool of pre-allocated memory blocks of a fixed size (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 directly calling malloc), as well as malloc itself. If anyone has an irresistible desire to implement the first or port the second - write.

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

    5. The code uses a modified version of pause_thread: pause_this_thread. In addition to euthanizing the current stream, it atomically (in interruption) releases the spinlock transmitted to it.

    When the mutex is freed, the host captures ilock, and then checks for waiting threads in the queue. If the stream is found, then it wakes up, becoming the new owner of the mutex. If there are no pending threads, 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 talk more about the implementation of the sleep function, but this post already contains enough food for thought, so I’ll postpone it until the next time.

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

    Also popular now: