Разработка структур данных с диiиплиной доступа один пишет - много читают для многопоточного взаимодействия в системах реального времени
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
ом. Для обеспечения безопасности флаг будет устанавливаться с помощью операции CAS только в том случае, если ни один поток не удаляет опасные указатели в текущей момент. После завершения флаг сбрасывается атомарно. В качестве входных данных необходимо передавать указатель на свой элемент с опасным указателем в списке опасных указателей. Блок-схема алгоритма удаления опасных указателей представлена на рис. 2.10.
Рис. 2.10 Блок-схема алгоритма удаления опасных указателей
Глава 3. Реализация и тестирование разработанных структур и алгоритмов взаимодействия
.1 Особенности программной реализации
Данные алгоритмы реализовывались на языке программирования C++ в среде Microsoft Visual Studio.
Вначале был реализован класс ArrayHP, который содержит в себе все необходимые типы данных и функции для выполнения поставленной задачи в соответствии c разработанными алгоритмами для метода опасных указателей. Описание класса представлено в листинге 3.1.
Листинг 3.1 Описание класса ArrayHP
class ArrayHP {
private:tOldDataHP *headOldData;tOldDataHP *headHP;tDataHP **mass;int flagDelHP;countMass;countOldData;createArray();clearMem();:init(int nMass, int nHP);**getHP(int n);*newGetHP();delHP(tOldData **p);delAllHP();write(tDataHP **newData, int n);read(tDataHP **hp, int n);
};
Квалификатор типа volatile при определении переменных служит для указания компилятору, что данная переменная может изменяться независимо от исполнения шагов программы - под действием внешних факторов, то есть, например, вследствие обращения к ней из других потоков. Это необходимо, так как в данной работе используются алгоритмы, правильный порядок выполнения операций в которых чрезвычайно важен, поэтому нужно сообщить компилятору о том, что явно заданный порядок изменять нельзя. В противном случае компилятор при проведении оптимизации кода может изменить реальный порядок операций, по сравнению с тем порядком, который указан явно в тексте программы, что может стать источником серьезных ошибок, особенно в многопоточном приложении.
Первые два указателя содержат адрес вершины списков выбывших узлов и опасных указателей соответственно, третий - адрес указателя на массив. Такое определение позволяет задавать длину массива. Следующая переменная позволяет выполнять удаление опасных указателей после завершения работы потока только одному потоку одновременно. Все эти переменные должны изменяться строго в том порядке, который описан в алгоритмах, поэтому использовался квалификатор типа volatile при их определении. В следующих двух полях класса указаны переменные, отвечающие за длину массива и количество узлов в списке выбывших узлов соответственно. Длина массива задается при создании, а количество узлов в списке выбывших узлов изменяется только в одном потоке, поэтому при их определении использовать квалификатор не обязательно. Далее идут первые две функции, которые отвечают за создание массива указанной длины и освобождение памяти из-под неиспользуемых данных. Все описанные выше переменные и функции доступны только для функций-членов класса.
Следующие семь функций доступны для внешней программы. Первая служит для инициализации переменных класса как для заранее известного, так и для заранее неизвестного числа читающих потоков (если nHP равен нулю). Также она вызывает функцию для создания массива. Вторая функция отвечает за получение потоком своего опасного указателя, если количество читающих потоков было известно заранее, третья выполняет аналогичную функцию, но для случая, когда число читающих потоков неизвестно заранее. Следующие две функции удаляют опасные указатели для завершившихся читающих потоков. Первая из них удаляет опасный указатель сразу после завершения потока и используется при заранее неизвестном числе читающих потоков, а вторая - после того как завершились все читающие потоки и используется при заранее известном числе читающих потоков. Последние две функции служат для записи и чтения данных из указанных ячеек массива и полностью соответствуют разработанным алгоритмам.
Класс ArrayLC, который реализован в соответствии с разработанными алгоритмами для метода неблокирующего подсчёта ссылок, имеет схожую реализацию, однако имеет и отличия. Описание класса представлено в листинге 3.2.
Листинг 3.2 Описание класса ArrayLC
class ArrayLC {
private:tOldDataLC *headOldData;tDataLC **mass;countMass;countOldDataLC;createAarray();clearMem();:init(int nMass);
void write(tDataLC **newData, int n);*read(int n);endRead(tDataLC **data);
};
Главным отличием класса ArrayLC от ArrayHP является отсутствие всех переменных и функций, связанных со списком опасных указателей. Помимо этого функция чтения возвращает указатель на данные, а также присутствует функция, которая вызывается после того, как читающий поток закончил работу с данными. Также необходимо отметить, что структуры tOldDataLC и tOldDataHP являются идентичными и используются только в указанном виде описанными классами (листинг 3.3), а tDataLC отличается от tDataHP наличием дополнительного поля, отвечающего за подсчёт количества ссылок. Они являются структурами, в которых непосредственно хранятся данные. Форматы структур tDataLC и tDataHP, использующихся при отладке и тестировании программы, приведены в листинге 3.4.
Листинг 3.3 Описание структур tOldDataLC и tOldDataHP
struct tOldDataLC
{*next;*data;
};tOldDataHP
{*next;*data;
};
Листинг 3.4. Пример структур tDataLC и tDataHP
struct tDataHP
{data1;data2;data3;cs;
};
};tDataLC
{data1;data2;data3; cs;counter;
};
Описанный формат структур tDataLC и tDataHP позволяет генерировать значения случайным образом и проверять верность считанных данных.
Т