Эффективность выполнения стохастических задач в режимах перегрузки тема диссертации и автореферата по ВАК РФ 05.13.15, кандидат технических наук Бабак, Дмитрий Александрович

• Бабак, Дмитрий Александрович
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Бабак, Дмитрий Александрович

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ. 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, реализующий выполнение стохастических задач с оптимизацией по предложенным критериям.

Список литературы диссертационного исследования кандидат технических наук Бабак, Дмитрий Александрович, 2005 год

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.