?

Log in

No account? Create an account
o_O

Что означает "Реальное время".

В последнее время приходится достаточно часто разговаривать и переписываться с людьми, которые часто употребляют термин "реальное время" и "ОС реального времени". И, судя по контексту обсуждения, многие плохо себе представляют, что же это такое, как в таких ОС осуществляется планирование, как расставлять приоритеты задач в таких системах и т.д.

Если и вы из таких людей, то возможно вам будет интересно то, что под катом... Но предупреждаю - букв Реально много.



Например, часто встречается мнение, что более важные для работы процессы должны получать больший приоритет, а менее важные - меньший. То есть решение о планировании таких процессов принимается исходя из каких-то априорных соображений типа "ввод-вывод должен быть побыстрее, технологическая задача должна иметь средний приоритет, а уж связь с системами верхнего уровня должна быть самой низкоприоритетной".

Звучит в общем-то разумно, не правда ли?

Также бытует мнение, что ОСРВ работает "быстрее" и "надежнее", и что если взять обычную систему, и перенести ее в РВ-окружение, то все магическим образом будет работать правильно.

На вопрос "а с чего должно быть быстрее", обычно отвечают - "ну как же, это ж РЕАЛ-ТАЙМ! Он ГАРАНТИРУЕТ, что все выполнится в выставленные сроки!".

Как правило, в качестве определения системы реального времени приводится некий "отказ", если какая-то операция не укладывается в гарантированные рамки. По этому отказу могут проводиться какие-то контраварийные действия, например остановка производства, срабатывание систем противоаварийной защиты, все рабочие на производстве срочно натягивают строительные каски на головы и быстро покидают объект... Это жесткое (hard) Реальное Время. Звучит страшно, и внушает уважение к этому "реальному жосткому времени для реальных жостких пацанов".

В действительности же, в большинстве ситуаций, необходимости в такой обработке ситуации "превышение временных рамок или дедлайна" нет... Как правило, программист обрабатывает такую ситуацию, просто повторяя неудавшийся запрос. Такое "ленивое" реальное время еще называют "мягким (soft)".

Так что же такое - это самое Реальное Время? Чтобы понять это, представим систему, которая закручивает крышечки бутылок Nuka-Cola на заводе. Допустим, это большой конвейер, на который выставляются пустые бутылки, они подходят к аппарату, заполняющему их свежей ну-ка-колой, выходят с другой стороны и поступают к роботу, закручивающему крышечки.

Для простоты представим, что конвейер движется со скоростью одна бутылка в секунду. То есть за одну секунду лента конвейера успевает подать новую бутылку, дождаться пока автоматы по всей линии конвейера сделают свои дела (заполнят бутылку, накрутит крышку, наклеят этикетку etc), и сдвинуть ленту дальше, чтобы подать следующую бутылку. Таким образом, на таком конвейере все передвижения ленты происходят с периодичностью в секунду. Эта величина называется периодом выполнения задачи (task period), обозначим ее как Т = 1000 мс.

Далее, допустим что на запуск, протяжку и остановку ленты, тоже тратится некоторое время (из этой одной секунды), и работа всех механизмов во время протяжки ленты невозможна. Например, на протяжку тратится 200 мс из каждой секунды, так что с момента остановки ленты до момента начала её движения остается 800 мс, и работа всех агрегатов конвейера должна быть завершена за это время. Это время называется дедлайном (deadline) задачи, обозначим его как D = 800 мс.

Теперь рассмотрим только робота, закручивающего крышки. Допустим, что робот устанавливает и закручивает крышку за 200 мс. Эта величина называется временем исполнения (computation time), обозначим ее как C.

Что же получилось в итоге? Каждую секунду к роботу подъезжает новая бутылка, он за 200 мс закручивает ее крышку, и остается еще 600 мс до того, как лента начнет двигаться, и 800 мс до подъезда следующей бутылки. Итого, робот работает только 20% (200 мс / 1000 мс * 100%), а остальное время ничего не делает. Величина, равная отношению времени исполнения к периоду исполнения, называется загруженностью (utilization) и обозначается как U. В такой системе робот всегда выполняет все свои задачи в срок, и это - система жесткого реального времени.

Но для такого дорогого оборудования, 20% загрузка это слишком мало. И тут инженеру, изнывающему без премий, приходит в голову гениальная мысль! А что если поставить рядом две конвейерные ленты, а робота снабдить поворачивающимся основанием? Тогда он сможет закручивать крышки на двух лентах, периодически переключаясь между ними. Все довольны, руководство завода пропивает стоимость второго робота вмести с изобретательным инженером.

Но возможно ли это сделать так, чтобы не приходилось останавливать конвейеры? То есть, можно ли сделать так, чтобы все задачи выполнялись до достижения дедлайна? Этот вопрос придётся решать бедняге инженеру, когда он проспится после грандиозной попойки и придёт программировать робота.

Допустим, второй конвейер разливает не ну-ка-колу, а нано-колу. Она менее вязкая, в результате чего удалось поднять скорость второго конвейера до одной бутылки за 800мс. T' = 800 мс.
При этом лента его движется с той же скоростью, что и у первого. затрачивая те же 200 мс на протяжку. То есть время дедлайна равно D' = 600 мс. Время закручивания крышки оставляем тем же - 200 мс (C' = C = 200 мс).

Также, требуется определенное время для переключения робота с одной ленты на другую. Допустим, что робот у нас поворачивается за 200 мс. Это время называется временем переключения контекста.

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

Начинается ее решение с того, что проверяется суммарная загрузка системы, не превышает ли она 100%. Если превышает - то задача в принципе не решаемая, какой-то из конвейеров придется тормозить. Эта величина складывается как сумма загруженностей отдельных лент.

В нашем случае она равна U + U' = C/T + C'/T' = 200/1000 + 200/800 = 0.45, то есть 45%. Это не так уж много. Теперь посмотрим, удастся ли найти такой алгоритм планирования, который бы не превышал дедлайны, с учетом времени переключений контекста. Для иллюстрации процесса очень полезно иметь при себе диаграмму процесса, подобную приведенной на рисунке 1.

Верхняя линия - это более медленный конвейер, нижняя - более быстрый. Стрелочками показаны переключения робота между линиями, звездочками - закручивание крышек. Закрашенными прямоугольниками показываются дедлайны, промежутки между ними - это протягивание линии. Серый прямоугольник - простой робота.

Рисунок 1 4.25 КБ
Рисунок 1.


Это диаграмма показывает планирование на протяжении 4 секунд. После окончания четырех секунд, робот находится в том же положении, что и был изначально, так что такое планирование можно "зациклить". Как видно, задача планирования решена - все крышки закручены вовремя. Но какой ценой? Робот простаивал только 400 мс из всех четырех секунд, то есть реальная загрузка с учетом переключений составила 90%! В два раза больше расчетных 45% (без учета переключений контекста).

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

Делятся они, в основном, на два типа - динамические и статические. Динамические планировщики оперируют в предположении, что каждая задача сообщает планировщику, какой у нее период, и каков дедлайн, а также время исполнения, так что планировщик в любой момент знает, когда нужно переключать процессы.
В качестве примера динамического планирования можно привести алгоритм Ealiest Deadline First (EDF). Когда имеются две задачи, между которыми нужно выбирать, выбирай ту, у которой раньше всего истечет дедлайн. Такой планировщик требует наиболее точных знаний о системе, но зато, позволяет нагрузить все 100% ресурсов (система остается планируемой даже если суммарная загрузка равна 100%).

Статические планировщики производят планирование по приоритетам. Каждой задаче назначается свой приоритет (в соответствии с алгоритмом планирования), и далее, планировщик всегда выбирает процесс с наибольшим приоритетом. Одним из примеров таких алгоритмов является Rate-monotonic Scheduling (RMS). В нем приоритеты назначаются согласно длительности цикла задачи - чем меньше T, тем больше приоритет. Для такой системы, чтобы оставаться планируемой, необходима загрузка меньше чем определенное число, обычно большее чем 69%.

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

Впрочем, об инверсии приоритетов, пожалуй, в следующий раз, если кому-нибудь это вообще интересно.
Метки:

Comments

Такой планировщик требует наиболее точных знаний о системе, но зато, позволяет нагрузить все 100% ресурсов (система остается планируемой даже если суммарная загрузка равна 100%).
Можно уточнить, что понимается под «наиболее точными знаниями»? По моему в случае EDF как раз знаний надо мало: дедлайны (при условии, что задача пристреливается если она не укладывается в дедлайн).
Имеется ввиду, динамические планировщики должны обладать данными обо всех ожидающих задачах в системе, обновляемых в режиме реального времени. Для EDF - да, достаточно дедлайнов (хотя, наверное, неплохо было бы еще знать время выполнения, чтобы не переключаться на заведомо провальные таски).
ну к сожалению знание времени выполнения — это как раз Holy Grail, найти его очень хочется, но обходиться приходится полумерами (которые, правда, всё равно полезные).
Мило. Разумеется, продолжительность цикла не имеет отношения к реальности времени.

Можно заставить систему работать 100%, если расставить правильно приоритеты. Когда ей нефиг делать, она будет яйца чесать статистику считать да фоновые задачи; а так... а так, главное дело, что в жизни нужно - это preemptive task switch. Если его нет, то, имхо, и реального времени нету. Тут в моду входит новый трюк, trampolining, но это, по-моему, не решает задачу в целом. Только preemptive. А впрочем, я с реальным временем уже 20 лет как не работаю...
Ну я не сказал про preemptive task switch лишь потому, что на вышеприведенной аналогии с роботом она бы выглядела странно.

А что значит "расставить правильно приоритеты"? Это статическое планирование, утилизирующее 100% разделяемого ресурса?
Насчёт приоритетов - нет, я не столь конкретно. Главное, имхо, расставить их так, чтобы доказуемо месаги проходили без дедлоков; а в остальном они хороши для регулирования. 100%, по-моему, будет только если есть чем заняться в свободное от важной работы время.
ну мы например занимаемся garbage producing'ом и garbage collection'ом в нашем тесте :-)
Ну, процесс idle может занять все оставшееся время ;)
Вообще вся статья была написана для того, чтобы пояснить, почему реальное время - это весьма сложная штука, с кучей подводных камней, и каждую конкретную систему приходится тюнить отдельно, расставляя приоритеты.
Тема 69% не раскрыта. Остальное время хавают какие-то неучтённые расходы, а как так получилось, что они неучтённые? Это расходы на синхронизацию/переключение контекстов?
Нет, не неучтенные. Просто алгоритм RMS, дающий приоритет процессам с меньшим циклом выполнения, не сможет выполнить задачу планирования, если суммарная загрузка превышает определенное число.

Формула указана тут:
http://en.wikipedia.org/wiki/Rate-monotonic_scheduling
Спасибо. Этот пост + статья в педивикии много объясняют.
Извините, не являюсь реальным ЖЖ-шником, поэтому не имею возможности быть неанонимом. Случайно наткнулся на вот этот ваш пост в блоге и решил откликнуться несколькими ремарками.

1. Насколько я понял, вы критикуете общепринятое определение РВ (например, данное в Википедии). Вам не нравится привлечение понятия "отказа" для характеристики режима РВ? Вы считаете, что "настоящее" РВ почти всегда "мягкое"?

Вы ошибаетесь, хотя бы потому, что не оставляете места системам, где нарушение временных ограничений действительно "чревато боком": критические производства (в химической индустрии, на АЭС и т.п.); военные приложения; космос и т.п. Вот они-то и являются подлинными СРВ.

2. Далее, для иллюстрации вы приводите пример типично синхронной системы с временными ограничениями. Для решения подобных задач, действительно, очень удобны приоритетные дисциплины планирования типа RM, EDF и пр.

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

3. Далее, вы как-то вскользь упомянули некое "РВ-окружение" и сразу же от него отмежевались. :)

Действительно, само по себе "РВ-окружение" задач РВ не решает. Его назначение - не мешать решению этих задач. :) В частности, MS Windows живет своей жизнью, меняя приоритеты задач, самостоятельно включая и выключая кэширование, свопинг, priority boosting и т.п., и поэтому для ЖРВ непригодна. Основное отличие ОС РВ не в том, что в них используются какие-нибудь планировщики RM/EDF, а в том, что все фичи, влияющие на временные характеристики работы прикладных задач, в них полностью управлябельны. А уж насколько программер сумеет воспользоваться этим для построения своей СРВ - эт отдельный вопрос.

4. И, наконец, а вас никогда не интересовало, почему в QNX/OS-9/WxWorks и пр. нет никаких RM/EDF?

Да просто потому, что они, увы, не нужны. Для задач "мягкого РВ" вполне достаточно обычного Round Robbina или дисциплин со "стареющими" приоритетами, как в UNIX. А для "жесткого РВ" просто есть возможность включить кооперативную многозадачность и управлять порядком выполнения задач самостоятельно.

Еще раз извините. Я случайно наткнулся на ваш пост и огорчился, что он настолько безаппеляционен и, притом, неполон.
--
WBR, Константин

1. Насколько я понял, вы критикуете общепринятое определение РВ (например, данное в Википедии). Вам не нравится привлечение понятия "отказа" для характеристики режима РВ? Вы считаете, что "настоящее" РВ почти всегда "мягкое"?

Дело не в понятии "отказ", а в понятии, что делать, если этот отказ зафиксирован. То есть какая должна быть реакция системы на отказ. В приведенном примере, если произошел отказ, и пробку не успели накрутить, бутылка упадет и ее содержимое зальет ленту транспортера. Стоит ли останавливать все ради одной бутылки? От ответа на этот вопрос зависит, мягкое у нас время или жесткое.


Вы ошибаетесь, хотя бы потому, что не оставляете места системам, где нарушение временных ограничений действительно "чревато боком": критические производства (в химической индустрии, на АЭС и т.п.); военные приложения; космос и т.п. Вот они-то и являются подлинными СРВ.


Приведите пример подлинной СРВ, а также что там происходит, если в такой СРВ будет превышено время реакции на какое-нибудь событие?
Кстати, наша компания поставляет решения в том числе и для химической индустрии, и для атомной тоже, так что я в общем-то знаю о этих самых нарушениях временных ограничений достаточно много.


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

Что вы имеете ввиду под "самостоятельно выстраивать приоритеты"? Вы заранее задаете отдельным процессам в системе определенные приоритеты, и используете вытеснение? Это и называется статическое планирование. RMS является лишь одним из вариантов статического планирования, вы самостоятельно можете выставить какие угодно приоритеты, определяя таким образом собственную стратегию планирования.
Как только приоритеты определены, статический планировщик просто выбирает каждый раз из списка готовых к выполнению процессов процесс с наибольшим приоритетом.
Стратегия планирования RMS, кстати, является доказанно оптимальной - то есть если статическое планирование вообще возможно в этой ситуации, то RMS тоже даст планируемую стратегию. Вы можете привести пример, когда "априорно эффективный шедулер" не поможет, а самостоятельно выстроенные приоритеты помогут?

Под РВ-окружением я понимал то, что существует поверье, что если взять обычную, не реалтайм программу, и запустить ее в РВ-окружении, она магическим образом станет реалтаймовой. Многие для этого просто выставляют в ОС приоритет "реального времени" (в Windows это можно сделать из Диспетчера Процессов), а далее везде лепят наклейки "Реальное время". И люди верят.


4. И, наконец, а вас никогда не интересовало, почему в QNX/OS-9/WxWorks и пр. нет никаких RM/EDF?

Да просто потому, что они, увы, не нужны. Для задач "мягкого РВ" вполне достаточно обычного Round Robbina или дисциплин со "стареющими" приоритетами, как в UNIX. А для "жесткого РВ" просто есть возможность включить кооперативную многозадачность и управлять порядком выполнения задач самостоятельно.

Очевидно, вы не вполне понимаете, что такое RMS, иначе ни в коем случае не смешивали его в одном предложении с EDF. Почитайте побольше про статическое планирование. В ОСРВ и не должно быть поддержки RMS. Должна быть поддержка вытесняемой многозадачности по жестким приоритетам, с мерами против инверсии приоритетов. И во всех приведенных ОС она собственно и есть. А EDF пока сложно реализовать, так как требуется информация о всех дедлайнах в системе, а этого часто нельзя предоставить.