2009 overview ИУС РВ (1185197), страница 4
Текст из файла (страница 4)
Является алгоритмомпланирования без переключений. Процессам предоставляется доступ к процессору в томпорядке, в котором они его запрашивают. При FIFO диспетчеризации процесс продолжаетвыполнение, пока не наступит момент, когда он:• добровольно уступает управление (заканчивается, блокируется и т.п.);• вытесняется процессом с более высоким приоритетом.Заметим, что при отсутствии второго условия возможен случай,высокоприоритетная задача будет ожидать окончания работы низкоприоритетной.когдаПроцесс A выполняется до тех пор, пока не блокируется.Процесс A блокируется, процесс B выполняется.«Кратчайшая задача – первая». Этот алгоритм без переключений предполагает, чтовременные отрезки работы известны заранее. В этом алгоритме первым выбирается не самаяпервая, а самая короткая задача.
Приведем пример.ABCDaBCDAbПусть процессы 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. Это получило название снижение приоритета (prioritydecay). "Пониженный" процесс не будет продолжать "снижаться", даже если ониспользовал еще один квант времени и не блокировался - он снизится только на одинуровень ниже своего исходного приоритета.• Если процесс блокируется, то ему возвращается первоначальное значение приоритета.Адаптивная диспетчеризация. Процесс A использовал свой квант времени; его приоритетснизился на 1.
Выполняется следующий процесс в состоянии готовности (процесс B).В системах реального времени наиболее распространенными являются алгоритмы FIFO,адаптивной диспетчеризации, карусельной диспетчеризации и их разновидности.Планирование периодических процессов. Статический алгоритм планирования RMS.Динамический алгоритм планирования EDF.Внешние события, на которые система реального времени должна реагировать, можноразделить на периодические (возникающие через регулярные промежутки времени) инепериодические (возникающие непредсказуемо). Возможно наличие нескольких потоковсобытий, которые система должна обрабатывать.
В зависимости от времени, затрачиваемого наобработку каждого из событий, может оказаться, что система не в состоянии своевременнообработать все события. Если в систему поступает m периодических событий, событие сномером i поступает с периодом Pi и на его обработку уходит Ci секунд работы процессора, всепотоки могут быть своевременно обработаны только при выполнении условияmCi≤1∑i =1 PiСистема реального времени, удовлетворяющая этому условию, называется поддающейся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 представлена временная диаграмма работы процессов.
Видно, что необходимоприменить некоторый алгоритм планирования, так как в определенные моменты времениимеется сразу несколько готовых к выполнению процессов.Время, мсAA1A2A3B1BB2C C10A4B3C210Начальныймомент для A1,B1, C1203040A550B4C360708090100110120130140КрайнийКрайнийКрайнийсрок для A1 срок для B1 срок для C1Рис. 1. Три периодических процесса с разным периодом и временем обработкиКлассическим примером статического алгоритма планирования реального времени дляпрерываемых периодических процессов является алгоритм RMS (Rate Monotonic Scheduling –планирование с приоритетом, пропорциональным частоте). Этот алгоритм можетиспользоваться для процессов, удовлетворяющих следующим условиям:1.
Каждый периодический процесс должен быть завершен за время его периода2. Ни один процесс не должен зависеть от любого другого процесса3. Каждому процессу требуется одинаковое процессорное время на каждом интервале4. У непериодических процессов нет жестких сроков5. Прерывание процесса происходит мгновенно, без накладных расходов.Алгоритм 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, имеющий больший приоритет.Время, мсAA1BA2A3B1B2C C1B4C2C3A1B1C1A2B2C2A3EDFA1B1C1A2B2C2A310203040A5B3RMS0A45060B3A4B3708090B3A4100C3A5B4C3A5B4110120130140Рис. 2. Пример алгоритмов планирования RMS и EDF.Алгоритм RMS может быть использован только при не слишком высокой загруженностипроцессора.
Предположим, что процесс A имеет продолжительность работы не 10 мс, а 15 мс.Коэффициент использования процессора в таком случае равен 0,975. Теоретически для данногослучая должен иметься метод планирования. Работа алгоритма показана на рис. 3.На этот раз процесс B завершает обработку к моменту времени 30 мс. В этот же моментпроцесс A снова приходит в состояние готовности. К тому времени, когда он заканчиваетработу, снова готов процесс B и поскольку у него приоритет больше, чем у C, то запускаетсяпроцесс B. Процесс C пропускает свой критический срок, алгоритм RMS терпит неудачу.Теоретически было показано, что данный алгоритм гарантированно работает в любойсистеме периодических процессов при условииmCi≤ m(21 / m − 1)∑i =1 PiТаким образом, для 3 процессов максимальная загруженность процессора равна 0,780.Хотя в нашем примере (рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
