Какие знаешь алгоритмы планирования?

Алгоритмы планирования (Scheduling Algorithms)

В контексте разработки на Go, понимание алгоритмов планирования критически важно для работы с горутинами и системным планировщиком. Эти алгоритмы делятся на две основные категории: алгоритмы планирования процессов/потоков на уровне операционной системы и алгоритмы планирования горутин в рантайме Go.

Алгоритмы планирования в операционных системах

Это классические алгоритмы, которые изучаются в курсах по операционным системам. Они управляют выделением времени ЦП между различными процессами или потоками ядра.

1. First-Come, First-Served (FCFS) / FIFO

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

1. Shortest Job First (SJF) / Shortest Process Next (SPN)

    *   Невытесняющий алгоритм, который выбирает для выполнения процесс с наименьшим временем выполнения (длиной следующего CPU-бурста).
    *   Оптимален для минимизации среднего времени ожидания, но на практике длину процесса сложно предсказать. Вытесняющая версия — **Shortest Remaining Time First (SRTF)**.

1. Round Robin (RR) / Циклическое планирование

    *   Основа большинства современных систем. Каждому процессу выделяется фиксированный **квант времени (time slice)**. Если процесс не завершился за квант, он вытесняется и помещается в конец очереди.
    *   Справедливый и обеспечивает хорошее время отклика. Эффективность сильно зависит от размера кванта.

1. Приоритетное планирование (Priority Scheduling)

    *   Каждому процессу назначается приоритет. Выбирается процесс с наивысшим приоритетом. Может быть вытесняющим или нет.
    *   **Проблема:** "Голодание" процессов с низким приоритетом. Решается через **старение (aging)** — постепенное увеличение приоритета долго ожидающих процессов.

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

    *   Процессы разделяются по категориям (например, системные, интерактивные, пакетные), каждая со своей отдельной очередью и своим алгоритмом планирования (например, RR для интерактивных, FCFS для пакетных).

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

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

Алгоритм планирования горутин в Go

Планировщик Go (Goroutine Scheduler) — это не вытесняющий планировщик на уровне пользовательского пространства, который работает поверх потоков ОС (M). Он реализует гибридную модель, известную как M:N планирование, где M горутин планируются на N потоков ОС. Его ключевой алгоритм можно описать как вытесняющую кооперативную многозадачность с work-stealing.

Основные концепции и "алгоритмические" приёмы планировщика Go:

1. Три ключевые сущности (G-M-P модель):

    *   **G (Goroutine):** Сама горутина.
    *   **M (Machine):** Поток ОС (Machine Thread), который выполняет код.
    *   **P (Processor):** Виртуальный процессор, контекст планировщика. Управляет локальной очередью горутин для M. Количество P по умолчанию равно количеству логических ядер CPU (`GOMAXPROCS`).

1. Кооперативная вытесняющая модель:

    *   **Кооперативность:** Горутина добровольно отдаёт управление в **точках вызова (preemption points)**, таких как системные вызовы, операции с каналами, вызов `runtime.Gosched()`, операции сборки мусора.
    *   **Вытеснение:** Начиная с Go 1.14, реализовано **асинхронное вытеснение** на основе сигналов. Если горутина выполняет длительный цикл без точек вызова, планировщик может принудительно её вытеснить, чтобы дать ход другим. Это предотвращает "голодание".

1. Work-Stealing (кража работы):

    *   Это основной алгоритм балансировки нагрузки. Каждый `P` поддерживает **локальную очередь (runqueue)** горутин.
    *   Если локальная очередь `P` пуста, он пытается "украсть" половину горутин из очереди другого, случайно выбранного `P`. Это позволяет эффективно распределять работу между ядрами.

1. Глобальная очередь:

    *   Существует также общая глобальная очередь. Новые горутины или горутины, снятые с заблокированного `M`, часто попадают в локальную очередь своего `P`, но могут быть помещены и в глобальную.

Пример кода, демонстрирующий взаимодействие с планировщиком:

package main

import (
    "fmt"
    "runtime"
    "time"
)

func cpuIntensiveTask(id int, resultChan chan int) {
    sum := 0
    // Длительный цикл. Благодаря асинхронному вытеснению в Go 1.14+
    // другие горутины также получат время CPU.
    for i := 0; i < 100000000; i++ {
        sum += i % (id + 1)
    }
    resultChan <- sum
}

func ioTask(id int, doneChan chan struct{}) {
    time.Sleep(100 * time.Millisecond) // Имитация блокирующего I/O
    fmt.Printf("IO task %d done\n", id)
    doneChan <- struct{}{}
}

func main() {
    // Устанавливаем максимальное количество потоков ОС (M),
    // которые могут выполняться одновременно.
    // Количество виртуальных процессоров P = GOMAXPROCS.
    fmt.Printf("GOMAXPROCS is %d\n", runtime.GOMAXPROCS(0))

    // Демонстрация работы с CPU-интенсивными задачами
    cpuResultChan := make(chan int, 4)
    for i := 0; i < 4; i++ {
        go cpuIntensiveTask(i, cpuResultChan)
    }

    // Демонстрация работы с I/O задачами
    ioDoneChan := make(chan struct{}, 2)
    for i := 0; i < 2; i++ {
        go ioTask(i, ioDoneChan)
    }

    // Явная уступка выполнения текущей горутины (кооперативная точка).
    // Планировщик переключится на другую готовую горутину.
    runtime.Gosched()
    fmt.Println("Main goroutine yielded CPU")

    // Ожидаем завершения
    for i := 0; i < 2; i++ {
        <-ioDoneChan
    }
    for i := 0; i < 4; i++ {
        <-cpuResultChan
    }
}

Вывод для разработчика на Go: Понимание этих алгоритмов, особенно модели M-P-G и work-stealing, позволяет писать более эффективные конкурентные программы. Например, знание о том, что горутины из одного канала часто обрабатываются одним P (из-за локальности очереди), или что блокирующий системный вызов может привести к созданию нового потока ОС (M), помогает избегать узких мест в производительности. Планировщик Go постоянно развивается, и основные улучшения в последних версиях связаны именно с усовершенствованием алгоритмов вытеснения и балансировки.