Планирование в системах реального времени кратко

Обновлено: 05.07.2024

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

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

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

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

При рассмотрении в качестве примеров подсистем планирования потоков/процессов в операционных системах Windows NT, OS/2 и UNIX System V Release 4 было отмечено, что во всех этих системах имеется приоритетный класс реального времени. Для потоков/процессов, относящихся к этому классу, каждая из вышеназванных систем не гарантирует выполнение заданных временных ограничений, а лишь обеспечивает предпочтение в скорости обслуживания. Следовательно, эти ОС могут быть основой для построения мягких систем реального времени, но непригодны для жестких систем реального времени.

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

Предположим, что имеется периодический набор задач с периодами рi предельными сроками di и требованиями ко времени выполнения ci. Для проверки возможности существования расписания достаточно проанализировать расписание на периоде времени, равном по крайней мере наименьшему общему множителю периодов этих задач. Необходимым критерием существования расписания для набора периодических задач является следующее достаточно очевидное утверждение: сумма коэффициентов использования mi= сi/рi должна быть меньше или равна k, где k — количество доступных процессоров, то есть:

Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.

Название работы: Планирование в системах реального времени

Предметная область: Информатика, кибернетика и программирование

Описание: Планирование облегчается тем что в системах реального времени весь набор выполняемых задач известен заранее часто также известно времени выполнения задач моменты активизации и т. Если нарушение сроков выполнения задач не допустимо то система реального времени считается жесткой система управления ракетой или атомной электростанцией система обработки цифрового сигнала при воспроизведении оптического диска. Для периодической задачи все будущие моменты запроса можно определить заранее путем прибавления к моменту начального запроса величины.

Размер файла: 20.19 KB

Работу скачали: 32 чел.

Вопрос 19. Планирование в системах реального времени.

§4.2.6.Планирование в системах реального времени.

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

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

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

Все периодические задачи могут быть своевременно обработаны однопроцессорной системой только при выполнении условия:

где t обр i – время обработки i -го события процессором;

T i – период возникновения i -го события;

m – число событий.

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

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

- исчерпывающее тестирование всех возможных сценариев поведения управляемого объекта и управляющих программ;

- построением статического расписания (для планируемых задач);

- выбором математически обоснованного динамического алгоритма планирования.

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

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

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

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

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

Для реализации алгоритма планирования ОС должна получать управление всякий раз, когда в системе происходит событие, требующее перераспределения процессорного времени. К таким событиям относятся:

Прерывание от таймера, сигнализирующее, что время, отведенное активной задаче на выполнение, закончилось. Планировщик переводит задачу в состояние готовности и выполняет перепланирование.

Активная задача выполнила системный вызов, связанный с запросом на ввод-вывод или на доступ к ресурсу, который в настоящий момент занят. Планировщик переводит задачу в состояние ожидания и выполняет перепланирование.

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

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

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

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

Диспетку процессора процессора в режиме реального времени

M: номер задачи в реальном времени, CI: каждое время обработки, PI: время цикла


Например: 6 жестких задач в реальном времени, время цикла составляет 50 мс, каждый раз, когда время обработки составляет 10 мс, система немозмана.

Multi-Process Machine: (N: Количество машин обработки)


Классификация алгоритма планирования в реальном времени

В соответствии с задачами в реальном времени (т. Е. Степень слабости временных ограничений)

  • Планирование в реальном времени: должны соответствовать требованиям срока задач, и последствия серьезны.
  • Мягкий алгоритм планирования в реальном времени: ожидать соответствия требованиям срока задач, пропустите его
    терпеть.

Расписание

Недвижимый алгоритм планирования

  • Нерешимый вращение запланированного алгоритма: в групповой системе управления промышленным производством.
  • Неблокирующий приоритетный алгоритм планирования: используется в системах управления в реальном времени в течение определенного периода времени.

Алгоритм планирования вытеснения (время, чтобы занять время)

  • Алгоритм модификации приоритета на основе сеанса прерывания часов
  • Приоритетный запланированный алгоритм для немедленного захвата

Возьмите алгоритм планирования


Самый ранний крайний срок приоритетный алгоритм

Алгоритм является приоритетом задачи, основанной на сроке начала и завершения задачи. Чем ранее крайний срок, тем выше приоритет. Задача в очереди готовности расположена своим сроком, и первая задача команды сначала распределяет процесс.

Неблокирующее график для неизолированных задач в реальном времени
График вытеснения для задач в режиме реального времени

Неблокирующее график для неизолированных задач в реальном времени

График вытеснения для задач в режиме реального времени

Существует два периодических задача, периодическое время задачи A составляет 20 мс, каждое время обработки цикла составляет 10 мс; периодическое время задачи B составляет 50 мс, каждое время обработки цикла составляет 25 мс. Время прибытия двух задач, срок и время выполнения следующие:


Фиксированный приоритетный планирование (высокий приоритет)



Фиксированный приоритетный планирование (B имеет более высокий приоритет)

Самый ранний алгоритм приоритета времени завершения срока




Минимальный алгоритм приоритета расслабления (LLF, главную слабость сначала)
Низкое расслабление = высокая чрезвычайная ситуация

Алгоритм основан на уровне аварийной ситуации (или расслабляющей) для определения приоритета задачи. Чем выше задача, тем выше приоритет, и она предпочтительно реализована.

Алгоритм использует режим Seizational планирования, который можно использовать для планирования периодической задачи в реальном времени с сроком завершения.

Расслабиться = должно завершить время - сам остается время - точное время

В системе в реальном времени существует два периодических задания в реальном времени A и B. Задача A требует за 20 мс, а время выполнения составляет 10 мс; задача B выполняется каждые 50 мс, а время выполнения составляет 25 мс. Попробуйте планирование в соответствии с минимальным алгоритмом приоритета релаксации.


Приоритетное перевернутое явление
Высокоприоритетные процессы (или потоки) задерживаются или заблокированы низкими приоритетами (или потоками).

Например: есть три совершенно независимых процессов задач A, задач B и TaskC, задача приоритет, задача B, задача C минимум. Задача A и задача C Обносят один и тот же критический ресурс X.


Согласно принципу приоритета, приоритетный процесс высокого приоритета. Однако в этом случае задача A и задача C долится одни и те же критические ресурсы, существует необоснованное явление.

Высокоприоритетная задача A заблокирована из-за задачи процессов с низким приоритетом C, но и, поскольку наличие задач B низкого приоритета расширена.

Приоритетное решение

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

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


Когда задача высокого приоритета A - это ввести критическую область с использованием критического ресурса x, если уже есть низкая приоритетная процесса задача C использует этот ресурс, приоритетом является наследство.

На данный момент задача A заблокирована и с другой стороны, наследует приоритет задачи A по заданию C и остается задачей C для выхода из критических регионов.

vedro-compota

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

Единственным интересным моментом этого алгоритма является длина кванта. Переключение с одного процесса на другой занимает некоторое время — необхо­димо сохранить и загрузить регистры и карты памяти, обновить таблицы и списки, сохранить и перезагрузить кэш памяти и т. п. Вывод можно сформулировать следующим образом: слишком малый квант приведет к частому переключению процессов и небольшой эффективности, но слишком большой квант может привести к медленному реагированию на корот­кие интерактивные запросы. Значение кванта около 2 0 -5 0 мс часто является ра­зумным компромиссом.

Приоритетное планирование.

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

Несколько очередей.

Один из первых приоритетных планировщиков был реализован в системе CTSS (compatible time-shared system — совместимая система с разделением времени).Основной проблемой системы CTSS было слишком медленное переключе­ние процессов, поскольку в памяти компьютера IBM 7094 мог находиться только один процесс. Каждое переключение означало выгрузку текущего процесса на диск
и считывание нового процесса с диска. Разработчики CTSS быстро сообразили, что эффективность будет выше, если процессам, ограниченным возможностями про­цессора, выделять больший квант времени, чем если предоставлять им небольшие кванты, но часто. С одной стороны, это уменьшит количество перекачек из памяти на диск, а с другой — приведет к ухудшению времени отклика, как мы уже видели.

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

В качестве примера рассмотрим процесс, которому необходимо производить вычисления в течение 100 квантов. Вначале ему будет предоставлен один квант, затем он будет перекачан на диск. В следующий раз ему достанется 2 кванта, за­тем 4, 8,16, 32, 64, хотя из 64 он использует только 37. В этом случае понадобится всего 7 перекачек (включая первоначальную загрузку) вместо 100, которые пона­добились бы при использовании циклического алгоритма. Помимо этого, по мере погружения в очереди приоритетов процесс будет все реже запускаться, предо­ставляя процессор более коротким процессам.

“Самый короткий процесс - следующий”

Один из методов основывается на оценке длины процесса, базирующейся на предыдущем поведении процесса. При этом запускается процесс, у которого оце­ненное время самое маленькое. Допустим, что предполагаемое время исполнения команды равно Т0 и предполагаемое время следующего запуска равно Т1. Можно улучшить оценку времени, взяв взвешенную сумму этих времен аТ0 + (1 - а)Т1. Выбирая соответствующее значение а, мы можем заставить алгоритм оценки быс­тро забывать о предыдущих запусках или, наоборот, помнить о них в течение дол­гого времени. Взяв а = 1/2, мы получим серию оценок:

После трех запусков вес Т0 в оценке уменьшится до 1/8.

Метод оценки следующего значения серии через взвешенное среднее предыдущего значения и предыдущей оценки часто называют старением. Этот метод применим во многих ситуациях, где необходима оценка по предыдущим значениям. Проще всего реализовать старение при а = 1/2. На каждом шаге нужно всего лишь
добавить к текущей оценке новое значение и разделить сумму пополам (сдвинув вправо на 1 бит).

Гарантированное планирование.

Принципиально другим подходом к планированию является предоставление пользователям реальных обещаний и затем их выполнение. Вот одно обещание, которое легко произнести и легко выполнить: если вместе с вами процессором пользуются n пользователей, вам будет предоставлено 1 / n мощности процессора.

И в системе с одним пользователем и n запущенными процессорами каждому достанется 1 / n циклов процессора.
Чтобы выполнить это обещание, система должна отслеживать распределение процессора между процессами с момента создания каждого процесса. Затем система рассчитывает количество ресурсов процессора, на которое процесс имеет право, например время с момента создания, деленное на n. Теперь можно сосчитать отношение времени, предоставленного процессу, к времени, на которое он имеет право. Полученное значение 0,5 означает, что процессу выделили только полови­ну положенного, а 2,0 означает, что процессу досталось в два раза больше, чем положено. Затем запускается процесс, у которого это отношение наименьшее, пока
оно не станет больше, чем у его ближайшего соседа.

Лотерейное планирование.

Более важным процессам можно раздать дополнительные билеты, чтобы увеличить вероятность выигрыша. Если всего 100 билетов и 20 из них находятся у одного процесса, то ему достанется 20 % времени процессора. В отличие от приоритетного планировщика, в котором очень трудно оценить, что означает, скажем, приоритет 40, в лотерейном планировании все очевидно. Каждый процесс получит процент ресурсов, примерно равный проценту имеющихся у него билетов.

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

Справедливое планирование.

До сих пор мы предполагали, что каждый процесс управляется независимо от того, кто его хозяин. Поэтому если пользователь 1 создаст 9 процессов, а пользователь 2 — 1 процесс, то с использованием циклического планирования или в случае равных приоритетов пользователю 1 достанется 90 % процессора, а пользователю 2 всего 10.

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

Читайте также: