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

  • Tutorial

Отсутствие комментариев к двум моим предыдущим постам, несмотря на большое число лайков, привели меня к выводу, что подавляющее большинство ничего не поняло. Просто, будучи давно погружённым в тему, я проявил невнимательность к своему читателю. Моя вина, буду исправляться. Поговорим о планировании доступным языком.

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

По способу переключения между задачами планировщики делятся на кооперативные и вытесняющие. При кооперативном планировании ответственность за переключение задач несут сами задачи. Т.е. задача сама решает, когда можно уступить место следующей. В отличие от кооперативных, вытесняющие планировщики самостоятельно принимают решение о смене задачи. Легко понять, что второй метод планирования в общем случае является более предпочтительным для ОС в силу своей предсказуемости и надёжности.

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

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

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

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

В toy это делается так:

DEFINE_ISR(timer, 0) {
  ...
  thrd->context = *stack_frame; // сохраняем текущий контекст в структуре thread_data
  update_priority_quantum(thrd); // вычисляем новый квант и приоритет потока
  ...
  prio = &cpud->priorities[cpud->current_priority = highest]; // работает с наивысшим текущим приоритетом
  struct thread_data *thrd2 = prio->active_tail; // берём из очереди наивысшего приоритета первый поток
  if (thrd2 != thrd) { // если старый и новый - не один и тот же поток
    *stack_frame = thrd2->context; // устанавливаем контекст из нового потока 
    wrmsr(MSR_FS_BASE, (uint64_t)thrd2);
  }
  ...
}


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

Важно понимать, что код SMP-планировщика работает в каждом логическом процессоре. Т.е. в каждом из них генерируются прерывания по таймеру, переключающие контексты потоков. Итак, потоки распределены между имеющимися логическими процессорами (балансировка их загрузки — отдельная нетривиальная задача). В современных x86-системах наряду со старым программируемым таймером поддерживаются, так называемые, local APIC таймеры. Главное их преимущество заключается в том, что каждый логический процессор имеет свой независимый local APIC таймер. Поэтому, именно эти таймеры удобно использовать для планирования. Код работы с APIC таймером в toy можно посмотреть здесь.

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

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

Основным примитивом синхронизации, основанным на активном ожидании, является спинлок. В современных системах спинлоки базируется на атомарных инструкциях. Для x86 это xchg, lock cmpxchg, и другие. Главная задача таких инструкций — атомарно прочесть и изменить ячейку памяти. Реализация базовых захвата и освобождения спинлока в toy:

struct spinlock {
  volatile uint8_t busy;
};

static inline void create_spinlock(struct spinlock *lock) {
  lock->busy = false;
}

// zero tries means (practically) forever
static inline bool acquire_spinlock_int(struct spinlock *lock,
                                        uint64_t tries) {
  uint8_t al;
  do ASMV("mov $1, %%al\nxchgb %%al, %0" : "+m"(lock->busy), "=&a"(al));
  while (al && --tries);
  return !al;
}

static inline void release_spinlock_int(struct spinlock *lock) {
  ASMV("xorb %%al, %%al\nxchgb %%al, %0" : "+m"(lock->busy) : : "al");
}


На сегодня всё.

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

Продолжить писать популярно?

Поделиться публикацией

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

    –11
    Моск взорван. Web-програмеру тяжело читать про системное программирование (:
      +13
      А вы пробовали не читать? Должно полегчать… :)
        0
        Что вы. Читать полезно.
        Просто как-то крайне абстрактно, хотя вроде и относительно доступно описано все (:
          –1
          Смайлик вместо точки обязательно ставить? Что же вы «Web-програмеры» все какие-то не такие. Ну неудобно ведь читать.
            +1
            В Web-программировании точно такие же абстракции. Программирование в любом виде — это работа с абстракциями.
        +13
        Если вам нужны комментарии — меняйте тему. Сделайте обзор китайского смартфона, обязательно с анбоксингом, или напишите про то, как вы ненавидите копирайт и копирастов, и как вы сейчас всем объясните, как можно жить без копирайта. (trollface).
          +2
          «Отсутствие комментариев к двум моим предыдущим постам, несмотря на большое число лайков, привели меня к выводу, что подавляющее большинство ничего не поняли. „

          Или же может многое из того, что вы описали, уже знакомо, скажем, из тех же “Операционных систем» В. Столлингса)
            0
            Или из «Современных операционных систем» Таненбаума.
            0
            Совсем не понял зачем Вы в статьи код вставляете? Если есть какие-то готовые и компилируемые реализации чего-то, то выложите на github куда-нить и дайте ссылку… Зачем какие-то отстранённые куски вставлять в статьи?
              +4
              Обычно код вставляют для того, чтобы показать, как абстрактная идея работает на практике. Мне же это тем более приятно, так как это мой код. Кроме того, есть вероятность того, что внимательный читатель найдёт какую-либо ошибку, за что я буду ему благодарен.
                0
                В куске кода, вырванном из контекста вряд ли вам кто что-либо найдёт. Мало ли какие феньки для оптимизации вы используете и какие очевидно (мне) нужные вещи реализуете за скобками и как.
                  –3
                  Вот именно это я и имею ввиду, кусок кода по данной теме выранный из контекста только засоряет текст статьи… Реализовать то, что автор описывает можно 10000+1 способом… зачем нужны конкретные буквы по данной теме… непонятно…
                    0
                    Действительно, зачем вам конкретные буквы…
                      0
                      Вы хотели конструктивной критики насчёт ваших статей? Так получите её… зачем встаёте в позу?
                        0
                        Да никакой позы, спасибо вам за коммент. Просто улыбнула фраза.
                          0
                          А Вам спасибо за статью… Сам текст вполне читаемый и может быть кому-то полезен в качестве «общего образования»… Но куски кода реально напрягают :)
              –1
              Класс! Но я бы советовал Вам попробовать написать визуальную оболочку под экспериментальную ОС Singularity, она полностью написана на защищенном коде, на подобии языка C#. Было бы очень интересно и полезно! Можно начать кикстратер компанию собрать программеров описать проект, нечто вроде Linux 2.0, может быть и получилась национальная ОСь за которую не стыдно!
                +2
                Национальная ось… за которую не стыдно…

                image
                0
                Капитан Пикар плакал…

                  0
                  Нашел в readme такую строчку:
                  > 3. Virtual machine for memory protection and security.
                  Какую VM собираетесь использовать — JVM, CLI или что-то другое?
                    0
                    Что-то своё, наверное. Слишком много специфики, в силу которой JVM или CLR не подойдут. В частности, это связанно с поддержкой персистивности и распределённости. Но до этого пока очень далеко. Сейчас нужно заниматься базовой системой (отображение всей памяти на адресное пространство, разработка API, поддерживающего персистивность...)
                      0
                      Круто! А можно узнать больше деталей об Design vision? Собираетесь поддерживать capability-based security или будет глобально доступное пространство имен? Граф объектов будет сплошной или разделенный на кластеры/домены/SIP-ы?
                        0
                        Вот как раз security у меня наименее проработан. Ничего не могу вам рассказать об этом. Смотрел вашу статью о capability based security. Вообще, в сравнении с UNIX-security эта модель выглядит более предпочтительной.
                          0
                          В ОС с ортогональной персистентностью и виртуальной машиной такая модель безопасности реализуется сама собой. Но чтобы от нее был толк, нужно отсутствие глобальной барахолки, где каждый может найти каждого. В идеале надо вообще убрать из языка возможность создавать глобальные/статические переменные, а API ядра предоставлять в виде интерфейса, а не статических функций.
                    0
                    Баловался когда-то. С одной стороны было легче, т.к. на 8086, без PM, с другой — из литературы только Бах. Это нереальное ощущение крутости, когда даешь структурам названия типа task и sheduler.
                      0
                      Тема интересная и завораживающая. После таких статей так и хочется нырнуть поглубже и познакомиться со всей этой магией :)
                      Добавил в список 2read, 2try, 2taste на досуге!
                        0
                        Попробуйте исходники. Их пока очень мало, можно легко со всем разобраться.
                        +1
                        Этот участок:
                          do ASMV("mov $1, %%al\nxchgb %%al, %0" : "+m"(lock->busy), "=&a"(al));
                          while (al && --tries);
                        

                        можно переписать, например, так:
                          do {
                            if (lock->busy) {
                              al = 1;
                            } else {
                              ASMV("mov $1, %%al\nxchgb %%al, %0" : "+m"(lock->busy), "=&a"(al));
                            }
                          } while (al && --tries);
                        

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

                        Другими словами на Wikipedia.
                          +1
                          Да, тут возможны и другие оптимизации, например, использование инструкции pause после каждой неудачной попытки (что особенно полезно для NetBurst процессоров). Пока это решение в лоб, а оптимизацию я оставил на будущее. Первый комментарий по делу!

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

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