Какие алгоритмы планирования ресурсов в linux ты знаешьdevops-43

В Linux существует несколько ключевых алгоритмов планирования ресурсов, которые можно разделить на две основные категории: планировщики процессов (CPU) и планировщики ввода-вывода (I/O). Рассмотрим их подробно.

1. Планировщики процессов

Completely Fair Scheduler

  • Описание: Основной планировщик процессов в Linux с 2007 года (начиная с ядра 2.6.23). CFS использует концепцию "виртуального времени" для обеспечения справедливого распределения CPU между процессами.
  • Принцип работы:
    • Каждому процессу выделяется "квант времени" в зависимости от его приоритета (nice value).
    • CFS использует красно-черное дерево для отслеживания процессов, сортируя их по виртуальному времени выполнения.
  • Ключевые параметры:
    • sched_latency — период, за который все задачи должны получить CPU.
    • min_granularity — минимальный квант времени для задачи.

Пример настройки приоритета (nice value):

nice -n 10 ./script.sh  # Запуск с низким приоритетом

O Scheduler

  • Описание: Использовался до CFS (в ядрах 2.6). Назван так из-за сложности O(1) для операций вставки и выбора задачи.
  • Особенности:
    • Использовал две очереди: активную и экспирированную.
    • Поддерживал интерактивные задачи, но был менее предсказуем, чем CFS.

Real-Time Schedulers

Для задач реального времени (RT) в Linux есть два алгоритма:

  1. SCHED_FIFO (First-In-First-Out):
    • Задачи выполняются строго по очереди, пока не освободят CPU.
    • Приоритет статичен (от 1 до 99, где 99 — наивысший).
  2. SCHED_RR (Round Robin):
    • Как FIFO, но с квантованием времени для задач с одинаковым приоритетом.

Пример установки RT-приоритета:

struct sched_param param;
param.sched_priority = 50;
sched_setscheduler(pid, SCHED_FIFO, &param);

2. Планировщики ввода-вывода

CFQ

  • Описание: Стандартный планировщик для HDD. Создает отдельные очереди для каждого процесса.
  • Плюсы: Справедливо распределяет ресурсы между задачами.
  • Минусы: Неэффективен для SSD.

Deadline

  • Описание: Обеспечивает минимальную задержку для операций I/O.
  • Особенности:
    • Использует три очереди: read FIFO, write FIFO и сортированную.
    • Гарантирует, что запросы не будут ждать дольше заданного времени.

NOOP

  • Описание: Простейший планировщик, работающий по принципу FIFO.
  • Использование: Оптимален для SSD, где аппаратная очередь уже эффективна.

Kyber

  • Описание: Современный планировщик для быстрых устройств (NVMe, SSD).
  • Особенности:
    • Управляет двумя очередями: синхронных и асинхронных запросов.
    • Поддерживает "бюджеты" для ограничения задержек.

Пример смены I/O-планировщика:

echo deadline > /sys/block/sda/queue/scheduler

3. Дополнительные механизмы

  • cgroups: Позволяют ограничивать ресурсы (CPU, I/O, память) для групп процессов.
  • CPU Affinity: Закрепление процессов за определенными ядрами CPU.
  • Energy-Aware Scheduling (EAS): В мобильных и embedded-системах для оптимизации энергопотребления.

Резюмируем:

  • Для CPU: CFS (основной), O(1) (устарел), SCHED_FIFO/SCHED_RR (реальное время).
  • Для I/O: CFQ (HDD), Deadline (универсальный), NOOP (SSD), Kyber (NVMe).
  • Дополнительно: cgroups, CPU affinity, EAS.

Вопросы

Собеседования