June 22nd, 2015

ДР Цертуса 2011

Efficient scheduling

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

Я отвлекусь и опишу в общем виде задачу планирования:
- Планировщик получает список задач, напр. "обновить показания индикатора температуры", "обновить показания индикатора скорости автомобиля", "проверить показания системы безопасности и принять меры по экстренному торможению, если что".
- Про каждую задачу указаны дедлайн и цена неуспевания: скажем, третью задачу надо сделать до такого-то момента (скажем, не позже 0.01 секунды после окончания прошлой такой проверки), а если этого не сделать, то это может стоить условно 1000 долларов. А несдержание дедлайна про спидометр допустим 1 доллар, а про индикатор погоды, скажем, 1 цент. Могу быть дополнительные дедлайны с повышенным штрафом, например продолб апдейта спидометра на целых 10 секнуд уже грозит превышением скорости без ведома водителя, стало быть штраф за продолб дедлайна увеличивается до 20 долларов.
- Дополнительно про задачи известно, сколько времени они в худшем случае занимают.

Задача планировщика состоит в том, чтобы минимизировать максимальный возможный суммарный штраф. Если эта задача достигается многими способами (это часто бывает, т.к. часто у системы есть запас и соответственно, можно вообще исключить штраф), то добавляеся ещё задача: сделать систему максимально подготовленной к спонтанному появлению новых задач, т.е. обеспечить в каждый момент времени максимальный запас времени и минимальное возрастание суммарного штрафа при его недостатке.
Для эффективного решения этой задачи, планировщику дополнительно (к worst case execution time) нужно знать про имеющиеся задачи матожидание их времени выполнения и его дисперсию.

В системах за пределами управления машинами задач с дедлайнами мало (они сводятся к тому, чтобы пользовательский интерфейс быстро реагировал на действия пользователя, не создавая неприятных ощущений, музыка с видеорядом декодировались/кадр игры рендерирлся достаточно быстро, чтобы фильм/игра не тормозили, входящая информация (вдруг у нас компутер биржевого трейдера или оператора АЭС) быстро попадала на экран. Если у нас сервер, то запросы должны обрабатываться своевременно. Задач, которые бы появлялись спонтанно, очень мало, простоя очень много, та что вторичной задачей планировщика ту должна быть не подготовка к внезапному наплыву спонтанных задач (это напоминает анекдот про "вдруг война, а я устал"), а подготовительная работа для задач, которые ещё не возникли, или дедлайны которых ещё очень далеки. Например, до момента, когда пользователь переключится в другой таб броузера, может пройти произвольное количество времени, однако если сейчас делать нечего, можно совершить пререндеринг страницы в этом табе, тогда когда ему надо будет переключиться, рендер займёт не 70мс, а одну.

Чтобы осуществлять такое планирование, нужен список "задач на время простоя" и их приоритеты (которые удобно задавать при помощи ординалов меньше w^w, как номера версий через точечку.

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

Планировщики операционных систем вроде виндоуса с линуксом и маком в основном занимабтся именно последним. Первым занимаются планировщики RT-систем.

При изучении этой тематики очень легко упустить из виду, что смена контекста (как и перемена рода деятельности у живых людей) сама требует при неэффективном пооде дочерта времени, а содержание в памяти кучи задач и экторов - дочерта памяти.

Чтобы оценить меру разврата в этой области, скажу лишь, что процессы в виндоусе, на маке и в линуксе примерно в 40 раз тормознее и больше JVM-потоков, и и в сотни раз больше и тормознее потоков нативных систем на Эрланге и seL4, которые в свою очередь в полтора раза тормознее QNX-потоков и примерно вдвое тормознее процессов захостенных на микроядре Fiasco.
И эти вот последние всё ещё тратят на переключение контекста в десяток раз больше времени, чем системы, пренебрегающие изоляцией потоков.

Предел совершенства - семейство ядер Sloth, пользующихся на всю катушку аппаратными хаками, достнупными в x86, ARM Cortex и крутых микроконтроллер Freescale и Infineon, стандартно используемых в машингстроении, автомобилях, самолётах и т.д. Очень советую публикации авторов про это ядро и его варианты с частичной изоляцией процессов и т.д.
https://www4.cs.fau.de/Research/Sloth/

В варианте "без всего" переключение контекста за 26 циклов worst case против полутора тысяч в QNX, десятков тысяч в JVM и сотен тысяч между процессами в каком-нибудь Виндоусе.
Операционки общего применения всё-таки очень зажрались.