Лекция
Это окончание невероятной информации про операционная система мягкого времени.
...
переключения, поэтому ее не рекомендуют использовать в системах с разделением времени.
Рис. 5. Планирование по принципу FIFO
Как правило, принцип FIFO редко используется самостоятельно в качестве основной дисциплины обслуживания, чаще он комбинируется с другими дисциплинами, например, диспетчирование процессов может выполняться согласно их приоритетам, однако процессы с одинаковыми приоритетами диспетчируются по принципу FIFO.
Планирование по принципу RR предполагает диспетчирование процессов по принципу FIFO, но каждый процесс получает временной квант, в течение которого он может использовать ресурсы ЦП. Если завершения процесса не происходит по истечении кванта времени, то этот процесс переводится в конец списка готовых к выполнению процессов, а ресурсы ЦП предоставляются следующему процессу из списка. Такой алгоритм планирования подходит, например, для работы с разделением времени, когда система должна гарантировать приемлемые времена ответа для всех интерактивных пользователей.
Рис. 6. Планирование по принципу RR
Очевидно, что для данного алгоритма планирования основной вопрос заключается в определении размера кванта времени, и следует ли делать его фиксированным или переменным. Очевидно, если квант времени выбирается слишком большим, то система RR фактически вырождается в FIFO, т.к. каждому процессу выделяется достаточно времени для завершения. Если же квант времени выбирается слишком малым, то контекстные переключения начинают играть доминирующую роль, что в итоге ухудшает характеристики системы.
Механизм планирования должен оказывать предпочтение коротким заданиям с лимитируемым вводом-выводом, чтобы обеспечить хороший коэффициент использования устройств ввода-вывода; как можно быстрее определять характер задания, чтобы соответствующим образом ппланировать его выполнение. Многоуровневые очереди с обратными связями позволяют достичь этих целей.
При таком алгоритме планирования, новый процесс входит в сеть очередей с конца верхней очереди и перемещается по ней по принципу FIFO пока не получит в свое распоряжение ЦП. Если процесс не успевает завершиться по истечении отведенного ему кванта времени, он перемещается в конец очереди более низкого уровня и получит в свое распоряжение ЦП, когда достигнет начала этой очереди и не будет ожидающих процессов в верхней очереди. Обычно в такой многоуровневой системе предусматривается нижняя очередь, организованная по принципу RR, где процесс циркулирует до окончательного завершения. Как правило, в таких структурах квант времени при переходе в каждую очередь более низкого уровня увеличивается.
Рис. 7. Многоуровневые очереди с обратными связями
Многоуровневые очереди с обратными связями представляют собой идеальный механизм, позволяющийцессы на категории в соответствиии с их потребностями в ресурсах ЦП. В системе с разделением времени, каждый раз, когда процесс выходит из сети очередей, он может быть отмечен признаком очереди самого низкого уровня, где он побывал, что дает возможность впоследствии, когда он снова войдет в сеть очередей, направлять его прямо в ту очередь, в которой он в последний раз завершал свою работу. Заметим, что при таком алгоритме планирования, чем дольше процесс занимает ЦП, тем ниже становится его приоритет, пока процесс не опускается в очередь самогго приоритета. Размер же кванта времени, выделяемого процессу, как правило увеличивается по мере перехода процесса в каждую следующую очередь.
Сеть мноуровневых очередей с обратными связями — это пример адаптивного механизма планирования, который реагирует на изменение поведения контролируемой им системы.
В связи с проблемой дедлайнов главной проблемой в ОСРВ становится планирование задач (scheduling), которое обеспечивало бы предсказуемое поведение системы при всех обстоятельствах. Процесс с дедлайнами должен стартовать и выполняться так, чтобы он не пропустил ни одного своего дедлайна. Если это невозможно, процесс должен быть отклонен.
В связи с проблемами планирования в ОСРВ используются статические алгоритмы планирования (RMS – Rate Monotonic Scheduling) [LL73] и динамические алгоритмы планирования (EDF – Earliest Deadline First).
Примером такого алгоритма является алгоритм планирования со статическим расписанием. Он подразумевают, что расписание запуска задач составляется заранее, до старта системы. Планировщик лишь просто следует этому расписанию и не составляет его в ходе работы. Строго это относится, разумеется, только к периодическим задачам. Если же имеются еще и спорадические задачи, то планировщик, естественно, должен выбрать моменты времени запуска таких задач по ходу работы.
К преимуществам данного класса алгоритмов относят следующие обстоятельства:
Благодаря этим качествам, алгоритмы именно этого типа чаще всего применяются там, где требуется высокая надежность (автопилоты и т.п.)
К недостаткам — следующие:
Принцип работы планировщиков на основе приоритета задач состоит в том, что в каждый момент момент времени исполняется та задача, которая имеет наивысший приоритет. Различные виды планировщиков различаются правилами, в соответствии с которыми назначается приоритет. У работ одной и той же задачи может быть разный приоритет. В этом случае планировщик (или алгоритм) называется динамическим алгоритмом с динамическими приоритетами.
Рассмотрим 2 алгоритма динамического планирования с динамическими приоритетами
При этом имеются 2 модификации алгоритма EDF:
Под вытеснением имеется ввиду то, что если во время работы какой-то задачи возникает работа другой задачи с приоритетом выше, чем у работающей в данный момент, то управление передается вновь возникшей задаче.
При невытесняющем EDF задача всегда доделывает свою очередную работу до конца, независимо от того, появились ли во время работы этой задачи другие задачи с более высоким приоритетом или не появились.
Алгоритмы EDF и LLF считаются оптимальными для любого набора задач (периодические с любым соотношением между периодами и крайними сроками, спорадические) если:
Другим классом динамических алгоритмов являются динамические алгоритмы планирования со статическими приоритетами. Напомним, что принцип работы любого планировщика на основании приоритета состоит в том, что в каждый момент времени исполняется та задача, которая имеет наивысший приоритет. В случае динамических планировщиков со статическими приоритетами задач приоритет задачи, будучи однажды ей назначен, не изменяется с течением времени. Приводимые далее способы назначения приоритетов ориентированы на системы периодических задач.
Существует 2 распространенных способа назначения приоритетов:
Эти алгоритмы неоптимальны, так как при определенных условиях могут привести к превышению дедлайна, однако ввиду их относительной простоты именно они чаще используются в системах реального времени
Обычно в ОСРВ используется планирование с приоритетами, прерывающими обслуживание, которое основано на RMS. Приоритетное прерывание обслуживания (preemption) является неотъемлемой составляющей ОСРВ, т.к. в системе реального времени должны существовать гарантии того, что событие с высоким приоритетом будет обработано перед событием более низкого приоритета. Все это ведет к тому, что ОСРВ нуждается не только в механизме планирования на основе приоритетов, прерывающих обслуживание, но также и в соответствующем механизме управления прерываниями. Более того, ОСРВ должна быть способна запрещать прерывания, когда необходимо выполнить критический код, который нельзя прерывать. Длительность обработки прерываний должна быть сведена к минимуму.
ОСРВ должна обладать развитой системой приоритетов. Во-первых, это требуется потому, что система сама может рассматриваться как набор серверных приложений, подразделяющихся на потоки, и несколько высоких уровней приоритетов должно быть выделено системным процессам и потокам. Во-вторых, в сложных приложениях необходимо все потоки реального времени помещать на разные приоритетные уровни, а потоки не реального времени помещать на один уровень (ниже, чем любые потоки реального времени). При этом потоки не реального времени можно обрабатывать в режиме циклического планирования (RRS – round-robin scheduling), при котором каждому процессу предоставляется квант времени процессора, а когда квант заканчивается, контекст процесса сохраняется, и он ставится в конец очереди. Во многих ОСРВ для планирования задач на одном уровне используется RRS. Приоритетный уровень 0 обычно используется для холостого режима.
При планировании на основе приоритетов необходимо решить две обязательные проблемы:
Для борьбы с инверсией приоритетов в ОСРВ часто используется механизм наследования приоритетов, однако при этом приходится отказываться от планирования на основе RMS, поскольку приоритеты становятся динамическими.
Ключевой характеристикой ОСРВ является уровень ее согласованности в отношении количества времени, необходимого для принятия и выполнения задачи приложения ; изменчивость - это « джиттер ». «Жесткая» операционная система реального времени (Hard RTOS) имеет меньший джиттер, чем «мягкая» операционная система реального времени (Soft RTOS). Поздний ответ - это неправильный ответ в жесткой ОСРВ, в то время как поздний ответ приемлем в мягкой ОСРВ. Основная цель дизайна - не высокая пропускная способность , а скорее гарантия категории « мягких» или «жестких» характеристик. ОСРВ, которая обычно или в целом может уложиться в срок, является ОС реального времени, но если она может уложиться в срок детерминированно, то это ос жесткого реального времени .
RTOS имеет расширенный алгоритм планирования . Гибкость планировщика позволяет более широкую оркестровку компьютерных систем приоритетов процессов, но ОС реального времени чаще выделяется для узкого набора приложений. Ключевыми факторами в ОС реального времени являются минимальная задержка прерывания и минимальная задержка переключения потоков ; ОС реального времени ценится больше за то, насколько быстро и предсказуемо она может реагировать, чем за объем работы, которую она может выполнить за определенный период времени.
См. Полный список в сравнении операционных систем реального времени . Также см. Список операционных систем для всех типов операционных систем.
RTOS - это операционная система, в которой время, необходимое для обработки входного стимула, меньше времени, прошедшего до следующего входного стимула того же типа.
Наиболее распространенные конструкции:
В проектах с разделением времени задачи переключаются чаще, чем это необходимо, но обеспечивают более плавную многозадачность , создавая иллюзию, что процесс или пользователь единолично использует машину.
Ранние конструкции ЦП требовали большого количества циклов для переключения задач, в течение которых ЦП не мог делать больше ничего полезного. Поскольку переключение занимало очень много времени, ранние операционные системы пытались свести к минимуму потери процессорного времени, избегая ненужного переключения задач.
В типовых проектах задача имеет три состояния:
Большинство задач заблокированы или готовы большую часть времени, потому что обычно только одна задача может выполняться одновременно на ЦП . Количество элементов в очереди готовности может сильно различаться в зависимости от количества задач, которые система должна выполнить, и типа планировщика, который система использует. В более простых, не вытесняющих, но по-прежнему многозадачных системах задача должна отдавать свое время ЦП другим задачам, что может привести к тому, что очередь готовности будет иметь большее количество общих задач в состоянии готовности к выполнению ( нехватка ресурсов ) .
Обычно структура данных списка готовности в планировщике предназначена для минимизации наихудшего времени, затрачиваемого в критическом разделе планировщика, в течение которого запрещается вытеснение, и в некоторых случаях все прерывания отключены, но выбор структуры данных зависит также от максимального количества задач, которые могут быть в готовом списке.
Если в готовом списке никогда не больше нескольких задач, то двусвязный список готовых задач, вероятно, будет оптимальным. Если в готовом списке обычно всего несколько задач, но иногда и больше, то список следует отсортировать по приоритету. Таким образом, поиск задачи с наивысшим приоритетом для выполнения не требует итерации по всему списку. Затем для вставки задачи требуется пройти по списку готовности до тех пор, пока не будет достигнут конец списка или задача с более низким приоритетом, чем у вставляемой задачи.
Следует проявлять осторожность, чтобы не препятствовать вытеснению во время этого поиска. Более длинные критические секции следует разделять на небольшие части. Если происходит прерывание, которое делает задачу с высоким приоритетом готовой во время вставки задачи с низким приоритетом, эта задача с высоким приоритетом может быть вставлена и запущена непосредственно перед вставкой задачи с низким приоритетом.
Критическое время отклика, иногда называемое временем обратного хода, - это время, необходимое для постановки новой готовой задачи в очередь и восстановления состояния выполнения задачи с наивысшим приоритетом. В хорошо спроектированной ОСРВ для подготовки новой задачи потребуется от 3 до 20 инструкций на каждую запись очереди готовности, а для восстановления задачи готовности с наивысшим приоритетом потребуется от 5 до 30 инструкций.
В более продвинутых системах задачи реального времени совместно используют вычислительные ресурсы со многими задачами, не относящимися к реальному времени, и готовый список может быть сколь угодно длинным. В таких системах список готовых планировщиков, реализованный как связанный список, будет неадекватным.
Некоторые часто используемые алгоритмы планирования RTOS:
Многозадачная операционная система, такая как Unix , плохо справляется с задачами реального времени. Планировщик отдает наивысший приоритет заданиям с наименьшей нагрузкой на компьютер, поэтому невозможно гарантировать, что для критичного по времени задания будет доступ к достаточному количеству ресурсов. Системы многозадачности должны управлять совместным использованием данных и аппаратных ресурсов между несколькими задачами. Обычно для двух задач небезопасно обращаться к одним и тем же конкретным данным или аппаратному ресурсу одновременно. Есть три распространенных подхода к решению этой проблемы:
Операционные системы общего назначения обычно не позволяют пользовательским программам маскировать (отключать) прерывания , потому что пользовательская программа может управлять процессором столько, сколько пожелает. Некоторые современные процессоры не позволяют коду пользовательского режима отключать прерывания, поскольку такое управление считается ключевым ресурсом операционной системы. Однако многие встроенные системы и ОСРВ позволяют самому приложению работать в режиме ядра для большей эффективности системных вызовов, а также для того, чтобы приложение могло иметь больший контроль над операционной средой, не требуя вмешательства ОС.
В однопроцессорных системах приложение, работающее в режиме ядра, и маскирование прерываний - это метод с наименьшими издержками для предотвращения одновременного доступа к общему ресурсу. Хотя прерывания замаскированы, и текущая задача не выполняет блокирующий вызов ОС, текущая задача имеет исключительное использование ЦП, поскольку никакая другая задача или прерывание не может взять на себя управление, поэтому критическая секция защищена. Когда задача выходит из критического раздела, она должна демаскировать прерывания; ожидающие прерывания, если таковые имеются, будут выполнены. Временное маскирование прерываний должно выполняться только тогда, когда самый длинный путь через критический участок короче желаемой максимальной задержки прерывания.. Обычно этот метод защиты используется только тогда, когда критическая секция состоит всего из нескольких инструкций и не содержит циклов. Этот метод идеален для защиты аппаратных битовых регистров, когда биты управляются различными задачами.
Когда общий ресурс должен быть зарезервирован, не блокируя все другие задачи (например, ожидание записи во флэш-память), лучше использовать механизмы, также доступные в операционных системах общего назначения, такие как мьютекс и межпроцессный обмен сообщениями под контролем ОС. Такие механизмы включают в себя системные вызовы и обычно вызывают код диспетчера ОС при выходе, поэтому для их выполнения обычно требуются сотни инструкций ЦП, в то время как маскирование прерываний может занимать всего одну инструкцию на некоторых процессорах.
(Нерекурсивный) мьютекс либо заблокирован, либо разблокирован. Когда задача заблокировала мьютекс, все другие задачи должны ждать, пока мьютекс не будет разблокирован его владельцем - исходным потоком. Задача может установить тайм-аут на ожидание мьютекса. Есть несколько хорошо известных проблем с проектами на основе мьютексов, такими как инверсия приоритета и взаимоблокировки .
При инверсии приоритета задача с высоким приоритетом ожидает, потому что задача с низким приоритетом имеет мьютекс, но задаче с более низким приоритетом не дается процессорное время для завершения своей работы. Типичное решение - заставить задачу, владеющую мьютексом, «унаследовать» приоритет самой высокой ожидающей задачи. Но этот простой подход становится все более сложным , когда есть несколько уровней ожидания: задача А жду мьютекса запирается задача B , который ожидает мьютекс заблокированного задачи C . Обработка нескольких уровней наследования заставляет другой код работать в контексте с высоким приоритетом и, таким образом, может вызвать нехватку потоков со средним приоритетом.
В тупике две или более задач блокируют мьютекс без тайм-аутов, а затем вечно ждут мьютекса другой задачи, создавая циклическую зависимость. Самый простой сценарий взаимоблокировки возникает, когда две задачи поочередно блокируют два мьютекса, но в обратном порядке. Тупиковая ситуация предотвращается благодаря тщательному проектированию.
Другой подход к совместному использованию ресурсов заключается в том, что задачи отправляют сообщения по организованной схеме передачи сообщений . В этой парадигме ресурсом напрямую управляет только одна задача. Когда другая задача хочет опросить ресурс или манипулировать им, она отправляет сообщение управляющей задаче. Хотя их поведение в реальном времени менее четко, чем у семафоровСистемы, простые системы, основанные на сообщениях, избегают большинства опасностей тупиковых ситуаций протокола и, как правило, ведут себя лучше, чем системы семафоров. Однако возможны проблемы, подобные проблемам семафоров. Инверсия приоритета может происходить, когда задача работает с сообщением с низким приоритетом и игнорирует сообщение с более высоким приоритетом (или сообщение, косвенно исходящее из задачи с высоким приоритетом) в своей очереди входящих сообщений. Взаимоблокировки протокола могут возникать, когда две или более задачи ожидают друг от друга отправки ответных сообщений.
Поскольку обработчик прерывания блокирует выполнение задачи с наивысшим приоритетом и поскольку операционные системы реального времени предназначены для минимизации задержки потока, обработчики прерываний обычно используются как можно короче. Обработчик прерывания откладывает все взаимодействия с оборудованием, если это возможно; обычно все, что необходимо, - это подтвердить или отключить прерывание (чтобы оно больше не повторялось при возврате обработчика прерывания) и уведомить задачу о том, что работа должна быть выполнена. Это можно сделать, разблокировав задачу драйвера, выпустив семафор, установив флаг или отправив сообщение. Планировщик часто предоставляет возможность разблокировать задачу из контекста обработчика прерываний.
ОС поддерживает каталоги объектов, которыми она управляет, таких как потоки, мьютексы, память и т. Д. Обновления этого каталога должны строго контролироваться. По этой причине может возникнуть проблема, когда обработчик прерывания вызывает функцию ОС, в то время как приложение также выполняет это. Функция ОС, вызываемая из обработчика прерывания, могла обнаружить, что база данных объектов находится в несогласованном состоянии из-за обновления приложения. Есть два основных подхода к решению этой проблемы: унифицированная архитектура и сегментированная архитектура. ОСРВ, реализующие унифицированную архитектуру, решают проблему, просто отключая прерывания во время обновления внутреннего каталога. Обратной стороной этого является то, что задержка прерывания увеличивается, потенциально теряя прерывания. Сегментированная архитектура не выполняет прямых вызовов ОС, но делегирует работу, связанную с ОС, отдельному обработчику. Этот обработчик работает с более высоким приоритетом, чем любой поток, но ниже, чем обработчики прерываний. Преимущество этой архитектуры состоит в том, что она добавляет очень мало циклов для задержки прерывания. В результате ОС, реализующие сегментированную архитектуру, более предсказуемы и могут работать с более высокой частотой прерываний по сравнению с унифицированной архитектурой
Точно так же режим управления системой на x86-совместимом оборудовании может занять слишком много времени, прежде чем он вернет управление операционной системе. Как правило, неправильно писать программы реального времени для оборудования x86.
Выделение памяти более важно в операционной системе реального времени, чем в других операционных системах.
Во-первых, для стабильности не должно быть утечек памяти (память, которая выделяется, но не освобождается после использования). Устройство должно работать бесконечно, без перезагрузки. По этой причине использование динамической памяти не одобряется. По возможности, все необходимое выделение памяти указывается статически во время компиляции.
Еще одна причина избегать динамического распределения памяти - это фрагментация памяти. При частом выделении и освобождении небольших фрагментов памяти может возникнуть ситуация, когда доступная память разделена на несколько разделов и ОСРВ неспособна выделить достаточно большой непрерывный блок памяти, хотя свободной памяти достаточно. Во-вторых, важна скорость выделения. Стандартная схема распределения памяти сканирует связанный список неопределенной длины, чтобы найти подходящий свободный блок памяти , что неприемлемо в ОСРВ, поскольку выделение памяти должно происходить в течение определенного промежутка времени.
Поскольку механические диски имеют гораздо более длительное и непредсказуемое время отклика, подкачка файлов на диск не используется по тем же причинам, что и выделение ОЗУ, описанное выше.
Простой алгоритм блоков фиксированного размера работает довольно хорошо для простых встроенных систем из-за его низких накладных расходов.
В заключение, эта статья об операционная система мягкого времени подчеркивает важность того что вы тут, расширяете ваше сознание, знания, навыки и умения. Надеюсь, что теперь ты понял что такое операционная система мягкого времени, ос жесткого реального времени, операционная система реального времени, осрв и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Операционные системы и системное программировние
Часть 1 Операционная система мягкого и жесткого реального времени и отличие от ОС общего назначения - особенности,
Часть 2 Взаимодействие между задачами и разделение ресурсов - Операционная система мягкого
Часть 3 Характеристики операционных систем реального времени - Операционная система мягкого и
Комментарии
Оставить комментарий
Операционные системы и системное программировние
Термины: Операционные системы и системное программировние