Alexander Kuklev (akuklev) wrote,
Alexander Kuklev
akuklev

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 и сотен тысяч между процессами в каком-нибудь Виндоусе.
Операционки общего применения всё-таки очень зажрались.
Subscribe

  • (no subject)

    Встретил фотографию толпы футбольных фанатов, и она меня скорее напугала, у меня уж точно нет желания быть там среди них. Но внезапно я понял, что…

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

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

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 10 comments

  • (no subject)

    Встретил фотографию толпы футбольных фанатов, и она меня скорее напугала, у меня уж точно нет желания быть там среди них. Но внезапно я понял, что…

  • Прогресс

    Десять дней назад, вторая ступень SpaceX'овского корабля Starship своим ходом слетала своим ходом на десять километров вверх, и усмепшно приземлилась…

  • О водосбережении

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