Содержание к диссертации
Введение
1 Обзор средств и методов отладки распределенных систем 9
1.1 Постановка задачи и основные понятия 9
1.2 Средства и методы отладки 11
1.2.1 Детерминированное воспроизведение и интерактивная отладка распределенных программ 11
1.2.2 Мониторинг 18
1.2.3 Средства самоконтроля программ 25
1.2.4 Средства и методы, ориентированные на отладку сложных систем 27
1.2.5 Отладка в жизненном цикле программы. Интегрированное использование средств отладки, тестирования, контроля выполнения 29
1.3 Вопросы архитектуры и реализации средств отладки 30
1.3.1 Архитектура средств отладки 30
1.3.2 Функциональность агентов и псевдо-агентов отладки . 31
1.3.3 Взаимодействие менеджера и агента 32
1.3.4 Аппаратная поддержка отладки 33
1.3.5 Стратегии передачи данных трассировки 34
1.3.6 Настраиваемость и масштабируемость 34
1.4 Выводы 3G
2 Контролируемое выполнение, ассоциированные понятия и требования 38
2.1 Контролируемое выполнение и ассоциированные понятия . 38
2.2 Роль контролируемого выполнения и его составляющих . 40
2.3 Требования к средствам контролируемого выполнения и их реализации 44
2.4 Интеграция средств отладки и управления 45
2.5 Выводы 47
3 Организация инструментального комплекса "СОМ" 49
3.1 Пример применения комплекса 49
3.2 Организация инструментального комплекса 52
3.2.1 Архитектура 52
3.2.2 Взаимодействие со средами выполнения 55
3.3 Функциональные возможности комплекса и вопросы реализации 59
3.3.1 Инициализация системы 59
3.3.2 Интерактивная отладка 62
3.3.3 События 64
3.3.4 Контроль целостности и отказоустойчивость комплекса. Многопользовательская работа 73
3.4 Выводы 74
4 Средства внешнего и внутреннего контроля программ 76
4.1 Библиотека средств самоконтроля 77
4.2 Связь инструментального комплекса "СОМ" с системой управления OpenNMS 87
4.3 Выводы 89
5 Средства детерминированного воспроизведения распреде ленных программ 91
5.1 Постановка задачи 91
5.2 Реализация системы воспроизведения 92
5.2.1 Архитектурные и технические решения 92
5.2.2 События и векторное время в распределенном приложении 93
5.2.3 Первичное выполнение и воспроизведение распределен ного приложения 95
5.3 Обоснование алгоритма воспроизведения распределенного приложения 103
6 Реализация контролируемого выполнения с помощью комплекса "СОМ" 106
6.1 Классификация программных ошибок и функциональные возможности комплекса "СОМ" 106
6.1.1 Логические ошибки и ошибки кодирования 107
6.1.2 Утечка ресурсов и ошибки работы с памятью 107
6.1.3 Ошибки указателей 108
6.1.4 Ошибки синхронизации 108
6.1.5 Ошибки в распределенных приложениях 108
6.1.6 Ошибки систем реального времени 109
6.2 Анализ средств мониторинга 109
6.3 Пример отладки распределенной программы для ППС 117
6.3.1 Постановка задачи 117
6.3.2 Первая ошибка 120
6.3.3 Вторая ошибка 124
6.4 Пример отладки распределенной программы для ос2000 . 127
6.4.1 Постановка задачи 127
6.4.2 Ошибка 128
6.5 Анализ опыта применения комплекса "СОМ" 130
Заключение 132
Литература
- Детерминированное воспроизведение и интерактивная отладка распределенных программ
- Требования к средствам контролируемого выполнения и их реализации
- Связь инструментального комплекса "СОМ" с системой управления OpenNMS
- Первичное выполнение и воспроизведение распределен ного приложения
Введение к работе
Актуальность темы. Специализированные распределенные программно-аппаратные комплексы, предназначенные для решения ответственных задач, таких как обработка радиолокационных сигналов в реальном времени, в общем случае строятся из множества разнородных компонентов.
В качестве основных характеристик рассматриваемых комплексов можно выделить: разнородность, наличие узлов, работающих в реальном масштабе времени; часто меняющуюся конфигурацию; внешнюю изолированность и удаленность от разработчика в режиме функционирования.
Ввиду важности решаемых комплексами задач большое значение приобретает качество их функционирования, однако сложность комплексов делает решение этой задачи проблематичным. В частности, перед разработчиками и пользователями комплексов возникают следующие проблемы: ошибочная ситуация сложно воспроизводится; традиционные отладочные средства могут вносить дополнительные ошибки; отсутствуют средства описания архитектуры программно-аппаратных комплексов; комплексы функционируют в потенциально недружественной среде, в которой возможно возникновение программных и аппаратных ошибок, сбоев, а также внешних и внутренних атак (например, в результате тех же сбоев).
Таким образом, в исключительно важной области разработки и сопровождения распределенных разнородных программно-аппаратных комплексов в настоящее время имеется ряд нерешенных проблем, требующих как выработки новых концептуальных подходов, так и разработки соответствующих инструментальных средств.
Цели диссертационной работы. Основной целью диссертационной работы является разработка методов и программных средств организации процесса функционирования распределенных разнородных программно-аппаратных комплексов, направленных на обеспечение выполнения этими комплексами своих задач.
Для достижения поставленной цели требуется решить следующие задачи: разработать средства, позволяющие контролировать поведение комплекса не только на стадии разработки, но и в процессе эксплуатации; разработать методы, интегрирующие средства отладки и управления программно-аппаратными комплексами, позволяющие оперативно корректировать работу комплексов при возникновении нештатных ситуаций.
Научная новизна. Предложена концепция контролируемого выполнения - специально организованного процесса функционирования программно-аппаратных комплексов, целью которого является выполнение комплексами своих задач, несмотря на возможное проявление ошибок, атаки и отказы. Основными положениями данной концепции являются: интеграция средств информационной безопасности, отладки и управления; распространение контролируемого выполнения на все этапы жизненного цикла программно-аппаратных комплексов; целостность набора средств контролируемого выполнения, различающихся по степени воздействия на целевые комплексы, возможность взаимодействия между этими средствами.
Практическая ценность. Реализован инструментальный комплекс "СОМ" (Система Отладки/Мониторинга) для отечественных ЭВМ серии Багет на базе микропроцессоров с архитектурой х86 и 1В578, а также для Программируемого Процессора Сигналов - многопроцессорной ЭВМ на базе цифрового процессора обработки сигналов 1В577. Инструментальный комплекс применяется при отладке и сопровождении программ, созданных для отечественной операционной системы реального времени ос2000, работающей на перечисленных выше аппаратных платформах.
Апробация. Основные положения диссертационной работы докладывались на международной конференции "Параллельные вычисления и задачи управления", Москва, ИПУ РАН 2001, на семинаре "Современные сетевые технологии", МГУ, 2002, на научно-исследовательских семинарах в институте системного программирования РАН и НИИ системных исследований РАН.
Публикации. По теме диссертации опубликовано 10 печатных работ: [16], [8], [17], [18], [6], [9], [10], [5], [4], [7], из них 7 в соавторстве.
Объем и структура работы. Диссертация состоит из введения, 6 глав, заключения, списка литературы и 2 приложений.
Первая глава представляет собой обзор имеющихся средств и методов отладки распределенных разнородных программно-аппаратных комплексов. Подробно рассматриваются различные средства воспроизведения выполнения, интерактивной отладки, мониторинга и самоконтроля программ.
Во второй главе вводится концепция контролируемого выполнения и приводится обоснование необходимости ее применения при отладке распределенных комплексов с разнородными компонентами. Анализируются следствия этой концепции, изменения в модели жизненного цикла программных систем. Формулируются требования, которым должен удовлетворять инструментальный комплекс, реализующий концепцию контролируемого выполнения.
В третьей главе подробно рассматривается реализация инструментального комплекса для разнородных распределенных программно-аппаратных комплексов. Приводится описание архитектурных и технологических решений, которые позволили объединить средства воспроизведения выполнения, интерактивной отладки, мониторинга и самоконтроля в единый программный комплекс, а также обеспечить простоту его настройки на новые целевые архитектуры.
Четвертая глава посвящена описанию средств внутреннего и внешнего контроля программ. В частности, рассматриваются средства внутреннего (или самоконтроля) программ, которые могут применяться в совокупности с другими элементами инструментального комплекса или как самостоятельное средство контролируемого выполнения. Также описывается взаимодействие инструментального комплекса с системой управления OpenNMS.
В пятой главе описывается средство воспроизведения выполнения распределенного приложения, взаимодействие между узлами которого происходит путем обмена сообщениями. Приводится описание алгоритма воспроизведения и доказательство его корректности.
В шестой главе рассматривается практика применения инструментального комплекса "СОМ". Приводятся различные примеры, и формулируется методология применения инструментального комплекса.
В заключении излагаются основные результаты диссертационной работы.
Список литературы насчитывает 143 названия.
В приложении А приведены фрагменты файлов настройки инструментального комплекса "СОМ" на языке XML.
Приложение Б содержит UML-диаграммы различных компонентов инструментального комплекса "СОМ".
Детерминированное воспроизведение и интерактивная отладка распределенных программ
Существующие в настоящее время промышленные стандарты [ПС], [41] фиксируют требования к функциональности, интерфейсу и другим свойствам интерактивных отладочных средств.
В первой версии стандарта отладки высокопроизводительных систем (High Perfomance Debugging Standard - HPDS, [HG]) сформулированы базовые требования к функциональности и интерфейсу интерактивных отладчиков, предназначенных для отладки последовательных и многопоточных программ, а также программ, состоящих из множества процессов (выполняющихся, возможно, в распределенной среде). В разработке стандарта принимали участие известные фирмы - производители программного обеспечения и аппаратуры: IBM, Sun Microsystems, Hewlett-Packard, Cygnus Solutions. Рамки данного стандарта охватывают возможности, реализованные в настоящее время в ряде промышленных отладчиков.
Цель спецификаций HPDS - выделить набор отладочных действий и определить поведение интерактивного отладчика таким образом, чтобы предоставить пользователю полноценные средства отладки, унифицировать систему команд и пользовательский интерфейс отладчика. Стандарт определяет такие понятия как допустимые состояния потока управления, механизм группирования потоков управления и процессов, пошаговое выполнение, точки действия (точки прерывания, точки слежения и барьеры), модели останова потоков.
Требования HPDS реализованы в большинстве промышленных отладчиков (TotalView [55], Cdbx [50], codeview [133], CXdb [49], HP/DDE [73], ipd [83], Ladebug [54], MPPE [106], ndb [117], P2D2 [75], pdbx [81], Prism [147]), многие из которых поддерживают и дополнительные возможности. Например, в [15] предложен интеллектуальный подход к реализации пошагового выполнения.
Дополнительные требования по функциональности отладочных средств для многопроцессорных систем изложены в так называемой программе ускоренной стратегической компьютерной инициативы (ASCI - Accelerated Strategic Computing Initiative) [41]. Подробный обзор обоих стандартов можно найти в [17], [8].
Стандарты интерактивной отладки, хотя и отражают до некоторой степени потребности отладки распределенных приложений, не охватывает всех связанных с ней проблем, в частности, в них не представлена в полном объеме задача распространения парадигмы традиционной интерактивной отладки на случай распределенного приложения. Решение данной задачи подразумевает наличие средств детерминированного воспроизведения ([114]) и согласованного останова компонентов распределенной программы ([40], [128]). Далее в этом разделе представлен краткий обзор существующих подходов к решению данных проблем.
Первичное выполнение и детерминированное воспроизведение
Детерминированное воспроизведение - это механизм, позволяющий воспроизводить выполнение распределенных, параллельных и других видов программ с внутренне недетерминированным характером выполнения с целью отладки. Механизм включает фазу первичного выполнения, во время которого производится запись информации о событиях, определяющих поведение программы в недетерминированных ситуациях, и собственно фазу воспроизведения, когда выполнение программы происходит под управлением записанной ранее информации (см. обзоры [51], [120] и др.).
Мы остановимся на вопросах воспроизведения распределенных программ, взаимодействующих при помощи обмена сообщениями, оставив за рамками рассмотрения специфические проблемы, связанные с отладкой параллельных программ, где процессы или потоки управления могут взаимодействовать через разделяемую память. Основной источник недетерминированности в распределенных программах - операции приема сообщений, которые могут доставляться в различном порядке.
Информация, записываемая при первичном выполнении, соответствует некоторому уровню абстракции; при воспроизведении обеспечивается детерминированность выполнения на том же уровне, в то время как выполнение на
более низких уровнях абстракции может оставаться недетерминированным. Например, (см. [112]) воспроизведение может быть детерминированным на уровне обмена сообщениями между узлами распределенной программы, но оставаться недетерминированным на уровне количества неудачных попыток приема без ожидания. Чем детальнее уровень абстракции, на котором ведется трассировка событий при первичном выполнении, тем точнее ее воспроизведение и тем выше накладные расходы трассировки.
Воспроизведение подразумевает наличие некоторой упорядоченности событий, записанных при первичном выполнении. В [52] дается анализ различных подходов, используемых для получения информации об упорядоченности событий в распределенной среде. Рассмотрены механизмы, основанные на применении часов реального времени (локальных и глобальных, реализованных в виде множества локальных часов, синхронизированных с известной точностью) и так называемых логических часов. Глобальные часы могут быть необходимы для отладки систем реального времени, поскольку они дают информацию о физических интервалах времени между различными событиями (см. например, [80]) однако их реализация не всегда возможна; к тому же (см. [52], [13]) часы реального времени не дают достоверной информации о взаимной обусловленности событий в распределенной системе. Поэтому в большинстве систем воспроизведения используется логическое время.
Системы логического времени
Система логического времени - это набор правил, связывающий с каждым событием е некоторое значение С(е), называемое временной меткой события, и позволяющий делать заключения о взаимной обусловленности или необусловленности событий на основе их временных меток.
Отношение обусловленности на множестве событий в распределенном приложении, где узлы взаимодействуют посредством обмена сообщениями, определяется как транзитивное замыкание отношения непосредственной обусловленности, содержащего все пары событий {а, Ь}, такие что либо а и Ь принадлежат одному процессу и Ь произошло непосредственно вслед за а, либо а является событием отсылки сообщения, а Ь - событием приема этого сообщения [13].
Отношение обусловленности задает частичную упорядоченность на множестве событий, которая должна быть соблюдена при воспроизведении. События, не связанные этим отношением, считаются независимыми (concurrent) и при воспроизведении их порядок несуществен. (clock condition): е\ - e-i = С(еі) С(ег), где через е\ - e% обозначено отношение обусловленности, или причинной зависимости (см. например, [112]).
Простейшие скалярные часы (часы Лампорта, см. [101], [102]) с каждым событием соотносят скалярную временную отметку.
Система часов Лампорта является состоятельной в широком смысле: Єї — 2 =Ф- С(еі) С(ег), однако эти часы вводят избыточные зависимости между событиями - соотношение С(е\) С(ег) может иметь место для событий, не связанных отношением следования. Это может препятствовать эффективной отладке (см., например, [53]). Поэтому на практике чаще используют векторные или матричные часы которые предоставляют информацию о текущем времени на каждом узле распределенной системы и не вносят избыточной упорядоченности событий, т.е. удовлетворяют условию состоятельности в строгом смысле: е\ — е2 & С(еі) С(е2). Различные типы и модификации логических часов рассматриваются в [129], [97], [98].
Требования к средствам контролируемого выполнения и их реализации
В этом разделе формулируются требования, предъявляемые к средствам контролируемого выполнения распределенных разнородных программно-аппаратных комплексов. Требования к функциональности Следование стандартам.
Должны поддерживаться все возможности отладки и мониторинга, предусмотренные стандартами HPDS и POSIX. Гибкость воздействия на отлаживаемую систему. Средства контролируемого выполнения должны обеспечивать различные уровни воздействия на целевой комплекс от минимального (использование аппаратных средств) до максимального (программная интерактивная отладка). Технологические требования
Расширяемость.
Архитектура комплекса контролируемого выполнения должна допускать естественные способы наращивания функциональности. Настраиваемостъ и масштабируемость.
Средства контролируемого выполнения должны содержать механизмы настройки на новые аппаратно-программные платформы. Средства контролируемого выполнения должны поддерживать любое изменение числа узлов целевого комплекса. Отказоустойчивость.
Выход из строя нескольких узлов целевого комплекса не должен приводить к сбоям в работе средств контролируемого выполнения. Требования к интерфейсу
Развитый, настраиваемый графический интерфейс. Целевой комплекс может содержать большое число разнородных объектов, которые должны быть представлены пользователю в легко обозримой, удобной для восприятия форме. С этой точки зрения важны такие средства, как поддержка различных уровней детализации в представлении информации о системе, структурированность представления, удобный интерфейс для выполнения действий над объектами. Полноценный командный язык задания сценариев отладки.
Основой выполнения перечисленных выше технологических требований может служить интеграция средств отладки и управления в рамках единой среды контролируемого выполнения.
Подобная интеграция предусматривает следование единому набору стандартов и общность архитектурных подходов.
Программные продукты, предназначенные для управления информационными системами, развиваются несколько десятилетий, и основные стандарты и архитектурные подходы в этой области можно считать устоявшимися.
Для средств управления разработано и разрабатывается большое число стандартов и рекомендаций (в рамках сообществ IETF, DMTF, OMG, отдельными компаниями, такими, как Tivoli Systems и т.п.), которым целесообразно следовать при реализации средств интерактивной отладки и мониторинга. Здесь имеются в виду спецификации SNMP [44, 45, 107, 108], регламентирующие взаимодействие между менеджерами и агентами, организацию базы управляющей информации (МІВ) и создание расширяемых агентов для целевых систем со сложной структурой.
Следование стандартам на средства управления при разработке средств контролируемого выполнения распределенных разнородных программно-аппаратных комплексов представляется целесообразным по нескольким при чинам. Во-первых, оно позволяет интегрировать средства отладки и управления, осуществлять контролируемое выполнение с различным уровнем детализации. Во-вторых, оно дает возможность использовать имеющиеся наработки - архитектурные, протокольные и программные.
Архитектурная интеграция подразумевает консолидацию вокруг многоуровневой архитектуры, включающей консоль оператора, менеджеры и агенты (см. рис. 2.1). Важным элементом архитектуры является база данных с информацией об управляемых объектах (целевых системах).
На рис. 2.2 ( [12, 118]) представлена архитектура менеджер/агент в системе распределенного управления. Целесообразно следовать такой схеме и при проектировании средств отладки распределенных систем.
Идея расширяемого агента состоит в том, чтобы менеджер был избавлен от учета сложной внутренней структуры управляемого объекта и от общения с агентами по нестандартным протоколам. Примером такого объекта может служить многопроцессорная система с закрытой архитектурой. Расширяемый агент состоит из главного и подчиненных агентов. Главный агент является промежуточным звеном между менеджером и агентом на конкретной целевой платформе (подчиненным агентом).
Целесообразно применить эту идею и при построении средств контролируемого выполнения (см. рис. 2.3). Главный агент может располагаться на фронтальной машине или выделенном процессоре многопроцессорной системы, то есть там, где для его функционирования имеется достаточный набор ресурсов.
Понятие контролируемого выполнения является обобщением традиционного управления информационными системами и отладки их программных компонентов. В контексте настоящей работы важны такие требования к средствам контролируемого выполнения, как наличие широкого спектра механизмов отладки, среди которых ключевая роль отводится средствам самоконтроля программ.
Среди других требований к средствам контролируемого выполнения выделим минимальность вносимых ими возмущений, что облегчает отладку и, в принципе, дает возможность их использования на этапе эксплуатации систем.
Базой для выполнения технологических требований к средствам контролируемого выполнения служит использование стандартов и архитектурных подходов, разработанных для средств управления, интеграция средств отладки и управления.
Для выполнения перечисленных выше требований необходимо создать единый комплекс, включающий, наряду со средствами интерактивной отладки, средства мониторинга и самоконтроля программ.
Связь инструментального комплекса "СОМ" с системой управления OpenNMS
Если какие-либо компоненты распределенной программы перестают работать (аварийно завершаются, или останавливаются под действием актуа-тора), порождается событие, отображаемое в главном окне системы управления. При этом появляется возможность отладки узла, на котором произошел сбой (рис. 4.2).
Служба отладки запускает инструментальный комплекс "СОМ", который автоматически присоединится к узлам, требующим его вмешательства. Теперь можно проводить необходимые отладочные действия, включающие интерактивную отладку, мониторинг событий и пр.
Интеграция средств отладки и управления позволяет осуществлять контроль за состоянием целевой системы, при необходимости переходя к активным отладочным действиям. Rwcan &ІШіа Update SNMP
Представленные в данной главе средства, благодаря слабо интрузивному характеру и возможности автономного применения, могут использоваться не только в целях отладки, но и как средства контроля выполнения приложений в эксплуатационном режиме. Средства самоконтроля позволяют проверять и поддерживать корректное функционирование отдельных компонентов приложения, а система сетевого управления обеспечивает контроль и поддержку целостности распределенного приложения как совокупности компонентов (например, обеспечивая перезапуск компонента, в котором произошел сбой).
Библиотека средств самоконтроля использует механизм трассировки, описанный в стандарте POSIX ( [82]), благодаря чему может быть использована при отладке многих posix-совместимых приложений. Оказывая в целом незначительное влияние (см. таблицу 4.1) на работу системы, БСС является эффективным инструментом при отладке приложений реального времени, а также приложений со сложной внутренней структурой.
Преимущество БСС по сравнению с аналогичными средствами состоит в том, что она может использоваться совместно с инструментальным комплексом "СОМ". Например, можно использовать компонент контроля выполнения из состава "СОМ" для задания схемы, по которой при возникновении пользовательского события будет автоматически запускаться компонент интерактивной отладки для детального исследования программы.
Архитектура инструментального комплекса, основанная на использовании открытых интерфейсов, позволила естественным образом реализовать его интеграцию с системой сетевого управления для обеспечения контроля целостности распределенных приложений. Указанная интеграция может быть реализована не только как вызов всего комплекса "СОМ" в случае возникновения нештатной ситуации, но и на уровне отдельных компонентов комплекса; в частности, возможно отображение событий целевых узлов в системе управления, а также управление средствами самоконтроля непосредственно из системы управления.
Недетерминированный характер выполнения распределенных приложений представляет серьезную проблему при их отладке. Парадигма традиционной "циклической"отладки оказывается не применимой, так как приложение может выполняться всякий раз по-разному, даже без вмешательства со стороны средств отладки, что затрудняет воспроизведение ошибки. Для решения данной проблемы обычно применяют средства детерминированного воспроизведения, краткий обзор которых представлен в главе 1.
В рамках инструментального комплекса "СОМ" реализованы средства детерминированного воспроизведения распределенных программ для архитектур без общей памяти. В существующей реализации предполагается, что процессы взаимодействуют путем обмена сообщениями при помощи UDP-сокетов, однако данный подход может быть обобщен для широкого класса приложений, взаимодействующих посредством обмена сообщениями.
Первичное выполнение и воспроизведение распределен ного приложения
Архитектурные и технические решения, использованные в реализации системы воспроизведения, выбирались с учетом требований минимизации воздействия на отлаживаемые приложения и масштабируемости среды воспроизведения.
В контексте системы воспроизведения различают первичное выполнение приложения и его воспроизведение. При первичном выполнении записывается последовательность событий, произошедших в каждом из процессов; при воспроизведении записанного ранее первичного выполнения обеспечивается повторение тех же последовательностей событий в каждом процессе.
Как при первичном выполнении, так и при воспроизведении воздействие на отлаживаемое приложение должно быть минимальным. Исходя из этого требования выбран метод воспроизведения по синхронизации событий (см. раздел 1.2.1) с использованием векторного логического времени как описано в следующем разделе. В отличие от воспроизведения по данным, этот подход не требует записи в трассу событий содержимого пересылаемых сообщений, что существенно сокращает накладные расходы.
Требование масштабируемости означает, что производительность при воспроизведении не должна деградировать с ростом числа узлов в отлаживаемом приложении. Из этого следует, в частности, что для управления воспроизведением не должен использоваться какой-либо выделенный узел. В представленной реализации контроль упорядоченности сообщений, получаемых каждым узлом, осуществляется распределен-но, что исключает появление "узких мест "при воспроизведении.
Для отладки с применением воспроизведения пользователь должен выполнить инструментовку своего приложения, добавив в каждый модуль вызов функции, которая инициализирует среду воспроизведения, и заменив вызовы стандартных функций отправки и получения сообщений на вызовы соответствующих функций среды воспроизведения.
Пусть S - распределенное приложение, состоящее из N процессов Pi,...,PN.
Система воспроизведения основана на механизме регистрации и контроля событий, происходящих в процессах распределенного приложения. Поддерживаются события отправки и получения сообщений. В системе воспроизведения с каждым событием е связывается логическое векторное время Т(е), которое определяется (см. [101, 102, 13]) следующим образом. Множество значений векторного времени совпадает с множеством iV-мерных векторов с целыми неотрицательными компонентами, где N - количество процессов в распределенном приложении. В качестве начального значения векторного времени для всех процессов устанавливается вектор с нулевыми компонентами.
Обозначим через ТІ текущее значение векторного времени процесса Р При наступлении события е в этом процессе ТІ изменяется следующим обра зом.
Для любого типа события сначала ТІ[І] увеличивается на единицу. Если е - событие отправки сообщения, полученное значение ТІ присоединяется к телу отправляемого сообщения в качестве временного маркера. Далее, если е -событие успешного получения сообщения, то каждой компоненте Т([к] присваивается значение max(Ti[k],T [k]), где Т" - временнбй маркер полученного сообщения, k = 1,...,N. Вычисленное таким образом значение векторного времени сопоставляется с событием е или, как говорят, является временнбй меткой события е.
Из определения системы логического векторного времени следует свойство ее монотонности или состоятельности в широком смысле: е- е =ї Т(е) Т(е ) где — - отношение обусловленности на множестве событий 1 (см раздел 1.2.1).
Для векторного времени верно также свойство состоятельности в строгом смысле: е — е -О- Т(е) Т(е ). Однако для обоснования правильности приводимого далее алгоритма воспроизведения существенно лишь свойство уникальности временных меток событий на основе векторного времени, поэтому ниже приведено доказательство этого свойства.
Обозначим через е\ г-е событие в процессе Р . Назовем вычислительной историей hk процесса Рк упорядоченную последовательность событий в этом процессе hk = (е ,..., e,fcx). Будем называть к-ю компоненту векторного времени событий из hk собственной компонентой векторного времени для hk-Из определения векторного времени следует, что последовательность собственных компонент векторного времени T(e )[fc] монотонно возрастает на hk, а последовательности других компонент являются монотонно неубывающими. Лемма 1 Если е\ и ej- - два разных события, то Т(е ) ф Т(е ). О Если е\ —» elj или elj - е\, то Т{е\) ф Т(е ) следует из свойства монотонности векторного времени. Рассмотрим случай, когда события е - и е\ не связаны отношением обусловленности. Из этого следует, в частности, 1Т Т, если Vk:k N T[k] Т Щ и 31: Т{1] Т [1]. что кфі.
Докажем, что Т(еJ)[к] Ф T(e )[fc]. Предположим, что это не так, т.е. T{e\)[k) = T(ef)[k] = t и докажем, что в таком случае должно иметь место е — elj.
Возьмем самое раннее событие e\irst,lktx из hi такое что Ti firattiktdik] = t. Это должно быть событие приема сообщения от некоторого процесса Рт. Пусть е - событие отправки этого сообщения; тогда Т(е)[к\ = t. Если m — к, то е = е\ (поскольку в hk только одно событие имеет временную метку, собственная компонента которой равна t), и мы доказали, что е\ —» е -.
Если тф к, то возьмем самое раннее событие гз1/т к из hm, такое что Т{е га1,тк1Л[к\ = t. Это также должно быть событие приема сообщения от некоторого процесса Рп. Обозначим через е событие отправки этого сообщения, причем T(e )[k] — t.
Опять, если п ф к, рассмотрим самое раннее событие е.п.іти,п к {ч из hn, такое что Т{егїіга1,пк1Л[к] = t, и т.д. Поскольку последовательность выбираемых таким образом процессов Pi, Рт, Рп, ...и событий конечна (в силу конечности общего числа процессов), то она рано или поздно должна закончиться процессом Рк (см. рис. 5.1) и событием е\; следовательно, е\ -Л ёу
Таким образом, и в случае, когда события е - и е\ не связаны отношением обусловленности, T{elA[k\ Ф Т(е )[/г].
