Функция полезности времени
Функция времени/полезности ( TUF ), также известная как функция времени/значения для конкретного приложения , определяет полезность , которую дает действие (например, вычислительная задача, механическое движение) в зависимости от времени его завершения. [1] [2] TUF и их полезные интерпретации (семантика), шкалы и значения получены на основе знаний предметной области, специфичной для области применения. Примером (но не единственным) толкования полезности является относительная важность действия , которая в противном случае не зависит от его своевременности . Традиционный крайний срок, представленный в виде TUF, представляет собой особый случай — понижение полезности от 1 до 0 в момент крайнего срока — например, своевременность без важности. TUF носит более общий характер: у него есть критическое время, с формами, специфичными для конкретного приложения, и значениями полезности с каждой стороны, после чего он не увеличивается. Различные определения твердого и мягкого реального времени, используемые исследователями и практиками, также могут быть представлены как частные случаи модели TUF.
Критерием оптимальности для планирования нескольких действий, ограниченных TUF, исторически в литературе было только максимальное накопление полезности ( UA ) — например, (возможно, ожидаемая) взвешенная сумма полезностей завершения отдельных действий. Таким образом, при этом учитывается своевременность в критические моменты. Дополнительные критерии (например, энергия, предсказуемость), ограничения (например, зависимости), системные модели, алгоритмы планирования и гарантии были добавлены по мере развития парадигмы TUF/UA и вариантов ее использования. Говоря более выразительно, TUF/UA позволяет сравнивать накопленную полезность, своевременность, предсказуемость и другие критерии и ограничения планирования друг с другом, чтобы расписание обеспечивало ситуативное качество обслуживания приложения. [а] — а не только своевременность как таковая. Примеры парадигмы TUF/UA использовались в самых разных областях применения, чаще всего в военных системах.
Функции времени/полезности [ править ]
Парадигма TUF/UA изначально была создана для удовлетворения требований своевременности определенных действий, предсказуемости своевременности и потребностей планирования на основе QoS приложений различных военных приложений, для которых традиционные концепции и практики реального времени недостаточно выразительны (например, для динамически критичных к своевременности действий). системы, не имеющие сроков) и устойчивость к нагрузкам (например, для систем, подверженных рутинным перегрузкам). Важным общим примером таких приложений является противоракетная оборона (теоретически [3] [4] [5] ).
Впоследствии в академической литературе были изучены многочисленные вариации исходной модели TUF, системной модели парадигмы TUF/UA и, следовательно, методов и алгоритмов планирования, например: [6] [7] [8] [9] [10] — и применяется в гражданском контексте.
Некоторые примеры последних включают: киберфизические системы, [11] ИИ, [12] мультироботные системы, [13] планирование дронов, [14] автономные роботы, [15] интеллектуальная передача данных из автомобиля в облако, [16] управление производственными процессами, [17] системы транзакций, [18] высокопроизводительные вычисления, [19] облачные системы, [20] гетерогенные кластеры, [21] сервис-ориентированные вычисления, [22] сеть, [23] и управление памятью по-настоящему [24] и виртуальный [25] машины. Пример сталелитейного завода кратко описан во введении к докторской диссертации Кларка. диссертация. [26]
TUF и их полезные интерпретации (семантика), шкалы и значения получены на основе знаний предметной области, специфичной для предметной области. [27] [5] Исторически часто встречающаяся интерпретация полезности - это относительная важность действий. [б] Была разработана основа для априорного присвоения статических значений полезности с учетом строгих ограничений на модели системы. [8] но последующие (как и предыдущие) исследования и разработки TUF/UA предпочли полагаться на использование специфики приложения, а не на попытки создать более общие структуры. Однако такие структуры и инструменты остаются важной темой исследований.
По традиционному условию TUF — это вогнутая функция , в том числе линейная. См. изображения некоторых примеров TUF.
Статьи TUF/UA в исследовательской литературе, за некоторыми исключениями, например, [28] [6] [29] [30] [8] [10] предназначены только для линейных или кусочно-линейных [31] (в том числе обычные, основанные на сроках) TUF, потому что их легче определить и запланировать. Во многих случаях TUF монотонно уменьшаются .
Постоянная функция представляет полезность действия, которая не связана со временем завершения действия, например постоянную относительную важность действия. Это позволяет согласованно планировать как зависящие от времени, так и независимые от времени действия.
У TUF есть глобальное критическое время , после которого его полезность не увеличивается. Если TUF никогда не уменьшается, его глобальное критическое время — это первый момент, когда достигается его максимальная полезность. Постоянный TUF имеет произвольное критическое время для целей планирования, например время завершения действия или время завершения TUF. За глобальным критическим временем могут следовать локальные критические времена. [2] — например, рассмотрим TUF, имеющий последовательность ступеней вниз, возможно, для аппроксимации плавной нисходящей кривой. [с]
Значения полезности TUF обычно представляют собой целые или рациональные числа.
Утилита TUF может включать отрицательные значения. (TUF, имеющий отрицательные значения в своем диапазоне, не обязательно исключается из планирования или прерывается во время его работы — это решение зависит от алгоритма планирования.)
Обычный крайний срок ( d ), представленный как TUF, представляет собой особый случай — TUF с шагом вниз. [д] наличие единичного штрафа (т. е. наличие значений полезности 1 до и 0 после критического момента).
В более общем смысле, TUF позволяет функциям шага вниз (и вверх) иметь любую полезность до и после критического времени.
Опоздание [32] представленный как TUF, представляет собой особый случай, ненулевая полезность которого представляет собой линейную функцию C - d , где C — время завершения действия — текущее, ожидаемое или предполагаемое. [и] В более общем смысле, TUF допускает, чтобы ненулевая заблаговременность и запаздывание были нелинейными — например, увеличение задержки может привести к нелинейному уменьшению полезности, например, при обнаружении угрозы.
Таким образом, TUF обеспечивают богатое обобщение традиционных ограничений времени выполнения действий в вычислениях в реальном времени .
В качестве альтернативы, парадигма TUF/UA может использоваться для использования своевременности по отношению к глобальному критическому времени как средства достижения цели накопления полезности, т. е. качества обслуживания (QoS) на уровне приложения, вместо того, чтобы своевременность сама по себе была целью в сам( ).
TUF (его форма и значения) может динамически адаптироваться приложением или его операционной средой. [2] независимо для любых действий, ожидающих или выполняемых в данный момент. [ф]
Эти адаптации обычно происходят в отдельных событиях, например, при изменении режима применения, например, на этапах полета баллистической ракеты. [5]
Альтернативно, эти адаптации могут происходить непрерывно, например, для действий, продолжительность работы которых и TUF зависят от приложения и зависят от того, когда эти действия либо запускаются, либо начинаются. Продолжительность работы может увеличиваться или уменьшаться, или и то, и другое, и может быть немонотонным. Этот непрерывный случай называется планированием, зависящим от времени . [33] [34] Зависимое от времени планирование было введено для (но не ограничиваясь этим) некоторых военных приложений реального времени, таких как системы радиолокационного слежения. [35] [36] [г]
Планирование начисления коммунальных услуг [ править ]
Несколько действий в системе могут конкурировать за доступ к эксклюзивным последовательным [час] общие ресурсы — физические, такие как процессоры, сети, внешние прикладные устройства (датчики, исполнительные механизмы и т. д.) — и логические, такие как синхронизаторы, данные.
Парадигма TUF/UA разрешает каждый случай этого конфликта, используя алгоритмический метод, специфичный для приложения, который создает (или обновляет) расписание при планировании событий — например, времени (например, прибытия или завершения действия) или состояний. Конкурирующие действия экземпляра отправляются для доступа к ресурсу последовательно, начиная с начала расписания. Таким образом, последовательность действий UA не является жадной. [я]
Алгоритмический метод создает расписание на основе одной или нескольких целей , специфичных для приложения (т. е. критериев оптимальности).
Основной целью планирования действий с TUF является максимальное накопление полезности ( UA ). Начисляемая полезность представляет собой специфичную для приложения полиномиальную сумму полезностей завершенных действий расписания. Когда действия имеют один или несколько стохастических параметров (например, продолжительность операции), наращенная полезность также является стохастической (т. е. ожидаемой полиномиальной суммой).
Полезность и накопленная полезность являются общими, их интерпретации (семантика) и масштабы зависят от приложения. [27]
Продолжительность действия действия может быть фиксирована и известна во время настройки системы. В более общем смысле, оно может быть либо фиксированным, либо стохастическим, но неизвестным (либо с уверенностью, либо в ожидании), пока оно не прибудет или не будет выпущено.
Продолжительность операции может быть зависящей от приложения функцией времени начала операции — она может увеличиваться или уменьшаться, или и то, и другое, и может быть немонотонной. Этот случай называется планированием, зависящим от времени . [33] [34] [35] [36]
Примечания [ править ]
- ^ Термин «качество обслуживания» (QoS) изначально возник в контексте сетей связи, но впоследствии стал широко применяться на уровне приложений.
- ^ Планирование на основе важности — это не то же самое, что жадная диспетчеризация на основе важности.
- ↑ Это более общий характер, чем введение Локком термина «критическое время» в Локке 86.
- ^ Имеется разрыв либо в функции, либо в ее первой или второй производной.
- ^ Например, теории математических доказательств, такие как теория Демпстера-Шафера , неточные теории вероятностей и т. д., могут использоваться для определенных системных моделей, имеющих эпистемические неопределенности.
- ^ Эксплуатация используется в общем случае для включения невычислительных (например, мехатронных) действий, а также выполняемых вычислительных задач.
- ^ Планирование, зависящее от времени (т. е. продолжительность операций некоторых действий является функцией времени их начала), отличается от планирования в реальном времени и не ограничивается им в том смысле, что действия имеют крайние сроки (или критическое время).
- ^ Последовательное исключение — это особый случай совместного доступа, используемый здесь для простоты без потери общности.
- ^ Некоторые планировщики UA могут жадно удалять перегрузку - ср. §7.5.1 в Локке 86.
Ссылки [ править ]
- ^ Э. Дуглас Дженсен, К. Дуглас Локк и Хидеюки Токуда. Модель планирования, основанная на временных параметрах, для операционных систем реального времени, Proc. Симпозиум по системам реального времени, IEEE, 1985.
- ^ Jump up to: а б с Э. Дуглас Дженсен. Модель своевременности для асинхронных децентрализованных компьютерных систем, Учеб. Международный симпозиум по автономным децентрализованным системам, IEEE, 1993 г.
- ^ Э. Дуглас Дженсен. Глава 3. Радарное планирование, раздел 1. Проблема планирования в Gouda+ 77 (несекретная версия).
- ^ Мохамед Г. Гауда, И-Ву Хан, Э. Дуглас Дженсен, Уэсли Д. Джонсон, Ричард Ю. Кейн (редактор). Технология распределенной обработки данных, Vol. IV, Применение технологии DDP для ПРО: архитектуры и алгоритмы, несекретная версия, Центр технической информации Министерства обороны a047477, Центр систем и исследований Honeywell, Миннеаполис, Миннесота, 1977.
- ^ Jump up to: а б с Дэвид П. Мейнард, Сэмюэл Э. Шипман, Рэймонд К. Кларк, Дж. Дуэйн Норткатт, Э. Дуглас Дженсен, Рассел Б. Кегли, Бетси А. Циммерман, Питер Дж. Келехер. Пример приложения командования и управления боем в реальном времени для Alpha, раздел 8.2.1, Технический отчет проекта Archons, 1988 г., и общедоступная версия 2008 г.
- ^ Jump up to: а б Биной Равиндран, Э. Дуглас Дженсен и Пэн Ли. О последних достижениях в области функций времени/полезности, планирования в реальном времени и управления ресурсами, учеб. Восьмой международный симпозиум IEEE по объектно-ориентированным распределенным вычислениям в реальном времени, 2005 г.
- ^ Сауд А. Алдами и Алан Бернс. Динамическая плотность значений для планирования систем реального времени, Учеб. 11-я конференция Euromicro по системам реального времени, IEEE, 1999 г.
- ^ Jump up to: а б с Алан Бернс, Д. Прасад, А. Бондавалли, Ф. Ди Джандоменико, К. Рамамритам, Дж. Станкович, Л. Стригини. Значение и роль ценности в планировании гибких систем реального времени, Журнал системной архитектуры, Elsivier, 2000.
- ^ Дивья Прасад, Алан Бернс и Мартин Аткинс. Допустимое использование полезности в адаптивных системах реального времени. Системы реального времени, Клювер, 2003.
- ^ Jump up to: а б Кен Чен и Пол Мюлеталер. Семейство алгоритмов планирования для систем реального времени, использующих функции временного значения. Системы реального времени, том. 10 нет. 3, Клювер, 1996.
- ^ Терри Тидвелл, Роберт Глаубиус, Кристофер Д. Гилл и Уильям Д. Смарт. Оптимизация ожидаемой полезности времени в планировщиках киберфизических систем, учеб. Симпозиум IEEE по системам реального времени, 2010 г.
- ^ Ягиль Ронен, Дэниел Моссе и Марта Э. Поллак. Алгоритмы плотности значений для проблемы планирования и обсуждения, Бюллетень ACM SIGART, том 7, выпуск 2, 1996.
- ^ Михал Барцис, Агата Барцис и Герман Хеллвагнер. Модель оценки распределения информации в мультироботных системах и датчиках, январь 2020 г.
- ^ Ширин Сихоа-Кинг, Пол Баладжи, Николас Трама Альварес и Уильям Дж. Ноттенбелт. Планирование, ориентированное на прибыль, в сетях доставки дронами с срочными соглашениями об уровне обслуживания, Учеб. 12-я Международная конференция EAI по методологиям и инструментам оценки эффективности, ACM, 2019.
- ^ Алдис Баумс. Автоматическое управление и информатика, Vol. 46, № 6, Аллертон Пресс, 2012.
- ^ Жан Ибарц, Мишель Лауэр, Матье Рой, Жан-Шарль Фабр, Оливье Флебус. Оптимизация передачи данных от автомобиля к облаку с использованием концепций мягкого планирования в реальном времени , Учеб. 28-я Международная конференция по сетям и системам реального времени, ACM, 2020.
- ^ Рутгер Хабетс. Повышение производительности упаковочной линии 41 в Heineken Zoeterwoude, дипломная работа бакалавра наук, промышленная инженерия и менеджмент, Университет Твенте, 2019.
- ^ Джаянт Р. Харица, Джаянт Р., Майкл Дж. Кэри и Мирон Ливни. Планирование на основе значений в базах данных реального времени, журнал VLDB, 2 (2) 1993.
- ^ Луис Диего Брисеньо, Бхавеш Хемка, Ховард Джей Сигел, Энтони А. Мациевски, Кристофер Гроер, Грегори Кениг, Джин Оконски и Стив Пул. Функции полезности времени для моделирования и оценки распределения ресурсов в гетерогенной вычислительной системе, Учеб. Международный симпозиум IEEE по параллельной и распределенной обработке, 2011 г.
- ^ Джихан Тунч, Нирмал Кумбхаре, Али Акоглу, Салим Харири, Дилан Маховец, Ховард Джей Сигел. Значение планирования задач на основе услуг для систем облачных вычислений, Учеб. Международная конференция по облачным и автономным вычислениям, 2016.
- ^ Винеш Т. Рави1, Микела Бекки2, Гаган Агравал1 и Шримат Чакрадхар. ValuePack: Структура планирования на основе значений для кластеров CPU-GPU, Proc. Международная конференция IEEE по высокопроизводительным вычислениям, сетям, хранению и анализу, 2012 г.
- ^ Элвин АуЯнг, Лаура Грит, Джанет Винер, Джон Уилкс. Контракты обслуживания и совокупные функции полезности, Учеб. 15-й Международный симпозиум IEEE по высокопроизводительным распределенным вычислениям, 2006 г.
- ^ Цзинган Ван и Биной Равиндран. Коммутируемый Ethernet, управляемый функцией Time-Utility: алгоритм планирования пакетов, реализация и технико-экономический анализ, Транзакции IEEE в параллельных и распределенных системах, том. 15, нет. 2 февраля 2004 г.
- ^ Хёнджун Чо, Биной Равиндран, Чеу На. Планирование сборщика мусора в динамических многопроцессорных системах реального времени, транзакции IEEE в параллельных и распределенных системах 20 (6), июнь 2009 г.
- ^ Шахруз Фейзабади и Годмар Бэк. Планирование начисления коммунальных услуг с учетом сбора мусора, Real-Time Systems Journal, июль 2007 г., том 36, выпуск 1–2, 2007 г.
- ^ Раймонд К. Кларк. Планирование зависимых действий в реальном времени, к.т.н. Диссертация, CMU-CS-90-155, факультет компьютерных наук, Университет Карнеги-Меллона, 1990.
- ^ Jump up to: а б Рэймонд К. Кларк, Э. Дуглас Дженсен, Аркадий Каневский, Джон Маурер, Пол Уоллес, Том Уилер, Юн Чжан, Дуглас М. Уэллс, Том Лоуренс и Пэт Херли. Адаптивная распределенная бортовая система слежения, параллельные и распределенные системы реального времени IEEE, том 1586 LNCS, Springer-Verlag, 1999.
- ^ К. Дуглас Локк. Принятие решений с максимальным усилием для планирования в реальном времени, доктор философии. Диссертация CMU-CS-86-134, факультет компьютерных наук, Университет Карнеги-Меллона, 1986 г.
- ^ Пэн Ли. Планирование начисления коммунальных услуг в реальном времени: модели и алгоритмы, к.т.н. диссертация, Политехнический институт и Государственный университет Вирджинии, 2004 г.
- ^ Пэн Ли, Хайсан Ву, Биной Равиндран и Э. Дуглас Дженсен. Алгоритм планирования начисления коммунальных услуг для действий в реальном времени с ограничениями ресурсов взаимного исключения, IEEE Transactions on Computers, vol. 55, нет. 4 апреля 2006 г.
- ^ Чжишань Го и Санджой Буруа. Нейродинамический подход к планированию в реальном времени посредством максимизации кусочно-линейной полезности , Транзакции IEEE в нейронных сетях и системах обучения, том. 27 нет. 2 февраля 2016 г.
- ^ Джереми П. Эриксон. Управление границами опозданий и перегрузкой в системах мягкого реального времени , к.т.н. диссертация, Университет Северной Каролины, 2014 г.
- ^ Jump up to: а б Станислав Гавейнович. Обзор четырех десятилетий планирования, зависящего от времени: основные результаты, новые темы и открытые проблемы, Journal of Scheduling 23, 3–47, Springer, 2020.
- ^ Jump up to: а б К.Д. Глейзбрук. Планирование случайных работ с использованием одной машины, подверженных ухудшению качества или задержке, Naval Research Logistics 39, no. 5, Уайли, 1992 г.
- ^ Jump up to: а б Умут Балли, Хайсанг Ву, Биной Равиндран, Джонатан Стивен Андерсон, Э. Дуглас Дженсен. Планирование начисления коммунальных услуг в реальном времени с использованием функций переменных затрат, Транзакции IEEE на компьютерах, том 56, номер 3, март 2007 г.
- ^ Jump up to: а б Кевин Эй Джей. Эй, Джозеф Ю.Т. Люнг и В.Д. Вэй. Сложность задач планирования с зависящим от времени временем выполнения, Information Processing Letters 48 (1993), вып. 6, Эльзевир, 20 декабря 1993 г.
Внешние ссылки [ править ]
- Реальное время для реального мира.
- 2006–2009 гг., Группа исследований системного программного обеспечения, Биной Равиндран, ECE, Технологический институт Вирджинии.
- Майкл Л. Пиндо, Планирование: теория, алгоритмы и системы, 5-е изд., 2015 г.
- Станислав Гавейнович, Модели и алгоритмы временного планирования , 2-е изд., электронная книга ISBN 978-3-662-59362-2 , Спрингер, 2020 г.
- Крис Н. Поттс и Виталий А. Струсевич, Пятьдесят лет планирования: обзор основных этапов (2009)
- Журнал планирования.
- Междисциплинарная международная конференция по планированию.
- Международный семинар по проблемам динамического планирования.