Планирование нитей (thread scheduling)

Планирование нитей (thread scheduling) – это процесс распределения процессорного времени между конкурирующими потоками выполнения. Цель планировщика – обеспечить справедливость, эффективность и отзывчивость системы. Алгоритмы планирования делятся на статические (с фиксированными правилами) и динамические (адаптирующиеся к текущей нагрузке и поведению потоков). В этой статье рассматриваются основные алгоритмы, их характеристики и применение, с акцентом на динамические методы.

1.1. Английские сокращения

1.2. Русские сокращения

2.1. Задачи планировщика

• Распределение процессорного времени между потоками.
• Минимизация времени ожидания, времени отклика и накладных расходов на переключение контекста.
• Обеспечение справедливости и предотвращение голодания (starvation).

2.2. Ключевые метрики

• Время выполнения (Turnaround Time) – интервал от момента поступления задачи до её завершения.
• Время ожидания (Waiting Time) – суммарное время, которое задача провела в очереди.
• Время отклика (Response Time) – время от поступления задачи до первого получения процессора.
• Пропускная способность (Throughput) – количество задач, завершаемых за единицу времени.

3.1. FIFO (FCFS – First Come, First Served)

Простейший алгоритм: потоки выполняются в порядке поступления. Невытесняющий.

• + Простота реализации.
• – Эффект конвоя (длинные задачи задерживают короткие).

3.2. Круговая очередь (Round Robin – RR)

Каждый поток получает квант времени (time quantum) и по истечении кванта переходит в конец очереди. Вытесняющий.

• + Справедливость, хорошее время отклика.
• – Накладные расходы на частые переключения, выбор оптимального кванта критичен.

3.3. Приоритетное планирование

Каждому потоку назначается приоритет. Выполняется поток с наивысшим приоритетом. Может быть вытесняющим или невытесняющим.

• + Поддержка важных задач.
• – Риск голодания низкоприоритетных потоков.

3.4. Многоуровневые очереди (Multilevel Queue)

Потоки разделяются на несколько очередей с разными приоритетами (например, системные, интерактивные, фоновые). Каждая очередь использует свой алгоритм (RR, FIFO). Между очередями – фиксированный приоритет.

• + Гибкость.
• – Не учитывает изменение поведения потоков.

Динамическое планирование адаптирует решения на основе текущего состояния системы, истории выполнения и внешних факторов. Оно позволяет улучшить использование ресурсов и отзывчивость.

4.1. Многоуровневая очередь с обратной связью (Multilevel Feedback Queue – MFQ)

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

• Схема: несколько очередей, каждая с разным квантом (чем выше приоритет, тем меньше квант). Новый поток попадает в самую высокоприоритетную очередь. Если поток не завершается за свой квант, он перемещается в очередь ниже. Это автоматически даёт приоритет коротким и интерактивным задачам.

• + Адаптивность, предотвращает голодание.

• – Сложность настройки, возможна нестабильность.

4.2. Алгоритмы реального времени

• Rate‑Monotonic (RM): статический приоритет, основанный на периоде задачи (чем короче период, тем выше приоритет). Оптимален для независимых задач с совпадающими крайними сроками.
• Earliest Deadline First (EDF): динамический приоритет – задача с ближайшим крайним сроком получает наивысший приоритет. Является оптимальным для однопроцессорных систем.

4.3. Планировщик CFS (Completely Fair Scheduler) в Linux

CFS использует красно-чёрное дерево для хранения очереди задач. Каждой задаче назначается виртуальное время выполнения (vruntime). Планировщик выбирает задачу с наименьшим vruntime, обеспечивая справедливое распределение процессорного времени. Приоритеты задаются через веса (nice values).

CFS можно считать динамическим, так как vruntime обновляется в зависимости от загрузки системы, а выбор задачи адаптивен.

4.4. Планирование на основе квот и групп (например, в контейнерах)

Используется для гарантирования минимальной доли процессорного времени группам потоков (например, через cgroups в Linux). Это динамическое планирование, так как распределение может пересматриваться в зависимости от нагрузки.

5.1. Симуляция RR (Python)

import collections

def round_robin(tasks, quantum):
    queue = collections.deque(tasks)
    time = 0
    while queue:
        task = queue.popleft()
        if task[1] > quantum:
            print(f"Время {time}: выполняется {task[0]} (осталось {task[1]-quantum})")
            task = (task[0], task[1] - quantum)
            time += quantum
            queue.append(task)
        else:
            print(f"Время {time}: завершён {task[0]}")
            time += task[1]
    return time


tasks = [("A", 5), ("B", 3), ("C", 8)]
quantum = 2
total_time = round_robin(tasks, quantum)
print(f"Общее время выполнения: {total_time}")

5.2. Симуляция MFQ (упрощённая)

def mfq(tasks, queues):
    # queues: список очередей, каждая очередь — список (имя, остаток)
    # кванты для очередей: [2, 4, 8] (в порядке приоритета)
    time = 0
    quantum = [2, 4, 8]
    level = 0
    while any(q for q in queues):
        for i, q in enumerate(queues):
            if q:
                task = q.pop(0)
                if task[1] > quantum[i]:
                    print(f"Время {time}: выполняется {task[0]} в очереди {i}, осталось {task[1]-quantum[i]}")
                    task = (task[0], task[1] - quantum[i])
                    if i+1 < len(queues):
                        queues[i+1].append(task)   # понижаем приоритет
                    else:
                        queues[i].append(task)     # в последнюю очередь циклически
                    time += quantum[i]
                else:
                    print(f"Время {time}: завершён {task[0]}")
                    time += task[1]
                break
    return time

queues = [[("A", 5)], [("B", 3)], [("C", 8)]]  # начальное распределение по очередям
total = mfq(None, queues)
print(f"Общее время: {total}")

5.3. Пример динамического приоритета (EDF) – упрощённо, с выбором по дедлайну

def edf(tasks):
    # tasks: список (имя, deadline, remaining_time)
    time = 0
    while tasks:
        # выбираем задачу с наименьшим дедлайном
        task = min(tasks, key=lambda x: x[1])
        if task[2] > 0:
            print(f"Время {time}: выполняется {task[0]} (deadline {task[1]})")
            task = (task[0], task[1], task[2] - 1)
            time += 1
            # обновляем список
            idx = tasks.index((task[0], task[1], task[2]+1))  # находим старую
            tasks[idx] = task
        else:
            print(f"Время {time}: завершён {task[0]}")
            tasks.remove(task)
    return time

tasks = [("A", 5, 3), ("B", 10, 4), ("C", 7, 2)]
total = edf(tasks)
print(f"Общее время: {total}")

1. Сравните время отклика для RR с квантами 2 и 5 для задач (A:10, B:5, C:3). Какой квант лучше?
2. Реализуйте симуляцию приоритетного планирования с поддержкой динамического изменения приоритета (например, увеличение приоритета для долго ожидающих потоков).
3. Изучите документацию CFS в Linux и объясните, как vruntime влияет на выбор задачи.
4. Для набора периодических задач (T1: период 10, время 3; T2: период 15, время 4) проверьте, являются ли они планируемыми по RM и EDF.

Алгоритмы планирования нитей эволюционировали от простых очередей до сложных адаптивных систем. Динамическое планирование, реализованное в MFQ, CFS и EDF, позволяет учитывать изменчивую нагрузку и поведение потоков, обеспечивая высокую производительность и отзывчивость. Выбор алгоритма зависит от требований приложения: для реального времени – EDF/RM, для серверов – CFS, для настольных систем – MFQ/CFS. Понимание принципов работы планировщиков необходимо для оптимизации систем и разработки высоконагруженных приложений.

Примеры Python могут быть выполнены в среде с интерпретатором Python 3. Для работы с реальным планировщиком Linux требуется доступ к системным параметрам (требуются права root). Блоки кода можно запускать в org-babel при наличии поддержки `ob-python`.