Особенности программной реализации

Данные алгоритмы реализовывались на языке программирования C++ в среде Microsoft Visual Studio.

Вначале был реализован класс ArrayHP, который содержит в себе все необходимые типы данных и функции для выполнения поставленной задачи в соответствии c разработанными алгоритмами для метода опасных указателей. Описание класса представлено в листинге 3.1.

Листинг 3.1. Описание класса ArrayHP

class ArrayHP {

private:

volatile tOldDataHP *headOldData;

volatile tOldDataHP *headHP;

volatile tDataHP **mass;

volatile int flagDelHP;

int countMass;

int countOldData;

void createArray();

void clearMem();

public:

void init(int nMass, int nHP);

tDataHP **getHP(int n);

tOldData *newGetHP();

void delHP(tOldData **p);

void delAllHP();

void write(tDataHP **newData, int n);

void read(tDataHP **hp, int n);

};

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

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

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

Класс ArrayLC, который реализован в соответствии с разработанными алгоритмами для метода неблокирующего подсчёта ссылок, имеет схожую реализацию, однако имеет и отличия. Описание класса представлено в листинге 3.2.

Листинг 3.2. Описание класса ArrayLC

class ArrayLC {

private:

volatile tOldDataLC *headOldData;

volatile tDataLC **mass;

int countMass;

int countOldDataLC;

void createAarray();

void clearMem();

public:

void init(int nMass);

void write(tDataLC **newData, int n);

tDataLC *read(int n);

void endRead(tDataLC **data);

};

Главным отличием класса ArrayLC от ArrayHP является отсутствие всех переменных и функций, связанных со списком опасных указателей. Помимо этого функция чтения возвращает указатель на данные, а также присутствует функция, которая вызывается после того, как читающий поток закончил работу с данными. Также необходимо отметить, что структуры tOldDataLC и tOldDataHP являются идентичными и используются только в указанном виде описанными классами (листинг 3.3), а tDataLC отличается от tDataHP наличием дополнительного поля, отвечающего за подсчёт количества ссылок. Они являются структурами, в которых непосредственно хранятся данные. Форматы структур tDataLC и tDataHP, использующихся при отладке и тестировании программы, приведены в листинге 3.4.

Листинг 3.3. Описание структур tOldDataLC и tOldDataHP

struct tOldDataLC

{

tOldDataLC *next;

tDataLC *data;

};

struct tOldDataHP

{

tOldDataHP *next;

tDataHP *data;

};

Листинг 3.4. Пример структур tDataLC и tDataHP

struct tDataHP

{

int data1;

int data2;

int data3;

int cs;

};

struct tDataLC

{

int data1;

int data2;

int data3;

int cs;

int counter;

};

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

Также необходимо отметить, что различные компиляторы под разными операционными системами имеют различные возможности по работе с процессорными инструкциями типа CAS, которые использовались при реализации некоторых функций. Microsoft Visual Studio обеспечивает доступ к этим инструкциям на центральных процессорах архитектуры Intel с помощью семейства функций _InterlockedCompareExchange и _InterlockedCompareExchangePointer, определенных в заголовочном файле “intrin.h”. Для атомарных операций увеличения и уменьшения значения счетчика на единицу можно использовать функции _InterlockedIncrement и _InterlockedDecrement.

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

Суммарный объём разработанных классов без учёта комментариев составляет около тысячи строк.

Дата добавления: 2015-11-14