Пишу игрушечную ОС (о планировщике)


    Продолжаю вести блог о разработке игрушечной ОС.

    В прошлом посте я писал о том, как добиться возможности реализовывать на C обработчики прерываний. Теперь, пользуясь написанными ранее макросами, можно реализовать простой SMP-планировщик. Он будет предоставлять минимально возможный функционал, на базе которого в будущем нужно будет возводить различные надстройки, в частности, примитивы синхронизации (например, мьютекс). Опять же, красивая модульная структура не способствует высокой производительности, но красота, как известно, спасёт мир, так что отдадим ей предпочтение.

    Итак, попробуем сформулировать требования к нашему планировщику. Нам нужна возможность создать поток, указать для него стек, маску разрешённых логических процессоров (affinity), базовый приоритет и функцию выполнения. Далее, поток можно запустить, приостановить, продолжить его выполнение и, наконец, завершить.

    Кроме того, было бы здорово, если бы планировщик не занимался выделением памяти, а мог принимать и возвращать память, выделенную под поток кем-то другим. С одной стороны, это бы обеспечило гибкость произвольного резервирования памяти потоков. С другой – дало бы уникальную возможность сохранять поток во внешней памяти (например, на жёстком диске) с последующей его загрузкой и запуском с прерванного места.

    Итак, вышеперечисленные требования вылились у меня в следующий интерфейс планировщика:

    // IN fields should be set before calling attach_thread
    struct thread_data {
      INTERNAL uint64_t magic;
      INTERNAL struct thread_data *prev, *next, *all_prev, *all_next;
      IN struct int_stack_frame context;
      IN uint8_t *stack;
      IN size_t stack_size; // size available to thread: stack_size - 8
      IN uint64_t affinity[THREAD_AFFINITY_SIZE];
      OUT uint64_t output;
      OUT uint64_t run_time;
      IN uint8_t priority;
      INTERNAL uint8_t real_priority;
      INTERNAL uint16_t quantum;
      INTERNAL uint8_t cpu;
      INTERNAL uint8_t state: 2;
      IN uint8_t fixed_priority : 1;
    };
    
    typedef uint64_t thread_id;
    typedef uint64_t (*thread_proc)(uint64_t input);
    
    // set stack and stack_size fields before calling this function
    err_code set_thread_context(struct thread_data *thread, thread_proc proc,
                                uint64_t input);
    
    // attached thread becomes paused; thread should not reside in stack!
    err_code attach_thread(struct thread_data *thread, thread_id *id);
    err_code detach_thread(thread_id id, struct thread_data **thread);
    
    err_code resume_thread(thread_id id);
    err_code pause_thread(thread_id id);
    err_code stop_thread(thread_id id, uint64_t output);
    
    thread_id get_thread(void);

    Вот пример кода, запускающего новый поток:

    static uint64_t thread_proc(uint64_t input) {
      // do some work
      return output;
    }
    
    #define STACK_SIZE 0x1000
    
    static void start_thread(void) {
      thread_id id;
      struct thread_data *thrd;
    
      struct thread_data *thrd = kmalloc(sizeof(*thrd)+STACK_SIZE);
      if (!thrd) {
        LOG_ERROR("Failed to allocate memory");
        return;
      }
    
      memset(thrd, 0, sizeof(*thrd));
      thrd->stack = (uint8_t*)(thrd + 1);
      thrd->stack_size = STACK_SIZE;
      thrd->affinity[0] = 1; // will run on first CPU only
      thrd->priority = 3;
      thrd->fixed_priority = true;
      set_thread_context(thrd, thread_proc, 0);
    
      if (attach_thread(thrd, &id) != ERR_NONE) {
        LOG_ERROR("Failed to attach thread");
        return;
      }
    
      if (resume_thread(id) != ERR_NONE) {
        LOG_ERROR("Failed to resume thread");
        return;
      }
    

    Теперь самое время заглянуть под капот.

    Наш планировщик состоит из следующих частей:
    1. Список всех добавленных потоков. Защищён собственным спинлоком.
    2. Список неактивных потоков. К неактивным потокам относятся приостановленные и завершённые потоки. Защищён собственным спинлоком.
    3. Рабочая область CPU (по одной на каждый логический процессор). Она содержит очереди приоритетов, а также специальную структуру задачи (о ней пойдёт речь позже). Рабочая область CPU также защищена собственным спинлоком.



    Рассмотрим работу планировщика на примере запуска нового потока. Прежде всего, захватывается спинлок списка неактивных потоков (будем извлекать из него элемент). Этот спинлок не только защищает список от несогласованной модификации разными потоками, но и отключает прерывания, обеспечивая атомарность операции на данном процессоре. После извлечения потока ищется процессор с наименьшим числом планируемых потоков (из разрешённых в affinity) – простой вариант балансировки нагрузки.

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

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

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

    Несколько сумбурное изложение, многие вещи остались за кадром, но на сегодня хватит. Если у кого будут вопросы — опишу подробнее в комментариях. И да, всегда можно почитать исходники.
    Share post

    Similar posts

    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 16

      +3
      struct thread_data { INTERNAL uint64_t magic;

      — А вы не могли бы пояснить, что это за магия такая?
        +1
        Это простая проверка id потока. Когда поток добавлятся в планировщик, ему в magic пишется магическая константа, когда же он удаляется, то константа обнуляется. В текущей реализации id — это просто адрес потока, приведённый к числу. Соответственно, если мы передаём неправильный id, то magic не совпадёт и функция вернёт ERR_NOT_FOUND.
          +1
          А как magic и id связаны?
            +1
            В текущей реализации id — это просто адрес потока, приведённый к числу.
              +2
              Из ответа автора мне тоже не удалось до конца понять, что к чему. Потому полез в исходники (файл src/schedule.c):
              #define CAST_TO_THREAD(thrd, id)                        \
                struct thread_data *thrd = (struct thread_data*)id;   \
                if (thrd->magic != THREAD_MAGIC)                      \
                  return ERR_NOT_FOUND;
              
                +1
                То есть эта переменная, фактически, флаг, что тред создан?
                  +1
                  Да, точнее, что он attached к планировщику. Это для того, чтобы минимизировать вероятность ошибки передачи неверного id.
                    +1
                    Понятно, спасибо.

                    Не знаю, насколько бестактно вам указывать, но я бы эту переменную назвал bool isThreadAttached :)
                    +2
                    Скорее, что id указывает на валидную (созданую, запланированую и ещё не разрушеную) структуру thread_data, а не на случайный адрес в памяти.
            +1
            А можно ли приостановленный поток запустить на другом процессоре или даже на другой машине в сети?
              +1
              Преостановленный поток, т.е. поток находящийся в планировщике может быть запущен в любой момент (resume_thread), причём каждый раз при запуске находится наименее загруженный процессор. Отсюда следуют, что в общем случае поток каждый раз может запускаться на любом процессоре.

              Вторая часть вашего вопроса особенна интересна. Действительно, можно приостановить поток, извлечь его из планировщика (detach_thread), сохранить (например в файл) и возобновить на другой машине (при условии совместимости процессоров). Последнее возможно с точки зрения планировщика. В реальности всё будет гораздо сложнее, поскольку поток пользуется не только стеком, но и другой памятью, иными ресурсами, которые должны совпадать (или эмулироваться) на другой машине.
              +1
              А как запущен сам планировщик? Как поток на одном из процессоров? Успеет ли он в таком случае справиться с планированием большого количества других потоков на многих процессорах?
                0
                Нет, планировщик распределён между всеми логическими процессорами. На каждом из них срабатывает прерывание по таймеру, в котором и происходит само планирование. Т.е. один и тот же код выполняется на каждом процессоре.
                0
                перенёс
                  0
                  Автор, надеюсь «Operating Systems Design and Implementation» Andrew S. Tanenbaum — ваша настольная книга ;-))
                    0
                    Нет, в электронном виде и читаю редко. Больше спецификации.

                  Only users with full accounts can post comments. Log in, please.