Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Планировщик процессов ядра Linux 2.6
Historical Linux 2.6 kernel process scheduler
Планировщик O(1) (произносится как "O от 1", "Большой O от 1" или "планировщик с постоянным временем") — это архитектура планирования ядра, способная планировать процессы за постоянное время, независимо от количества запущенных в операционной системе процессов. Это улучшение по сравнению с ранее использовавшимися планировщиками O(n), время работы которых масштабируется линейно в зависимости от количества процессов. В области операционных систем реального времени ключевым является детерминированное выполнение, и планировщик O(1) способен предоставлять услуги планирования с фиксированной верхней границей времени выполнения. Планировщик O(1) использовался в версиях Linux 2.6.0 – 2.6.22 (2003–2007), после чего был заменен на Completely Fair Scheduler (Полностью справедливый планировщик).
An O(1) scheduler (pronounced "O of 1 scheduler", "Big O of 1 scheduler", or "constant time scheduler") is a kernel scheduling design that can schedule processes within a constant amount of time, regardless of how many processes are running on the operating system. This is an improvement over previously used O(n) schedulers, which schedule processes in an amount of time that scales linearly based on the amounts of inputs. In the realm of real time operating systems, deterministic execution is key, and an O(1) scheduler is able to provide scheduling services with a fixed upper bound on execution times. The O(1) scheduler was used in Linux releases 2.6.0 thru 2.6.22 (2003 2007), at which point it was superseded by the Completely Fair Scheduler.
Обзор
Linux scheduler был полностью переработан с выпуском ядра 2.6 в 2003 году. Новый планировщик получил название O(1)-планировщик. Алгоритм, используемый O(1)-планировщиком, основывается на активных и просроченных массивах процессов для достижения постоянного времени планирования. Каждому процессу выделяется фиксированный квант времени, после чего он прерывается и перемещается в просроченный массив. Когда все задачи из активного массива исчерпывают свой квант времени и перемещаются в просроченный массив, происходит переключение массивов. Поскольку доступ к массивам осуществляется только через указатели, переключение происходит так же быстро, как обмен двумя указателями. Это переключение делает активный массив новым пустым просроченным массивом, а просроченный массив становится активным.
The Linux scheduler was overhauled completely with the release of kernel 2.6 in 2003. The new scheduler was called the O(1) scheduler. The algorithm used by the O(1) scheduler relies on active and expired arrays of processes to achieve constant scheduling time. Each process is given a fixed time quantum, after which it is preempted and moved to the expired array. Once all the tasks from the active array have exhausted their time quantum and have been moved to the expired array, an array switch takes place. Because the arrays are accessed only via pointer, switching them is as fast as swapping two pointers. This switch makes the active array the new empty expired array, while the expired array becomes the active array.
О O(1) обозначении
Алгоритм оперирует с входными данными, и размер этих данных обычно определяет время его выполнения. Нотация «Большое О» используется для обозначения скорости роста времени выполнения алгоритма в зависимости от объема входных данных. Например, время выполнения алгоритма O(n) увеличивается линейно с ростом размера входных данных n. Время выполнения алгоритма O(n²) растет квадратично. Если возможно установить постоянную верхнюю границу времени выполнения алгоритма, он считается O(1) (можно сказать, что он выполняется за «постоянное время»). То есть, алгоритм O(1) гарантированно завершается за определенное время, независимо от размера входных данных.
An algorithm operates over an input, and the size of that input usually determines its running time. Big O notation is used to denote the growth rate of an algorithm's execution time based on the amount of input. For example, the running time of an O(n) algorithm increases linearly as the input size n grows. The running time of an O(n) algorithm grows quadratically. If it is possible to establish a constant upper bound on the running time of an algorithm, it is considered to be O(1) (one might say it runs in "constant time"). That is, an O(1) algorithm is guaranteed to complete in a certain amount of time regardless of the size of the input.
Улучшение производительности планировщика Linux
Планировщик Linux 2.6.8.1 не содержал алгоритмов, время выполнения которых превышало бы O(1). То есть, каждая часть планировщика гарантированно выполняется за определенное постоянное время, независимо от количества задач в системе. Это позволяет ядру Linux эффективно обрабатывать огромное число задач без увеличения накладных расходов по мере их роста. В планировщике Linux 2.6.8.1 две ключевые структуры данных обеспечивают выполнение задач за время O(1), и вокруг них строится вся его конструкция: очереди выполнения и массивы приоритетов.
The Linux 2.6.8.1 scheduler did not contain any algorithms that run in worse than O(1) time. That is, every part of the scheduler is guaranteed to execute within a certain constant amount of time regardless of how many tasks are on the system. This allows the Linux kernel to efficiently handle massive numbers of tasks without increasing overhead costs as the number of tasks grows. There are two key data structures in the Linux 2.6.8.1 scheduler that allow for it to perform its duties in O(1) time, and its design revolves around them: runqueues and priority arrays.
Проблемы
Основная проблема этого алгоритма — сложная эвристика, используемая для определения задачи как интерактивной или неинтерактивной. Алгоритм пытается выявить интерактивные процессы, анализируя среднее время ожидания (время, в течение которого процесс ожидает ввода). Процессы, которые долгое время находятся в состоянии ожидания, вероятно, ждут ввода от пользователя, поэтому планировщик считает их интерактивными. Планировщик предоставляет приоритетный бонус интерактивным задачам (для повышения производительности) и снижает приоритет неинтерактивных задач. Все вычисления, определяющие интерактивность задач, сложны и подвержены потенциальным ошибкам, что может привести к неинтерактивному поведению интерактивного процесса.
The main issue with this algorithm is the complex heuristics used to mark a task as interactive or non interactive. The algorithm tries to identify interactive processes by analyzing average sleep time (the amount of time the process spends waiting for input). Processes that sleep for long periods of time probably are waiting for user input, so the scheduler assumes they're interactive. The scheduler gives a priority bonus to interactive tasks (for better throughput) while penalizing non interactive tasks by lowering their priorities. All the calculations to determine the interactivity of tasks are complex and subject to potential miscalculations, causing non interactive behavior from an interactive process.
Замена
В версии 2.6.23 (октябрь 2007 года) был представлен Полностью Справедливый Планировщик, заменивший планировщик O(1). По словам Инго Молнара, автора CFS, основная идея его разработки может быть выражена одним предложением: "CFS по сути моделирует 'идеальный, точный многозадачный процессор' на реальном аппаратном обеспечении".
In 2.6.23 (October 2007), the Completely Fair Scheduler was introduced, replacing the O(1) Scheduler. According to Ingo Molnar, the author of the CFS, its core design can be summed up in single sentence: "CFS basically models an 'ideal, precise multitasking CPU' on real hardware."