Наработки к планированию процессов в ОСРВ

Закончив изучение Таненбаума и ковыряние ядра Linux решил, что надо заняться чем-то дельным. По личным мотивам решил переделать ядро minix3 под планирование в жёстком реальном времени. Множество существующих алгоритмов планирования ввели меня в уныние, тем более, что хочется сделать ОС максимально универсальной и гибкой. Зацикленность на клиент-серверной модели привели к идеи о вынесении из ядра ОС механизмов планирования и разделение процессов на группы, управляемые: каждая своим планировщиком (в режиме ядра оставить только обработку deadline).
Основная проблема, которая стала очевидной сразу же — это выбор математической модели для построения алгоритма планирования. Очевидно, что подход разделения общего ресурса можно рассмотреть в аналогии с сетевыми протоколами разделения общего физического пространства.

Для вдохновения были рассмотрены алгоритмы IPv4 адресации и протоколы динамической маршрутизации (RIP1\2, OSPF)
Итак, сам алгоритм:
По аналогии с IP адресацией потоки/процессы планирования описываем номером и маской (как подсети), а сами группы только номером (целевые точки). В зависимости от реализации процессов, передаём данные о процессах, времени их выполнения, приоритетах и прочее между планировщиками групп. В моих примерах используется адресация «байт адреса / байт маски». Всего до 255 групп процессов с возможностью запустить до 8ми контролирующих группу планировщиков, суммарно до 510 процессов планировщиков.
image
                Зарисовка к алгоритму

Так как развиваю эту идею для ОС реального времени, то и все идеи применения связаны с отказоустойчивостью и предсказуймостью.
Из зарисовки можно понять основные идеи применения:
1) Передача процессов между планировщиками. Например, при срабатывании wathcdog можно перевести процесс из режима мягко реального времени в жёсткое или при зацикливании одного процесса можно подменить его другим.
2) Возможность перезапуска микроядра без остановки планировщиков. Например, можно перевести все процессы на другое физическое устройство для замены оборудования.
3) Планировщики могут выполняться на отдельных процессорах/контролерах. Очень актуально для промышленного оборудования, которое часто требуется распределить в пространстве.
4) Из 3го вытекает возможность реализации RPC на уровне системных вызовов. Не надо будет использовать дополнительные middleware.
5) Возможно реализовать несколько алгоритмов планирования, работающих параллельно. Позволит легко переносить уже существующие проекты, подготовленные для определённого алгоритма.
6) При ошибках в планировщике достаточно будет перезапустить группу процессов с новым планировщиком. Возможно восстановление информации о состоянии группы до сбоя по информации от других планировщиков.

Идей по применению много, но создавать с нуля ядро ОС с системными библиотеками нет ресурсов, поэтому ковыряю ядро minix3. Что удастся реализовать, а что нет под вопросом. Надеюсь кому-то сама идея алгоритма пригодится. Ещё обдумываю возможность реализации в linux || *bsd; с GNU\Hurd должно быть проще. Ещё есть идея об увеличении адреса до 16 бит, что даст возможность однозначно сопоставлять PPID и адес (вместо групп будут сами процессы), но пока не придумал достойного применения такой схеме. Здесь буду размещать исходники и новости (сайт на домашнем компе, не всегда доступен).

Забыл дополнить, что для доведения алгоритма до полноты необходимо определить правило для установки ценности вершин графа и рассчитывать путь прохождения графа по алгоритму Дейкстры.
Буду моделировать с нормальным распределением ценности графов и проведу тесты с самыми распространёнными пакетами, которые смогу портировать.
Реклама
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее

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

    0
    Ничего не понятно.
      0
      Действительно. Почитал сайтик ваш, помочь даж хочется, но куда уж мне, ламеру))
        0
        А должно?
          0
          Ну, как бы занимаюсь embedded порд самые разные платформы и не раз делал закат солнца вручную — самопальные планировщики и ядра, в т.е. под реальное время.
            0
            Когда будет конкретная реализация с полной спецификацией алгоритма напишу новую заметку. Пока собираю материал и продумываю детали. Может проблема в том, что я относительно слабо владею терминологией в данной области, так как старюсь максимально оградиться от знания существующих алгоритмов и реализаций? Когда будут закончены наработки — буду сравнивать и знакомится, а пока стараюсь максимально самобытно всё делать, важен, так скажем, сам процес.
        0
        Старался))
          0
          Между прочим, из всех книг по архитектуре ОС, по моему, только в Таненбауме(«Современные операционные системы») наиболее глубоко и детально описывается работа планировщика процессов, памяти, IO, отлично раскрыты вопросы синхронизации потоков/процессов, предотвращения взаимоблокировок etc
          Также есть конкретные примеры реализации(Linux, Windows Vista)

          В общем до сих пор под впечатлением от этой книги :)
            0
            Ну, он не даром получил грант на развитие minix3. Книга, несомненно, войдёт в историю.
            0
            Автор, а вы не смотрели в сторону QNX? Мне некоторое время доводилось под нее писать, весьма приятная ОС, да и реального времени к тому же :) Исходники открыты.

            Minix, насколько я понимаю, больше академический проект, QNX же вполне боевая система.
              0
              Смотрел, но исходники уже закрыты, как я понял. Их же недавно RIM купили. А в minix-е уже довольно много реализовано (в том числе и портированы ИКС-ы, основной компилятор Clang) и обилие комментариев доставляет много радости.

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

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