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

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

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

Избежать указанного недостатка позволяет невытесняющий алгоритм, при котором планировщик выбирает первым для выполнения самый короткий процесс (задачу). Этот алгоритм называется «кратчайший процесс (задача) - первый» или SJN (Shortest Job Next)/7,8,12/. Алгоритм позволяет уменьшить оборотное время - среднее время от момента поступления процесса (задачи) на выполнение до завершения выполнения.

Пусть имеется четыре процесса со временем выполнения первого - a, второго - b, третьего - c и четвертого - d. Тогда первый процесс выполнится через время t_a=a, второй - через время t_b=a+b, третий через время t_c=a+b+c, а четвертый через время t_d=a+b+c+d. Следовательно, среднее оборотное время t_o вычисления четырех процессов равно t_o=(t_a+t_b+t_c+t_d)/4 =(4a+3b+2c+d)4. Очевидно, что вклад времени a в среднее больше, чем всех остальных интервалов времени, поэтому первым должен выполняться самый короткий процесс, а последним - самый длинный, вносящий вклад, равный собственному оборотному времени. Этот вывод справедлив для любого количества процессов и потоков.

Пример 3.1. Положим, имеется четыре процесса со временем выполнения первого a=10, второго b=8, третьего c=6 и четвертого d=4 единиц времени.

Вычислим среднее оборотное время t_o1 четырех процессов для случая выполнения в порядке a-b-c-d. Это время равно t_o1=(4a+3b+2c+d)4=20.

Вычислим среднее оборотное время t_o2 четырех процессов для случая выполнения в порядке «кратчайший процесс - первый», т.е. d-c-b-a. Это время равно t_o2=(4d+3c+2b+a)4=15. Очевидно, t_o1> t_o2.

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

Следующей версией предыдущего алгоритма планирования является алгоритм наименьшего оставшегося времени выполнения или SRT (Shortest Remaining Time)/7,8,12/. В соответствии с этим алгоритмом планировщик всякий раз выбирает на выполнение процесс с наименьшим оставшимся временем выполнения. Когда появляется новый процесс, его полное время выполнения сравнивается с оставшимся временем выполнения текущего процесса. Если время выполнения нового процесса меньше, текущий процесс приостанавливается и управление передается новому процессу. Этот алгоритм позволяет быстро обслуживать короткие процессы.

Упражнение 3.1. В каком порядке в зависимости от уровня подготовки студентов преподавателю целесообразно проводить опрос студентов на экзамене, чтобы экзамен не был чрезмерно долгим? В каком порядке в зависимости от сложности вопросов в экзаменационном билете студенту целесообразно отвечать на вопросы в билете, чтобы сократить сроки ответа?

3.4 Алгоритмы планирования, основанные на квантовании

В основе многих вытесняющих алгоритмов планирования лежит концепция квантования. В соответствии с этой концепцией каждому потоку поочередно для выполнения предоставляется ограниченный непрерывный период процессорного времени - квант (time slice). Этот алгоритм получил название циклического (карусельного) или RR (Round Robin) /1,7,8,12/.

Смена активного потока происходит в следующих случаях:

поток завершился и покинул систему;

произошла ошибка;

поток перешел в состояние ожидания;

исчерпан квант процессорного времени, отведенный данному потоку.

Размещено на http://www.allbest.ru

Поток, который исчерпал свой квант, переводится в состояние готовности и ожидает, когда ему будет предоставлен новый квант процессорного времени, а на выполнение в соответствии с определенным правилом выбирается новый поток из очереди готовых. Граф состояний потока, изображенный на рис.3.1, соответствует алгоритму планирования, основанному на квантовании.

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

Если квант короткий, то суммарное время, которое проводит поток в ожидании процессора, прямо пропорционально времени, требуемому для его выполнения (то есть времени, которое потребовалось бы для выполнения этого потока при монопольном использовании ВС). Действительно, поскольку время ожидания между двумя циклами выполнения равно q(n-1), а количество циклов B/q, где B - требуемое время выполнения, то W=(B\q)xq(n-1)=B(n-1).

Заметим, что это соотношение основано на предположении, что B>>q. При этом не учитывается, что потоки могут использовать кванты не полностью, что часть времени они могут потратить на ввод-вывод, что количество потоков в системе может динамически меняться и т.д.

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

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

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

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

Размещено на http://www.allbest.ru

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

3.5 Алгоритмы планирования, основанные на приоритетах

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

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

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

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

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

Существуют две разновидности приоритетного планирования: обслуживание с относительными приоритетами и обслуживание с абсолютными приоритетами.

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

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

В системах с абсолютными приоритетами (рис.3.4) выполнение активного потока прерывается еще при одном условии: если в очереди готовых потоков появился поток, приоритет которого выше приоритета активного потока. В этом случае прерванный поток переходит в состояние готовности.

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

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

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

3.6 Смешанные алгоритмы планирования

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

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

Подобным образом реализовано планирование в системах Windows NT/2000, в которых квантование сочетается с динамическими абсолютными приоритетами. На выполнение выбирается готовый поток с наивысшим приоритетом и ему выделяется квант времени. Если во время выполнения в очереди готовых потоков появляется поток с более высоким приоритетом, то он вытесняет выполняемый поток. Вытесняющий поток возвращается в очередь готовых, причем он становится впереди всех остальных потоков, имеющих такой же приоритет.

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

4. ПЛАНИРОВАНИЕ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ В СИСТЕМАХ РЕАЛЬНОГО ВРЕМЕНИ

4.1 Принципы планирования в системах реального времени

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

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

Выделим следующие группы алгоритмов планирования вычислительных процессов в системах реального времени /7,8,12,13/.

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

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

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

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

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

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

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

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

4.2Планирование с предельными сроками

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

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

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

Предельное время начала выполнения. Время, когда должно начаться выполнение задания.

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

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

Требования к ресурсам. Множество ресурсов (отличных от процессора), требующихся заданию при его выполнении.

Приоритет. Мера относительной важности задания. Задания в «жестком» реальном времени имеют абсолютный приоритет, нарушение временных ограничений этих заданий недопустимо, в противном случае неизбежны повреждения объекта и катастрофические последствия. В системах «мягкого» реального времени возможны редкие нарушения временных ограничений заданий, но они не приводят к фатальным последствиям и лишь ухудшают свойства систем и качество управления.

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

Доказано /1,7,8,13/, что для стратегии вытеснения применение планирования, выбирающего для выполнения задание с наиболее ранним предельным временем завершения, минимизирует долю заданий с нарушенными временными ограничениями. Этот вывод справедлив как для однопроцессорных, так и для многопроцессорных систем.

Пример 4.1. В качестве примера планирования периодических заданий с предельным временем завершения рассмотрим систему, которая собирает и обрабатывает данные от двух датчиков - А и В /13/. Сроки сбора данных от датчика А - каждые 20 ms, датчика В - 50 ms. Процесс снятия данных, включая накладные расходы ОС, занимает для датчика А 10 ms, а для датчика В - 25 ms. В табл.4.1 приведен профиль выполнения этих двух заданий, а на рис.4.1,а - времена поступления, выполнения и предельные времена для заданий А и В.

Таблица 4.1

Процесс	Время поступления	Время выполнения	Предельное время окончания
А(1) А(2) А(3) А(4) А(5) . . В(1) В(2) .	0 20 40 60 80 . . 0 50 .	10 10 10 10 10 . . 25 25 .	20 40 60 80 100 . . 50 100 .

Компьютер может принимать решение о планировании каждые 10 ms.

Предположим, что при этих условиях используется схема планирования с приоритетами. Результат показан на двух временных диаграммах на рис.4.1,б и 4.1,в.

Если задание А имеет более высокий приоритет, задание В1 получит только 20 ms процессорного времени в двух смежных интервалах по 10 ms; после этого будет достигнуто предельное время его выполнения, и задание В1 выполнено не будет. Если более высокий приоритет получит задание В, то выполниться в срок не сможет задание А1.

Временная диаграмма на рис.4.1,г показывает применение в данной ситуации планирования с наиболее ранним предельным сроком. В момент времени t=0 поступают задания А1 и В1. Поскольку предельный срок А1 наступает раньше предельного срока В1, сперва выполняется задание А1. После его завершения начинается выполнение В1. В момент времени t=20 в систему поступает задание А2, предельный срок которого наступает раньше предельного срока В1. Соответственно, задание В1 прерывается, и начинается выполнение задания А2. Выполнение В1 продолжается, начиная с момента t=30. В момент t=40 в систему поступает задание А3, предельный срок которого, однако, более поздний, чем предельный срок задания В1, так что задание В1 продолжает выполнение до завершения в момент времени t=45. В этот момент начинается выполнение задания А3, завершающееся к моменту t=55 и т.д.

Размещено на http://www.allbest.ru

В этом примере, где в каждой точке вытеснения планировщик дает высший приоритет тому заданию, предельный срок которого наступает раньше, удовлетворяются все требования к системе реального времени, т.е. задания А и В выполняются без опоздания. Здесь использовано статическое планирование на основе таблиц, поскольку задания периодичны и предсказуемы. Анализ расписания выполнения заданий необходимо провести на временном интервале, равном наименьшему общему кратному (НОК) периодов поступления заданий (процессов). В рассмотренном примере период анализа расписания равен НОК(20,50)=100 ms.

Пример 4.2. Рассмотрим планирование выполнения непериодических заданий, для которых заданы предельные сроки начала работы. В верхней части рис.4.2 приведены времена поступления и предельные сроки начала работы для примера, состоящего из пяти заданий, время выполнения каждого из которых составляет 20 ms. Профиль выполнения этих заданий приведен в табл.4.2.

Размещено на http://www.allbest.ru

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

Таблица 4.2

Процесс	Время поступления	Время выполнения	Предельное время начала работы
A B C D E	10 20 40 50 60	20 20 20 20 20	110 20 50 90 70

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

Если предельное время заданий известно до того, как задания становятся готовыми к выполнению, можно усовершенствовать эту систему планирования. Усовершенствованная система, именуемая планированием с наиболее ранним предельным сроком начала со свободным временем простоя, работает следующим образом. Планировщик всегда запускает подходящее задание с наиболее ранним предельным сроком начала, которое выполняется до полного завершения. Подходящее задание может оказаться не готовым, и это может привести к тому, что несмотря на наличие готовых к выполнению заданий процессор простаивает. В рассматриваемом примере система воздерживается от выполнения задания А, несмотря на то, что это единственное готовое к выполнению задание. В результате, хотя процессор и не используется с максимальной эффективностью, все требования к предельным срокам начала выполнения заданий в примере при таком планировании удовлетворены. И, наконец, для сравнения на нижней части рис.4.2 приведен результат использования стратегии FCFS «первым поступил - первым обслужен». Как видно, в этом случае отклоненными оказываются два задания - В и Е.

4.3 Частотно-монотонное планирование

Одним из эффективных методов планирования для периодических задач является частотно-монотонное планирование (rate monotonic scheduling -- RMS). Система RMS назначает приоритеты заданиям на основе их периодов /13/.

На рис. 4.3 представлены параметры периодических заданий. Период задания Т представляет собой интервал времени между поступлениями двух последовательных заданий одного типа. Частота заданий, измеряемая в герцах, представляет собой величину, обратную периоду (в секундах). Например, задание с периодом 50 ms имеет частоту 20 Гц. Обычно окончание периода задания является жестким предельным сроком завершения задания, хотя некоторые задания могут иметь и более ранние предельные сроки. Время выполнения (вычисления) С представляет собой количество процессорного времени, требующегося для каждого задания определенного типа. Очевидно, что в однопроцессорной системе время выполнения не должно превышать период заданий (т.е. должно выполняться ). Если периодическое задание всегда выполняется до полного завершения, т.е. если не имеется отклоненных из-за нехватки вычислительного ресурса заданий, то загруженность процессора этим заданием равна U = С/Т. Например, если задание имеет период 80 ms и время выполнения 55 ms, то загруженность им процессора составляет 55/80 = 0,6875.

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

Размещено на http://www.allbest.ru

Размещено на http://www.allbest.ru

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

. (4.1)

Сумма загруженности процессора разными заданиями не может превышать единицу, что соответствует полной загрузке процессора. Неравенство (4.1) определяет верхнюю границу количества заданий, которые может успешно обслуживать идеальный алгоритм планирования. Для конкретного реального алгоритма граница может оказаться ниже из-за затрат ресурсов процессора на планирование и диспетчеризацию. В /13/ показано, что для алгоритма RMS справедливо следующее неравенство:

. (4.2)

В табл. 4.3 приведены некоторые значения верхней границы загруженности процессора для метода RMS для разных значений n в (4.2). При возрастании количества заданий верхняя граница стремится к значению In 2 =0,693.

Таблица 4.2

n
1	1.000
2	0.828
3	0.779
4	0.756
5	0.743
6	0.734
*	*
*	*

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

задание P₁: C₁ = 20; Т₁ = 100;

задание P₂: С₂ = 40; T₂ = 150;

задание Р₃: С₃ = 100; T₃= 350.

Загруженность процессора каждым из заданий составляет соответственно: U₁= 0,2; U₂= 0,267; U₃= 0,286. Тогда общая загруженность процессора тремя заданиями составляет U_o=0,2+0,267+0,286=0,753.

Верхняя граница загруженности этих трех задач при использовании метода RMS составляет:

.

Поскольку общая загруженность процессора по обработке приведенных заданий ниже верхней границы для метода RMS (0,753<0,779), можно сделать вывод, что при RMS-планировании будут успешно выполнены все задания.

В /13/ указывается, что определяемая выражением (4.2) верхняя граница справедлива и для метода наиболее раннего предельного срока. Хотя при применении планирования с наиболее ранним предельным сроком можно достичь более высокой загрузки процессора и, соответственно, обработать большее количество заданий, метод RMS широко распространен и используется во многих промышленных приложениях.

Упражнение 4.1. Для группы периодических задач с заданным профилем построить временные диаграммы их выполнения для следующих алгоритмов планирования: с квантованием, относительными и абсолютными приоритетами, предельными сроками завершения и RMS.

Упражнение 4.2. Для группы непериодических задач с заданным профилем построить временные диаграммы их выполнения для следующих алгоритмов планирования: с заданными предельными сроками начала работы; предельными сроками начала и свободным временем простоя.

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

5. ПЛАНИРОВАНИЕ В WINDOWS 2000

5.1 Уровни приоритетов потоков в Windows 2000

В Windows 2000 предусмотрено 32 уровня приоритета, которые организованы в виде двух групп или классов - реального времени и переменные (динамические) /7,8,11,13/. Каждая из этих групп состоит из 16 уровней приоритета, как показано на рис.5.1.

Размещено на http://www.allbest.ru

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

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

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

Преимущества планирования с динамическими приоритетами уже были продемонстрированы в предыдущем разделе на примерах систем реального времени. Хотя Windows 2000 относится к ОС свободного времени, преимущества планирования с динамическими приоритетами в этой ОС в значительной мере также реализованы.

Win32 API упорядочивает процессы по уровням приоритета, назначенным при их создании следующим образом: Real time (реального времени), High (высокий), Above Normal (выше обычного), Normal (обычный), Below Normal (ниже обычного) и Idle (простаивающий) /11/. Каждой из указанных шести групп уровней приоритетов соответствует определенный диапазон приоритетов, и значения приоритетов из середин диапазонов называются базовыми приоритетами процессов. Обычно базовые приоритеты групп процессов по умолчанию равны соответственно 24, 13, 10, 8, 6, 4.

Размещено на http://www.allbest.ru

Начальный приоритет потока в классе переменных приоритетов определяется двумя величинами: базовым приоритетом процесса и относительным приоритетом потока (рис.5.2). Каждый поток, связанный с определенным процессом, имеет собственный относительный приоритет, который указывает на приоритет потока по отношению к базовому приоритету процесса, и может отличаться от базового приоритета процесса не более чем на 2 уровня в большую или меньшую сторону. Так, например, если базовый приоритет процесса равен 4, а относительный приоритет одного из потоков равен -1, то начальный приоритет этого потока равен 3.

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

На рис.5.2 приведен пример процесса с базовым приоритетом, равным 4. Каждый поток, связанный с данным процессом, должен иметь начальный приоритет от 2 до 6, и в процессе работы значения динамических приоритетов потоков могут колебаться в диапазоне от 2 до 15.

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

В Windows 2000 никогда динамически не изменяются приоритеты потоков в классе приоритетов реального времени (16 - 31), поэтому у таких потоков базовый приоритет идентичен текущему.

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

5.2 Особенности алгоритмов планирования в Windows 2000

ОС Windows 2000 (W2K) разработана таким образом, чтобы быть по возможности максимально чувствительной либо к запросам отдельного пользователя в интерактивной среде (Windows 2000 Professional), либо запросам группы пользователей сети при использовании ОС серверной версии (Windows 2000 или Server Advanced Server).

Следует заметить, что алгоритмы планирования Windows 2000 для одно- и многопроцессорных систем отличаются. Ниже будет рассмотрен алгоритм планирования для однопроцессорных ВС.

В Windows 2000 реализован вытесняющий планировщик, использующий как концепцию абсолютных приоритетов, так и концепцию квантования. На каждом из уровней класса приоритетов реального времени применяется циклическое (карусельное) RR планирование. В классе переменных приоритетов также используется карусельное планирование, дополненное возможностью динамического изменения приоритета на основе текущей активности потоков (рис.5.1) /11/.

Выбранный для выполнения поток работает в течение определенного кванта времени. После завершения кванта времени планировщик решает, какой другой ожидающий поток поставить на выполнение. Потокам выделяются разные кванты, их длительность, в частности, зависит от версии ОС - Windows 2000 Professional, или Windows 2000, или Server Advanced Server. Однако поток может не полностью использовать свой квант. Это происходит, если в очереди готовых к выполнению потоков появляется поток с более высоким приоритетом. Тогда текущий выполняемый поток вытесняется, даже если его квант еще не истек. Фактически поток может быть выбран следующим для выполнения и вытеснен, не успев воспользоваться своим квантом.

Код Windows 2000, отвечающий за планирование, реализован в ядре ОС. Совокупность процедур, выполняющих эти обязанности, называется диспетчером ядра (kernel`s dispatcher). Диспетчеризация потоков осуществляется при прерываниях уровня «DPC/dispatch» и инициируется событиями:

поток готов к выполнению (например создан или вышел из состояния ожидания);

поток выходит из состояния выполнения (например квант истек, поток завершается или переходит в состояние ожидания);

приоритет потока изменяется в результате вызова системного сервиса или самой Windows 2000;

изменяется привязка к процессорам выполняемого потока (в случае мультипроцессорных SMP-систем).

После выбора нового потока, Windows 2000 переключает контекст. Эта операция заключается в сохранении параметров состояния ВС, связанных с выполняемым потоком, и загрузке аналогичных параметров для другого потока, после чего начинается выполнение нового потока.

В типичном случае переключение контекста требует сохранения и восстановления следующих данных:

программного счетчика (program counter);

регистра состояния процессора;

содержимого остальных регистров процессора (РОН и других);

указателя на стек ядра и пользовательский стек;

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

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

Следует обратить внимание на то, что планирование в Windows 2000 осуществляется на уровне потоков, т.е. система не обращает внимание на то, какому процессу принадлежит тот или иной поток.

Рассмотрим на примерах отдельных сценариев планирования как практически работает приведенный выше алгоритм /11/.

1.Самостоятельное переключение. Поток может самостоятельно освободить процессор, перейдя в состояние ожидания на каком-либо объекте (например событии, мьютексе, семафоре, порте ввода-вывода, процессе, потоке и др.) путем вызова одной из функций ожидания Win32 API (например WaitForSingleObject или WaitForMultipleObject). Если поток переходит в состояние ожидания, не израсходовав выделенный ему квант времени полностью, то его квант не сбрасывается. В этом случае после успешного завершения ожидания квант потока уменьшается на одну квантовую единицу, что эквивалентно одной трети интервала таймера. Исключение составляют потоки, приоритет которых от 14 и выше, у которых после ожидания квант сбрасывается.

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

завершилось ожидание потока с более высоким приоритетом (т.е. произошло событие, которого он ждал);

приоритет потока увеличился или уменьшился.

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

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

4.Завершение потока. Завершаясь (например после вызова функции ExitThread или TerminateThread), поток переходит в состояние Terminated. Если в этот момент ни один описатель его объекта «поток» не открыт, он удаляется из списка потоков процесса, а соответствующие структуры данных освобождаются.

5.Поток простоя. Если нет ни одного потока, готового к выполнению на процессоре, Windows 2000 подключает к данному процессору поток простоя (процесса Idle). Для каждого процессора создается свой поток простоя, работающий вне приоритетов, так как он работает лишь в отсутствие других потоков. Этот поток выполняет следующие действия:

включает и выключает прерывания, давая возможность выполнить отложенные прерывания;

проверяет, есть ли у процессора отложенные программные прерывания DPC и организует их выполнение;

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

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

Для принятия решений при планировании потоков ядро поддерживает набор структур данных, в совокупности известных как база данных диспетчера ядра (dispatcher database). Эта база данных позволяет отслеживать потоки, ждущие выполнения, и принадлежность потоков процессам. Самой важной структурой в базе данных диспетчера ядра является очередь готовых потоков (ready queue), находящаяся в KiDispatcherReadyListHead - списке заголовков для 32 очередей готовых потоков (по одной для каждого приоритета).

Для ускорения выбора потока, подлежащего выполнению или вытеснению, Windows 2000 поддерживает 32-битовую маску, называемую сводкой готовности (ready summary) (KiReadySummary). Каждый установленный в ней бит указывает на присутствие одного или более потоков в очереди готовых потоков для данного уровня приоритета (бит 0 соответствует приоритету 0, бит 1 - приоритету 1 и т.д.). Кроме того, Windows 2000 поддерживает сводку простоя (idle summary) (KidleSummary), в которой каждый установленный бит представляет простаивающий процессор.

5.3Учет квантов и управление их величиной

Квант - интервал процессорного времени, отведенный потоку для выполнения /11/. По его окончании Windows 2000 проверяет, готов ли к выполнению другой поток с таким же уровнем приоритета. Если на момент истечения кванта других потоков с таким же уровнем приоритета нет, Windows 2000 выделяет текущему потоку еще один квант. У каждого потока есть свое значение кванта, которое отражается полями параметра Win32PrioritySeparation. Это значение выражается не в единицах времени, а в так называемых квантовых единицах (quantum units).

По умолчанию начальная величина кванта в Windows 2000 Professional равна 6, а в Windows 2000 Server -- 36. В Windows 2000 Server величина кванта увеличена для того, чтобы свести к минимуму переключение контекста. Получая больший квант, серверные приложения, которые пробуждаются при получении клиентского запроса, имеют больше шансов выполнить запрос и вернуться в состояние ожидания до истечения выделенного кванта.

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

В Windows 2000 Professional квант по умолчанию равен двум интервалам системного таймера, а в Windows 2000 Server - двенадцати. Период таймера в большинстве однопроцессорных х86-систем равен 10 msec, а в большинстве мультипроцессорных х86-систем - 15 msec.

Относительная величина кванта (короткая или длинная) задается в реестре параметром

HKLM\SYSTEM\CurrentControlSet\Control\PriorityControl\Win32PrioritySeparation.

Этот же параметр определяет, можно ли динамически увеличивать кванты потоков (если да, то насколько), выполняемых в активном процессе. Поясним на примере, почему Windows 2000 динамически увеличивает величину кванта, а не приоритета активных потоков. Допустим, начат длительный пересчет электронной таблицы и затем произведено переключение на приложение, активно использующее процессор. Если повысить приоритет активного процесса, фоновый пересчет получит лишь очень малую часть процессорного времени. В то же время увеличение кванта для активного потока не приведет к фактическому блокированию потока пересчета -- система всего лишь будет отдавать активному потоку несколько большее предпочтение. Приложение можно запустить с различными классами приоритета, использую команду start. Приоритет запущенного потока можно сменить с помощью «Диспетчера задач».

5.4 Динамическое повышение приоритета

Windows 2000 может динамически повышать значение текущего приоритета потока в одном из пяти случаев: