Планирование процессов в UNIX-подобных системах

Содержание

1. Введение в планирование процессов3
2. 2. Классификация алгоритмов планирования5
3. 3. Критерии эффективности планирования7
4. 4. Реализация планировщика в UNIX10

Введение в планирование процессов

Операционная система нужна, чтобы делить ограниченные ресурсы между множеством задач. Главный из них, процессорное время, распределяется через планирование процессов. Это механизм, который каждый раз решает, какой из готовых процессов получит управление. Если бы его не было, компьютер мог бы выполнять только одну программу за раз, и мультипрограммный режим потерял бы всякий смысл.

У планировщика несколько целей, и они часто противоречат друг другу. Поэтому его работа сводится к поиску компромисса. Система должна быть справедливой, чтобы ни один процесс не голодал в ожидании процессора. Но одновременно нужна эффективность: все ядра должны быть загружены без простоев. Для интерактивных программ критично время отклика, чтобы между нажатием клавиши и реакцией не было заметной паузы. А для серверов важнее пропускная способность, то есть сколько задач успевает завершиться за единицу времени. Улучшение одного показателя почти всегда ухудшает другой, поэтому конкретная политика планирования выбирается разработчиками под определенный тип нагрузки.

Разобраться в планировании проще, если посмотреть на жизненный цикл процесса. В любой системе процесс проходит несколько состояний. Сначала он «новый», потом попадает в очередь «готовых» и ждет процессора. Когда планировщик его выбирает, процесс переходит в состояние «выполняется». Если он запрашивает ввод-вывод или ждет события, то блокируется и оказывается в состоянии «ожидания». После завершения работы он переходит в состояние «завершен». Особенно важен переход между «выполняется» и «готов», потому что он требует переключения контекста. Это процедура сохранения состояния одного процесса (регистры, счетчик команд, данные) и загрузки состояния другого. Само переключение ничего полезного не делает, это чистые накладные расходы. Чем чаще оно происходит, тем ниже

производительность.

В UNIX-подобных системах планированием занимается ядро. У него полный доступ к аппаратуре, и оно обрабатывает прерывания от таймера. Благодаря этому поддерживается многозадачность: на одном процессоре десятки программ выполняются почти одновременно, и это лишь иллюзия. Ядро периодически прерывает текущий процесс, когда истекает квант времени, и передает управление планировщику. Тот решает, что делать с задачей дальше. Такая схема появилась еще в ранних версиях UNIX и описана в классической работе Таненбаума. Она остается основой для всех современных производных систем, включая Linux и BSD. Решение о том, какой процесс получит процессор, принимается на основе данных о состоянии всех процессов в системе, а не случайным образом. Именно это отличает осмысленное планирование от простого циклического перебора.

2. Классификация алгоритмов планирования

Деление алгоритмов по способу взаимодействия с выполняющимся процессом лежит в основе любой классификации. Невытесняющий алгоритм однажды назначает процессу процессор и ждет, пока тот сам освободит его: завершится, перейдет в состояние ожидания или выполнит системный вызов. Пока процесс работает, планировщик остается пассивным наблюдателем. Такая схема проста и предсказуема, но она дорого обходится системе, если процесс занят долгими вычислениями, а в очереди стоит интерактивная задача, требующая немедленного ответа пользователю.

Вытесняющий алгоритм действует иначе. Он позволяет планировщику в любой момент снять процесс с процессора, например, по истечении выделенного кванта времени или при появлении более приоритетной задачи. Решение о переключении принимает ядро, а не сам процесс. Это дает системе рычаги управления: она может гарантировать отклик для одних задач и ограничивать аппетиты других. Именно вытесняющие механизмы лежат в основе современных многозадачных операционных систем, где пользователь ожидает мгновенной реакции интерфейса на фоне фоновых вычислений.

Второй значимый признак классификации связан с приоритетами. Статический приоритет назначается процессу один раз и остается неизменным на протяжении всей его жизни. Такая схема удобна, когда важность задач известна заранее и не меняется со временем. Динамический приоритет, напротив, пересчитывается планировщиком в зависимости от поведения процесса. Интерактивные задачи, которые часто ожидают ввода, получают повышение приоритета, чтобы быстрее реагировать на действия пользователя. Вычислительные процессы, долго занимающие процессор, наоборот, понижаются, уступая место более «отзывчивым» соседям. Подобная адаптация позволяет системе подстраиваться под реальную нагрузку, не требуя вмешательства администратора.

Третий критерий классификации связан с целевой нагрузкой системы. Алгоритмы, ориентированные на пакетную обработку, рассчитаны на выполнение длинных вычислительных задач без участия человека. Здесь важна максимальная загрузка процессора и высокая пропускная способность, а время реакции не играет роли. Интерактивные алгоритмы ставят во главу угла отзывчивость: пользователь должен получать ответ на свои действия почти мгновенно. Смешанные системы, такие как современные серверы и персональные компьютеры, сочетают оба подхода, переключаясь между режимами в зависимости от текущей активности.

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

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

3. Критерии эффективности планирования

Любой алгоритм планирования оценивается не сам по себе, а по тому, насколько хорошо он справляется с поставленными задачами. Чтобы сравнивать разные подходы, нужны измеримые показатели. Их принято называть критериями эффективности. Именно они превращают планирование из искусства в инженерную дисциплину.

Основных метрик пять: время ожидания, время отклика, время оборота, пропускная способность и загрузка процессора. Каждая из них отвечает на свой вопрос о поведении системы. Зачастую улучшение одной метрики ухудшает другую, и понимание этих противоречий важнее, чем запоминание определений.

Время ожидания считается самым простым показателем. Это суммарное время, которое процесс провел в очереди готовых к выполнению, ожидая своей очереди на процессор. Сюда не входит время самого выполнения или операции ввода-вывода. Представьте процесс, который выполнялся 5 секунд, но до этого простоял в очереди 30 секунд. Его время ожидания равно 30 секундам. Эта метрика удобна тем, что она напрямую показывает, насколько справедливо распределяется процессорное время, и не зависит от того, как долго процесс реально работает.

Время отклика критично для интерактивных систем. Это интервал от момента, когда пользователь отправил запрос, до момента, когда система выдала первый ответ. Не полный результат, а именно первый сигнал. В 1960-х годах исследователи Массачусетского технологического института, работая над системой CTSS, эмпирически выяснили: если реакция системы занимает больше 100 миллисекунд, пользователь начинает ощущать задержку. Поэтому для текстовых редакторов или терминалов важнее не общее время выполнения задачи, а скорость появления курсора или эха на экране. Длинный фоновый расчет может идти минутами, но каждый ввод символа должен обрабатываться мгновенно.

Время оборота, это полный жизненный цикл процесса: от момента его появления в системе до полного завершения, включая все ожидания и выполнение. Для пакетных заданий, которые запускаются без участия человека, именно эта метрика часто является главной. Если научный расчет занял 40 минут, из которых 10 минут процесс ждал ресурсы, время оборота составило 40 минут. Пользователю пакетного сервера неважно, как именно распределялся процессор, ему важен итоговый результат в срок.

Пропускная способность измеряет количество процессов, завершенных за единицу времени. Например, веб-сервер, обрабатывающий 5000 запросов в секунду, имеет более высокую пропускную способность, чем сервер, обрабатывающий 3000. Эта метрика отражает общую производительность системы, но у нее есть коварная особенность. Можно увеличить пропускную способность, обрабатывая только короткие задачи и откладывая длинные. Формально показатель вырастет, но система станет несправедливой по отношению к сложным вычислениям.

Загрузка процессора показывает, какой процент времени процессор занят полезной работой, а не простаивает. Идеальное значение близко к 100%, но на практике это опасно. Если загрузка достигает 95% и выше, очереди процессов растут лавинообразно, а время отклика резко увеличивается. Исследования показывают, что при загрузке выше 80% система начинает деградировать нелинейно: небольшое увеличение нагрузки приводит к кратному росту задержек.

Выбор приоритетного критерия зависит от типа системы, и это ключевой момент. Для пакетной обработки, где задачи выполняются ночью без участия оператора, важнее пропускная способность и загрузка процессора. Никого не волнует, что конкретный процесс ждал 20 минут, если общая партия заданий завершилась быстрее. Для интерактивных систем, где за терминалом сидит человек, на первое место выходит время отклика. Загрузка процессора в 70% здесь

лучше, чем 99%, если это обеспечивает мгновенную реакцию на действия пользователя. Системы реального времени, управляющие станками или автопилотом, вообще игнорируют пропускную способность, требуя гарантированного времени отклика в пределах жесткого дедлайна.

На практике планировщики редко оптимизируют одну метрику. Современные ОС, включая Linux, пытаются найти баланс, но сам баланс всегда смещен в зависимости от назначения системы. Сервер баз данных настраивается иначе, чем рабочая станция дизайнера, хотя оба используют одно ядро. Понимание критериев позволяет администратору осознанно выбирать параметры планировщика, а разработчику проектировать алгоритмы, которые дают предсказуемое поведение в нужных сценариях.

4. Реализация планировщика в UNIX

От классификации и метрик логично перейти к тому, как эти идеи выглядят в реальном коде ядра. В UNIX-подобных системах планировщик устроен не как монолитная сущность, а как набор структур данных и правил их обработки. Основа этой конструкции, очередь готовых процессов. Правда, это не единый список. Процессы сгруппированы по приоритетам, и для каждой группы заведена отдельная очередь.

Ядро берёт на выполнение процесс из очереди с самым высоким приоритетом. И только когда эта очередь пустеет, планировщик переходит к следующему уровню. Такая иерархия даёт гарантию, что критичные задачи (например, обработка прерываний) получат процессор раньше, чем фоновые вычисления. Однако жёсткая привязка к статическому приоритету быстро привела бы к голоданию низкоприоритетных процессов. Поэтому в UNIX приоритеты сделали динамическими. Система непрерывно следит за поведением процессов и корректирует их «вес». Интерактивный процесс, который часто блокируется в ожидании ввода с клавиатуры, получает повышение приоритета, чтобы быстро реагировать на действия пользователя. А вычислительный процесс, который подолгу занимает процессор без прерываний, наоборот, понижается, уступая дорогу остальным. Этот механизм, реализованный ещё в классических версиях UNIX, даёт приемлемое время отклика в интерактивных сессиях, при этом пакетные задачи не вытесняются полностью.

Переход к многопроцессорным архитектурам добавил планировщику новое измерение. В однопроцессорной системе задача сводится к выбору следующего процесса из общей очереди. Здесь же нужно решить, на каком именно ядре его запускать. Простейший подход с общей очередью создаёт узкое место: одновременный доступ нескольких процессоров к одной структуре данных требует синхронизации, а это снижает производительность. Современные системы, например Linux, используют per-CPU

очереди. У каждого процессора своя очередь, что минимизирует конкуренцию за блокировки. Но тут возникает проблема дисбаланса: один процессор может быть перегружен, пока другой простаивает. Чтобы решить эту задачу, планировщик периодически выполняет балансировку нагрузки, мигрируя процессы с загруженных ядер на свободные. Процесс этот недешёвый: миграция требует переноса контекста и инвалидации кэшей.

Реализация планировщика в современном Linux, известная как CFS (Completely Fair Scheduler), отошла от классических очередей с приоритетами. Вместо них моделируется «идеальный мультиплексированный процессор», который выполняет все процессы одновременно с равной скоростью. На практике это достигается хранением готовых задач в красно-чёрном дереве. Ключом в этом дереве служит vruntime, виртуальное время выполнения процесса, учитывающее его приоритет (nice value). Чем меньше vruntime у процесса, тем дольше он был обделён процессорным временем, и тем левее он находится в дереве. Следующим для выполнения всегда выбирается крайний левый узел, то есть процесс с наименьшим накопленным временем. Красно-чёрное дерево даёт логарифмическую сложность операций вставки, удаления и поиска минимального элемента, что критично для систем с тысячами активных процессов. Динамическая приоритизация в CFS реализована не через явное изменение приоритета, а через накопление vruntime: интерактивные процессы, которые часто спят, накапливают меньше виртуального времени и потому чаще выбираются планировщиком при пробуждении.