Кратчайшее оставшееся время
Кратчайшее оставшееся время , также известное как « Сначала самое короткое оставшееся время» (SRTF) , — это метод планирования , который представляет собой упреждающую версию планирования самого короткого оставшегося задания . В этом алгоритме планирования процесс для выполнения выбирается с наименьшим количеством времени, оставшимся до завершения. Поскольку текущий выполняющийся процесс по определению имеет наименьшее оставшееся время, и поскольку это время должно уменьшаться только по мере выполнения, процесс будет либо выполняться до завершения, либо будет вытеснен, если будет добавлен новый процесс, требующий меньшее количество времени.
Кратчайшее оставшееся время является преимуществом, поскольку короткие процессы выполняются очень быстро. Система также требует очень небольших накладных расходов, поскольку она принимает решение только тогда, когда процесс завершается или добавляется новый процесс, а при добавлении нового процесса алгоритму нужно только сравнить выполняющийся в данный момент процесс с новым процессом, игнорируя все другие процессы. в настоящее время ожидает выполнения.
Как и самое короткое задание , оно может привести к голоданию процессов : длинные процессы могут задерживаться на неопределенный срок, если короткие процессы постоянно добавляются. [1] Эта угроза может быть минимальной, если время процесса соответствует распределению с тяжелым хвостом . [2] Аналогичный алгоритм, который позволяет избежать голодания за счет более высоких накладных расходов на отслеживание, является следующим по самому высокому коэффициенту ответа (HRRN).
Ограничения
[ редактировать ]Как и планирование наименьшего оставшегося времени, планирование наименьшего оставшегося времени редко используется за пределами специализированных сред, поскольку оно требует точных оценок времени выполнения каждого процесса.
Ссылки
[ редактировать ]- ^ Эндрю С. Таненбаум; Герберт Бос (2015). Современные операционные системы . Пирсон. ISBN 978-0-13-359162-0 .
- ^ Хархол-Балтер, Мор ; Шредер, Бьянка ; Бансал, Нихил; Агравал, Мукеш (2003). «Планирование на основе размера для улучшения веб-производительности». Транзакции ACM в компьютерных системах . 21 (2): 207–233. CiteSeerX 10.1.1.25.1229 . дои : 10.1145/762483.762486 . S2CID 213935 .
| Одиночные узлы массового обслуживания | |
|---|---|
| Процессы прибытия | |
| Сети массового обслуживания | |
| Политика обслуживания | |
| Ключевые понятия | |
| Предельные теоремы | |
| Расширения | |
| Информационные системы | |
