Закончив изучение Таненбаума и ковыряние ядра Linux решил, что надо заняться чем-то дельным. По личным мотивам решил переделать ядро minix3 под планирование в жёстком реальном времени. Множество существующих алгоритмов планирования ввели меня в уныние, тем более, что хочется сделать ОС максимально универсальной и гибкой. Зацикленность на клиент-серверной модели привели к идеи о вынесении из ядра ОС механизмов планирования и разделение процессов на группы, управляемые: каждая своим планировщиком (в режиме ядра оставить только обработку deadline).
Основная проблема, которая стала очевидной сразу же — это выбор математической модели для построения алгоритма планирования. Очевидно, что подход разделения общего ресурса можно рассмотреть в аналогии с сетевыми протоколами разделения общего физического пространства.
Для вдохновения были рассмотрены алгоритмы IPv4 адресации и протоколы динамической маршрутизации (RIP1\2, OSPF)
Итак, сам алгоритм:
По аналогии с IP адресацией потоки/процессы планирования описываем номером и маской (как подсети), а сами группы только номером (целевые точки). В зависимости от реализации процессов, передаём данные о процессах, времени их выполнения, приоритетах и прочее между планировщиками групп. В моих примерах используется адресация «байт адреса / байт маски». Всего до 255 групп процессов с возможностью запустить до 8ми контролирующих группу планировщиков, суммарно до 510 процессов планировщиков.
Так как развиваю эту идею для ОС реального времени, то и все идеи применения связаны с отказоустойчивостью и предсказуймостью.
Из зарисовки можно понять основные идеи применения:
1) Передача процессов между планировщиками. Например, при срабатывании wathcdog можно перевести процесс из режима мягко реального времени в жёсткое или при зацикливании одного процесса можно подменить его другим.
2) Возможность перезапуска микроядра без остановки планировщиков. Например, можно перевести все процессы на другое физическое устройство для замены оборудования.
3) Планировщики могут выполняться на отдельных процессорах/контролерах. Очень актуально для промышленного оборудования, которое часто требуется распределить в пространстве.
4) Из 3го вытекает возможность реализации RPC на уровне системных вызовов. Не надо будет использовать дополнительные middleware.
5) Возможно реализовать несколько алгоритмов планирования, работающих параллельно. Позволит легко переносить уже существующие проекты, подготовленные для определённого алгоритма.
6) При ошибках в планировщике достаточно будет перезапустить группу процессов с новым планировщиком. Возможно восстановление информации о состоянии группы до сбоя по информации от других планировщиков.
Идей по применению много, но создавать с нуля ядро ОС с системными библиотеками нет ресурсов, поэтому ковыряю ядро minix3. Что удастся реализовать, а что нет под вопросом. Надеюсь кому-то сама идея алгоритма пригодится. Ещё обдумываю возможность реализации в linux || *bsd; с GNU\Hurd должно быть проще. Ещё есть идея об увеличении адреса до 16 бит, что даст возможность однозначно сопоставлять PPID и адес (вместо групп будут сами процессы), но пока не придумал достойного применения такой схеме. Здесь буду размещать исходники и новости (сайт на домашнем компе, не всегда доступен).
Забыл дополнить, что для доведения алгоритма до полноты необходимо определить правило для установки ценности вершин графа и рассчитывать путь прохождения графа по алгоритму Дейкстры.
Буду моделировать с нормальным распределением ценности графов и проведу тесты с самыми распространёнными пакетами, которые смогу портировать.
Основная проблема, которая стала очевидной сразу же — это выбор математической модели для построения алгоритма планирования. Очевидно, что подход разделения общего ресурса можно рассмотреть в аналогии с сетевыми протоколами разделения общего физического пространства.
Для вдохновения были рассмотрены алгоритмы IPv4 адресации и протоколы динамической маршрутизации (RIP1\2, OSPF)
Итак, сам алгоритм:
По аналогии с IP адресацией потоки/процессы планирования описываем номером и маской (как подсети), а сами группы только номером (целевые точки). В зависимости от реализации процессов, передаём данные о процессах, времени их выполнения, приоритетах и прочее между планировщиками групп. В моих примерах используется адресация «байт адреса / байт маски». Всего до 255 групп процессов с возможностью запустить до 8ми контролирующих группу планировщиков, суммарно до 510 процессов планировщиков.
Зарисовка к алгоритму
Так как развиваю эту идею для ОС реального времени, то и все идеи применения связаны с отказоустойчивостью и предсказуймостью.
Из зарисовки можно понять основные идеи применения:
1) Передача процессов между планировщиками. Например, при срабатывании wathcdog можно перевести процесс из режима мягко реального времени в жёсткое или при зацикливании одного процесса можно подменить его другим.
2) Возможность перезапуска микроядра без остановки планировщиков. Например, можно перевести все процессы на другое физическое устройство для замены оборудования.
3) Планировщики могут выполняться на отдельных процессорах/контролерах. Очень актуально для промышленного оборудования, которое часто требуется распределить в пространстве.
4) Из 3го вытекает возможность реализации RPC на уровне системных вызовов. Не надо будет использовать дополнительные middleware.
5) Возможно реализовать несколько алгоритмов планирования, работающих параллельно. Позволит легко переносить уже существующие проекты, подготовленные для определённого алгоритма.
6) При ошибках в планировщике достаточно будет перезапустить группу процессов с новым планировщиком. Возможно восстановление информации о состоянии группы до сбоя по информации от других планировщиков.
Идей по применению много, но создавать с нуля ядро ОС с системными библиотеками нет ресурсов, поэтому ковыряю ядро minix3. Что удастся реализовать, а что нет под вопросом. Надеюсь кому-то сама идея алгоритма пригодится. Ещё обдумываю возможность реализации в linux || *bsd; с GNU\Hurd должно быть проще. Ещё есть идея об увеличении адреса до 16 бит, что даст возможность однозначно сопоставлять PPID и адес (вместо групп будут сами процессы), но пока не придумал достойного применения такой схеме. Здесь буду размещать исходники и новости (сайт на домашнем компе, не всегда доступен).
Забыл дополнить, что для доведения алгоритма до полноты необходимо определить правило для установки ценности вершин графа и рассчитывать путь прохождения графа по алгоритму Дейкстры.
Буду моделировать с нормальным распределением ценности графов и проведу тесты с самыми распространёнными пакетами, которые смогу портировать.
