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

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

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

Вопрос №3. «Планирование».

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

3.1.1. «Первым пришел — первым обслужен» - алгоритм без переключений

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

Основным преимуществом этого алгоритма является то, что его легко понять и столь же легко программировать.

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

Конечный результат будет следующим: каждый из процессов, ограниченных возможностями устройств ввода-вывода, считывает 1 блок данных в секунду, и им потребуется по 1000с, чтобы закончить работу. Если алгоритм планирования будет прерывать процесс, ограниченный возможностями процессора, раз в 10мс, процессы, ограниченные возможностями устройств ввода-вывода, закончат за 10с вместо 1000с и не очень замедлят работу процесса, ограниченного возможностями процессора.

3.1.2. «Кратчайшая задача — первая» - алгоритм без переключения, предполагающий, что временные отрезки работы известны заранее.

Если в очереди есть несколько одинаково важных задач, планировщик выбирает первой самую короткую задачу.

Есть четыре задачи: А, В, С и D, со временем выполнения 8, 4, 4 и 4 мин соответственно. Если запустить их в данном порядке, оборотное время задачи А будет 8 мин, В — 12 мин, С — 16 мин и D — 20 мин, и среднее время будет равно 14 мин: (8+12+16+20)/4=14. рис.а

Запустим задачи в соответствии с алгоритмом, как показано на рис.б. Теперь значения оборотного времени составляют 4, 8, 12, 20 мин соответственно, а среднее время равно 11 мин: (4+8+12+20)/4.Алгоритм оптимизирует задачу.

Рассмотрим четыре процесса со временем выполнения а, b, с, d.

Первая задача выполняется за время а.

Вторая задача выполняется за время а+b.

Третья задача выполняется за время а+b+с.

Четвертая задача выполняется за время а+b+с+d

Среднее оборотное время будет равно (4а + 3b + 2с + d)/4.

(4*4+3*4+2*4+8)/4

Очевидно, что вклад времени «а» в среднее больше, чем всех остальных интервалов времени, поэтому первой должна выполняться самая короткая задача, а последней — самая длинная, вносящая вклад, равный собственному оборотному времени.

Трехъуровневое планирование

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

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

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

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

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

Для оптимизации эффективности системы планировщик памяти должен решить, сколько и каких процессов может одновременно находиться в памяти. Количество процессов, одновременно находящихся в памяти, называется степенью многозадачности. Если планировщик памяти обладает информацией о том, какие процессы ограничены возможностями процессора, а какие — возможностями устройств ввода-вывода, он может пытаться поддерживать смесь этих процессов в памяти. Можно грубо оценить, что если некая разновидность процессов будет занимать примерно 20% времени процессора, то пяти процессов будет достаточно для поддержания постоянной занятости процессора.

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

Критерии, используемые планировщиком:

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

2. Сколько времени процесс уже использовал процессор?

3. Каков размер процесса (маленькие процессы не мешают)?

4. Какова важность процесса?

Третий уровень: отвечает за доступ процессов, находящихся в состоянии готовности, к процессору. Когда идет разговор о «планировщике», обычно имеется в виду именно планировщик процессора.

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

Циклическое планирование. Все процессы равноправны.

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

Если к концу кванта времени процесс все еще работает, он прерывается, а управление передается другому процессу.

Если процесс блокируется или прекращает работу раньше, переход управления происходит в этот момент.

Реализация циклического планирования проста. Планировщику нужно всего лишь поддерживать список процессов в состоянии готовности согласно рисунку «а». Когда процесс исчерпал свой лимит времени, он отправляется в конец списка (рис. «б»).

Основным этого алгоритма является длина кванта.

Переключение с одного процесса на другой занимает некоторое время — необходимо:

· Сохранить/загрузить регистры и карты памяти,

· обновить таблицы и списки,

· сохранить и перезагрузить кэш памяти.

Предположим, что переключение контекста занимает 1мс, включая переключение карт памяти, перезагрузку кэша и т. п.

Пусть размер кванта установлен в 5мс.

В таком случае 20% процессорного времени уйдет на администрирование — это слишком много.

Для увеличения эффективности назначим размер кванта, скажем, 100мс. Теперь пропадает только 1% времени.

Но представьте, что будет в системе с разделением времени, если 10 пользователей одновременно нажмут клавишу возврата каретки. В список будет занесено 10 процессов. Если процессор был свободен, первый процесс будет запущен немедленно, второму придется ждать 100мс и т. д. Последнему процессу, возможно, придется ждать целую секунду, если все остальные не блокируются за время кванта. Большинству пользователей секундная задержка вряд ли понравится.

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

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

Значение кванта около 20-50 мс часто является разумным компромиссом.

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

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

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

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

Часто бывает удобно сгруппировать процессы в классы по приоритетам и использовать приоритетное планирование среди классов, и циклическое планирование внутри каждого класса. На рис. 2.24 представлена система с четырьмя классами приоритетов. Алгоритм планирования выглядит следующим образом: пока в классе 4 есть готовые к запуску процессы, они запускаются один за другим согласно алгоритму циклического планирования, и каждому отводится квант времени. При этом классы с более низким приоритетом не будут их беспокоить. Если в классе 4 нет готовых к запуску процессов, запускаются процессы класса 3 и т. д. Если приоритеты постоянны, до процессов класса 1 процессор может не дойти никогда

Несколько очередей

Разработано решение с классами приоритетов.

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

В качестве примера рассмотрим процесс, которому необходимо производить вычисления в течение 100 квантов. Вначале ему будет предоставлен один квант, затем он будет перекачан на диск. В следующий раз ему достанется 2 кванта, затем 4, 8,16, 32, 64, хотя из 64 он использует только 37. В этом случае понадобится всего 7 перекачек (включая первоначальную загрузку) вместо 100, которые понадобились бы при использовании циклического алгоритма. Помимо этого, по мере погружения в очереди приоритетов процесс будет все реже запускаться, предоставляя процессор более коротким процессам.

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

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

Чтобы выполнить это обещание, система должна отслеживать распределение процессора между процессами с момента создания каждого процесса. Затем система рассчитывает количество ресурсов процессора, на которое процесс имеет право, например время с момента создания, деленное на n. Теперь можно сосчитать отношение времени, предоставленного процессу, к времени, на которое он имеет право. Полученное значение 0,5 означает, что процессу выделили только половину положенного, а 2,0 означает, что процессу досталось в два раза больше, чем положено. Затем запускается процесс, у которого это отношение наименьшее, пока оно не станет больше, чем у его ближайшего соседа.

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

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

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

Свойства лотерейного планирования.

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

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

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

До сих пор мы предполагали, что каждый процесс управляется независимо от того, кто его хозяин. Поэтому если пользователь 1 создаст 9 процессов, а пользователь 2 — 1 процесс, то с использованием циклического планирования или в случае равных приоритетов пользователю 1 достанется 90 % процессора, а пользователю 2 всего 10.

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

В качестве примера рассмотрим систему и двух пользователей, каждому из которых отведено по 50 % процессора. У первого пользователя четыре процесса: A, В, С и D, у второго один процесс Е. Если используется циклическое планирование, цепочка процессов, удовлетворяющая всем требованиям, будет выглядеть следующим образом:

AЕВЕ CEDE AЕВЕ CEDE...

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

ABECDE ABECDE...

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

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

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

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

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

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

периодические (возникающие через регулярные интервалы времени)

непериодические (возникающие непредсказуемо).

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

Системы реального времени, удовлетворяющие этому условию, называются поддающимися планированию или планируемыми

В качестве примера рассмотрим гибкую систему реального времени с тремя периодическими сигналами с периодами в 100, 200 и 500 мс соответственно. Если на обработку этих сигналов уходит 50,30 и 100 мс соответственно, система является поддающейся планированию, поскольку 0,5 + 0,15 + 0,2 < 1. Даже при добавлении четвертого сигнала с периодом в 1 с системой все равно можно будет управлять при помощи планирования, пока время обработки сигнала не будет превышать 150 мс. В этих расчетах существенным является предположение, что время переключения между процессами пренебрежимо мало.

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

В первом случае все решения планирования принимаются заранее, еще до запуска системы.

Во втором случае решения планирования принимаются по ходу дела.

Статическое планирование применимо только при наличии достоверной информации о работе, которую необходимо выполнить; и о временном графике, которого нужно придерживаться. Динамическое планирование не нуждается в подобных ограничениях.