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

Расположение «планировщика O (1)» (a планировщик процессов ) в упрощенной структуре Ядро Linux.

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

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

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

Обзор

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

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

Основная статья: Обозначение Big O

An алгоритм работает над входом, и размер этого входа обычно определяет время его работы. Обозначение Big O используется для обозначения скорости роста времени выполнения алгоритма в зависимости от количества вводимых данных. Например, время работы алгоритма O (n) линейно увеличивается с увеличением размера входных данных n.[4] Время работы O (nˆ2) алгоритм растет квадратично. Если возможно установить постоянную верхнюю границу времени работы алгоритма, оно считается равным 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 г.) Полностью честный планировщик был представлен, заменив планировщик O (1). По словам Инго Молнара, автора CFS, его основной дизайн можно описать одним предложением: «CFS в основном моделирует« идеальный, точный многозадачный процессор »на реальном оборудовании».[7]

Смотрите также

Рекомендации

  1. ^ «Представляем ядро ​​2.6 | Linux Journal». www.linuxjournal.com. Получено 2019-07-19.
  2. ^ Чандандип Сингх Пабла (1 августа 2009 г.). "Совершенно честный планировщик". журнал Linux. Получено 2014-09-09.
  3. ^ Роберт Лав. «Планировщик процессов Linux». Получено 2014-09-09.
  4. ^ DWS. "Неформальное введение в обозначение O (N)". Получено 2014-09-09.
  5. ^ Роб Белл. "Руководство для начинающих по нотации Big O". Получено 2014-09-09.
  6. ^ Джош Аас. «Понимание планировщика ЦП Linux 2.6.8.1» (PDF). Получено 2014-09-09.
  7. ^ , Инго Мольнар. "Linux-Kernel Archive: Re: честное использование времени в CFS". lkml.iu.edu. Получено 2018-08-30.

внешняя ссылка