Алгоритмы планирования вычислений и организации рестартов в системах реального времени
Диссертация
Во-вторых, в работах предполагается, что задания выполняются последовательно в строго оговоренном заранее порядке. На практике, однако, некоторые задания являются независимыми по данным, и при выполнении мы можем менять их местами. В общем случае все задания могут быть связаны произвольным графом зависимости по данным. Такая модель организации рестартов в системах реального времени была… Читать ещё >
Содержание
- Глава 1. Исследование задачи планирования вычислений в многопроцессорных системах с неполным графом связей
- 1. 1. Постановка задачи
- 1. 2. Потоковый алгоритм для случая полного графа связей
- 1. 3. ЫР-трудность некоторых задач
- 1. 3. 1. Задача с издержками на переключения
- 1. 3. 2. Задача с издержками на прерывания на одном процессоре
- 1. 3. 3. Случай неидентичных процессоров. ф 1.3.4. Случай произвольного графа связей
- 1. 3. 5. Случай двух отдельных полных компонент
- 1. 4. Формулировка основной задачи. Некоторые упрощения
- 1. 5. Алгоритм решения основной задачи
- 1. 5. 1. Задача преобразования расписания
- 1. 5. 2. Задача преобразования таблицы
- 1. 5. 3. Полиномиальное сведение
- 1. 5. 4. Масштабирование
- 1. 6. ИР-трудностъ основной задачи в общем случае
- 1. 7. Учет издержек на прерывания и переключения
- 1. 7. 1. 1. чПР-трудность
- 1. 7. 2. Случай полного графа связей
- 1. 7. 3. Метод последовательных приближений
- 1. 7. 4. 0. бщий случай. ф
- 1. 8. Специальная задача с учетом некоторых переключений
- 1. 8. 1. Формулировка задачи
- 1. 8. 2. Эквивалентная задача
- 1. 8. 3. Сведение к задаче булевого линейного программирования
- 1. 8. 4. Сведение к задаче целочисленного линейного программирования
- 2. 1. Формулировка задачи
- 2. 2. Простейший случай
- 2. 2. 1. Упрощающие предположения
- 2. 2. 2. Предварительные результаты
- 2. 2. 3. Одинаковое число модулей-буферов и модулей контроля. ф 2.2.4. Один модуль-буфер
- 2. 2. 5. Два модуля-буфера
- 2. 2. 6. Произвольное число модулей-буферов
- 2. 3. Случай нескольких параллельных цепочек рабочих модулей
- 2. 3. 1. Постановка задачи
- 2. 3. 2. Разделение модулей контроля по одинаковым цепочкам
- 2. 3. 3. Разделение модулей контроля по цепочкам при заданном разделении модулей-буферов
- 2. 3. 4. Приближенный алгоритм расстановки модулей
- 2. 3. 5. Точный алгоритм расстановки модулей контроля и модулей-буферов в случае нескольких параллельных цепочек
- 2. 4. Расположение модулей контроля для случая ориентированного дерева
- 2. 4. 1. Постановка задачи
- 2. 4. 2. Связь расстановок модулей контроля в дереве и в цепочке
- 2. 4. 3. Алгоритм для построения оптимальной расстановке модулей контроля в дереве
- 2. 5. Расположение модулей контроля для случая произвольного графа связей между рабочими модулями
- 2. 5. 1. Порядок выполнения рабочих модулей при заданном расположении модулей контроля
- 2. 5. 2. КР-трудность в сильном смысле задачи расстановки модулей контроля для случая произвольного графа
- 2. 5. 3. Применение метода «ветвей и границ»
- 2. 5. 4. Альтернативная стратегия при обнаружении ошибки
- 2. 6. Расстановка модулей контроля для случая произвольной вероятности ошибки
- 2. 6. 1. Вычисление математического ожидания
- 2. 6. 2. Оптимальное расположение модулей контроля для случая цепочки
- 2. 6. 3. Случай равных паралельных цепочек
- 2. 6. 4. Случай произвольных паралельных цепочек
Список литературы
- Liu C.L., Layland J. W. Scheduling Algorithms for Multiprogramming in Hard Real-Time Environment // Journal of the ACM, 20(1). C. 46−61.
- Э.Г. Коффман. Введение в детерминированную теорию расписаний. // В кн.: Теория расписаний и вычислительные машины / Под ред. Коффмана Э.Г. М. Наука, 1984. — С. 9−64.
- Baruah S., Howell R.R., Rosier L.E. Algorithms and Complexity Concerning the Preemptive Scheduling of Periodic, Real-Time Tasks on One Processor // Real-time systems, 2, 1990. C. 301−324.
- Танаев B.C., Гордон B.C., Шафранский Я. М. Теория расписаний. Одностадийные системы. М.: Наука, 1984. — 381 с.
- Головкин Б.А. Расчет характеристик и планирование параллельных вычислительных процессов. // М.: Радио и Связь, 1983. 272 с.
- Martel С. Preemptive scheduling with release times, deadlines and due times // Journal of the ACM. 1982 — V. 29, N 3. — P. 812−829.
- Gonzales Т., Sahni S. Preemptive Scheduling of Uniform Processor Systems // Journal of the Association for Computing Machinery. 1978 — V. 25, N 1. — P. 92−101.
- Federgruen A., Groenevelt H. Preemptive Scheduling of Uniform Machines by Ordinary Network Flow Technique // Management Science. 1986 — V.32, N 3. — P. 341−349.
- Audsley N., Burns A., Richardson M., Tindell K., Wellings A.J. Applying # New Scheduling Theory to Static Priority Preemptive Scheduling //
- Software Eng. 1993 — V.8, N 5. — P. 284−292.
- Marco Spurt Analysis of Deadline Scheduled Real-Time Systems // Technical Report No. 2772, INDIA, 1996.
- Banus J.M., Arenas A., Labarta J. Dual Priority Algorithm to Schedule Real-Time Tasks in a Shared Memory Multiprocessor // Workshop on Parallel and Distributed Rael-Time Systems, 2003.
- Brucker P. Scheduling Algorithms Springer, 3rd ed. New York, 2001 -377 p.
- Фуругян М.Г. Некоторые алгоритмы распределения ресурсов в ф многопроцессорных системах реального времени: Препринт / ВЦ1. РАН. М., 1996.-24 с.
- Гуз Д.С., Красовский Д. В., Фуругян М. Г. Эффективные алгоритмы планирования вычислений в многопроцессорных системах реального времени: Препринт / ВЦ РАН. М., 2004. — 65 с.
- Гуз Д. С., Фуругян М. Г. Планирование вычислений в многопроцессорных АСУ реального времени с ограничениями на память процессоров // Автоматика и телемеханика 2005 — № 2 — С. 138−147.
- Гуз Д. С. Разработка точных и приближенных алгоритмов составления расписаний и синтеза систем жесткого реального времени: Диссертация на соискание ученой степени кандидата физико-математических наук М., 2005. — 132 с.
- Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. // М.: Мир, 1982. 416 с.
- Chandy К. A survey of analytic models of roll-back and recovery strategies. // Computer 1975 — V.8, N 5. — P.40−47.
- Young J. W. A first-order approximation to the optimum checkpoint * interval. // Comm. ACM 1974 — V.17, N 9. — P. 530−531.
- Gelembe E. On the Optimum Checkpoint Interval I I J. ACM 1979 — V. 26 — P. 259−270.
- Duda A. The Effects of Checkpointing on Program Execution Time. // Information Processing Letters. 1983 — V. 16, N 5. — P. 221−229.
- Grassi V., Donatiello L., Tucci S., On the Optimal Checkpointing of Critical Tasks and Transaction-Oriented Systems. // IEEE Trans. Software Eng. 1992 — V. 18, N 1. — P. 72−77.
- Leung C., Choo Q. On the Execution of Large Batch Programs in Unreliable Computing Systems // IEEE Trans. Software Eng. 1984 -V.10,N4.-P. 444−450.
- Coffman E., Gilbert E. Optimal Strategies for Scheduling Checkpoints and Preventive Maintenance // IEEE Trans. Reliability 1990 — V.39, N 1 -P. 9−18.
- Benczur A, Kramlin A. An example for an adaptive control method providing database integrity. // In Proceedings of the Fourth International Symposium on Modeling and Performance Evaluation of Computer Systems 1979 -P. 249−262.
- Tantawi A., Ruschitzka M. Performance Analysis of Checkpointing Strategies. // ACM Trans. Computer Systems-1984-V.2,N 2- P. 123−144.
- Toueg S., Babaoglu O., On the Optimum Checkpoint Selection Problem I I SIAM J. Computing 1984 — V. 13, N 3. — P. 630−649.
- Bruno J.L., Coffman E.G., Optimal Fault-Tolerant Computing on Multiprocessor Systems // Acta Informatica 1997 — V.34 — P. 881−904.
- Ecuyer P., Malenfant J. Computing optimal checkpointing strategies for rollback and recovery systems // IEEE Trans. Computers 1988 — V.37, N4.-P. 491−496.
- Луганская М.И., Сушков Б. Г. Контроль данных в системах реального времени. // Математические методы управления обработкой информации. М.: МФТИ, 1986. С. 18 24.
- Белый Д.В., Сушков Б. Г. Модель организации рестартов в системах реального времени: Препринт / ВЦ РАН. М., 1996. — 32 с.
- Гречук Б. В., Фуругян М. Г. Составление оптимальных расписаний с прерываниями в многопроцессорных системах с неполным графом связей: Препринт / ВЦ РАН. М., 2004. — 44 с.
- Гречук Б. В., Фуругян М. Г. Составление оптимальных расписаний с прерываниями в многопроцессорных системах с неполным графом связей. // Кибернетика и системный анализ, 3, 2005, С. 94−102.
- Гречук Б.В., Фуругян М. Г. Алгоритмы организации рестартов в системах реального времени: Препринт / ВЦ РАН. М., 2004. — 32 с.
- Гречук Б.В., Фуругян М. Г. Алгоритмы организации рестартов в системах реального времени с произвольным графом связей: Препринт / ВЦ РАН. М., 2005. — 34 с.
- Гречук Б.В., Фуругян М. Г. Планирование вычислений в многопроцессорных системах с неполным графом связей // Моделирование процессов управления: Сб.ст./Моск.физ.-тех. ин-т. -М., 2004.-С. 155−161.
- В. V. Grechuk, M. G. Fourougian Optimal Scheduling of Incomplete Communication Graph Multiprocessor Systems. // Труды 4-й Московской международной конференции по исследованию операций, Москва, 2004. С. 98−100.
- Гречук Б.В., Фуругян М. Г. Алгоритмы организации рестартов в системах реального времени. // Материалы 12-й международной конференции «Проблемы управления безопасностью сложных систем», Москва, 2004. С. 234−237.
- Гречук Б.В. Эффективные алгоритмы для приближенного решения задачи о кратчайшем пути с ограничением по весу // Компьютерная математика, 1,2006-С. 140−151.
- ALON, N. A simple algorithm for edge-coloring bipartite multigraphs. Inf. Proc. Lett. Computers 2003 — V.85, N 6. — P. 301−302.
- Кормен Т., Лейзерсон 4., Pueecm Р. Алгоритмы. Построение и анализ. М.: МЦНМО, 2001 960 с.