Альтернатива алгоритма EDF

Question

Я хочу знать, есть ли любые альтернативы Earliest Deadline First (EDF) алгоритм планирования. Если да, укажите ссылочные ссылки.

Спасибо.

Answer 1

График сроков может быть разделен на две категории: 1) как думает сообщество в реальном времени; и 2), о чем думает сообщество теории планирования. Категория 1 является подмножеством категории 2. Большинство специалистов в области вычислительной техники в реальном времени не знают о категории 2.

Основное отличие состоит в том, что категория 1 предполагает относительно простой частный случай, когда крайние сроки встречаются или пропущены, и что отсутствует крайние сроки - это сбой, поэтому критерий оптимальности планирования соответствует всем предельным срокам (так называемый «жесткий» в реальном времени). Самый ранний конечный срок (EDF) является наиболее распространенным алгоритмом планирования сроков в 1-й категории. Существует огромное количество литературы по планированию сроков для категории 1 - например, в материалах симпозиума IEEE в режиме реального времени. Хорошей книгой является Станкович и др. Deadline Scheduling for Real-Time Systems - EDF and Related Algorithms.

AFAIK, в настоящее время нет существующих продуктов COTS в режиме реального времени, которые осуществляют планирование сроков, в частности EDF. Было предпринято несколько коммерческих продуктов (например, DEC, IBM), но они отказались из-за различных трудностей, таких как интеграция EDF с другим управлением ресурсами (например, синхронизаторы, незапланированные действия) в ОС при сохранении обратной совместимости. Решением является планирование сроков (EDF и другие алгоритмы) как неотъемлемая часть ОС с нуля.Я знаю о трех продуктах ОС COTS в режиме реального времени, которые сделали это, ни одна из которых не вышла на рынок по организационным причинам, не связанным с ОС: DECs Libra, IBM OS/2 для PowerPC (сделано в сотрудничестве с DEC) и Open OS Foundation Foundation OSF-1 Mk7.3a (выполняется в сотрудничестве с DEC и IBM). Некоторые исследовательские ОС, разработанные и реализованные с помощью голого оборудования (например, Jensen's Alpha at CMU), смогли включить планирование сроков. Alpha воспользовалась полной свободой, позволяя подключать произвольные алгоритмы планирования, включая EDF и Utility Acrual. Другие исследовательские операционные системы стремились увеличить Linux (см. Проект ChronOS от VA Tech, цитируемый постом Джонатана Андерсона). ChronOS ограничен Linux-основанием, но также поддерживает алгоритмы планирования начисления полезности.

Категория 2 охватывает всю тему планирования сроков в целом, из которых категория 1 является более легким подмножеством. В частности, категория 2 признает понятия ранности и опоздания в отношении крайнего срока. Критерии оптимальности планирования включают в себя минимизацию количества пропущенных крайних сроков, минимизацию средней задержки, минимальную максимальную задержку и многие (любые) другие. Технически категория 2 за вычетом подкатегории категории 1 является «мягкой» в режиме реального времени », хотя практикующие в реальном времени и даже исследователи используют много разных неточных и неточных описаний термина« мягкий »режим реального времени. является расписанием по категории 1. Однако он более реалистичен и более широко применим, используется во многих отраслях промышленности (например, в сфере транспорта, производства и т. д.). Существует еще больший объем литературы, чем для категории 1. Хорошим учебником является Pindo's Scheduling: Theory, Algorithms, and Systems .

Answer 2

Ядро акции Linux поддерживает только следующие политики планирования (для CPU):

• SCHED_FIFO - FIFO в режиме реального времени приоритет планирования
• SCHED_RR - Круговой в режиме реального времени приоритет планирования
• SCHED_OTHER - не в реальном времени, лучшие усилия планирования

Особенно отсутствующий учитывая ваш вопрос EDF, или действительно любой мертвый линейный планировщик. Почему нет? Ну, число драйверов, желающих сделать анализ, необходимых для использования планировщика сроков, и осложнений с его интеграцией с другими политиками планирования, могут быть драйверами. LWN article does discuss deadline scheduling in Linux, около 2009 года.

Некоторые попытки были направлены на предоставление дополнительных политик планирования для Linux. Несколько хороших примеров - это LitmusRT project и Virginia Tech's ChronOS project. LitmusRT фокусируется на семействе мягких планировщиков реального времени и сопровождающих примитивов синхронизации. ChronOS находится в том же домене, но в основном сосредоточен на планировании с помощью Utility-Accrual (UA) (см., Например, this thesis и time-utility functions на странице Дженсена) и политик синхронизации.

Существует также недавняя реализация планировщика EDF (которую я не использовал и не заметил, пока не ответил на этот вопрос.) "Evidence" EDF scheduler.

Существуют также коммерческие производители linux, которые имеют другие реализаторы планировщика реального времени. Их доступность может быть немного запутанной. Примером может служить Concurrent's RedHawk linux, которая включает в себя политику планирования с учетом времени. Подробная информация об ОС приведена в документе datasheet. RedHawk используется во многих приложениях DoD в режиме реального времени и распределенных.