Работа в реальном времени возможна только при первом алгоритме

Вернуться в Мотортестер DIAMAG 2

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 4

Необходимые термины объяснения

Крайний срок начала: задача должна начаться раньше определенного времени

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

Классификация на основе свойств задачи в реальном времени

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

Классификация по расписанию

Определение упреждающего и не упреждающего здесь не объясняется.

• Невытесняющее
• упреждающий

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

EDF（Earliest DeadLine First）
 Смысл этого алгоритма состоит в том, что тот, кто завершает задачу, имеет ранний срок, тот, кто выполняет его первым. Это как когда мы в очереди, чтобы купить билет
 Когда это происходит, люди часто говорят, извините, я спешу отпустить меня первым.

Применение EDF в не упреждающем планировании

Поясним на примере (t это ось времени)

1. Первая задача 1 прибывает первой и выполняет задачу
2. Во время выполнения задачи 1 задачи 2, 3 поступают. То есть, когда задача 1 завершена, есть задачи 2 и 3, ожидающие выполнения.
3. Сравните сроки выполнения задач 2, 3, которые являются главнымиНачальный срокДоступно, задача 3 выполняется первой
4. Таким же образом, мы можем сделать вывод, что задача 4 выполняется перед задачей 2.
5. Таким образом, порядок выполнения составляет 1, 3, 4, 2

Применение EDF в упреждающем планировании

Давайте объясним на примере

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

1. При t = 0 A1 и B1 прибывают одновременно. В это время, сравнивая крайние сроки (крайние сроки) двух, можно видеть, что крайний срок А1 является ранним, поэтому А1 запускается первым.

2. После того, как A1 выполняется в течение 10 мс, потому что A2 еще не прибыл, поэтому нет никакого сравнения, и он непосредственно переключает выполнение B1.

3. После того, как B1 выполняется в течение 10 мс, приходит A2 и сравнивает время отключения двух из них. A2 предшествует B1. Таким образом, A2 выгружает процессор, а B1 прерывает.

4. Последующий способ планирования может быть завершен в соответствии с анализом выше.

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

Наименьший релаксационный первый алгоритм

LLF（Least Laxity First）
Идея этого алгоритма заключается в том, чтобы судить по срочности задачи. Чем актуальнее задача, тем меньше провал и выше приоритет

Slack = время, необходимое для завершения сам время выполнения текущее время

Позвольте мне привести вам пример. Например, в это время ось времени равна 0 мс, и задачи A и B. прибывают одновременно. Вам необходимо определить, какую задачу выполнить первой.

Задача A должна быть выполнена за 200 мс (или раньше), а сама A выполняется за 100 мс. Таким образом, провал А составляет 200-100-0 = 100 мс.

В настоящее время существует еще одно задание B, которое должно быть выполнено за 400 мс (или раньше). Оно должно быть выполнено в течение 150 мс, поэтому провисание составляет 400-150-0 = 250

Следовательно, вялость (более неотложная задача) выполняется в первую очередь.

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

Если в системе реального времени есть две периодические задачи A и B реального времени, задача A выполняется каждые 20 мс и 10 мс одновременно.

Задача B выполняется каждые 50 мс и 25 мс.

Наблюдая за рисунком ниже, нарисуйте график временной шкалы графиков A и B в соответствии с алгоритмом LLF.

Ответ дан ниже

Готово!

Рис. 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 не было надежды.

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

Другим популярным алгоритмом планирования является алгоритм EDF (Earliest Deadline First – процесс с ближайшим сроком завершения в первую очередь). Алгоритм EDF представляет собой динамический алгоритм, не требующий от процессов периодичности. Он также не требует и постоянства временных интервалов использования процессора. Каждый раз, когда процессу требуется процессорное время, он объявляет о своем присутствии и о своем сроке выполнения задания. Планировщик хранит список процессов, сортированный по срокам выполнения заданий. Алгоритм запускает первый процесс в списке, то есть тот, у которого самый близкий по времени срок выполнения. Когда новый процесс переходит в состояние готовности, система сравнивает его срок выполнения со сроком выполнения текущего процесса. Если у нового процесса график более жесткий, он прерывает работу текущего процесса.

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

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

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

Литература

• Современные операционные системы, Э. Таненбаум, 2002, СПб, Питер, 1040 стр., (в djvu 10.1Мбайт) подробнее>>
• Сетевые операционные системы Н. А. Олифер, В. Г. Олифер (в zip архиве 1.1Мбайт)
• Сетевые операционные системы Н. А. Олифер, В. Г. Олифер, 2001, СПб, Питер, 544 стр., (в djvu 6.3Мбайт) подробнее>>

4.1 Основные понятия планирования процессов

Планирование — обеспечение поочередного доступа процессов к одному процессору.

Планировщик — отвечающая за это часть операционной системы.

Алгоритм планирования — используемый алгоритм для планирования.

Ситуации, когда необходимо планирование:

1. Когда создается процесс

2. Когда процесс завершает работу

3. Когда процесс блокируется на операции ввода/вывода, семафоре, и т.д.

4. При прерывании ввода/вывода.

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

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

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

Основные три системы:

1. Системы пакетной обработки — могут использовать неприоритетный и приоритетный алгоритм (например: для расчетных программ).

2. Интерактивные системы — могут использовать только приоритетный алгоритм, нельзя допустить чтобы один процесс занял надолго процессор (например: сервер общего доступа или персональный компьютер).

3. Системы реального времени — могут использовать неприоритетный и приоритетный алгоритм (например: система управления автомобилем).

Задачи алгоритмов планирования:

1. Для всех систем
   Справедливость — каждому процессу справедливую долю процессорного времени
   Контроль над выполнением принятой политики
   Баланс — поддержка занятости всех частей системы (например: чтобы были заняты процессор и устройства ввода/вывода)

2. Системы пакетной обработки
   Пропускная способность — количество задач в час
   Оборотное время — минимизация времени на ожидание обслуживания и обработку задач.
   Использование процесса — чтобы процессор всегда был занят.

3. Интерактивные системы
   Время отклика — быстрая реакция на запросы
   Соразмерность — выполнение ожиданий пользователя (например: пользователь не готов к долгой загрузке системы)

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

4.2 Планирование в системах пакетной обработки

4.2.1 «Первый пришел — первым обслужен» (FIFO — First In Fist Out)

Процессы ставятся в очередь по мере поступления.

Преимущества:

• Простота

• Справедливость (как в очереди покупателей, кто последний пришел, тот оказался в конце очереди)

Недостатки:

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

4.2.2 «Кратчайшая задача — первая»

Нижняя очередь выстроена с учетом этого алгоритма

Преимущества:

• Уменьшение оборотного времени

• Справедливость (как в очереди покупателей, кто без сдачи проходит в перед)

Недостатки:

• Длинный процесс занявший процессор, не пустит более новые краткие процессы, которые пришли позже.

4.2.3 Наименьшее оставшееся время выполнение

Аналог предыдущего, но если приходит новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса.

4.3 Планирование в интерактивных системах

4.3.1 Циклическое планирование

Самый простой алгоритм планирования и часто используемый.

Каждому процессу предоставляется квант времени процессора. Когда квант заканчивается процесс переводится планировщиком в конец очереди. При блокировке процессор выпадает из очереди.

Пример циклического планирования

Преимущества:

• Простота

• Справедливость (как в очереди покупателей, каждому только по килограмму)

Недостатки:

• Если частые переключения (квант — 4мс, а время переключения равно 1мс), то происходит уменьшение производительности.

• Если редкие переключения (квант — 100мс, а время переключения равно 1мс), то происходит увеличение времени ответа на запрос.

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

Каждому процессу присваивается приоритет, и управление передается процессу с самым высоким приоритетом.

Приоритет может быть динамический и статический.

Динамический приоритет может устанавливаться так:

П=1/Т, где Т- часть использованного в последний раз кванта

Если использовано 1/50 кванта, то приоритет 50.

Если использован весь квант, то приоритет 1.

Т.е. процессы, ограниченные вводом/вывода, будут иметь приоритет над процессами ограниченными процессором.

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

Приоритетное планирование 4-х групп

4.3.3 Методы разделения процессов на группы

Группы с разным квантом времени

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

Процесс либо заканчивает работу, либо переходит в другую группу

Этот метод напоминает алгоритм — «Кратчайшая задача — первая».

Группы с разным назначением процессов

Процесс, отвечающий на запрос, переходит в группу с наивысшим приоритетом.

Такой механизм позволяет повысить приоритет работы с клиентом.

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

В системе с n-процессами, каждому процессу будет предоставлено 1/n времени процессора.

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

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

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

Процессорное время распределяется среди пользователей, а не процессов. Это справедливо если у одного пользователя несколько процессов, а у другого один.

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

Системы реального времени делятся на:

• жесткие (жесткие сроки для каждой задачи) — управление движением

• гибкие (нарушение временного графика не желательны, но допустимы) — управление видео и аудио

Внешние события, на которые система должна реагировать, делятся:

• периодические — потоковое видео и аудио

• непериодические (непредсказуемые) — сигнал о пожаре

Что бы систему реального времени можно было планировать, нужно чтобы выполнялось условие:

m — число периодических событий

i — номер события

P(i) — период поступления события

T(i) — время, которое уходит на обработку события

Т.е. перегруженная система реального времени является не планируемой.

4.4.1 Планирование однородных процессов

В качестве однородных процессов можно рассмотреть видео сервер с несколькими видео потоками (несколько пользователей смотрят фильм).

Т.к. все процессы важны, можно использовать циклическое планирование.

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

4.4.2 Общее планирование реального времени

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

Планировщик должен знать:

• частоту, с которой должен работать каждый процесс

• объем работ, который ему предстоит выполнить

• ближайший срок выполнения очередной порции задания

Рассмотрим пример из трех процессов.

Процесс А запускается каждые 30мс, обработка кадра 10мс

Процесс В частота 25 кадров, т.е. каждые 40мс, обработка кадра 15мс

Процесс С частота 20 кадров, т.е. каждые 50мс, обработка кадра 5мс

Три периодических процесса

Проверяем, можно ли планировать эти процессы.

10/30+15/40+5/50=0.808<1

Условие выполняется, планировать можно.

Будем планировать эти процессы статическим (приоритет заранее назначается каждому процессу) и динамическим методами.

4.4.3 Статический алгоритм планирования RMS (Rate Monotonic Scheduling)

Процессы должны удовлетворять условиям:

• Процесс должен быть завершен за время его периода

• Один процесс не должен зависеть от другого

• Каждому процессу требуется одинаковое процессорное время на каждом интервале

• У непериодических процессов нет жестких сроков

• Прерывание процесса происходит мгновенно

Приоритет в этом алгоритме пропорционален частоте.

Процессу А он равен 33 (частота кадров)

Процессу В он равен 25

Процессу С он равен 20

Процессы выполняются по приоритету.

Статический алгоритм планирования RMS (Rate Monotonic Scheduling)

4.4.4 Динамический алгоритм планирования EDF (Earliest Deadline First)

Наибольший приоритет выставляется процессу, у которого осталось наименьшее время выполнения.

При больших загрузках системы EDF имеет преимущества.

Рассмотрим пример, когда процессу А требуется для обработки кадра — 15мс.

Проверяем, можно ли планировать эти процессы.

15/30+15/40+5/50=0.975<1

Загрузка системы 97.5%

Динамический алгоритм планирования EDF (Earliest Deadline First)

Алгоритм планирования RMS терпит неудачу.