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

Введение.

1. Отказоустойчивость вычислительных систем.

1.1 Основные понятия отказоустойчивости вычислительных систем.

1.2 Обеспечение отказоустойчивости вычислительных систем к отказам и сбоям.

Выводы.

2. Схемы отказоустойчивых вычислительных систем.

2.1 Схемы восстановления вычислительного процесса.

2.1.1 Схемы с дублированием вычислительного процесса.

2.1.2 Схема с трехкратным резервированием задач.

2.2 Индексы производительности схем.

Выводы.

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

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

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

3.2.1 Вычисление среднего времени выполнения задачи в безресурсных конфликтах» « Тб ».

3.2.2 Вычисление среднего времени выполнения задачи при наличии «ресурсных конфликтов» « тс ».

Выводы.

4. Имитационное моделирование схем восстановления с дополнительными модулями в мультипроцессорной среде.

4.1 Имитационное моделирование.

4.2 Сравнение результатов аналитического и имитационного моделирования.

4.2.1 Дисциплина Восстановления с откатом.

4.2.2 Дисциплина восстановления с ожиданием свободного дополнительного модуля.

4.3 Использование метода анализа для поиска оптимальных условий производительности схем в мультипроцессорной среде.

Выводы.

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

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

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

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

5.2 Исследование технических решений и технологий по созданию программного обеспечения и вычислительных средств Бортовая радиолокационная станция (БРЛС) маловысотного полёта (МВП) летательных аппаратов.

Выводы.

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

Актуальность проблемы. Расширение области применения вычислительных систем (ВС), особенно для управления реальными объектами, резко повысило требования не только к их быстродействию, но в большей степени, - к отказоустойчивости ВС.

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

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

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

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

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

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

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

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

На защиту выносятся следующие положения:

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

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

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

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

Внедрение результатов работы. Результаты диссертации были использованы при выполнении научно-исследовательской работы с предприятием ОАО «Корпорация «Фазотрон-НИИР» на тему «Исследование технических решений и технологий по созданию программного обеспечения и вычислительных средств БРЛС маловысотного полёта летательных аппаратов», что подтверждается соответствующим актом.

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

Второй Всероссийской научно-технической конференции, 10-15 сентября 2001 года, Восточно-Сибирский государственный технологический университет, г. Улан-Удэ;

6th International Conference on Development and Applications Systems, 23th - 25th May 2002, The Faculty of Electrical Engineering "Stefan eel Mare" University Suceava, ROMANIA IEEE Romanian Section;

1-ой Всероссийской Научно-технической Конференции по Проблемам Создания Перспективной Авионики. " Корпорация ФАЗОТРОН-НИИР" и Военный Авиационный Технический Университет. 12 апреля 2002, г. Москва, Россия;

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

Структура и объем работы. Диссертация состоит из введения, пяти глав, заключения и двух приложений. Общий объем работы 142 страницы, в том числе 52 рисунков и 6 таблиц. Список литературы включает 68 наименования.

выводы

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

2. Разработан проект отказоустойчивых бортовых вычислительных систем, работающих по «плюс—двухмодульной схеме» и предназначенных для спутников зондирования земли.

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

Заключение

1. Предложены два критерия оценки эффективности схем: критерий среднего времени выполнения задания и критерий времени выполнения задания при / откатах за время решения задачи.

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

3. Разработаны имитационные модели рассматриваемых схем восстановления.

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

5. Предложена методика исследования параметров для повышения эффективности схем восстановления с дополнительными модулями в мультипроцессор среде.

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

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

3. Бизяев Р.В., Герасимов Н.И., Круглов В.И., Чернышев A.B. Конструктивные, Функциональные Характеристики и Условия Эксплуатации Бортовых Систем Космических Летательных Аппаратов; МГАТУ. М; 1995. 82 с.

4. Борисов A.A., Горвачева В.М., Картачов Г.Д., Мартинова М.Н., Притков С.Ф. Надежност зарубежной элементой базы. Зарубежная радиоэлектроника. №5, 2000 ст. 34-53.

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

6. Брехов О.М., Саул Де Ля Росса. "Способ восстановления вычислительного процесса в дублированной системе на основе двух дополнительных модулей". Тез. докл. ТиПВСИТ 2001, Восточно-Сибирский государственный технологический университет, г. Улан-Удэ, 2001.

7. Виттих В.А., Цыбатов В.А. Оптимизация бортовых систем сбора и обработки данных. -М.: Наука, 1985.- 176 с.

8. Гнеденко Борис Владимирович. Курс теории вероятностей. 7-е изд., исправл. М.: Эдиториал УРСС, 2001.-320 с,

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

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

11. Каган Б.М., Мкртумян И.Б. Основы эксплуатации ЭВМ. М.: Энергоатомиздат, 1988. - 376 с.

12. Клейнрок Л. Вычислительные системы с очередями. Пер. с англ. М.: Мир, 1979. -600 с.

13. Коваленко К.А. К вопросу повышения надежности функционирования с использованием аппаратных средств // Автоматика и телемеханика, 1997, № 3, с. 1219.

14. Козлов Д.И., Аншаков Г.П., Мостовой Я.А., Соллогуб A.B. Управление Космическими Аппаратами Зондирования Земли.

15. Компьютерные Технологии. Москва, Машиностроение 1998

16. Крэйн М., Лемуан О. Введение в регенеративный метод анализа моделей. М.: Наука, 1982.- 104 с.

17. Лобанов A.B. Обнаружение и идентификация неисправностей в распределенных управляющих ВС с программно-управляемой сбое и отказоустойчивостью // Автоматика и телемеханика, 1998, № 1, с. 155-164.

18. Лобанов A.B. Распределенное мажорирование информации с обнаружением и идентификацией проявления неисправностей // Автоматика и телемеханика, 1997, № 1, с.145-149.

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

20. Матов B.N,. Белоусов Ю.А, Федосеев Е.П. Бортовые Цифровые Вычислительные Машины и Системы. Москва, Высшая школа 1988.

21. Матов В.И., Артамонов Г.Т., Брехов О.М., Голубков Ю.А., Иыуду К.А., Любатов Ю.В., Ткачев O.A., Чугаев Б.Н., Шаповалов Ю.В. Теория Проектирования Вычислительных Машин, Систем и Сетей. Москва, Исдателсво МАИ 1998, 458 с.

22. Николаев О.В. Оценка производительности схем восстановления вычислительного процесса с дополнительными свободными модулями. Диссертация на соискание ученой степени к.т.н. М.: МАИ, 1999.

23. Прилепская В.Г., Чуконов В.О. Методы анализа надежности вычислительных систем с комбинированным резервированием на основе древовидных структур // Приборы и системы управления, 1997, № 27, с.72-81

24. Принципы обеспечения отказоустойчивости микропроцессорных вычислительных систем // Сборник трудов М: Институт Проблем Управления РАН, 1987. - 247 с.

25. Турута E.H. Концепция и методы обеспечения отказоустойчивости параллельных вычислительных систем выполняющие фиксированные комплексы задач. М: Институт Проблем Управления РАН, 1996. - 453с.

26. Фатхи В.А. Методика оптимального распределения заданий в отказоустойчивой многопроцессорной вычислительной системе // Автоматика и телемеханика, 1998, № 1, с. 30-40.

27. Харченко B.C., Лысенко И.В., Мельников В.А. Оценка и обеспечение живучести информационно-вычислительных и управляющих систем технических комплексов критического использования // Заруб, эл-ка. 1996. №1, с. 64 80.

28. Шрайбер Т. Моделирование на GPSS. М.: Машиностроение, 1980. - 593 с.

29. Яценко Д.Ю. Методы анализа функциональных и эксплуатационных характеристик однородных отказоустойчивых вычислительных систем. Диссертация на соискание ученой степени к.т.н. М.: МАИ, 1999.

30. Agraval P. Fault tolerance in multiprocessor systems without dedicated redundancy // IEEE Trans. On Computers, 1988, no. 3, pp.358-362.

31. Arlat J., Laprie J. Dependability modeling and evaluation of software fault-tolerant systems // IEEE Trans. On Computers, 1990, no. 4, pp.504-512.

32. Avizienis A. Laprie J. Depandable Computing From Concepts to Design Diversity, Proceedings of IEEE, 1986, no. 5, pp. 629-638.

33. Avizienis A. Toward systematic design of fault-tolerant systems // Computer, 1997, no. 4, pp.51-58.

34. Avizienis A., Kopetz H., Laprie J. The evolution of fault-tolerant computing. NY: Springer-Verlag, 1987.

35. Brekhov O., Kilichev G., An influence of methods of computing system tolerance support on system performance. The third Int. Conf. D&AS, Suceava, Romania, 1996.

36. Brekhov O., Dolgov A., Golubkov Y., Sobko S., An Adaptive Fault-tolerant Information Computing Environment for the Execution of Onboard Tasks. Conception and Realization of Operating System. 9-th CEAS Simposium on simulation technology, Holland, 1995.

37. Brekhov O.M., Maksimov A.N., Nikolaev O.V., Sobko S.L., Sokolov A.P., An approach to develop a control adaptive fault-tolerant information computing environment // Proceedings of the 1997 MAI/BAU, Sept. 1997, Moscow, Russia

38. Brekhov O.M., De La Rosa Nieves Saul. "Performance analysis of Checkpoints schemes in a Multiprocessors environment" // Proceedings of DAS 2002 International Conference, Suceava, Romania, 2002.

39. Bruno J. Optimal fault-tolerant computing on multiprocessor systems // Acta inf., 1997, no. 12, pp.881-904.

40. Carrasco Juan A. Computationally Efficient and Numerically Stable Reliability Bounds for Repairable Fault-Tolerant Systems // IEEE Transactions on Computers. Vol.51 No.3, pp 254-268, March 2002.

41. Coswami K., Iyer R., Young L. DEPEND: A simulation-based environment for system level dependability analysis // IEEE Trans. On Computers, 1997, no. 1, pp.60-74.

42. Cristian F., Dancey R., Dehn J. Fault-Tolerance in the advanced automation systems // Proc. 26-th Annual International Sympozium Fault-Tolerant Computing Los Alamitos: IEEE CS Press, 1996, pp.6-17.

43. Geist R., Trivedi K. Reliability estimation of fault-tolerant systems: tools and techniques // Computer, 1997, no. 6, pp. 59-67.

44. Howard J.W Jr, Hardage D.M. Spacecraft Enviroments Interactions: Sapece Radiation and Its Effects on Electronics Systems. National Aeronautics and Space Administration (NASA). Marshall Space Flight Center. July 1999. pp. 24.

45. Hyunki Kim, Hyung-Joon Jeon, Keyseo Lee and Hyuntae Lee. The Design of All Voting Triple Modular Redundancy System. Proceedings Annual Reliability and Maintainability Symposium. IEEE, 2002, pp. 439-444.

46. Kartik S., Murthy C. Task allocation algorithms for maximizing reliability of distributed computing systems // IEEE Trans. On Computers, 1997, no. 6, pp.719-724.

47. Kim J. Replicated process alocation for load distribution in fault-tolerant multicomputers // IEEE Trans. On Computers, 1997, no. 4, pp.499-512.

48. Kortik G. Task allocation algorithms for maximizing reliability of distributed computing systems// IEEE Trans. On Computers, 1997, no. 6, pp.714-724.

49. Ku H. Connective fault-tolerance in multiple bus systems // IEEE Trans. On Parallel and Distributed Systems, 1997, no. 8, pp. 1417-1429.

50. Johnson B. Design and analysis of fault-tolerant digital systems MA: Addison-Wesley, 1989.

51. Laprie J., Arlat J., Beounes C. Definition and analysis of hardware and software-fault-tolerant arhitecture // Computer, 1990, no. 6, pp.39-50.

52. Loman James, Wang Wendai. On Reliability Modeling and Analysis of Highly-Reliable Large Systems. Proceedings Annual Reliability and Maintainability Symposium. IEEE, 2002, pp. 456-459.

53. Lin T., Shin K. Damage assessment for optimal rollback recovery// IEEE Trans. On Computers, 1998, no. 5, pp.603-614.

54. Nikolas D. Optimal self-testing embedded parit checkers // IEEE Trans. On Computers, 1998, no. 3, pp.313-322.

55. Pelc A., Diks K. Globally optimal diagnosis in systems with random faults // IEEE Trans. On Computers, 1997, no. 2, pp.200-204.

56. Pierce W. Failure-Tolerant computer design. NY: Academic Press, 1985.

57. Pradhan D., Vaidya N. Roll-forward and rollback recovery: performance-reliability trade-off // IEEE Trans. On Computers, 1997, no. 3, pp. 372-378.

58. Pradhan D., Vaidya N. Roll-forward checkpointing scheme: a novell fault-tolerant architecture // IEEE Trans. On Computers, 1994, no. 10, pp. 1164-1173.

59. Siewiorek D., Swarz R. The theory and practice of reliable system design. Digital Press,1982.

60. Somani A., Vaidya N. Understanding fault tolerance and reliability // Computer, 1997, no. 4, pp. 45-50.

61. Subhasish Mitra, Nirmal R. Saxena, and Edward J. MacCkuskey. A Design Diversity Metric and Analysis of Redundant Systems. IEEE Transactions on Computers. Vol.51 No.5, pp 498-510, May 2002

62. Wang F., Ramamritham K. Determing redundancy levels for fault-tolerant real-time systems // IEEE Trans. On Computers, 1995, no. 2, pp. 292-301.

63. Wattanapongsakorn Neruemon, Levitan Steven. Readability Optimization Models for Fault-Tolerant Distributed Systems. . Proceedings Annual Reliability and Maintainability Symposium. IEEE, 2001, pp. 193-199.

64. Xu J., Rendell B. Software fault-tolerance: t/(n-l) variant programming // IEEE Trans. On Reliability, 1997, no.l, pp. 60-68.

65. Ziv A., Bruck J. Analysis of checkpointing schemes with task duplication // IEEE Trans. On Computers, 1998, no. 2, pp. 222-227.

66. Ziv A., Bruck J. Performance optimization of checkpointing schemes with task duplication // IEEE Trans. On Computers, 1997, no. 12, pp. 1381-1386.