Пишу игрушечную ОС (о реализации sleep)


    Очередной пост для блога, посвященного работе над игрушечной ОС. В прошлый раз я писал про необходимость в простеньком драйвере AHCI (SATA). Прежде чем начать двигаться в этом направлении, я решил набросать инфраструктуру драйверов: общий интерфейс драйвера + уточнённый интерфейс драйвера устройства хранения. Формулирование этих интерфейсов выявило проблему, на которую я ранее не обращал внимания — проблему портируемости.

    Не зависящий от платформы код (например, большая часть планировщика, вспомогательный код типа kprintf, ...) у меня перемешивается с кодом, заточенным только под x86_64 (системные таблицы дескрипторов, APIC, прерывания, ...). Хотя ничего не мешало мне сформулировать интерфейс драйвера, жёстко привязанного к x86_64 (в частности, свободно оперировать PCI-адресами), мне стало ясно, что без чёткого отделения кода, специфичного для конкретной платформы, от общего портируемого кода я буду лишь усугублять ситуацию. Итак, я принял решение перебрать всё написанное, отделив общий код (в корне src/) от кода, специфичного для платформы (в src/x86_64/). Этим я и занимался последние две недели.

    Опишу вкратце механизм разделения кода на примере планировщика. Интерфейс планировщика src/schedule.h подключает (#include) специальный файл src/x86_64/schedule.inc, содержащий зависящие от платформы static inline функции (как интерфейсные, так и внутренние). Все внутренние символы (не относящиеся к интерфейсным, но не могущие быть static) предваряются префиксом "__". Основная реализация планировщика находится в src/schedule.c, отдельные внутренние функции и код ассемблера в src/x86_64/schedule.c. Таким образом, кода планировщика «распыляется» на две директории. Разумеется, эта сложность лишь для общего случая, тогда как многие модули строятся по упрощённой схеме. Например, для cpu_info (информация о логических процессорах) заголовок раполагается в src/, а реализация — в src/x86_64/. Или полностью платформозависимый APIC целиком помещён в src/x86_64/.

    Теперь об обещанной функции sleep. В отличие от мьютекса реализация sleep потребовала некоторой модификации планировщика (пусть и минимальной). В интерфейсную часть (src/schedule.h) добавились функции:

    typedef void (*timer_proc)(uint64_t ticks);
    
    uint64_t get_ticks(void);
    timer_proc get_timer_proc(void);
    uint64_t get_timer_ticks(void); // is zeroed after triggering
    void set_timer_proc(timer_proc proc); // called within a timer interrupt
    void set_timer_ticks(uint64_t ticks); // not thread-safe
    

    Т.е. теперь планировщик выступает ещё и в роли таймера: хранит счётчик тиков (внутренних прерываний по таймеру), а также вызывает функцию-обработчик, как только число тиков достигнет заданного числа. Рассмотрим реализацию этого механизма (src/schedule.c).

    static inline void handle_timer(int cpu) {
      if (cpu == get_bsp_cpu())
        ticks++;
    
      if (timer_ticks[cpu] && timer_ticks[cpu] <= ticks) {
        uint64_t prev_ticks = timer_ticks[cpu];
        timer_ticks[cpu] = 0;
        set_outer_spinlock(true);
        timer_proc_(prev_ticks);
        set_outer_spinlock(false);
      }
    }
    

    Функция handle_timer вызывается в каждом прерывании по таймеру. Несмотря на то, что счётчик ticks инкрементируется только для bootstrap-процессора, таймер независимо программируется для каждого из логических процессоров. Оборачивание вызова обработчика в set_outer_spinlock нужно для того, чтобы вызов release_spinlock внутри обработчика случайно не выполнил инструкцию STI (не забываем, что мы находимся в контексте прерывания).

    Вот теперь, пользуясь этим расширенным функционалом планировщика, мы можем реализовать sleep (src/sync.c).

    struct sleep_node {
      struct sleep_node *next;
      thread_id thread;
      uint64_t ticks;
    };
    
    static struct sleep_data {
      struct sleep_node *tail;
      struct mem_pool pool;
      struct spinlock lock;
    } sleeping[CONFIG_CPUS_MAX];
    
    static void sleep_timer_proc(UNUSED uint64_t ticks) {
      struct sleep_data *slp = &sleeping[get_cpu()];
      if (slp->tail) {
        struct sleep_node *node = slp->tail;
        slp->tail = slp->tail->next;
        if (slp->tail)
          set_timer_ticks(slp->tail->ticks);
        resume_thread(node->thread);
        free_block(&slp->pool, node);
      }
    }
    
    err_code sleep(uint64_t period) {
      struct sleep_data *slp = &sleeping[get_cpu()];
      err_code err = ERR_NONE;
    
      acquire_spinlock(&slp->lock, 0);
      struct sleep_node *node = alloc_block(&slp->pool);
      if (node) {
        node->thread = get_thread();
        node->ticks = get_ticks() + period / CONFIG_SCHEDULER_TICK_INTERVAL;
    
        if (!slp->tail || slp->tail->ticks > node->ticks) { // is first to wake up
          node->next = slp->tail, slp->tail = node;
          set_timer_ticks(node->ticks);
        }
        else {
          struct sleep_node *prev = slp->tail;
          while (prev->next && prev->next->ticks <= node->ticks)
            prev = prev->next;
          node->next = prev->next, prev->next = node;
        }
    
        pause_this_thread(&slp->lock);
      }
      else
        err = ERR_OUT_OF_MEMORY;
      if (err)
        release_spinlock(&slp->lock);
    
      return err;
    }
    

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

    1. Экземпляр структуры sleep_data соответствует логическому процессору. Пул для sleep_node у каждого процессора независимый, поскольку mem_pool не потокобезопасен.

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

    2. Как видно из кода, при добавлении в список потоки ранжируются по времени пробуждения (в тиках).

    3. Функция sleep_timer_proc и есть тот обработчик, который вызывается планировщиком в контексте прерывания по таймеру. Её задача — разбудить нужный поток.

    Остальное кажется достаточно прозрачным.
    Поделиться публикацией

    Комментарии 15

      –1
      Предлагаю Вам, по аналогии с Андроид и Убунтой, называть версии вашей ОС по именам игрушек.
        0
        Поправка: у Debian-релизов (не Ubuntu) имена из мульта «Toy Story».
        У первых — зоологический принцип.
          +3
          У первых гастрономический всё же.
          0
          Ну хоть не политиков/президентов/генсеков :)
          0
          Как же хорошо, когда есть столько свободного времени. В далекие времена, когда мне было лет 17-18, я дошел до полноценной многозадачности и драйвера FDD. Эхх… :)
            +2
            Время можно найти всегда, если есть много интереса. :)
              +1
              А вы не задумывались поучаствовать в проекте посерьезней, типа KolibriOS? :)
                +3
                Если честно, то мне не кажется KolibriOS серьёзным. Т.е. с точки зрения стадии готовности он, конечно, не может сравниться с моей поделкой. Но моя главная задача — экспериментировать с новой, не UNIX-derived, архитектурой. Просто пока я ещё не подошёл к этому, главному для меня, этапу. Но через 1-2 месяца планирую это сделать.
                  +1
                  Я сам не участник разработки Kolibri (во всяком случае, пока), но, во-первых, я знаю, что её уже используют в достаточно серьезных делах (боюсь соврать, поэтому подробности можете, если хотите, почитать на их форуме), а во-вторых, мне кажется, что экспериментировать должно быть проще, когда куча мелкой, но важной работы уже проделано. Грубо говоря, можно сесть и самому писать дрова под видео/звук/мышь и т.п., потратив на это годик-другой, а можно воспользоваться готовым решением (благо, исходники — вот они), и заняться сразу самым интересным, не размениваясь по мелочам. :)
                    0
                    Вот про драйвера — горькая правда…
                    0
                    Но моя главная задача — экспериментировать с новой, не UNIX-derived, архитектурой.

                    А если не секрет, Вы уже определились, какие новаторские архитектурные решения Вы хотели бы Но моя главная задача — экспериментировать с новой, не UNIX-derived, архитектурой опробовать?
                      +2
                      Я, кажется, писал в первом посте об общем видении. Если кратко, то что-то похожее на Phantom OS: единое адресное пространство, виртуальная машина, персистивность адресного пространства (файлы не нужны), распределённость.
                        0
                        Ok, а цель, кроме Just For Fun (в первом приближении)?
                          0
                          В первом приближении — оно самое. Надеятся на успех Линукса, увы, не приходится. Лучше не питать никаких надежд, чем больно разочароваться.
                        +1
                        * А если не секрет, Вы уже определились, какие новаторские архитектурные решения Вы хотели бы опробовать?

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое