В. Столлингс - Операционные системы (1114679), страница 100
Текст из файла (страница 100)
Планирование: ..го завершения начинается выполнение В1. В момент времени 1 = 20 в систему юступает задание А2, предельный срок которого наступает раньше предельного рока В1. Соответственно, задание В1 прерывается, и начинается выполнение 1адания А2. Выполнение В1 продолжается, начиная с момента с = 30. В момент = 40 в систему поступает задание АЗ, предельный срок которого, однако, более гоздний, чем предельный срок задания В1, так что задание В1 продолжает выюлнение до завершения в момент времени 1 = 45. В этот момент начинается ,ыполнение задания АЗ, завершающееся к моменту 1 = 55.
А1 А2 В1 АЗ А4 Аб, В2 с 105 гг .Б. Планирование периодических заданий реального времени с предельными гками завергиенил В это этом примере, где в каждой точке вытеснения планировщик дает высший .' иоритет тому заданию, предельный срок которого наступает раньше, удовле-!' зряются все требования к системе. Здесь мы смогли использовать статическое ",,' ани ов Рование на основе таблиц, поскольку задания периодичны и предсказуемы.,",. Расс ассмотрим теперь схему для работы с непериодическими заданиями с пре-;:: тьными сроками начала работы.
В верхней части рис. 10.6 приведено время; ). ттупления и предельные сроки начала работы для примера, состоящего из пязаданий, время выполнения каждого из которых составляет 20 птв. Профиль,. полнения этих заданий приведен в табл. 10.3. 0 10 20 ЗО 40 50 60 70 80 80 100 110 120 ! ! ! ! ! ! ! ! ! ! ! ! ! Предельное время В С Е О А начала работы Время поступлвния А В С 0 Е Предельное время В (опоздание) С Е(опоздание) А начала работы Рис.
10.6. Планирование непериодических заданий реального времени с предельньгми сроками начала рабогпы Таблица 10.3. Профиль выполнения пяти непериодических заданий Процесс Время поступления Время выполнения Предельное время на шла работы Простейшая схема планирования состоит в запуске задания с наиболее Ранним предельным сроком и выполнении его до полного завершения. Обратите внимание на рис.
10.6, где при использовании такого подхода несмотря на то, что задание В требует немедленного выполнения, оно отклоняется системой. В этом заключается основной риск работы с непериодическими заданиями, в особенности с предельным временем начала выполнения. Если предельное время заданий известно до того, как задания становятся готовыми к выполнению, можно усовершенствовать эту схему, повысив тем самым производительность ~и~темы. Такая стратегия, именуемая стратегией наиболее раннего предельного ~рока со свободным временем простоя, работает следующим образом. Планировщик всегда запускает подходящее задание с наиболее ранним предельным сроком, которое выполняется до полного завершения, Подходящее задание может ::-'." Глава 1О.
Многсв8)роцессорное планирование и планирование... ба Высокий Высшая частота С, С, — '+ — '+...+ — '<1 т, т, т„ (10.Ц С, С, С. — '+ — '+...+ — '<тт 2" -1 Т Т Т .Р -1) Холостой код ° — — —.т Бдение Р, время еыоолеения С 1.000 0.828 О. 779 О. 756 аказаться не готовым, и это может привести к тому, что несмотря на наличие ~товых к выполнению заданий процессор простаивает. Обратите внимание, как а нашем примере система воздерживается от выполнения задания А, несмотря за то что это единственное готовое к выполнению задание. В результате, хотя зроцессор и не используется с максимальной эффективностью, все требования к предельным срокам в нашем примере при такой схеме удовлетворены.
И, накозец, для сравнения на рис. 10.6 приведен результат использования стратегии ° первым потупил — первым обслужен". Как видно на рисунке, в этом случае атклоненными оказываются два задания — В и Е. Частотно-монотонное планирование Одним из многообещающих методов разрешения конфликтов многозадачно-,.: го планирования для периодических задач является частотно-монотонное плани- "' рование (где птопойоп(с зсЬес(п11пд — КМЯ). Эта схема была впервые предложена ' а 11.Ш73], но популярность приобрела только недавно 1ВЙ1А99, ЯНА941.
Схема.,':. КМЯ назначает приоритеты заданиям на основе их периодов. На рис. 10 7 проиллюстрированы параметры периодических заданий. Пери-:' од задания Т представляет собой интервал времени между поступлениями двух,:" последовательных заданий одного типа. Частота заданий (измеряемая в Нз) представляет собой величину, обратную периоду (в секундах). Например, зада-..: зие с периодом 50 шз имеет частоту 20 Нз. Обычно окончание периода задания, авляется жестким предельным сроком завершения задания, хотя некоторые за-,' дания могут иметь и более ранние предельные сроки. Время выполненному.
;вычисления) С представляет собой количество процессорного времени, требую'. :цегося для каждого задания определенного типа. Очевидно, что в однопроц :орной системе время выполнения не должно превышать период заданий (т.' должно выполняться С< Т). Если периодическое задание всегда выполняется золного завершения, т.е. если не имеется отклоненных из-за нехватки вычи гельного ресурса заданий, то загруженность процессора этим заданием рав 11 = С/Т. Например, если задание имеет период 80 тпз и время выполи 55 пы, то загруженность им процессора составляет 55/80 = 0.6875.
В ВМЯ заданием с наивысшим приоритетом является задание с паиме периодом; вторым по приоритетности является задание со вторым по краткости Риодом и т.д. Соответственно, в случае готовности для выполнения несколысих зий первым обслуживается задание с наименьшим периодом.
Если мы изобра приоритеты заданий как Функцию их частоты, то получим монотонно возрастаю Функцию (см. рнс, 10.8), огкуда и происходит название метода. М вЂ” 3дй Р. РОЮТ оис. 10.7. Временная диаграмма аериодичесного задания Частота Рис. 10.В. Множество заданий в методе НМЯ 1'И~АЛВ911 Одной из характеристик эффективности алгоритма периодического планирования является его гарантия соответствия всем жестким предельным срокам. Предположим, что у нас имеется и заданий, каждое из которых имеет свое фиксированное время выполнения и период.
Тогда необходимым условием соответствия всем жестким предельным срокам является выполнение следующего неравенства: Сумма загруженности процессора разными заданиями не может превышать 1, что соответствует полной загрузке процессора. Неравенство (10.1) определяет верхнюю границу количества заданий, которые может успешно обслуживать идеальный алгоритм планирования. Для конкретного реального алгоритма гра.- ница может оказаться ниже.
Так, можно показать, что для алгоритма ВМВ справедливо следующее неравенство: В табл. 10.4 приведены некоторые значения верхней границы для метода ВМЯ. При возрастании количества заданий верхняя граница стремится к значению 1п2=0.693. Таблица 10.4. Значения верхней границы загруженности для метода ИМЯ 1'лава И). Многопроцессорное планирование и планирование... 54ф' Окончание табл. 10.4 и 2' — 1 О. 743 0.734 1п 2 = 0.693 + Сг + ~ < З 2з -1 = 0.779 . у, Часть 4. Планиро В качестве примера рассмотрим три периодических задания ° Задание Р,: С1 = 20; Т~ = 100; У, = 0.2.
° Задание Р2: С~ = 40; Т, = 150; У, = 0.267. е Задание Рз: Се = 100; Те = 350; Уз = 0.286. Общая загруженность процессора этими тремя заданиями составляет, .2+0.267+0.286 0.753. Верхняя граница загруженности этих трех задач при е спользовании метода ВМЯ составляет Поскольку общая загруженность процессора по обработке приведенных за- ,аний ниже верхней границы для метода ВМЯ, можно сделать вывод, что при.-'.. 1МБ-планировании будут успешно выполнены все задания, Можно также показать, что верхняя граница из (10.1) справедлива для мето ~аиболее раннего предельного срока. Таким образом, при применении планирование': наиболее ранним предельным сроком можно достичь более высокой загрузки рессора и, соответственно, обработать большее количество заданий. Тем не менее 'од ВМЯ широко распространен и используется во многих промышленных прил ~иях.
В работе 1ЯНА9Ц это поясняется следующими причинами. 1. На практике отличие производительности невелико. Кроме того, неравенс " во 110.2) консервативно, и на практике зачастую достигается 90Уо-ная грузка процессора. 2. Большинство жестких систем реального времени содержат мягкие компоне такие, как некритичный вывод на экран или встроенное самотестирование, полняющееся с низким приоритетом. Эти компоненты используют процессор время, которое остается после ВМЯ-планирования жестких заданий.
3. При использовании ВМЯ проще обеспечить стабильность. Когда система в состоянии обеспечить все предельные сроки в силу перегруженности временных ошибок, необходимо гарантировать выполнение предель сроков для подмножества обязательных заданий. При статическом назна нии приоритетов гарантируется только корректность выполнения осно задач с относительно высокими приоритетами. Это может быть достигнуто. в ВМЯ-планировании, путем реструктурирования обязательных задач повышения их частоты либо посредством изменен пр, ори тетов МБ для д ножества обязательных з дач При планировании с на б и олее ранним предельным сроком приоритеты периодических заданий изм еняются от одного периода к другому, что усложняет обеспечение корректной работь| обязательных заданий с жесткими предельными сроками. на традиционном планировании ПК1Х, описанном ле ., с добавлением двух классов планирования для мягких заданий реального времени.
Таким образом, в 1.1ппх имеется три класса планирования. ° ЯСНЕВ Р1РО. Потоки реального времени с использованием планирования по принципу "первым вошел — первым вышел"'. е ЯСНЕВ ВК. П . Потоки реального времени с использованием кругового планирования. ° ЯСНЕХ~ ОТН ОТНЕК. Прочие потоки, не являющиеся потоками реального времени. В пределах каждого класса могут использоваться различные приоритеты, ЯСНЕВ причем приоритеты классов реального времени выше приоритетов в класса ОТНЕВ. Для потоков Р1РО применимы следующие правила.
1. Система не прерывает выполняющийся поток этого класса за исключением следующих ситуаций: а) становится готовым другой поток этого же класса с более высоким приоритетом; б) выполнение потока блокируется ожиданием события (например, выполнения операции ввода-вывода)," в) выполняющийся поток добровольно отдает процессор посредством вызова примитива эс11еб у1е1о. 2. При прерывании выполняющегося потока Р1РО он помещается в очередь, предназначенную для его уровня приоритета. 3. Если поток оток Р1РО приходит в состояние готовности к выполнению и имеет более высокий приоритет, чем выполняющийся, то текущий поток вытесняется и начинает выполняться готовый поток с высшим приоритетом. Если таких потоков несколько, выбирается поток, находившийся в состоянии ожидания дольше других. Стратегия ЯСНЕВ ВВ аналогична стратегии БСНЕ0 Р1РО за исключением добавления в временной квоты, связанной с каждым потоком.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
