Планировщик O(n)¶

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

¶История

Планировщики с линейной сложностью исторически появились в первых многозадачных операционных системах, где количество одновременно выполняемых процессов было невелико (десятки, редко сотни). В 1960–1970-х годах, при разработке систем пакетной обработки и разделения времени (например, CTSS, MULTICS, ранние версии UNIX), использовались простые алгоритмы, такие как циклическое планирование (Round Robin) и планирование на основе приоритетов, которые требовали полного просмотра очереди готовых процессов для выбора следующего. С ростом числа процессов (до тысяч и десятков тысяч) в современных ОС (Linux, Windows, macOS) планировщики эволюционировали в сторону алгоритмов с меньшей сложностью (O(log n) или O(1)), однако концепция O(n) остаётся важной для понимания основ планирования и применяется в образовательных целях, а также в специализированных встраиваемых системах с ограниченным числом задач.

¶Классификация

Планировщики O(n) делятся на несколько основных типов в зависимости от критерия выбора процесса:

¶По типу очереди

• С неупорядоченной очередью — все готовые процессы хранятся в списке без сортировки. Выбор требует просмотра каждого элемента.
• С частично упорядоченной очередью — очередь поддерживается в некотором порядке (например, по приоритету), но для выбора всё равно требуется полный просмотр, если порядок не гарантирует мгновенного нахождения максимума/минимума.

¶По критерию выбора

• FCFS (First-Come, First-Served) — выбор первого пришедшего процесса. Реализуется через очередь FIFO, где выбор — O(1), но при перестроении очереди (например, при добавлении нового процесса с более высоким приоритетом) может потребоваться O(n).
• SJF (Shortest Job First) — выбор процесса с наименьшим оставшимся временем выполнения. Требует O(n) для нахождения минимума в неупорядоченном списке.
• Приоритетное планирование — выбор процесса с наивысшим приоритетом. При неупорядоченном списке — O(n).
• Round Robin — циклическое планирование с квантом времени. Выбор следующего процесса из круговой очереди — O(1), но при пересчёте приоритетов или динамическом изменении очереди может потребоваться O(n).

¶Устройство и характеристики

¶Структура данных

Основная структура данных для планировщика O(n) — односвязный или двусвязный список готовых процессов. Каждый элемент списка содержит:

• идентификатор процесса (PID);
• приоритет (числовое значение);
• оставшееся время выполнения (burst time);
• время поступления в очередь (arrival time);
• указатели на следующий/предыдущий элемент.

¶Алгоритм работы

Общий алгоритм выбора процесса в планировщике O(n) выглядит следующим образом:

1. Получить указатель на голову списка готовых процессов.
2. Пройти по всем элементам списка, сравнивая их по заданному критерию (например, минимальное оставшееся время).
3. Запомнить элемент, удовлетворяющий критерию, и его позицию.
4. После завершения обхода выбрать запомненный процесс для выполнения.
5. При необходимости удалить выбранный процесс из списка или переместить его в конец (для Round Robin).

¶Временная сложность

• Выбор процесса: O(n) — необходимо просмотреть все n элементов.
• Добавление нового процесса: O(1) — вставка в начало или конец списка.
• Удаление процесса: O(1) — если известен указатель на элемент, иначе O(n) для поиска.
• Пересчёт приоритетов: O(n) — если требуется обновить все элементы.

¶Пространственная сложность

O(n) — для хранения списка из n процессов.

¶Применение

¶В операционных системах

• Образовательные системы — для демонстрации принципов планирования в учебных курсах (например, в симуляторах планировщиков).
• Встраиваемые системы с малым числом задач — в микроконтроллерах и real-time системах, где количество задач не превышает нескольких десятков, а простота реализации важнее производительности.
• Легковесные ОС — например, ранние версии ОС для домашних компьютеров (MS-DOS, CP/M) не имели сложного планировщика, используя простые очереди.

¶В симуляторах и исследованиях

Планировщики O(n) часто используются в симуляторах алгоритмов планирования (например, в пакетах для моделирования операционных систем) для сравнения с более эффективными алгоритмами. Они позволяют наглядно продемонстрировать влияние количества процессов на время принятия решения.

¶Примеры

¶Пример 1: SJF с неупорядоченным списком

Пусть в очереди готовых процессов находятся три процесса с оставшимся временем: P1 (5 мс), P2 (2 мс), P3 (8 мс). Планировщик O(n) просматривает все три процесса, находит P2 с минимальным временем (2 мс) и выбирает его для выполнения. После выполнения P2 очередь пересматривается заново.

¶Пример 2: Приоритетное планирование

Процессы: P1 (приоритет 3), P2 (приоритет 1), P3 (приоритет 2). Планировщик проходит по списку, находит P2 с наивысшим приоритетом (1) и передаёт управление ему. Если приоритеты динамически меняются, каждый новый выбор требует O(n).

¶Критика

Основной недостаток планировщиков O(n) — низкая масштабируемость. При увеличении числа процессов до тысяч и более время выбора становится неприемлемо большим, что приводит к задержкам в работе системы. В современных операционных системах (Linux, Windows, macOS) используются планировщики с временной сложностью O(1) или O(log n), например, планировщик CFS (Completely Fair Scheduler) в Linux, основанный на красно-чёрных деревьях.

Дополнительные проблемы:

• Неравномерность времени отклика — при большом числе процессов время выбора может варьироваться, что критично для real-time систем.
• Сложность поддержки приоритетов — при динамическом изменении приоритетов требуется полный пересмотр очереди.
• Отсутствие гарантий справедливости — простые алгоритмы O(n) могут приводить к голоданию процессов с низким приоритетом.

¶Интересные факты

• В ранних версиях UNIX (1970-е годы) планировщик был основан на циклическом алгоритме с приоритетами, который требовал O(n) для пересчёта приоритетов каждую секунду.
• В операционной системе MINIX, созданной Эндрю Таненбаумом для учебных целей, использовался планировщик с линейным поиском, что было приемлемо для малого числа процессов.
• Термин «планировщик O(n)» часто используется в учебной литературе как противопоставление более эффективным алгоритмам, таким как планировщик О(1) в Linux 2.6.

¶Источники

• Таненбаум Э., Бос Х. Современные операционные системы. — 4-е изд. — СПб.: Питер, 2015.
• Silberschatz A., Galvin P. B., Gagne G. Operating System Concepts. — 10th ed. — Wiley, 2018.
• Love R. Linux Kernel Development. — 3rd ed. — Addison-Wesley, 2010.
• Stallings W. Operating Systems: Internals and Design Principles. — 9th ed. — Pearson, 2017.