Shortest Remaining Time

Shortest Remaining Time (SRT, также известный как Shortest Remaining Time First, SRTF, или Preemptive Shortest Job Next, PSJN) — это алгоритм планирования процессов в операционных системах, относящийся к классу вытесняющих (preemptive) дисциплин. В основе алгоритма лежит принцип предоставления центрального процессора (ЦП) тому процессу, у которого наименьшее оставшееся время выполнения. SRT является вытесняющей версией алгоритма Shortest Job Next (SJN).

Принцип работы

Алгоритм SRT работает следующим образом: в любой момент времени ЦП выделяется процессу с минимальным значением оставшегося времени выполнения (Burst Time). Если в систему поступает новый процесс, время выполнения которого меньше, чем оставшееся время у текущего активного процесса, происходит вытеснение (прерывание). Текущий процесс сохраняет своё состояние (счётчик команд, регистры) и помещается обратно в очередь готовых процессов, а ЦП передаётся новому, более короткому процессу.

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

Пример работы

Рассмотрим очередь процессов с указанием времени поступления (Arrival Time) и требуемого времени выполнения (Burst Time):

Хронология выполнения:

1. t=0: Поступает P1. Единственный процесс в очереди. Начинает выполняться. Оставшееся время: P1=8.
2. t=1: Поступает P2 (время выполнения 4). Оставшееся время P1 = 7. Так как 4 < 7, P1 вытесняется. ЦП получает P2. Очередь: P1(7), P2(4).
3. t=2: Поступает P3 (время выполнения 2). Оставшееся время P2 = 3. Так как 2 < 3, P2 вытесняется. ЦП получает P3. Очередь: P1(7), P2(3), P3(2).
4. t=3: Поступает P4 (время выполнения 1). Оставшееся время P3 = 1. 1 не меньше 1 (равно). В некоторых реализациях при равенстве может использоваться правило FCFS (первым пришёл — первым обслужен) или другой механизм. В данном примере P3 продолжает выполнение.
5. t=4: P3 завершается. В очереди: P1(7), P2(3), P4(1). Наименьшее оставшееся время у P4 (1). ЦП получает P4.
6. t=5: P4 завершается. В очереди: P1(7), P2(3). ЦП получает P2 (3 < 7).
7. t=8: P2 завершается. В очереди: P1(7). ЦП получает P1.
8. t=15: P1 завершается.

Итоговая диаграмма Ганта: P1 (0-1) -> P2 (1-2) -> P3 (2-4) -> P4 (4-5) -> P2 (5-8) -> P1 (8-15).

Характеристики

Преимущества

• Минимизация среднего времени ожидания: SRT является оптимальным алгоритмом с точки зрения минимизации среднего времени ожидания (Average Waiting Time) среди всех известных алгоритмов планирования. Это доказано теоретически: любой другой алгоритм даёт среднее время ожидания не меньше, чем SRT.
• Минимизация среднего времени оборота: Аналогично, SRT минимизирует среднее время оборота (Average Turnaround Time) — полное время от появления процесса в системе до его завершения.
• Высокая интерактивность: Благодаря вытеснению, короткие процессы (например, пользовательский ввод с клавиатуры) получают ЦП почти мгновенно, что делает систему более отзывчивой для пользователя.

Недостатки

• Невозможность точной оценки времени выполнения: Алгоритм требует знания точного оставшегося времени выполнения каждого процесса. В реальных системах это значение неизвестно. Приходится использовать прогнозирование на основе предыдущего поведения процесса (например, экспоненциальное сглаживание), что может приводить к ошибкам и снижению эффективности.
• «Голодание» (Starvation) длинных процессов: Процессы с большим временем выполнения могут постоянно откладываться, если в систему непрерывно поступают короткие процессы. В худшем случае длинный процесс может никогда не получить ЦП.
• Высокие накладные расходы: Вытеснение и переключение контекста (Context Switch) требуют затрат процессорного времени. Чем чаще происходят вытеснения, тем больше времени тратится впустую. В системах с высокой частотой поступления коротких процессов накладные расходы могут стать значительными.
• Сложность реализации: Необходимо вести учёт оставшегося времени для каждого процесса и реализовывать механизм быстрого поиска процесса с минимальным значением. Это сложнее, чем, например, реализация Round Robin (RR) или First-Come, First-Served (FCFS).

Сравнение с другими алгоритмами

Применение

В чистом виде SRT редко применяется в операционных системах общего назначения из-за проблемы прогнозирования времени выполнения и риска «голодания». Однако его идеи используются в гибридных подходах. Например, алгоритмы, основанные на многоуровневых очередях с обратной связью (Multilevel Feedback Queue), могут отдавать приоритет процессам, которые потребляют мало процессорного времени, что является эвристикой, приближающейся к поведению SRT.

В специализированных системах реального времени, где время выполнения задач известно заранее (например, в промышленных контроллерах или встроенных системах), SRT может применяться для минимизации времени отклика на критические события.

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

• SRT является теоретически оптимальным алгоритмом, но его практическая реализация сталкивается с фундаментальной проблемой: будущее (оставшееся время выполнения) неизвестно. Это делает его скорее эталоном для сравнения, чем рабочим инструментом.
• Алгоритм SRT можно рассматривать как частный случай алгоритма Shortest Job Next, где вытеснение происходит при каждом поступлении нового процесса.
• В некоторых учебных курсах SRT называют «идеальным» планировщиком, подчёркивая, что его недостатки связаны не с логикой, а с ограничениями реального мира.

Критика

Основная критика SRT связана с его непрактичностью. Требование знания точного времени выполнения процесса делает его непригодным для большинства современных многозадачных операционных систем. Кроме того, проблема «голодания» длинных процессов может привести к деградации производительности системы в целом, если не принять специальных мер (например, повышения приоритета процессов, долго ожидающих ЦП). Наконец, высокие накладные расходы на переключение контекста могут свести на нет теоретический выигрыш во времени ожидания, особенно в системах с большим количеством коротких процессов.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». 4-е издание. — СПб.: Питер, 2015.
• Сильбершац А., Гэлвин П., Гэгн Г. «Операционные системы: внутренняя структура и принципы проектирования». 9-е издание. — М.: Диалектика, 2016.
• Столлингс У. «Операционные системы: внутреннее устройство и принципы проектирования». 8-е издание. — М.: Вильямс, 2014.
• Лаборатория вычислительных систем и сетей МФТИ. «Алгоритмы планирования процессов». Учебные материалы.