Построение дерева контекстов

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

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

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

Определим некоторую структуру, которая будет содержать данные о текущем состоянии нити, и назовем ее контекстом (Context). Для каждой нити в каждый момент времени доступен некоторый набор переменных, к которым они могут обращаться, при этом у разных нитей эти наборы обычно разные, т.к. они могут обладать приватными переменными и находиться в разных частях программы. Пусть текущий контекст нити содержит структуры данных, описывающие каждую переменную, (VarInfo) к которой было обращение с момента существования этого контекста. Структура VarInfo может быть взята из текущего контекста нити по некоторому ключу, например, по адресу соответствующей переменной. Конкретные ключи будут приведены далее при описании алгоритмов обнаружения ошибок, так же как будет уточнено содержимое самой структуры Context.

Теперь для полноты описания состояния всей программы следует поместить в вершины приведенного выше дерева, описывающего связи между нитями, структуры описывающие состояния самих нитей, а именно структуры Context. Такое дерево назовем деревом контекстов.

Правила построения дерева контекстов выглядят следующим образом:

· В начале выполнения программы существует только одна нить, а следовательно дерево контекстов должно состоять из одной корневой вершины, соответствующей данной нити.

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

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

· При вызове проинструментированной функции, т.е. функции содержащей обращения к отладчику, к вершине данной нити добавляется вершина-потомок, которая становится текущей для этой нити.

· При выходе из функции текущая вершина нити удаляется, и текущей становится ее родительская вершина.

На рисунке 3 показан пример дерева контекстов. В вершинах этого дерева указан уникальный номер нитей, который в отличие от номеров OpenMP у любых двух нитей будет различным.

Рисунок 3: Пример дерева контекстов

Построенное дерево будет использоваться при дальнейшем описании алгоритмов, поэтому для удобства описания определим некоторые понятия, которые могут встретиться. Контекст или структура Context соответствует вершине дерева. Текущим контекстом для данной нити называется листовая вершина дерева, которая соответствует этой нити. Для каждой нити существует только один текущий контекст. Родительской вершиной называется вершина, к которой присоединена данная, и расположенная непосредственно над данной вершиной.