автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.15, диссертация на тему:Эффективность выполнения стохастических задач в режимах перегрузки

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

МАИ

На правах рукописи

БАБАК Дмитрий Александрович

ЭФФЕКТИВНОСТЬ ВЫПОЛНЕНИЯ СТОХАСТИЧЕСКИХ ЗАДАЧ В РЕЖИМАХ ПЕРЕГРУЗКИ Специальность 05.13.15 - «Вычислительные машины и системы»

Автореферат

диссертации на соискание ученой степени кандидата технических наук

Москва Издательство МАИ 2005

4

S

Г 6

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ (ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

МАИ

На правах рукописи

БАБАК Дмитрий Александрович

ЭФФЕКТИВНОСТЬ ВЫПОЛНЕНИЯ СТОХАСТИЧЕСКИХ ЗАДАЧ В РЕЖИМАХ ПЕРЕГРУЗКИ Специальность 05.13.15 - «Вычислительные машины и системы»

Автореферат

диссертации на соискание ученой степени кандидата технических наук

к

Москва Издательство МАИ,

2005 ' • А ..

£ **% 'МП

Работа выполнена на кафедре «Вычислительные машины и системы» факультета систем управления, информатики и электроэнергетики летательных аппаратов Московского авиационного института (государственного технического университета).

Научный руководитель: заслуженный деятель науки РФ,

доктор технических наук, профессор О.М. Брехов.

V

Официальные оппоненты: академик РАН,

доктор технических наук, профессор В.К. Левин, кандидат технических наук, старший научный сотрудник А.И. Слуцкин.

Ведущая организация: Институт проблем передачи

информации (ИППИ), г. Москва.

Защита состоится «_»_2005 г. в_час._мин. на

заседании диссертационного совета Д 212.125.01 при Московском авиационном институте (государственном техническом университете) по адресу: 125993, г.Москва, А-80, ГСП-3, Волоколамское шоссе, д.4.

Отзыв на автореферат в одном экземпляре, заверенный печатью, просим высылать по адресу: 125993, г.Москва, А-80, ГСП-3, Волоколамское шоссе, д.4, Ученый Совет, ученому секретарю диссертационного совета Д 212.125.01.

Автореферат разослан «__»_2005 г.

Ученый секретарь диссертационного совета,

кандидат технических наук, доцент Б.Н.Чугаев.

„W. НАЦИОНАЛЬНА*

i библиотека !

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы

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

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

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

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

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

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

Методы исследования

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

На защиту выносятся:

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

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

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

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

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

Научная новизна

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

Практическая ценность и реализация результатов работы

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

Внедрение результатов работы

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

Апробация работы

Результаты диссертационной работы докладывались и обсуждались на научно-технических конференциях и семинарах:

Международная конференция «Информационные средства и технологии», (Москва, 2004),

на научных семинарах каф. 304 "Вычислительные машины и системы", МАИ (Москва, 2001-2005).

Публикации

По материалам диссертационной работы опубликовано 5 работ.

Структура диссертации

Диссертация состоит из 4 глав, введения и заключения. Общий объем работы - 121 страница, в том числе 75 рисунков и 6 таблиц. Список литературы включает 89 наименований.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

Рассмотрена система из N стохастических задач Тп 1 <1< N . Задачи

выполняются периодически. Период выполнения /-й задачи равен Р1 (рис. 1). Выполнение 1-й задачи в периоде названо работой и обозначено Т1 ]. Число задач в системе N является параметром.

Каждаяу'-я работа /-й задачи характеризуется моментом поступления г,) и моментом готовности результатов а1 /. Время выполнения у-й работы ;-й

/

Рис. 1. Параметры стохастических задач

ё

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

распределения Ft(t), [Е~ <t< Е~]. Е~ и Е* - минимальное и

максимальное время выполнения /-й задачи. Для j-й работы /-й задачи

установлен директивный срок dt - момент времени, к которому работа

должна завершиться. Директивный сроку'-й работы /-й задачи совпадает по времени с окончанием j'-ro периода г'-й задачи, т.е. работа должна завершиться до окончания своего периода. Предполагается, что распределение величины времени выполнения задачи неизменно или слабо меняется на заданном интервале времени. Распределение времени выполнения для каждой задачи свое, а вид функции распределения может быть произвольным.

Основное внимание уделено случаю, когда разброс случайной величины

времени выполнения задачи значителен. При условии E+t — Е~ «Е*

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

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

задач в алгоритме EDF являются период выполнения /-й задачи Pt и время выполнения /'-й задачи С,. Пример значений параметров для трех задач приведен в табл. 1.

Табл. 1 Пример значений параметров задач для алгоритма планирования ЕОР

Задача с, р. Коэффициент загрузки процессора /-Й задачей U, —CJ Р,

т, 100 400 0.25

Т2 300 700 «0.43

Т, 100 500 0.2

»0.88

Достаточное и необходимое условие выполнимости плана для алгоритма ЕЭР, т.е. условие, при котором задачи будут выполняться без опозданий:

N Г

;=1 Г,

Диаграмма выполнения задач из табл. 1 приведена на рис. 2.

ti é_Vm_^

_ÉL

iiii

iiii

"I I г

I I I

O 500 1000 1500 2000

Рис. 2 Диаграмма выполнения задач по алгоритму EDF для значений параметров задач из табл. 1

В момент времени t-О директивные сроки задач равны соответственно 400, 700 и 500. Согласно алгоритму EDF процессорное время выделяется задаче, чей директивный срок наиболее близок - задаче Г,.

Для выполнения системы стохастических задач при помощи алгоритма EDF в режиме отсутствия перегрузки необходимо для /-й задачи в каждом периоде зарезервировать Е* процессорного времени. Работы будут

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

N Е* +

У —!- < 1, где Et - максимальное время выполнения /-й задачи, a Pt -период /-й задачи.

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

» е:

I

>ь

При использовании алгоритма планирования ЕЭР в режиме перегрузки задержки задач носят неконтролируемый характер, что приводит к неконтролируемому качеству выполнения задач. Могут появляться серии пропусков задач - так называемый эффект домино, когда пропуск одной задачи приводит к серии последующих пропусков. Задержки одних задач могут происходить чаще, чем других. Предлагается предоставлять /-й задаче в каждом периоде не более чем С, единиц времени (С, < Е*), так чтобы

N

выполнялось условие: V —^ < 1.

<=1 Л

Поскольку предоставляемое для решения /-й задачи время С, меньше максимального времени выполнения задачи Е*, возможно, чтоу'-я работа /-й

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

где *,«;,) =

Поступление новых работ для г'-й задачи на время обработки задержанной работы Тч блокируется. Предлагается ограничивать максимальную задержку результатов у'-й работы /-й задачи величиной К*.

Путем установки К= 1 реализуются ограничения задержек для задач жесткого реального времени. Зависимость К,(С,) от С, представлена на рис. 3.

к:

5

4 -3 - -2

1 --

I \

е]_ Е;

К* "' 3

2

е;

с,

Рис. 3 График зависимости величины К1 (С,) от С,

Максимальные задержки /-й задачи в зависимости от значений величины С1 показаны на рис. 4.

с, > е:

С, е

С, е

С, е

и

£

3 ' 2

£ £

4 ' 3

п П »

= 2

П П ЕЯ к,:

ПЖП

Рис. 4. Варианты максимальных задержек /-й задачи

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

литературе алгоритмом CUS (Constant Utilization Server).

Во второй главе рассмотрены показатели качества и критерии оптимизации выполнения системы стохастических задач с задержанными работами. Под качеством выполнения системы задач понимается близость к номинальному режиму выполнения. Для системы стохастических задач номинальный режим соответствует отсутствию задержек задач. Наличие задержек задач снижает качество выполнения относительно номинального режима. В режиме перегрузки система задач вынуждена деградировать, т.е. ухудшать качество выполнения задач. Для рассматриваемой системы задач с задержанными работами номинальный режим соответствует максимальному качеству и состоит в том, что каждая работа будет завершаться за один период. Моменты готовности результатов у-й работы /-й задачи aL] попадают в интервалы между моментами поступления у'-й работы г,; и моментами наступления директивного срока у'-й работы dn соответственно (рис. 5).

ы W 1 ч i {

У////Л ШУ, ///¿у/Л

<-»> t

Рис. 5. Иллюстрация моментов ац готовности результатов работы

Принято, что результаты у'-й работы /-й задачи не могут быть использованы ранее наступления директивного срока с1ч. С учетом этого момент А,р совпадающий с моментом директивного срока, принят за момент выдачи результатов у'-й работы /-й задачи. Номинальный режим выполнения задачи реализуется, когда моменты Ач следуют с периодом Р, (рис 6).

Аи АЧ>1

t t t t t.

Рис. 6. Номинальный режим выполнения /-й задачи

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

Рис. 7. Выдача результатов /-й задачей в режиме перегрузки

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

р]г" = М[к1 / ], где М-математическое ожидание.

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

ы 1

. где ^ (?) - функция распределения времени выполнения /-й задачи.

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

р]гс^ (С,) от величины С1 показан на рис. 8. При значениях С, близких к

О функция стремится к бесконечности, при значениях С, > Е*, функция равна 1.

Рис. 8. Характер зависимости р\ге"{С,) от С(

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

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

Для характеристики качества выполнения системы стохастических задач предложен показатель:

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

равномернее при одновременном росте значения показателя качества рХгслп . Предлагается использовать значение параметра п~3.

Случай неравноправности задач - показатель качества р1уе<" . Для учета неравноправности задач введем коэффициент важности /-й задачи У^", >0. Чем больше тем более важной является ¿-я

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

р)гел17 (С,) - трансформирован^! й показатель качества выполнения ;-й задачи:

-;;-1-

0 у,"*'<1 Е; С,

Рис. 9. Трансформация р]""^,) в р)'"У (С,)

Влиянию трансформации подвержена только область значений аргумента С, < Е* ■ Нетрансформированный график соответствует значению

коэффициента важности К|1ге" = 1. При У:[ге* > 1 влияние показателя

качества выполнения г-и задачи р1 (С,) на результирующее значение

показателя качества выполнения системы задач РуСт увеличивается.

Введение штрафа за опоздание - показатель качества р^"" . Каждая работа ;'-й задачи согласно установленным ограничениям может завершиться за число периодов от 1 до К. Вводится функция штрафа

Н]т(к) за задержку результатов задачи на к периодов. Область

определения функции Н]ге"(к) - натуральные числа из диапазона [1, К* ]. Область значений - множество действительных положительных чисел. Показатель качества выполнения системы задач р1"т рассчитывается с учетом функции штрафа по формуле:

Рн Ь

где = ^\р1{к С1)-РХ{к-\)-С1)\н:""{к)\

к=1

Отмечено, что показатель качества ри"" есть частный случай показателя р1™" при Н]ге'\к) = к (рис. 10).

Н]""(к) ' 3

2

1

12 3 к

Рис. 10 Случай Н)™ (к) = к

\resn

Консолидированный показатель качества рну .

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

\resn - „ Лгст „1 ге\п

рну объединяет возможности показателей качества ру и рн

„\resn / '

где р]тИУ (С,) = {р1Гн (С,) -1) +1 и Р]Г" = хкн1г(*)]•

4-1

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

Критерий оптимизации Q]rcxi

гшп р

N п

к ,{с,)< к;

Критерий оптимизации Q¡

Iresl

min p¡T3Í

N с

/•=1 1i

[к,(с,)<к;

Критерий оптимизации Q^^

Q«

шт рТъ

N г

1С'

1=)

<1

Р,

[к,(с,)<к;

Критерий оптимизации Q

\res 3 UV

Ö\res3 HV

min pHy

N Г"

Ifíl

/=| -Г.

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

Рассмотрено использование алгоритма координатного спуска для численного решения задачи оптимизации по предложенным критериям в режиме функционирования системы.

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

по критерию Qlre'3. Для решения задачи оптимизации использовался численный метод координатного спуска с необходимыми изменениями. Моделирование проводилось на наборе из 15 - ти задач, время выполнения которых распределено по нормальному закону. Проведено сравнение выполнения системы стохастических задач с использованием альтернативных методов:

-16-

без балансировки загрузки процессора; с пропорциональной балансировкой задач; - с оптимизацией по критерию £)1пих . В схеме без балансировки загрузки процессора значения С, устанавливались по формуле:

с, = е;

Коэффициент загрузки процессора:

N Г 1=1

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

Схема с пропорциональной балансировкой задач предполагает

балансировку значений С1 пропорционально значениям Е^. Время, предоставляемое /-й задаче в каждом периоде, устанавливалось

£+

пропорционально максимальному времени выполнения задачи: С, = —'+ ,

N

где и* •

1=1 Р,

Также проводилось сравнение с оптимизацией по существующему

критерию £)1пих; который определяет качество работы задачи Р, (С,) как

величину, пропорциональную вероятности завершения задачи за один период:

р:(с,)=р{к=\}=^(с,), РЦЕ;)=1, РЦЕ;) = О.

Рассматривая величину Р}(С,) как показатель качества выполнения

задачи, критерий £>|пшх требует равномерной деградации задач до достижения выполнимости плана:

МАХ(Р')

1=1

1=1 N,1=I N

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

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

1ге*Э _ _____

Ар = ---—--^L, где р1™3 AJopl0 - показатель качества

„1 геО

Р ли

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

01 гелЗ „ 1 res!

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

использованием альтернативных методов

J AdaptQ

дd = -где DA.,Ü = Mlp1;" - М(р]г")}2 - дисперсия

значений показателей качества отдельных задач в случае использования

оптимизации по критерию £),ге'3 5 а ВА11 = М[р]г" - М{р)п'' )]2 - дисперсия

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

- предложенная схема превосходит схему без балансировки загрузки

процессора по показателю качества р , начиная с величины коэффициента загрузки 6;

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

- выигрыш от использования схемы с оптимизацией доходит до 8% по

показателю качества и до 80% по величине дисперсии.

О

о

Коэффицимг звгрузки.и

Рис. 11 Рассеяние величины Ар для случая сравнения со схемой без балансировки загрузки процессора

10 12 14 Коэффициент за грузки,и

Рис. 12. Рассеяние величины Л£> для случая сравнения со схемой без балансировки загрузки процессора

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

£ из I

о " а о

о ® 0 0 л > -к -ж п0—

Коэффициент загрузки и

Рис. 13. Рассеяние величины Ар для случая сравнения со схемой с пропорциональной балансировкой задач

г 4 в в 10 12 14 1в 1В 20

Коэффициент зафуэки, и

Рис. 14. Рассеяние величины АО для случая сравнения со схемой с пропорциональной балансировкой задач

Приведенные данные позволяют сделать вывод о том, что: - предложенная схема превосходит схему с пропорциональной балансировкой задач на интервале значений коэффициента загрузки [1, 16]. В диапазоне загрузок [1, 4] схема давала некоторое количество случаев проигрыша по сравнению со схемой с пропорциональной балансировкой;

- выигрыш от использования схемы с оптимизацией в среднем составляет 10% по показателю качества р<ге^ и 50% по величине дисперсии показателей качества отдельных задач;

- в диапазоне значений коэффициента загрузки около значения 1.2 схема с оптимизацией давала выигрыш до 40% по показателю

качества р'""3 и до 100% по величине дисперсии показателей качества отдельных задач. На рис. 15 и рис. 16 показаны результаты сравнения со схемой с оптимизацией по критерию гаах .

ю

о; о ¡00

§ *

0.2

о

00

о

-0 .2 ---------1--■---'-<---'---

0 2 4 6 8 10 12 14 16 1«

Коэффициент загрузки, и

Рис. 15 Рассеяние величины Ьр для случая сравнения со схемой с оптимизацией по критерию Q,m"*

исюдеееиаши а* и> а» о еодсво

■ ч 6°

0 2 4 в В 10 12 14 1в 18

* Коэффициент загрузки и

Рис. 16 Рассеяние величины АЛ для случая сравнения со схемой с оптимизацией по критерию (V

Результаты сравнения со схемой с оптимизацией по критерию Qinш позволяют сделать вывод о том, что:

- предложенная схема оптимизации по критерию Q]re'^3 превосходит

схему с оптимизацией по критерию £),та* на интервале значений коэффициента загрузки [2, 16];

- выигрыш от использования схемы с оптимизацией в среднем

составляет 70% по показателю качества рие'ъ и 100% по величине дисперсии значений показателей качества отдельных задач. В четвертой главе приведена реализация диспетчера - надстройки операционной системы Ух\Уогкз. Диспетчер - надстройка выполняет

систему стохастических задач с оптимизацией по критерию Qlr"i,

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

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

6. Разработаны имитационные модели для рассматриваемой системы задач.

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

8. Реализован диспетчер-надстройка для операционной системы VxWorks, реализующий выполнение стохастических задач с оптимизацией по предложенным критериям.

ПУБЛИКАЦИИ

Содержание диссертации отражено в следующих работах:

1. Брехов О.М., Бабак. Д.А. Алгоритм минимизации пропуска решений задач в перегруженных системах. // Проблемы передачи и обработки информации в сетях и системах телекоммуникаций: Материалы 10-й Международной научн.-техн. конф. Рязань: Рязанская государственная радиотехническая академия, 2001. С.186-188.

2. Бабак Д.А. Оценка схем восстановления вычислительного процесса в системах реального времени. // Системные проблемы качества, математического моделирования, информационных, электронных и лазерных технологий. Материалы Международной конференции и

Российской научной школы. Часть 1. - Москва: ГНПО «Агат», 2001. С.121-124.

3. Брехов О.М., Бабак Д.А. Влияние погрешности оценки времени выполнения задач на работу алгоритма МПДС. // Современные технологии в задачах управления, автоматики и обработки информации: Сборник трудов XI международного научно-технического семинара. / М.: МГАПИ, 2002. с. 339-340.

4. Brekhov О., Babak D., Adaptive Scheduling of tasks in the conditions of system overload. D&AS Conference, Suceava. Advances in Electrical and Computer Engineering, ISSN 1582-7445 - No 1 /2002, pp. 16-22.

5. Бабак Д. А. Адаптивная диспетчеризация задач с недетерминированным временем исполнения. Труды международной конференции «Информационные средства и технологии». 12-14 октября 2004 г., в 3-х т.т. ТЗ. - М.: Янус-К, 2004. - с. 130-133.

Подписано в печать 22.04.2005. Бум. писчая Формат 60x84 1/16. Печать офсетная. Уел печ. л. 1,39. Уч.-изд. л. 1,50. Тираж 100 экз. Зак. 3055/5079. С. 330.

Отпечатано в типографии Издательства МАИ «МАИ», Волоколамское ш, д. 4, Москва, А-80, ГСП-3 125993

i I

f

V

V J

i

I

I

I i

i

i i

i

! i

РНБ Русский фонд

2006-4 11656

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ. v.jTT h 1. ВЫПОЛНЕНИЕ СТОХАСТИЧЕСКИХ ЗАДАЧ В РЕЖИМАХ ПЕРЕГРУЗКИ.

1.1 Обзор существующих моделей задач и алгоритмов riiai шрования.

1.2 Модель стохастических задач.

1.3 Режим перегрузки.

1.4 Алгоритм CUS.

1.5 Алгоритм CBS.

Выводы.

2. ЭФФЕКТИВНОСТЬ ВЫПОЛНЕНИЯ СТОХАСТИЧЕСКИХ ЗАДАЧ.

2.1 Схема задержанных работ.

2.2 Показатели качества выполнения задачи.

2.3 Критерии оптимизации.

2.4 Оптимизация в режиме энергосбережения.

2.5 Алгоритм численного решения задачи оптимизации.

2.6 Оценка распределения времени выполнения задач.

Выводы.

3. МОДЕЛИРОВАНИЕ РАБОТЫ АЛГОРИТМА ПЛАНИРОВАНИЯ.

3.1 Схема без балансировки загрузки процессора.

3.2 Пропорциональная балансировка задач.

3.3 Оптимизация по критерию QXmax.

3.4 Сравнение алгоритмов CUS и CBS.

3.5 Режим энергосбережения.

Выводы.

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

4.1 Средства диспетчеризации современных операционных систем.

4.2 Модульная структура диспетчера.

4.3 Временные параметры диспетчеризации.

4.4 Оценка накладных расходов.

Ч Выводы.

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

Актуальность проблемы

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

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

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

Методы исследования

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

На защиту выносятся:

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

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

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

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

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

Научная новизна работы

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

Практическая ценность и реализация результатов работы

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

Внедрение результатов работы

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

Апробация работы

Результаты диссертационной работы докладывались и обсуждались на научно-технических конференциях и семинарах:

Международная конференция «Информационные средства и технологии», (Москва, 2004), на научных семинарах каф. 304 "Вычислительные машины и системы", МАИ (Москва, 2001-2005).

Публикации

По материалам диссертационной работы опубликовано 5 работ.

Структура диссертации

Диссертация состоит из 4 глав, введения и заключения. Общий объем работы -121 страница, в том числе 75 рисунков и 6 таблиц. Список литературы включает 89 наименований.

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

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

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

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

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

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

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

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

- без балансировки загрузки процессора;

- с пропорциональной балансировкой задач;

- с использованием существующего критерия оптимизации Qimm.

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

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

1. ВЫПОЛНЕНИЕ СТОХАСТИЧЕСКИХ ЗАДАЧ В РЕЖИМАХ ПЕРЕГРУЗКИ

Выводы

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

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

Рассмотрены временные параметры функционирования диспетчераЛ надстройки и описаны основные алгоритмы его работы.

В процессе моделирования получены оценки накладных расходов функционирования диспетчера, которые составили 0.5 % в случае без проведения оптимизации выполнения задач и 6.7% в случае проведения оптимизации. В среднем при проведении оптимизации один раз в секунду величина накладных расходов составила менее 1%. t

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

6. Разработаны имитационные модели для рассматриваемой системы задач.

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

8. Реализован диспетчер-надстройка для операционной системы VxWorks, реализующий выполнение стохастических задач с оптимизацией по предложенным критериям.

1. Артамонов Г.Т. Анализ производительности ЦВМ методами теории массового обслуживания. -М.: Энергия, 1972. 176 с.

2. Артамонов Г.Т., Брехов О.М. Оценка производительности ВС аналитико-статистическими моделями. М.: Энергоатомиздат, 1993. - 302 с.

3. Брехов О.М. Аналитическая оценка производительности многопроцессорной вычислительной системы с динамическим изменением числа выполняемых процессов // Автоматика и телемеханника, 1995, №2, с. 141-154.

4. Иыуду К.А. Надежность, контроль и диагностика вычислительных машин и систем. М.: Высшая школа, 1989. - 216 с.

5. Иыуду К.А., Кривощеков С.А. Математические модели отказоустойчивых вычислительных систем. М.: Изд-во МАИ, 1989. - 144 с.

6. Конвей Р.В., В.Л.Максвелл, Л.В.Миллер. Теория расписаний. М., 1975 г., 360 С.

7. Мамедли Э.М., Соболев Н.А. Механизмы операционных систем, обеспечивающие отказоустойчивость в управляющих многомашинных вычислительных системах // Автоматика и телемеханика, 1995, №8, с.3-63.

8. Собко С.Л. "Обеспечение динамической самонастраиваемости бортовых многопроцессорных вычислительных систем". Диссертация на соискание ученой степени к.т.н. М.: МАИ, 1998.

9. Столингс В. Операционные системы (4-е издание). ISBN: 5-8459-0310-6. "Вильяме" • 2002 г. • 848 стр.

10. A. Ermedahl, F. Stappert, J. Engblom, Clustered Calculation of Worst-Case Execution Times.

11. A.K. Мок. Fundamental Design Problems of Distributed Systems for the Hard Real-Time Environment. PhD thesis, M.I.T., 1983.

12. Abeni L., Buttazzo G. Integrating multimedia applications in hard real-time systems. In Proceedings of the IEEE Real Time Systems Symposium, Madrid, Spain, December, 1998. CBS.

13. Abeni L., Palopoli L., Anna S., Buttazzo G. On Adaptive Control Techniques in Real-Time Resource Allocation // Proceedings of the IEEE Euromicro Conference on Real-Time Systems, Stockholm, Sweden, June 2000.

14. Atlas A. K., Bestavros A., "Statistical rate monotonic scheduling," in Proceedings of the 19th Real-Time System Symposium, Dec. 1998, pp. 123- 132.

15. B. Sprunt, J. Lehoczky, and L. Sha. Exploiting unused periodic time for aperiodic service using the extended priority exchange algorithm. In Real-Time Systems Symposium, 1988.

16. В. Sprunt, L. Sha, and J. P. Lehoczky, «Aperiodic Task Scheduling for Hard RealTime Systems,» Real-Time Systems: The International Journal of Time-Critical Computing Systems, vol. 1, pp. 27- 60, 1989.

17. B. Sprunt. Aperiodic task scheduling for real-time systems. PhD thesis, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, Aug. 1990.

18. B. Urgaonkar, P. Shenoy, and T. Roscoe. Resource overbooking and application profiling in shared hosting platforms. In Proc. of 5th Symp. on Operating Systems Design and Implementation, Dec. 2002.

19. Baruah Sanjoy K., Haritsa Jayant R. «Scheduling for Overload in Real-Time Systems,» IEEE Trans, on Computers, pages 1034-1039, September 1997.

20. Brinkley Sprunt. Aperiodic Task Scheduling for Real-Time Systems. Ph.D. Dissertation. Department of Electrical and Computer Engineering Carnegie Mellon University. August 1990.

21. С. D. Locke, "Best-effort Decision Making for Real-Time Scheduling," PhD thesis, Computer Science Department, Carnegie-Mellon University, 1986.

22. C. Krishna and Y. Lee, "Voltage Clock Scaling Adaptive Scheduling Techniques for Low Power in Hard Real-Time Systems," Proc. Sixth IEEE Real-Time Technology and Applications Symp. (RTAS '00), May 2000.

23. C. Lee, R. Rajkumar, and C. Mercer, "Experiences with Processor Reservation and Dynamic QOSin Real-Time Mach," Proceedings of Multimedia Japan 96, April 1996.

24. Compaq et al., "ACPI Specification, Version 3.0," 2004.

25. D.W. Leinbaugh. Guaranteed Response Time in a Hard Real-Time Environment. IEEE Transactions on Software Engineering, SE-6, January 1980.

26. Deng Z., Liu J. W. S. and Sun J. A scheme for scheduling hard real-time applications in open system environment. In Ninth Euromicro Workshop on RealTime Systems, 1997.

27. E. L. Lawler and C. U. Martel. Scheduling Periodically Occurring Tasks on Multiple Processors. Information Processing Letters, 12(1), February 1981.

28. F. Yao, A. Demers, and S. Shenker, "A Scheduling Model for Reduced CPU Energy," Proc. IEEE Ann. Foundations of Computer, Science, pp. 374-382, 1995.

29. G. Bernat and A. Burns. Combining (n m)-hard deadlines and dual priority scheduling. In Real-Time Systems Symposium, pages 46-57, 1997.

30. G. Buttazzo and J. Stankovic, "RED: A Robust Earliest Deadline Scheduling Algorithm", Proc. of 3rd International Worlcshop on Responsive Computing Systems, Austin, 1993.

31. G. Buttazzo, M. Spuri and F. Sensini, "Value vs. Deadline Scheduling in Overload Conditions," in Proceedings of the 19thIEEE Real-Time Systems Symposium, IEEE Computer Society Press, 1998.

32. G. Karen and D. Shasha, "D-over: An Optimal On-Line Scheduling Algorithm for Overloaded Real-Time Systems," Proceedings of the IEEE Real- Time Systems Symposium, December 1992.

33. G. Koren and D. Shasha. Skip-over: Algorithms and complexity for overloaded systems that allow skips. In Real-Time Systems Symposium, 1995.

34. Gardner M. К., Liu J.W.S. Performance of Algorithms for Scheduling Real-Time Systems with Overrun and Overload // In the Proceedings of the Eleventh Euromicro Conference on Real-Time Systems. 9-11 June 1999. - University of York, England.

35. Giorgio Buttazzo, Luca Abeni, "Adaptive Rate Control through Elastic Scheduling," Proceedings of the 39th IEEE Conference on Decision and Control (CDC 2000), Sydney, Australia, December 2000.

36. H. Aydin, R. Melhem, D. Mosse и др. "Power-Aware Scheduling for Periodic Real-Time Tasks", IEEE Transactions on computers, том 53, № 5, 2004.

37. H. Aydin, R. Melhem, D. Mosse', and P. Alvarez, "Dynamic and Aggressive Scheduling Techniques for Power-Aware Real-Time Systems," Proc. IEEE RealTime Systems Symp. (RTSS '99), Dec. 1999.

38. H. Chetto and M. Chetto, "Some Results of the Earliest Deadline Scheduling Algorithm," IEEE Transactions on Software Engineering, vol. 15(10), pp. 12611269, Oct. 1989.

39. H. Zeng, X. Fan, C. Ellis, A. Lebeck, and A. Vahdat, "ECOSystem: Managing i Energy as a First Class Operating System Resource," Proc. Int'l Conf. Architectural Support for Programming Languages and Operating Systems (ASPLOS 2002), Oct. 2002.

40. Hong, G. Qu, M. Potkonjak, and M. Srivastava, "Synthesis Techniques for Low-Power Hard Real-Time Systems on Variable Voltage Processors," Proc. 19th IEEE Real-Time Systems Symp. (RTSS '98), Dec. 1998.

41. Intel Corp, "SpeedStep", Intel® Pentium® M Processor, http://support.intel.com/support/processors/mobile/pm/sb/CS-007981.htm. 2004.

42. J. A. Stankovic, C. Lu, and S. H. Son, "The Case for Feedback Control in RealTime Scheduling", IEEE Proceedings of the Euromicro Conference on Real-Time Systems, York, England, June 1998.

43. J. K. Strosnider. Highly responsive real-time token rings. PhD thesis, Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, PA, Aug. 1988.

44. J. M. Anderson and et al. Continuous profiling: Where have all the cycles gone? In Proc. of 16th Symposium on Operating Systems Principles, Oct. 1997.

45. J. M. Schopf, F. Bermany, Stochastic Scheduling, August 9, 1999.

46. J. MARTIN, Programming Real-Time Computer Systems, Prentice-Hall, Englewood Cliffs, N.J., 1965.

47. J. Pouwelse, K. Langendoen, and H. Sips, "Dynamic Voltage Scaling on a Low-Power Microprocessor," Proc. Seventh Int'l Conf. Mobile Computing and Networking (MOBICOM), July 2001.

48. J.L. Lanet, "Task Allocation in a Hard Real-Time Distributed System," Proc. Second Conf. Real-Time Systems, pp. 244-252, Sept. 1995.

49. J.R. Lorch, "A Complete Picture of the Energy Consumption of a Portable Computer," master's thesis, Univ. of California, Berkeley, Dec. 1995.

50. K. D. Nilsen, B. Rygg, Worst-Case Execution Time Analysis on Modern Processors.

51. K. G. Shin and Y.-C. Chang. A reservation-based algorithm for scheduling both periodic and aperiodic real-time tasks. IEEE Transactions on Computers, 44:14051419, Dec. 1995.

52. K. Ramamritham, J. A. Stankovic. Scheduling Algorithms and Operating Systems Support for Real-Time Systems. Department of Computer Science University of Massachusetts Amherst, MA 01003

53. Liu C. L., Layland J. W., Scheduling algorithms for multiprogramming in a hard-real-time environment, Journal of the Association for Computing Machinery, vol. 20, no. 1, pp. 46-61, Jan. 1973.

54. Liu J. W.-S., Deng Z., Shankar M., Storch M., Sun J., Tia T.-S., and Wu L.-C. The Use of PERTS for an Architecture and Timing Study. Tech. Rep. in preparation, Department of Computer Science, University of Illinois at Urbana-Champaign, 1995.

55. LP-VxWin VxWorks & MS-Windows Technical Manual Version 3.4, LP Elektronik GmbH, 1999.

56. M. Caccamo, G. Buttazzo, L. Sha, Handling Execution Overruns in Hard RealTime Control Systems, IEEE Transactions on computers., Vol. 51, No. 7, July 2002

57. M. Fleischmann, "Crusoe Power Management: Cutting x86 Operating Power through LongRun," Embedded Processor Forum, June 2000.

58. M. Handaoui, A dynamic priority assignment Technique for Streams with (m,k)-Firm Deadlines // IEEE Transactions on computers, vol. 44, no. 12, 1995.

59. M. K. Gardner "Probabilistic Analysis and Scheduling of Critical Soft Real-Time Systems", Thesis for the degree of Doctor of Philosophy in Computer Science in the Graduate College of the University of Illinois at Urbana-Champaign, 1999

60. M. Spuri and G. C. Buttazzo. Efficient aperiodic service under the earliest deadline scheduling. In IEEE Real-Time Systems Symposium, December 1994.

61. M. Woodbury. Analysis of the execution time of real-time tasks. In Real-Time Systems Symposium, pages 89-96, 1986.

62. P. Kumar and M. Srivastava, "Power-Aware Multimedia Systems Using Run-Time Prediction," Proc. 13th Int'l Conf. Computer Design, Jan. 2001.

63. QNX Operating System. System Architecture. QNX Software Systems Ltd, 1996.

64. R. Gonzalez and M. Horowitz, "Energy Dissipation in General Purpose Microprocessors," IEEE J. Solid-State Circuits, vol. 31, no. 9, Sept. 1996.

65. Ramamritham, K., G. Fohler and J. M. Adan, Issues in the Static Allocation and Scheduling of Complex Periodic Tasks, 10th IEEE Workshop on Real-Time operating Systems and Software, May 1993.

66. Rami G. Melhem, Daniel Mosse, E. N. Elnozahy: The Interplay of Power Management and Fault Recovery in Real-Time Systems. IEEE Trans. Computers 53(2): 217-231 (2004).

67. S. Baruah, J. Haritsa, and N. Sharma. On line scheduling to maximize task completions. In Real-Time Systems Symposium, pages 228-237, Dec. 1994. URL is http://www.emba.uvm.edu/ sanjoy/Papers/cc-jnl.ps.

68. S. Manolache, P. Eles, Z. Peng, Schedulability Analysis of Multiprocessor Real-TimeApplications with Stochastic Task Execution Times

69. S. Ramos-Thuel and J. P. Lehoczky. Algorithms for scheduling hard aperiodic tasks in fixed-priority systems using slack stealing. In Real-Time Systems Symposium. IEEE Computer Society Press, Dec. 1994.

70. Spuri M. and Buttazzo G. Scheduling aperiodic tasks in dynamic priority systems. Real-Time Systems, 10(2), 1996.

71. T. G. Tan and W. Hsu. Scheduling multimedia applications under overload and non-deterministic conditions. In Real- Time Technology and Applications Symposium, June 1997.

72. T. Nakajima and H. Tezuka, "A Continuous Media Application supporting Dynamic QOS Control on Real-Time Mach".

73. T. Nakajima, "Resource Reservation for Adaptive QOS Mapping in Real-Time Mach," Sixth International Workshop on Parallel and Distributed Real-Time Systems, April 1998.

74. T. Tia, Z. Deng, M. Shankar, M. Storch, J. Sun, L.-C. Wu, and J. W.-S. Liu. tasks with varying computation times. In Real-Time Technology and Applications Symposium, pages 164-173, May 1995.

75. T.F. Abdelzaher, E.M. Atkins, and K.G. Shin, "QoS Negotiation in Real-Time Systems and Its Applications to Automated Flight Control," Proceedings of the IEEE Real-Time Technology and Applications Symposium, Montreal, Canada, June 1997.

76. T.M. Ghazalie and T. Baker. Aperiodic servers in a deadline scheduling environment. Real-Time Systems, 9, 1995.

77. T.-S. Tia, J. W.-S. Liu, J. Sun, and R. Ha, "A Linear-Time Optimal Acceptance Test for Scheduling of Hard Real-Time Tasks," Submitted to IEEE Transaction on Software Engineering, 1994.

78. Т.-W. Kuo, А. К, Мок, "Load Adjustment in Adaptive Real-Time Systems," Proceedings of the 12th IEEE Real-Time Systems Symposium, December 1991.

79. Tongsima S., Sha E. H.-M., Chantrapornchai C., Surma D. R., and Passos N. L. Probabilistic Loop Scheduling for Applications with Uncertain Execution Time // IEEE Transactions on Computers, V. 49, No. 1, January 2000.

80. V. Sarkar, Determining Average Program Execution Times and their Variance.

81. VxWorks. Programmer's Guide. Wind River Systems, Inc., 1997.

82. W. Yuan, K. Nahrstedt, Energy-Efficient Soft Real-Time CPU Scheduling for Mobile Multimedia Systems.

83. Wei Kuan Shih, J. W. S. Liu and C. L. Liu, Modified Rate-Monotonic Algorithm for Scheduling Periodic Jobs with Deferred Deadlines // IEEE Transactions on Software Engineering, Vol. 19, No. 12, pp. 1171-1179, December 1993.

84. X. Zhang, Z. Wang, N. Gloy, J. Chen, and M. Smith. System support for automated profiling and optimization. In Proc. of Symposium on Operating Systems Principles, Oct. 1997.