планировщик O(1)

Планировщик O(1) (произносится как «Планировщик O из 1», «Планировщик Big O из 1» или «Планировщик с постоянным временем») — это ядра конструкция планирования , которая может планировать процессы в течение постоянного промежутка времени, независимо от того, сколько процессы выполняются в операционной системе . Это улучшение по сравнению с ранее использовавшимися планировщиками O(n) , которые планируют процессы на период времени, который линейно масштабируется в зависимости от количества входных данных.

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

Планировщик O(1) использовался в выпусках Linux с 2.6.0 по 2.6.22 (2003–2007), после чего он был заменен Completely Fair Scheduler .

Обзор

Планировщик Linux был полностью переработан с выпуском ядра 2.6 в 2003 году. ^[1]^[2] Новый планировщик получил название планировщик O(1). Алгоритм, используемый планировщиком O(1), опирается на массивы активных и истекших процессов для достижения постоянного времени планирования. Каждому процессу дается фиксированный квант времени, после чего он вытесняется и перемещается в массив с истекшим сроком действия. Как только все задачи из активного массива исчерпают свой квант времени и будут перемещены в истекший массив, происходит переключение массива. Поскольку доступ к массивам осуществляется только через указатель, переключение между ними происходит так же быстро, как замена двух указателей. ^[3] Этот переключатель делает активный массив новым пустым массивом с истекшим сроком действия, а массив с истекшим сроком действия становится активным массивом.

Об обозначении O(1)

Алгоритм оперирует входными данными, и размер этих входных данных обычно определяет время его работы. Обозначение Big O используется для обозначения скорости роста времени выполнения алгоритма в зависимости от объема входных данных. Например, время работы алгоритма O(n) увеличивается линейно с ростом входного размера n. ^[4] Время работы O(n ²) алгоритм растет квадратично . Если можно установить постоянную верхнюю границу времени работы алгоритма, то оно считается равным O(1) (можно сказать, что он работает за «постоянное время»). То есть алгоритм O(1) гарантированно завершится за определенное время независимо от размера входных данных. ^[5]

Улучшение производительности планировщика Linux

Планировщик Linux 2.6.8.1 не содержал алгоритмов, которые работали бы за время хуже, чем O(1). ^[6] То есть каждая часть планировщика гарантированно выполняется в течение определенного постоянного промежутка времени независимо от количества задач в системе. Это позволяет ядру Linux эффективно обрабатывать огромное количество задач без увеличения накладных расходов по мере роста числа задач. В планировщике Linux 2.6.8.1 есть две ключевые структуры данных, которые позволяют ему выполнять свои обязанности за время O(1), и его конструкция вращается вокруг них: очереди выполнения и массивы приоритетов.

Проблемы

Основная проблема этого алгоритма — сложная эвристика, используемая для маркировки задачи как интерактивной или неинтерактивной. Алгоритм пытается идентифицировать интерактивные процессы, анализируя среднее время сна (количество времени, которое процесс проводит в ожидании ввода). Процессы, которые находятся в режиме ожидания в течение длительного периода времени, вероятно, ожидают ввода пользователя, поэтому планировщик предполагает, что они интерактивны. Планировщик дает бонус к приоритету интерактивным задачам (для повышения производительности), одновременно наказывая неинтерактивные задачи снижением их приоритета. Все расчеты по определению интерактивности задач сложны и подвержены возможным просчетам, ^{[ нужна ссылка ]} вызывая неинтерактивное поведение интерактивного процесса.

Замена

В версии 2.6.23 (октябрь 2007 г.) был представлен планировщик Completely Fair , заменяющий планировщик O (1). По словам Инго Молнара, автора CFS, его базовую конструкцию можно резюмировать одним предложением: «CFS в основном моделирует «идеальный, точный многозадачный процессор» на реальном оборудовании». ^[7]

См. также

Временная сложность
Brain Fuck Scheduler (BFS) - планировщик процессов, разработанный для ядра Linux в августе 2009 года в качестве альтернативы CFS и планировщику O (1).

Ссылки

^ «Представляем ядро 2.6 | Linux Journal» . www.linuxjournal.com . Проверено 19 июля 2019 г.
^ Чандандип Сингх Пабла (1 августа 2009 г.). «Совершенно честный планировщик» . Linux-журнал . Проверено 9 сентября 2014 г.
^ Роберт Лав. «Планировщик процессов Linux» . Проверено 9 сентября 2014 г.
^ ДВС. «Неофициальное введение в нотацию O(N)» . Проверено 9 сентября 2014 г.
^ Роб Белл. «Руководство для начинающих по нотации Big O» . Проверено 9 сентября 2014 г.
^ Джош Аас. «Понимание планировщика ЦП Linux 2.6.8.1» (PDF) . Гитхаб . Проверено 9 сентября 2014 г.
^ < [адрес электронной почты защищен] >, Инго Молнар. «Архив Linux-Kernel: Re: справедливое использование часов в CFS» . lkml.iu.edu . Проверено 30 августа 2018 г.

Внешние ссылки

Понимание планировщика ЦП Linux 2.6.8.1 ; Джош Аас, 17 февраля 2005 г.
HybridThreads (Hthreads). Архивировано 11 мая 2008 г. в Wayback Machine ; POSIX-совместимая ОС, разработанная совместно аппаратно и программно, с планировщиком O (1), реализованным аппаратно.
Внутри планировщика Linux ; Написано М. Тимом Джонсом, статья IBM DeveloperWorks
Дэвид Мосбергер. «Более подробный обзор планировщика Linux O(1)» . Исследовательские лаборатории HP. Архивировано из оригинала 16 марта 2012 года.

[1] «Представляем ядро 2.6 | Linux Journal» . www.linuxjournal.com . Проверено 19 июля 2019 г.

[2] Чандандип Сингх Пабла (1 августа 2009 г.). «Совершенно честный планировщик» . Linux-журнал . Проверено 9 сентября 2014 г.

[3] Роберт Лав. «Планировщик процессов Linux» . Проверено 9 сентября 2014 г.

[4] ДВС. «Неофициальное введение в нотацию O(N)» . Проверено 9 сентября 2014 г.

[5] Роб Белл. «Руководство для начинающих по нотации Big O» . Проверено 9 сентября 2014 г.

[6] Джош Аас. «Понимание планировщика ЦП Linux 2.6.8.1» (PDF) . Гитхаб . Проверено 9 сентября 2014 г.

[7] < [адрес электронной почты защищен] >, Инго Молнар. «Архив Linux-Kernel: Re: справедливое использование часов в CFS» . lkml.iu.edu . Проверено 30 августа 2018 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]