Функция полезности времени

Функция времени/полезности ( TUF ), урожденная функция времени/значения , определяет специфическую для приложения полезность , которую действие (например, вычислительная задача, механическое движение) дает в зависимости от времени его завершения. [1] [2] TUF и их интерпретации полезности (семантика), шкалы и значения выводятся из предметных знаний, специфичных для прикладной области. Примером (но не единственным) интерпретации полезности является относительная важность действия , которая в противном случае не зависит от его своевременности . Традиционный крайний срок, представленный как TUF, является особым случаем — нисходящий шаг полезности от 1 до 0 в момент крайнего срока — например, своевременность без важности. TUF более общий — он имеет критическое время с специфичными для приложения формами и значениями полезности с каждой стороны, после чего он не увеличивается. Различные определения твердого и мягкого реального времени исследователями и практиками также могут быть представлены как особые случаи модели TUF.

Изображение примеров TUF

Критерием оптимальности для планирования нескольких действий, ограниченных TUF, исторически в литературе было только максимальное накопление полезности ( UA ) — например, (возможно, ожидаемая) взвешенная сумма полезностей завершения отдельных действий. Таким образом, это учитывает своевременность по отношению к критическим временам. Дополнительные критерии (например, энергия, предсказуемость), ограничения (например, зависимости), системные модели, алгоритмы планирования и гарантии были добавлены по мере развития парадигмы TUF/UA и ее вариантов использования. Более выразительно, TUF/UA позволяет компенсировать накопленную полезность, своевременность, предсказуемость и другие критерии и ограничения планирования друг против друга для расписания, чтобы получить ситуативное прикладное QoS [a] — в отличие от только своевременности как таковой. Экземпляры парадигмы 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] Исторически частой интерпретацией полезности является относительная важность действий . [b] Была разработана структура для априорного назначения статических значений полезности с учетом строгих ограничений на системные модели, [8] но последующие (как и предыдущие) исследования и разработки TUF/UA предпочли полагаться на использование специфичности приложения, а не на попытки создания более общих структур. Однако такие структуры и инструменты остаются важной темой исследования.

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

Статьи TUF/UA в исследовательской литературе, за редкими исключениями, например, [28] [6] [29] [30] [8] [10], касаются только линейных или кусочно-линейных [31] (включая традиционные основанные на сроках) TUF, поскольку их легче определить и запланировать. Во многих случаях TUF только монотонно уменьшаются.

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

У TUF есть глобальное критическое время , после которого его полезность не увеличивается. Если TUF никогда не уменьшается, его глобальное критическое время — это первый момент, когда достигается его максимальная полезность. Постоянный TUF имеет произвольное критическое время для целей планирования, например, время выпуска действия или время завершения TUF. За глобальным критическим временем могут следовать локальные критические времена [2] — например, рассмотрим TUF, имеющий последовательность нисходящих шагов, возможно, для аппроксимации плавной нисходящей кривой. [c]

Значения полезности TUF обычно представляют собой целые или рациональные числа.

Утилита TUF может включать отрицательные значения. (TUF, в диапазоне которого есть отрицательные значения, не обязательно исключается из рассмотрения при планировании или прерывается во время работы — это решение зависит от алгоритма планирования.)

Условное время крайнего срока ( d ), представленное как TUF, является особым случаем — нисходящим шагом TUF [d] , имеющим единичный штраф (т. е. имеющим значения полезности 1 до и 0 после своего критического времени).

В более общем смысле, TUF допускает, чтобы нисходящие (и восходящие) ступенчатые функции имели любые пред- и посткритические временные полезности.

Опоздание [32], представленное в виде TUF, является особым случаем, ненулевая полезность которого является линейной функцией C - d , где C - время завершения действия - текущее, ожидаемое или предполагаемое. [e] В более общем смысле TUF допускает ненулевое раннее начало и опоздание, которые могут быть нелинейными - например, увеличение опоздания может привести к нелинейному уменьшению полезности, например, при обнаружении угрозы.

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

В качестве альтернативы можно применить парадигму TUF/UA для использования своевременности по отношению к глобальному критическому времени в качестве средства для достижения конечной цели — т. е. качества обслуживания (QoS) на уровне приложений — вместо того, чтобы своевременность сама по себе была конечной целью ( см. ниже ).

TUF (его форма и значения) могут динамически адаптироваться приложением или его операционной средой [2] независимо от любых действий, которые в данный момент находятся в состоянии ожидания или выполнения. [f]

Эти адаптации обычно происходят при дискретных событиях, например, при изменении режима применения, например, для фаз полета баллистической ракеты. [5]

В качестве альтернативы эти адаптации могут происходить непрерывно, например, для действий, операционные длительности и TUF которых являются функциями, специфичными для приложения, когда эти действия либо запущены, либо начинают работу. Длительности операций могут увеличиваться или уменьшаться, или и то, и другое, и могут быть немонотонными. Этот непрерывный случай называется зависящим от времени планированием . [33] [34] Зависящее от времени планирование было введено для (но не ограничивается) определенных военных приложений реального времени, таких как системы радиолокационного слежения. [35] [36] [g]

Планирование начисления коммунальных платежей

Несколько действий в системе могут конкурировать за доступ к последовательно исключительно [h] общим ресурсам — физическим, таким как процессоры, сети, внешние прикладные устройства (датчики, исполнительные механизмы и т. д.), и логическим, таким как синхронизаторы, данные.

Парадигма TUF/UA разрешает каждый экземпляр этого конфликта с помощью алгоритмической техники, специфичной для приложения, которая создает (или обновляет) расписание в планируемых событиях — например, времени (например, прибытия или завершения действия) или состояниях. Конкурирующие действия экземпляра отправляются для доступа к ресурсам последовательно в порядке от начала расписания. Таким образом, последовательность действий UA не является жадной. [i]

Алгоритмический метод создает расписание на основе одной или нескольких целей , специфичных для приложения (т. е. критериев оптимальности).

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

Полезность и накопленная полезность являются общими, их интерпретации (семантика) и шкалы зависят от конкретного приложения. [27]

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

Длительность операции может быть функцией приложения от времени начала операции действия — она может увеличиваться или уменьшаться или и то, и другое, и может быть немонотонной. Этот случай называется планированием, зависящим от времени . [33] [34] [35] [36]

Примечания

  1. ^ Термин «качество обслуживания» (QoS) изначально возник в контексте сетей связи, но впоследствии стал широко применяться на уровне приложений.
  2. ^ Планирование на основе важности — это не то же самое, что жадная диспетчеризация на основе важности.
  3. ^ Это более общее понятие, чем введение Локком термина «критическое время» в Локке 86.
  4. ^ Имеет место разрыв либо функции, либо ее первой или второй производной.
  5. ^ Например, математические теории доказательств, такие как теория Демпстера-Шейфера , неточные теории вероятностей и т. д., могут использоваться для определенных системных моделей, имеющих эпистемические неопределенности.
  6. ^ Термин «эксплуатация» используется в общем случае и включает невычислительные (например, мехатронные) действия, а также выполняемые вычислительные задачи.
  7. ^ Планирование, зависящее от времени (т. е. длительность выполнения некоторых действий является функцией времени их начала), отличается от планирования в реальном времени и не ограничивается им в том смысле, что действия имеют крайние сроки (или критические моменты времени).
  8. ^ Последовательно-исключающий доступ — это частный случай общего доступа, используемый здесь для простоты без потери общности.
  9. ^ Некоторые планировщики UA могут удалять перегрузку жадным образом — см. §7.5.1 в Locke 86.

Ссылки

  1. ^ Э. Дуглас Дженсен, К. Дуглас Лок и Хидеюки Токуда. Модель планирования, управляемая временем и значением, для операционных систем реального времени, Труды симпозиума по системам реального времени, IEEE, 1985.
  2. ^ abc E. Дуглас Дженсен. Модель своевременности для асинхронных децентрализованных компьютерных систем, Труды Международного симпозиума по автономным децентрализованным системам, IEEE, 1993
  3. ^ Э. Дуглас Дженсен. Глава 3 Планирование работы радаров, Раздел 1 Проблема планирования в Гауде+ 77 (несекретная версия).
  4. ^ Мохамед Г. Гауда, И-Ву Хан, Э. Дуглас Дженсен, Уэсли Д. Джонсон, Ричард Й. Кейн (редактор). Технология распределенной обработки данных, т. IV, Применение технологии DDP к ПРО: архитектуры и алгоритмы, несекретная версия, Центр технической информации Министерства обороны США, a047477, Honeywell Systems and Research Center, Миннеаполис, MN, 1977.
  5. ^ abc Дэвид П. Мейнард, Сэмюэл Э. Шипман, Рэймонд К. Кларк, Дж. Дуэйн Норткатт, Э. Дуглас Дженсен, Рассел Б. Кегли, Бетси А. Циммерман, Питер Дж. Келехер. Пример приложения для управления боем в реальном времени для Alpha, раздел 8.2.1, Технический отчет проекта Archons, 1988 г. и общедоступная версия 2008 г.
  6. ^ ab Биной ​​Равиндран, Э. Дуглас Дженсен и Пэн Ли. О последних достижениях в области планирования и управления ресурсами в реальном времени с использованием функций времени/полезности, Труды Восьмого международного симпозиума IEEE по объектно-ориентированным распределенным вычислениям в реальном времени, 2005.
  7. ^ Сауд А. Алдами и Алан Бернс. Динамическая плотность значений для планирования систем реального времени, Труды 11-й конференции Euromicro по системам реального времени, IEEE, 1999.
  8. ^ abc Алан Бернс, Д. Прасад, А. Бондавлли, Ф. Ди Джандоменико, К. Рамамритам, Дж. Станкович, Л. Стригини. Значение и роль ценности в планировании гибких систем реального времени, Журнал системной архитектуры, Elsivier, 2000.
  9. ^ Дивья Прасад, Алан Бернс и Мартин Аткинс. Допустимое использование полезности в адаптивных системах реального времени. Системы реального времени, Kluwer, 2003.
  10. ^ ab Кен Чен и Пол Мухлетхалер. Семейство алгоритмов планирования для систем реального времени с использованием функций значений времени. Системы реального времени, т. 10, № 3, Kluwer, 1996.
  11. ^ Терри Тидвелл, Роберт Глаубиус, Кристофер Д. Гилл и Уильям Д. Смарт. Оптимизация ожидаемой полезности времени в планировщиках киберфизических систем, Труды Симпозиума IEEE по системам реального времени, 2010.
  12. ^ Ягил Ронен, Даниэль Моссе и Марта Э. Поллак. Алгоритмы плотности значений для задачи планирования обсуждений, ACM SIGART Bulletin, том 7, выпуск 2, 1996.
  13. ^ Михал Барцис, Агата Барцис и Герман Хеллвагнер. Модель оценки распределения информации в многороботных системах, Датчики, январь 2020 г.
  14. ^ Ширин Сикхоа-Кинг, Пол Баладжи, Николас Трама Альварес и Уильям Дж. Кноттенбелт. Планирование с учетом доходов в сетях доставки дронами с соглашениями об уровне обслуживания, чувствительными к срокам, Труды 12-й Международной конференции EAI по методам и инструментам оценки эффективности, ACM, 2019.
  15. ^ Олдис Баумс. Автоматическое управление и компьютерные науки, т. 46, № 6, Allerton Press, 2012.
  16. ^ Жан Ибарц, Михаэль Лауэр, Матье Руа, Жан-Шарль Фабр, Оливье Флебюс. Оптимизация передачи данных между транспортным средством и облаком с использованием концепций мягкого планирования в реальном времени , Труды 28-й Международной конференции по сетям и системам реального времени, ACM, 2020.
  17. ^ Рутгер Хабетс. Повышение производительности упаковочной линии 41 на заводе Heineken Zoeterwoude, дипломная работа бакалавра наук, промышленная инженерия и менеджмент, Университет Твенте, 2019.
  18. ^ Джайант Р. Харица, Джайант Р., Майкл Дж. Кэри и Мирон Ливни. Планирование на основе ценностей в базах данных реального времени, VLDB Journal, 2 (2) 1993.
  19. ^ Луис Диего Брисеньо, Бхавеш Кхемка, Говард Джей Сигел, Энтони А. Мациевски, Кристофер Гроэр, Грегори Кёниг, Джин Оконски и Стив Пул. Функции полезности времени для моделирования и оценки распределения ресурсов в гетерогенной вычислительной системе, Proc. IEEE International Symposium on Parallel and Distributed Processing, 2011.
  20. ^ Джихан Тунч, Нирмал Кумбхаре, Али Акоглу, Салим Харири, Дилан Мачовец, Говард Джей Сигел. Ценность сервисного планирования задач для систем облачных вычислений, Труды Международной конференции по облачным и автономным вычислениям, 2016.
  21. ^ Вигнеш Т. Рави1, Микела Бекки2, Гаган Агравал1 и Шримат Чакрадхар. ValuePack: Платформа планирования на основе стоимости для кластеров CPU-GPU, Proc. IEEE Международная конференция по высокопроизводительным вычислениям, сетям, хранению и анализу, 2012.
  22. ^ Элвин АуЯнг, Лора Грит, Джанет Винер, Джон Уилкс. Контракты на обслуживание и функции совокупной полезности, Труды 15-го Международного симпозиума IEEE по высокопроизводительным распределенным вычислениям, 2006.
  23. ^ Цзинган Ван и Биной ​​Равиндран. Коммутируемый Ethernet с функцией полезности времени: алгоритм планирования пакетов, реализация и анализ осуществимости, IEEE Transactions on Parallel and Distributed Systems, т. 15, № 2, февраль 2004 г.
  24. ^ Хёнджун Чо, Биной ​​Равиндран, Чеву На. Планирование работы сборщика мусора в динамических многопроцессорных системах реального времени, IEEE Transactions on Parallel and Distributed Systems 20(6), июнь 2009 г.
  25. ^ Шахруз Фейзабади и Годмар Бэк. Планирование накопления коммунальных услуг с учетом сбора мусора, Real-Time Systems Journal, июль 2007 г., том 36, выпуск 1–2, 2007 г.
  26. ^ Рэймонд К. Кларк. Планирование зависимых действий в реальном времени, докторская диссертация, CMU-CS-90-155, Кафедра компьютерных наук, Университет Карнеги-Меллона, 1990.
  27. ^ ab Raymond K. Clark, E. Douglas Jensen, Arkady Kanevsky, John Maurer, Paul Wallace, Tom Wheeler, Yun Zhang, Douglas M. Wells, Tom Lawrence и Pat Hurley. Адаптивная распределенная система слежения за самолетами, IEEE Parallel and Distributed Real-Time Systems, том 1586 LNCS, Springer-Verlag, 1999.
  28. ^ К. Дуглас Локк. «Принятие решений с максимальным усилием для планирования в реальном времени», докторская диссертация CMU-CS-86-134, кафедра компьютерных наук, Университет Карнеги-Меллона, 1986.
  29. ^ Пэн Ли. Планирование накопления коммунальных услуг в реальном времени: модели и алгоритмы, докторская диссертация, Политехнический институт Вирджинии и Государственный университет, 2004.
  30. ^ Пэн Ли, Хайсан Ву, Биной ​​Равиндран и Э. Дуглас Дженсен. Алгоритм планирования накопления полезности для действий в реальном времени с ограничениями ресурсов взаимного исключения, IEEE Transactions on Computers, т. 55, № 4, апрель 2006 г.
  31. ^ Чжишан Го и Санджой Буруа. Нейродинамический подход к планированию в реальном времени с помощью максимизации кусочно-линейной полезности , IEEE Transactions on Neural Networks and Learning Systems, т. 27 № 2, февраль 2016 г.
  32. ^ Джереми П. Эриксон. Управление границами задержек и перегрузкой в ​​мягких системах реального времени , докторская диссертация, Университет Северной Каролины, 2014.
  33. ^ ab Станислав Гавейнович. Обзор четырех десятилетий планирования, зависящего от времени: основные результаты, новые темы и открытые проблемы, Журнал планирования 23, 3–47, Springer, 2020.
  34. ^ ab KD Glazebrook. Одномашинное планирование стохастических работ, подверженных ухудшению или задержке, Naval Research Logistics 39, № 5, Wiley, 1992.
  35. ^ ab Umut Balli, Haisang Wu, Binoy Ravindran, Jonathan Stephen Anderson, E. Douglas Jensen. Планирование начисления коммунальных услуг в режиме реального времени с использованием функций переменной стоимости, IEEE Transactions on Computers, том 56, номер 3, март 2007 г.
  36. ^ ab Кевин И. Дж. Хо, Джозеф И. Т. Леунг и В. Д. Вэй. Сложность планирования задач с зависящим от времени временем выполнения, Information Processing Letters 48 (1993), № 6, Elsevier, 20 декабря 1993 г.
  • Реальное время для реального мира.
  • 2006-2009 гг., Группа исследований системного программного обеспечения, Биной ​​Равиндран, ECE, Политехнический институт Вирджинии.
  • Майкл Л. Пиндо, Планирование: теория, алгоритмы и системы, 5-е изд., 2015.
  • Станислав Гавейнович, Модели и алгоритмы планирования, зависящего от времени, 2-е изд., электронная книга ISBN  978-3-662-59362-2 , Springer, 2020.
  • Крис Н. Поттс и Виталий А. Струсевич, Пятьдесят лет планирования: обзор основных этапов (2009)
  • Журнал планирования.
  • Междисциплинарная международная конференция по планированию.
  • Международный семинар по проблемам динамического планирования.
Взято с "https://en.wikipedia.org/w/index.php?title=Time-utility_function&oldid=1137275065"