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

ВВЕДЕНИЕ.".

1. ОБЕСПЕЧЕНИЕ ОТКАЗОУСТОЙЧИВОГО ФУНКЦИОНИРОВАНИЯ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ.

1.1. Требования к работе бортовой вычислительной системы.

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

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

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

Схема с повторным счетом.

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

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

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

1.6. Сравнение схем.

1.7. Производительность вычислительных систем с резервированием.

1.8. Постановка задачи.

Выводы.

2. ОЦЕНКА ПРОИЗВОДИТЕЛЬНОСТИ СХЕМ ВОССТАНОВЛЕНИЯ С ДОПОЛНИТЕЛЬНЫМИ СВОБОДНЫМИ МОДУЛЯМИ.

2.1. Метод исследования схем восстановления с дополнительными модулями.

2.2. Определение средней длительности интервалов.

ВМКР-схема.

СБ-схема.

2.3. ОММ^-схема с равновероятным обслуживанием.

Граф переходов системы.

Определение вероятностей переходов.

Определен ие свойств переходов.

Анализ схемы.

2.4. КРСБ-схема с равновероятным обслуживанием.

Граф переходов системы.

Определение вероятностей переходов.

Определение свойств переходов.

Анализ схемы.

2.5. Производительность ЭММ7- и М^-схем при равновероятном обслуживании.

2.6. БЫШ^-схема с приоритетным обслуживанием.

Граф переходов и вероятности переходов системы.

Определение свойств переходов.

Анал из схемы.

2.7. ^СБ-схема с приоритетным обслуживанием.

Граф переходов и вероятности переходов системы.

Определение свойств переходов.

Анализ схемы.

2.8. Граничные оценки среднего времени выполнения задачи при приоритетном обслуживании.

2.9. Производительность БМКР- и Ш?С8-схем при приоритетном обслуживании.

Выводы.

3. ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ СХЕМ ВОССТАНОВЛЕНИЯ С

ДОПОЛНИТЕЛЬНЫМИ СВОБОДНЫМИ МОДУЛЯМИ.

3.1. Программы моделирования схем восстановления с дополнительными свободными модулями.

3.2. Производительность схем.

Выводы.

4. ОПЕРАЦИОННАЯ СИСТЕМА БОРТОВОЙ ИНФОРМАЦИОННО

ВЫЧИСЛИТЕЛЬНОЙ СРЕДЫ.

4.1. Общее описание проекта.

Состав макета ИБС.

4.2. Описание операционной системы.

Функции операционной системы.

Принципы построения ОС.

Функция обеспечения отказоустойчивости системы.

Функции модулей ОС узла.

Выводы.

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

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

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

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

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

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

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

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

В соответствии с поставленной целью исследования проводились по следующим основным направлениям:

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

- сравнительный анализ существующих схем восстановления вычислительного процесса;

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

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

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

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

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

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

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

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

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

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

Всероссийская научно-техническая конференция "Вычислительные системы бортового базирования", Москва, 1995. ---------------—--------

Российско-китайский семинар "Proceedings of MAI/BU А", Москва, 1997.

Научные семинары каф.304 "Вычислительные машины, системы и сети", МАИ, Москва, 1996-1997.

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

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

Выводы

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

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

3. Разработка и испытание ОС подтвердили возможность использования схем восстановления вычислительного процесса с дополнительными свободными модулями при их совместном использовании в вычислительных системах бортового базирования.

Заключение

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

В ходе выполнения работы были получены следующие основные теоретические и практические результаты:

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

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

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

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

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

103 i

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

18. Фролов A.B., Фролов Г.В. Программирование для Windows NT. М.: ДИАЛОГ-МИФИ, 1996. - 272 с.

19. Хаманн Ф. Отказоустойчивая операционная система Tandem Non-Stop Kernel // Open Systems Journal, 1997, № 3, c.32-36.

20. Харп Г. Транспьютеры. Архитектура и программное обеспечение. М.: Радио и связь, 1993. - 304с.

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

22. Шнитман В. Отказоустойчивые компьютеры компании Stratus // Open Systems Journal, 1998, № 1, с. 12-22.

23. Шнитман В. Отказоустойчивые серверы ServerNet // Open Systems Journal, 1996, № 36 c.5-11.

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

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

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

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

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

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

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

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

32. O. Brekhov, A. Dolgov, Y. Golubkov, S. Sobko, 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.

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

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

35. 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.

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

37. Guerraoui R. Software-based replication for fault-tolerance // Computer, 1997, no. 4, pp.68-34.

38. Internet WWW Homepage of Stratus Computer Inc.: http://www.stratus.com, February, 1999. ----------- --------- ^

39. Internet WWW Homepage of Tandem Computer Inc. http://www.compaq.com/tandem, February, 1999.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

58. OS-9000. Technical Manual. Microware Systems Corporation, 1996.

59. Parallel Processing With the TMS320C4x. Application Guide. -Texas Instruments Inc., 1994.-p.316.

60. QNX Operating System. System Architecture. QNX Software Systems Ltd, 1996. -p. 142.

61. Transputer Databook. INMOS Ltd, 1989. - p 584.

62. VxWorks. Programmer's Guide. Wind River Systems Inc., 1997. - p.648.

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