Планирование задач и процессов ОСРВ

3.1.Функции ядра операционных систем.

Как было указано ранее, основой любой среды исполнения в реальном времени является ядро.
Все современные ОСРВ являются многозадачными. Таким образом, все программное обеспечение,
включая также часть операционной системы, организуется в виде набора последовательных
процессов. Исходя из этого, ядро может обеспечивать сервис пяти типов:
Синхронизация ресурсов. Метод синхронизации требует ограничить доступ к общим
ресурсам (данным и внешним устройствам). Наиболее распространенный тип примитивной
синхронизации - двоичный семафор, обеспечивающий избирательный доступ к общим ресурсам.
Так, процесс, требующий защищенного семафором ресурса, вынужден ожидать до тех пор, пока
семафор не станет доступным, что свидетельствует об освобождении ожидаемого ресурса, и,
захватив ресурс, установить семафор. В свою очередь, другие процессы также будут ожидать
доступа к ресурсу вплоть до того момента, когда семафор возвратит соответствующий ресурс
системе распределения ресурсов. Системы, обладающие большей ошибкоустойчивостью, могут
иметь счетный семафор. Этот вид семафора разрешает одновременный доступ к ресурсу лишь
определенному количеству процессов.
Межзадачный обмен. Часто необходимо обеспечить передачу данных между программами
внутри одной и той же системы Кроме того, во многих приложениях возникает необходимость
взаимодействия с другими системами через сеть. Внутренняя связь может быть осуществлена через
систему передачи сообщений. Внешнюю связь можно организовать либо через датаграмму
(наилучший способ доставки), либо по линиям связи (гарантированная доставка). Выбор того или
иного способа зависит от протокола связи.
Разделение данных. В прикладных программах, работающих в реальном времени, наиболее
длительным является сбор данных. Данные часто необходимы для работы других программ или
нужны системе для выполнения каких-либо своих функций. Во многих системах предусмотрен
доступ к общим разделам памяти. Широко распространена организация очереди данных.
Применяется много типов очередей, каждый из которых обладает собственными достоинствами.
Обработка запросов внешних устройств. Каждая прикладная программа в реальном
времени связана с внешним устройством определенного типа. Ядро должно обеспечивать службы
ввода/вывода, позволяющие прикладным программам осуществлять чтение с этих устройств и
запись на них. Для приложений реального времени обычным является наличие специфического для
данного приложения внешнего устройства. Ядро должно предоставлять сервис, облегчающий
работу с драйверами устройств. Например, давать возможность записи на языках высокого уровня -
таких, как Си или Паскаль.
Обработка особых ситуаций. Особая ситуация представляет собой событие, возникающее во
время выполнения программы. Она может быть синхронной, если ее возникновение предсказуемо,
как, например, деление на нуль. А может быть и асинхронной, если возникает непредсказуемо, как,
например, падение напряжения. Предоставление возможности обрабатывать события такого типа
позволяет прикладным программам реального времени быстро и предсказуемо отвечать на
внутренние и внешние события. Существуют два метода обработки особых ситуаций -
использование значений состояния для обнаружения ошибочных условий и использование
обработчика особых ситуаций для прерывания ошибочных условий и их корректировки.
Кроме того, важнейшей функцией ядра является диспетчеризация (планирование).
Планировщик должен определять, какому процессу должно быть передано управление, а также
должен определить время, выделяемое каждому процессу.

 

3.2.Процессы и потоки. Схемы назначения приоритетов

Рассмотрим подробнее, что такое процесс. Процесс – это динамическая сущность программы,
ее код в процессе своего выполнения. Имеет:

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

Процесс может находиться в одном из следующих типичных состояний:

  • «остановлен» - процесс остановлен и не использует процессор (например, в таком состоянии процесс находится сразу после создания)
  • «терминирован» - процесс терминирован и не использует процессор (например, процесс закончился, но еще не удален операционной системой)
  • «ждет» - процесс ждет некоторого события (им может быть аппаратное или программное прерывание, сигнал или другая форма межпроцессного взаимодействия)
  • «готов» - процесс не остановлен, не терминирован, не ожидает, не удален, но и не работает (например, процесс не может получить доступ к процессору, если в данный момент выполняется другой, более высокоприоритетный процесс)
  • «выполняется» - процесс выполняется и использует процессор. В ОСРВ это обычно означает, что этот процесс является самым приоритетным среди всех процессов, находящихся в состоянии «готов»

Рассмотрим более подробно состояния процесса и переходы из одного состояния в другое.

Состояния:
1. не существует
2. не обслуживается
3. готов
4. выполняется
5. ожидает ресурс
6. ожидает назначенное время
7. ожидает события

Переходы:

1. переход 1-2 создание процесса
2. переход 2-1 уничтожение процесса
3. переход 2-3 активизация процесса диспетчером
4. переход 3-2 деактивизация процесса
5. переход 3-4 загрузка на выполнение процесса диспетчером
6. переход 4-3 требование обслуживания от процессора другим процессом (preemption – приоритетное переключение)
7. переход 4-2 завершение процесса
8. переход 4-5 блокировка процесса до освобождения требуемого ресурса
9. переход 4-6 блокировка процесса до истечения заданного времени
10. переход 4-7 блокировка процесса до прихода события
11. переход 2-6 активизация процесса приводит к ожиданию временной задержки
12. переход 2-7 активизация процесса приводит к ожиданию события
13. переход 2-5 активизация процесса приводит к ожиданию освобождения ресурса
14. переход 5-3 активизация процесса из-за освобождения ожидавшегося ресурса
15. переход 6-3 активизация процесса по истечении заданного времени
16. переход 7-3 активизация процесса из-за прихода ожидавшегося события

Таким образом, каждый процесс имеет свой жизненный цикл, состоящий из 4 стадий:
1. создание
2. загрузка
3. выполнение
4. завершение.

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

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

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

Каждому процессу и каждому потоку в ОСРВ приписывается некоторое число, называемое
приоритетом. Чем больше это число, тем важнее процесс или поток. Приоритет может быть
фиксированным (назначается при создании процесса и не меняется в течение его жизни). В
зависимости от алгоритмов планирования приоритет также может изменяться в течение жизни.

 

3.3.Планирование задач.

3.3.3. Алгоритмы и задачи планирования в ОСРВ

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

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

Ключевым вопросом планирования является выбор момента принятия решения:

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

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

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

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

В-пятых, планировщик может принимать решение по истечении кванта времени,
отпущенному процессу.

Алгоритмы планирования можно разделить на две категории согласно их поведению
после прерываний.

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

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

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

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

• Турнирное определение приоритета - приоритет последней исполнявшейся задачи
понижается.

• Определение приоритета по алгоритму round robin - приоритет задачи определяется ее
начальным приоритетом и временем ее обслуживания. Чем больше задача обслуживается
процессором, тем меньше ее приоритет (но не опускается ниже некоторого порогового значения).

Эта схема в том или ином виде применяется в большинстве UNIX систем.

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

Как видно из рисунка, процессы A-F находятся в состоянии готовности. Процессы G-Z
блокированы. Процессы A, B, C имеют наивысший приоритет. Поэтому именно эти процессы
будут разделять процессор в соответствии с алгоритмами диспетчеризации. Рассмотрим их.
«Первым пришел – первым обслужен» (алгоритм FIFO).
Является алгоритмом
планирования без переключений. Процессам предоставляется доступ к процессору в том порядке, в
котором они его запрашивают. При FIFO диспетчеризации процесс продолжает выполнение, пока
не наступит момент, когда он:
• добровольно уступает управление (заканчивается, блокируется и т.п.);
• вытесняется процессом с более высоким приоритетом.

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

«Кратчайшая задача – первая». Этот алгоритм без переключений предполагает, что
временные отрезки работы известны заранее. В этом алгоритме первым выбирается не самая
первая, а самая короткая задача. Приведем пример.

Пусть процессы A,B,C,D имеют время выполнения 8,4,4,4 единиц времени (например,
секунд). По алгоритму FIFO они должны быть запущены в том же порядке, в котором они стоят в
очереди (вариант a). Тогда время выполнения процесса A будет равно 8, B – 12, C – 16 и D – 20.
Среднее время выполнения для этих 4 процессов будет равно 14. Рассмотрим теперь очередь,
отсортированную по времени выполнения (вариант b). Теперь время выполнения процесса B будет
равно 4, C – 8, D – 12, A – 20. Среднее время в данном варианте будет равно 11.

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

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

«Карусельная диспетчеризация (циклическое планирование)».

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

Карусельная диспетчеризация. Процесс A выполняется до тех пор, пока он не использовал
свой квант времени; затем выполняется следующий процесс, находящийся в состоянии
готовности (процесс B).

«Адаптивная диспетчеризация». При адаптивной диспетчеризации процесс ведет себя
следующим образом:
• Если процесс использовал свой квант времени (т.е. он не блокировался), то его приоритет
уменьшается на 1. Это получило название снижение приоритета (priority decay).
"Пониженный" процесс не будет продолжать "снижаться", даже если он использовал еще
один квант времени и не блокировался - он снизится только на один уровень ниже своего
исходного приоритета.
• Если процесс блокируется, то ему возвращается первоначальное значение приоритета.

Адаптивная диспетчеризация. Процесс A использовал свой квант времени; его приоритет
снизился на 1. Выполняется следующий процесс в состоянии готовности (процесс B).

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

 

3.3.2. Планирование периодических процессов

Проблемы планирования задач в ОСРВ

Классификация задач реального времени:
- периодические (входят в состояние выполнения периодически);
- апериодические (выполняются при возникновении определенных событий, характеризуются
мягким реальным временем);
- спорадические (выполняются при возникновении определенных событий, характеризуются
жестким реальным временем).
В общем случае задачи РВ имеют три параметра:
- P – период запуска;
- D – максимальная задержка выдачи сигнала управления;
- C - наихудшее время выполнения.
Общие принципы планирования задач РВ
1. Целью планирование является выполнение задач за заранее определенный интервал времени.
Поэтому алгоритм планирования должен определить последовательность выполнения задач в
соответствии с их требованиями к ресурсам и ко времени исполнения.
2. Алгоритмы планирования должны быть вытесняющими.
3. Алгоритмы планирования могут быть статическими и динамическими.

Статические алгоритмы  Динамические алгоритмы

определяют план выполнения задач

низкие издержки на планирование

требуют полной предсказуемости
системы РВ

RMS

модифицирует план во время
исполнения задач

значительные издержки на
планирование

способны адаптироваться к
изменяющемуся окружению

EDF, LSTF

 

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

Система реального времени , удовлетворяющая этому условию , называется поддающейся  планированию или планируемой . Соотношение Ci / Pi является просто частью процессорного времени , используемого процессом i, а сама сумма – это коэффициент использования (или коэффициент загруженности) процессора , который , естественно , не может быть больше 1.

В качестве примера рассмотрим систему с тремя периодическими сигналами с периодами 100,
200, 500 мс соответственно . Если на обработку этих сигналов уходит 50, 30, 100 мс , система

вляется поддающейся планированию, поскольку 0,5+0,15+0,2<1. Даже при добавлении четвертого
сигнала с периодом в 1 с системой все равно можно будет управлять при помощи планирования,
пока время обработки сигнала не будет превышать 150 мс. Эти расчеты не являются абсолютно
верными, так как не учитывают время переключения контекста и не учитывает возникновение
непериодических событий.
Алгоритмы планирования заданий могут быть разделены на статические и динамические.
Статические алгоритмы определяют приемлемый план выполнения заданий по их априорным
характеристикам, динамический алгоритм модифицирует план во время исполнения заданий.
Издержки на статическое планирование низки, но оно крайне нечувствительно и требует полной
предсказуемости той системы реального времени, на которой оно установлено. Динамическое
планирование связано с большими издержками, но способно адаптироваться к меняющемуся
окружению.
Алгоритмы планирования будем рассматривать на примере 3 периодических процессов A, B,
C. Предположим, что процесс A запускается с периодом 30 мс и временем обработки 10 мс.
Процесс B имеет период 40 мс и время обработки 15 мс. Процесс C запускается каждые 50 мс и
обрабатывается за 5 мс. Суммарно эти процессы потребляют 0,808 процессорного времени, что
меньше единицы. Соответственно, система в данном примере поддается планированию.
На рис. 1 представлена временная диаграмма работы процессов. Видно, что необходимо
применить некоторый алгоритм планирования, так как в определенные моменты времени имеется
сразу несколько готовых к выполнению процессов.

Рис. 1. Три периодических процесса с разным периодом и временем обработки

Классическим примером статического алгоритма планирования реального времени для
прерываемых периодических процессов является алгоритм RMS (Rate Monotonic Scheduling –
планирование с приоритетом, пропорциональным частоте). Этот алгоритм может использоваться
для процессов, удовлетворяющих следующим условиям:
1. Каждый периодический процесс должен быть завершен за время его периода
2. Ни один процесс не должен зависеть от любого другого процесса
3. Каждому процессу требуется одинаковое процессорное время на каждом интервале
4. У непериодических процессов нет жестких сроков
5. Прерывание процесса происходит мгновенно, без накладных расходов.
Требование 2 не вполне реалистично, так как на практике разные процессы могут обращаться
к одному разделяемому ресурсу и, соответственно, блокироваться. Последнее требование
нереально, но вводится для упрощения модели системы.
Алгоритм RMS работает, назначая каждому процессу фиксированный приоритет, обратно
пропорциональный периоду и, соответственно, прямо пропорциональный частоте возникновения
событий процесса. Например, в примере рис. 1 процесс A запускается каждые 30 мс (33 раза в
секунду) и получает приоритет 33. Процесс B запускается каждые 40 мс (25 раз в секунду) и
получает приоритет 25. Процесс C запускается каждые 50 мс (20 раз в секунду) и получает
приоритет 20. Отметим, что реализация алгоритма требует, чтобы у всех процессов были разные приоритеты.

Во время работы планировщик всегда запускает готовый к работе процесс с наивысшим
приоритетом, прерывая при необходимости работающий процесс с меньшим приоритетом. Таким
образом, в нашем примере процесс A может прервать процессы B и C, процесс B может прервать C.
Процесс C всегда вынужден ждать, пока процессор не освободится.
На рис. 2 показана работа алгоритма планирования для процессов A, B, C. Изначально все три
процесса готовы к работе. Выбирается процесс с максимальным приоритетом – A. Ему разрешается
работать в течение 10 мс, требующихся процессу до завершения. Когда процесс A освобождает
процессор, начинает работать процесс B, а затем процесс C. Вместе эти процессы потребляют 30
мс, поэтому, когда процесс C заканчивает работу, снова запускается процесс A. Этот цикл
повторяется до тех пор, пока в момент времени 70 мс у системы начинается период простоя. В
момент времени 80 мс процесс B переходит в состояние готовности и запускается. Однако в момент
времени 90 мс процесс A, обладающий более высоким приоритетом, также переходит в состояние
готовности. Поэтому он прерывает выполнение процесса B и работает до момента времени 100 мс,
пока не закончит свою работу. В этот момент времени система должна выбрать между процессом
B, который не закончил обработку, и C, который находится в состоянии готовности. Выбирается
процесс B, имеющий больший приоритет.

Рис. 2. Пример алгоритмов планирования RMS и EDF.

Алгоритм RMS может быть использован только при не слишком высокой загруженности
процессора. Предположим, что процесс A имеет продолжительность работы не 10 мс, а 15 мс.
Коэффициент использования процессора в таком случае равен 0,975. Теоретически для данного
случая должен иметься метод планирования. Работа алгоритма показана на рис. 3.
На этот раз процесс B завершает обработку к моменту времени 30 мс. В этот же момент
процесс A снова приходит в состояние готовности. К тому времени, когда он заканчивает работу,
снова готов процесс B и поскольку у него приоритет больше, чем у C, то запускается процесс B.
Процесс C пропускает свой критический срок, алгоритм RMS терпит неудачу.
Теоретически было показано, что данный алгоритм гарантированно работает в любой системе
периодических процессов при условии

Таким образом, для 3 процессов максимальная загруженность процессора равна 0,780. Хотя в
нашем примере (рис. 2) загруженность процессора составила 0,808, алгоритм RMS еще работал,
хотя с другими периодами и временем обработки при том же коэффициенте загруженности
процессора мог потерпеть неудачу. При увеличении коэффициента загруженности на алгоритм
RMS не было надежды.
Теорема о верхней границы коэффициента использования ЦП
Коэффициент использования ЦП для периодической зада-чи равен U = С/Т. Задача называется
планируемой, если она удовлетворяет всем временным ограничениям, то есть ее исполнение

завершается до истечения периода. Группа задач именуется планируемой, когда планируемой
является каждая входящая в нее задача.
Теорема. Множество из n независимых периодических задач, планируемых согласно алгоритму
RMS, всегда удовлетворяет временным ограничениям, если
С 1 /Т 1 + ...+ С n /Т n <= n (2 1/n – 1) = U(n),
где С i /Т i – время выполнения и период i – ой задачи соответственно.
Значения верхней границы для числа задач от 1 до 9 приведены в таблице:

Это оценка для худшего случая (когда все задачи готовы к выполнению одновременно), а для
случайно выбранной группы задач верхняя граница равна 88%. Если периоды задач гармоничны
(являются кратными друг другу), то верхняя граница оказывается еще выше.
Достоинство алгоритма монотонных частот заключается в том, что он сохраняет устойчивость в
условиях краткосрочной перегрузки. Т.е. подмножество задач, состоящее из задач с наивысшими
приоритетами (то есть наименьшими периодами), все еще будет удовлетворять временным
ограничениям, если система в течение короткого промежутка времени подвергается
сверхрасчетной нагрузке. Задачи с низкими приоритетами по мере повышения загрузки процессора
могут эпизодически выполняться дольше положенного времени.
Применение теоремы о верхней границы коэффициента использования ЦП
Число задач – 3;
Задача t 1 : С 1 = 20; Т 1 = 100; U 1 = 0,2;
Задача t 2 : С 2 = 30; Т 2 . = 150; U 1 =0,2;
Задача t 3 : С 3 = 60; Т 3 = 200; U 3 =0,3.
Полный коэффициент использования ЦП для всех трех задач равен 0,7 < 0,779, поэтому эти задачи
будут всегда удовлетворять временным ограничениям.
Попробуем изменить характеристики третьей задачи: С 3 = 90; Т 3 = 200; U 3 =0,45. Теперь полный
коэффициент использования ЦП равен 0,85 > 0,779, следовательно теорема о верхней границе не
дает гарантии, что задачи смогут удовлетворить временным ограничениям.
Более точную оценку можно получить с помощью теоремы о времени завершения
Теорема о времени завершения
Теорема. Если имеется такое множество независимых периоди-ческих задач, в котором каждая
задача успевает завершиться вовремя в случае, когда все задачи запускаются одновременно, то
все задачи смогут завершиться вовремя при любой комбинации моментов запуска.
В этой теореме предполагается худший случай, когда все периоди-ческие задачи готовы к
исполнению одновременно. Она позволяет точно определить, является ли данное множество
независимых периодических задач планируемым. Если в указанных условиях выполнение задачи
завершается до истечения ее первого периода, то она всегда будет удовлетворять временным
ограничениям.
Чтобы убедиться в выполнении условий теоремы, необходимо проверить момент завершения
первого периода для данной задачи t i , а также моменты завершения периодов всех задач с более
высоким приоритетом, т.к задача t i может быть прервана более приоритетной задачей.
Теорема о времени завершения графически представляется с помощью временной диаграммы, на
которой показана упорядоченная последовательность выполнения группы задач.
Рассмотрим выполнение группы из трех задач со следующими характеристиками в
однопроцессорной системе.

Задача t 1 : С 1 = 20; Т 1 = 100; U 1 = 0,2.
Задача t 2 : С 2 = 30; Т 2 . = 150; U 1 =0,2.
Задача t 3 : С 3 = 90; Т 3 = 200; U 3 =0,45

Другим популярным алгоритмом планирования является алгоритм EDF (Earliest Deadline First
– процесс с ближайшим сроком завершения в первую очередь). Алгоритм EDF представляет собой
динамический алгоритм, не требующий от процессов периодичности. Он также не требует и
постоянства временных интервалов использования процессора. Каждый раз, когда процессу
требуется процессорное время, он объявляет о своем присутствии и о своем сроке выполнения
задания. Планировщик хранит список процессов, сортированный по срокам выполнения заданий.
Алгоритм запускает первый процесс в списке, то есть тот, у которого самый близкий по времени
срок выполнения. Когда новый процесс переходит в состояние готовности, система сравнивает его
срок выполнения со сроком выполнения текущего процесса. Если у нового процесса график более
жесткий, он прерывает работу текущего процесса.
Пример работы алгоритма EDF показан на рис. 2. Вначале все процессы находятся в
состоянии готовности. Они запускаются в порядке своих крайних сроков. Процесс A должен быть
выполнен к моменту времени 30, процесс B должен закончить работу к моменту времени 40,
процесс C – 50. Таким образом, процесс A запускается первым. Вплоть до момента времени 90
выбор алгоритма EDF не отличается от RMS. В момент времени 90 процесс A переходит в
состояние готовности с тем же крайним сроком выполнения 120, что и у процесса B. Планировщик
имеет право выбрать любой из процессов, но поскольку с прерыванием процесса B не связано
никаких накладных расходов, лучше предоставить возможность продолжать работу этому
процессу.

Рис. 3. Пример, в котором алгоритм RMS не может быть использован

Рассмотрим рис. 3. В момент времени 30 между процессами A и C возникает спор. Поскольку
срок выполнения процесса C равен 50 мс, а процесса A – 60 мс, планировщик выбирает процесс C.
Этим данный алгоритм отличается от алгоритма RMS, в котором побеждает процесс A, как
обладающий большим приоритетом. В момент времени 90 процесс A переходит в состояние
готовности в 4 раз. Предельный срок процесса A такой же, что и у текущего процесса, поэтому у
планировщика появляется выбор – прервать работу процесса B или нет. Поскольку необходимости
прерывать процесс B нет, то он продолжает работу.
Алгоритм EDF работает с любым набором процессов, для которых возможно планирование.
Платой за это является использование более сложного алгоритма.

Источник: http://www.kafedra-aoi.ru/folder/950SRV_LK.pdf

Категории: 

Метки: