Суть данного алгоритма заключается в получении указателя на данные, которые хранятся в указанной ячейке массива, и увеличении счётчика ссылок. Однако во время этих действий может измениться указатель, могут удалиться данные, а также другой поток может изменить счётчик. В связи с этим, помимо использования операций подмены указателя и атомарного увеличения счётчика, необходимо ввести дополнительную проверку, подтверждающую, что данные операции прошли успешно и манипуляции произошли с теми данными, с которыми и должны были произойти. Однако при выполнении обычной проверки могут произойти изменения, и в результате получится ошибка. Таким образом, вначале мы должны получить указатель на данные из ячейки массива, а затем одновременно выполнить проверку, не изменился ли указатель, и увеличить счётчик, причём атомарно. Единственным оптимальным вариантом является атомарная подмена с помощью CAS, если производить сравнение счётчика скопированного указателя и счётчика указателя из ячейки массива. Однако даже такая проверка не даст стопроцентной гарантии, так как вполне может возникнуть такая ситуация, при которой эти два счётчика равны, но указатели разные, но данная проверка позволит уменьшить шанс этого. Таким образом, вначале происходит получение указателя на данные из ячейки массива, далее вышеописанная проверка. Если проверка успешна, то происходит атомарное увеличение счётчика, после чего возвращается указатель на данные и алгоритм завершается. После того, как читающий поток отработал с полученными данными, происходит атомарное уменьшение счётчика на единицу. Разработанный алгоритм является lock-free алгоритмом, так как любой поток может крутиться в этом цикле бесконечно, однако гарантируется прогресс минимум для одного потока. Блок-схема алгоритма чтения для метода неблокирующего подсчёта ссылок представлена на рис. 2.5.



Рис. 2.5 Блок-схема алгоритма чтения для метода неблокирующего подсчёта ссылок

Метод опасных указателей

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

Рис. 2.6 Блок-схема алгоритма чтения для метода опасных указателей

Обращение к данным происходит по опасному указателю. После того, как читающий поток отработал с данными, указатель обнуляется. Также как и алгоритм чтения для неблокирующего подсчёта ссылок, данный алгоритм является lock-free и гарантирует прогресс минимум для одного потока.

2.4.3 Алгоритм освобождения памяти

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

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

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

Метод неблокирующего подсчёта ссылок

В данном методе использование данных определяется по счётчику ссылок. На вход алгоритма поступает указатель на второй элемент списка выбывших узлов. После этого создаётся копия указателя, чтобы обеспечивать возможность прохода по списку без потери полученного указателя. Далее происходит обход списка, в котором проверяются значения счётчика по указателю на данные, которые хранится в узле списка выбывших узлов. Если счётчик равен нулю, то данные не используются и из-под них можно безопасно освободить память. Алгоритм завершается после обхода всех узлов, предварительно атомарно сбросив флаг запуска освобождения памяти. Разработанный алгоритм является wait-free алгоритмом, так как не содержит операций вида CAS и будет выполнен за конечное число шагов, не зависимо ни от чего.

Блок-схема алгоритма освобождения памяти для метода неблокирующего подсчёта ссылок представлена на рис. 2.7.

Рис. 2.7 Блок-схема алгоритма освобождения памяти для метода неблокирующего подсчёта ссылок

Метод опасных указателей

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



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

Если указатели совпадают, то совершается переход к следующему узлу списка выбывших узлов. В том случае, если ни один из опасных указателей не совпал с указателем на данные из списка выбывших узлов, то данные не используются ни одним читающим потоком и память из-под них может быть безопасно освобождена. Алгоритм завершается после обхода всех узлов, предварительно атомарно сбросив флаг запуска освобождения памяти. Данный алгоритм, также как и алгоритм освобождения памяти для метода неблокирующего подсчёта ссылок, является wait-free алгоритмом, так как не содержит операций вида CAS и будет выполнен за конечное число шагов, не зависимо ни от чего. Блок-схема алгоритма освобождения памяти для метода опасных указателей представлена на рис. 2.8.

2.4.4 Алгоритм добавления и удаления опасных указателей

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

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



Рис. 2.9 Блок-схема алгоритма добавления опасных указателей

При завершении работы поток должен удалить свой элемент из списка опасных указателей. Для этого необходимо найти предшествующий элемент в списке опасных указателей, изменить его указатель на следующий элемент, а затем удалить свой. Однако при завершении нескольких потоков одновременно может произойти следующая ситуация: один из потоков останавливается на элементе, который в этот момент времени удаляется другим потоком. В результате мы получаем ошибку при обращении к несуществующему элементу. В случае небольшого количества читающих потоков можно не освобождать память при завершении, а обнулять указатель и освобождать память из-под всего списка непосредственно перед завершением работы программы, так как решение данной задачи средствами неблокирующего программирования на данный момент не представляется возможным. Это объясняется тем, что во время проверки следующего элемента, может быть удалён текущий, как и любой другой элемент списка. Для решения данной проблемы можно использовать спин-блокировку. В данной ситуации использование простейшей блокирующей синхронизации не приведёт ни к каким отрицательным последствием, так как единственным её предназначением будет обеспечение выполнения алгоритма удаления опасных указателей только одним читающим потоком. Для обеспечения безопасности флаг будет устанавливаться с помощью операции CAS только в том случае, если ни один поток не удаляет опасные указатели в текущей момент. После завершения флаг сбрасывается атомарно. В качестве входных данных необходимо передавать указатель на свой элемент с опасным указателем в списке опасных указателей. Блок-схема алгоритма удаления опасных указателей представлена на рис. 2.10.

Рис. 2.10 Блок-схема алгоритма удаления опасных указателей

Глава 3. Реализация и тестирование разработанных структур и алгоритмов взаимодействия

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

Данные алгоритмы реализовывались на языке программирования 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 - старое значение, которое хранилось по адресу.

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

3.2 Тестирование разработанных алгоритмов

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

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

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

Для проверки алгоритмов освобождения памяти использовалась программа Visual Leak Detector. После завершения алгоритма она выдаёт информацию об утечках. Для проверки всех ветвей алгоритма освобождения памяти метода неблокирующего подсчёта ссылок (рис. 2.7) использовался следующий порядок обхода:

A1->B1->C1->E1->D2->C1->D1->E1->F1.

В алгоритме освобождения памяти метода опасных указателей (рис. 2.8) использовался следующий порядок обхода:

A1->B1->C1->D2->C3->C1->D2->E2->F1->G2->H2->C1->F1->J1.

Утечек выявлено не было:

Visual Leak Detector Version 2.2.3 installed.

No memory leaks detected.

Visual Leak Detector is now exiting.

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

3.3 Тестирование разработанной структуры при многопоточном доступе

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

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

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

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

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

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

Тестирование проводилось на двухъядерном процессоре, поэтому для проверки всех указанных проблем достаточно трёх читающих потоков. Распределение потоков по ядрам представлено в таблице 3.1.

Таблица 3.1 Распределение потоков по ядрам

Проблема	Ситуация	Ядро 1	Ядро 2
1)	1)	Пишущий поток без освобождения памяти	Читающий поток
	2)		Два читающих потока
	3)	Пишущий поток без освобождения памяти Три читающих потоков
2) 3)	4)	Пишущий поток	Читающий поток
	5)		Два читающих потока
	6)	Пишущий поток Три читающих потоков

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

1) Возможность выбора специального метода управления памяти: HP - метод опасных указателей, LC - метод неблокирующего подсчёта ссылок.

2) Возможность привязки пишущего потока к одному ядру, читающих - к другому.

3) Возможность задания длины массива.

4) Возможность указания числа читающих потоков.

5) Возможность задания времени работы программы.

6) Возможность запуска читающих потоков в течение всего времени работы программы.

Пример запуска программы представлен на рис. 3.1.

Рис. 3.1 Пример запуска тестирующей программы

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

Таблица 3.2 Результаты тестирования

Ситуация	Метод неблокирующего подсчёта ссылок	Метод опасных указателей
1)	Прочитано: 106260885 Количество ошибок: 0	Прочитано: 123647406 Количество ошибок: 0
2)	Прочитано: 108203020 Количество ошибок: 0	Прочитано: 121693470 Количество ошибок: 0
3)	Прочитано: 118821519 Количество ошибок: 0	Прочитано: 134767103 Количество ошибок: 0
4)	Прочитано: 109747632 Количество ошибок: 36	Прочитано: 121098202 Количество ошибок: 0
5)	Прочитано: 103586435 Количество ошибок: 49	Прочитано: 118382785 Количество ошибок: 0
6)	Прочитано: 119855489 Количество ошибок: 23	Прочитано: 143162986 Количество ошибок: 0

По результатам тестирования видно, что ошибки возникают только при использовании метода неблокирующего подсчёта ссылок с освобождением памяти. Это закономерно, так как отсутствие операции DCAS не позволяет сделать этот метод полностью безопасным. Было проведено десять запусков и выявлено, что процент ошибок не превышает 0,00008 процента.

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

Также стоит отдельно рассмотреть проблему запуска большого количества потоков в случае метода опасных указателей при заранее неизвестно числе потоков, так как список опасных указателей изменяется динамически, что может привести как к ошибкам, так и к утечке памяти. Для проверки данных проблем в течение двух секунд запускались читающие потоки, работающие также две секунды, а после чего завершающиеся. За указанное время было запущено 1282 потока и выполнено 6408718 операций чтения. Ошибок доступа к данным и утечки памяти выявлено не было. Результат запуска программы представлен на рис. 3.2.



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

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

3.4 Сравнение структур по временным характеристикам

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

1) Запуск методов неблокирующего подсчёта ссылок и опасных указателей поочерёдно.

2) Измерение времени выполнения операций записи и чтения.

3) Задание произвольного числа операций, время выполнения которых измеряется.

4) Запись в файл результатов измерения операций записи и чтения для методов неблокирующего подсчёта ссылок и опасных указателей.

Также необходимо отметить, что все потоки должны запускаться одновременно, а также одновременно завершаться, так как измеряемое время будет зависеть от числа одновременно работающих потоков. Сравнение будет проводиться для метода неблокирующего подсчёта ссылок и метода опасных указателей для известного числа потоков, так как операции записи и чтения идентичны. Было решено рассмотреть один, три, пять и семь потоков читающих потоков, причём взаимодействующие также с массивом единичной длины для увеличения нагрузки. При построении графиков использовалось среднее и максимальное время выполнения одной операции чтения. Было выполнено по десять запусков для каждого варианта. Пример запуска представлен на рис. 3.3, результат - в листингах 3.5 и 3.6. Итоговые результаты представлены в таблице 3.3 и на рис. 3.4.



Рис. 3.3 Пример запуска программы сравнения методов

Листинг 3.5 Результат запуска программы сравнения методов для одного потока для операции чтения

HP known threads

All time = 38249797, Average time for one operation = 38.

All time = 49071218, Average time for one operation = 49.

All time = 38288713, Average time for one operation = 38.

All time = 51675186, Average time for one operation = 51.

All time = 56317473, Average time for one operation = 56.

All time = 54771751, Average time for one operation = 54.

All time = 55610155, Average time for one operation = 55.

All time = 38313292, Average time for one operation = 38.

All time = 38396244, Average time for one operation = 38.

All time = 56585107, Average time for one operation = 56.

HP known threads end

-----------------------------------------

LC

All time = 72600128, Average time for one operation = 72.

All time = 69639428, Average time for one operation = 69.

All time = 54617452, Average time for one operation = 54.

All time = 52445999, Average time for one operation = 52.

All time = 72555067, Average time for one operation = 72.

All time = 51173714, Average time for one operation = 51.

All time = 66033198, Average time for one operation = 66.

All time = 63014806, Average time for one operation = 63.

All time = 52515639, Average time for one operation = 52.

All time = 63127458, Average time for one operation = 63.

LC end

Листинг 3.6 Результат запуска программы сравнения методов для одного потока для операции записи

HP known threads

All time = 350980157, Average time for one operation = 350.

All time = 382210881, Average time for one operation = 382.

All time = 533933688, Average time for one operation = 533.

All time = 316099509, Average time for one operation = 316.

All time = 359319991, Average time for one operation = 359.

All time = 335807808, Average time for one operation = 335.

All time = 333108598, Average time for one operation = 333.

All time = 537831790, Average time for one operation = 537.

All time = 521164753, Average time for one operation = 521.

All time = 339570386, Average time for one operation = 339.

HP known threads end

-----------------------------------------

LC

All time = 324355195, Average time for one operation = 324.

All time = 316458288, Average time for one operation = 316.

All time = 514269426, Average time for one operation = 514.

All time = 512787881, Average time for one operation = 512.

All time = 332048303, Average time for one operation = 332.

All time = 515198293, Average time for one operation = 515.

All time = 318821933, Average time for one operation = 318.

All time = 315950672, Average time for one operation = 315.

All time = 511196074, Average time for one operation = 511.

All time = 300171538, Average time for one operation = 300.

LC end

Таблица 3.3 Результаты сравнения структур по временным характеристикам

		Миллион операций	Одна операция	Потоки
		макс, ns	сред, ns	макс, ns	сред, ns
Чтение	HP*	56585107	47727894	56	47	1
		77628504	54897512	77	54	3
		106289225	55805852	106	55	5
		156406912	60533960	156	60	7
	LC**	72600128	61772289	72	61	1
		343743972	215129017	343	215	3
		560954469	293326453	560	293	5
		683642415	338068344	683	338	7
Запись	537831790	398564258	537	398	1
	794820055	655848363	794	655	3
	1608631875	866063324	1608	865	5
	1951584894	1252959897	1951	1252	7

HP* - метод опасных указателей; LC** - метод неблокирующего подсчёта ссылок.



Рис. 3.4 График зависимости времени выполнения одной операции чтения от количества читающих потоков

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

Заключение

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

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

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

Были разработаны структуры данных и алгоритмы взаимодействия структуры и внешней программы в соответствии со всеми принципами неблокирующей синхронизации, в том числе и с выбранными специальными методами освобождения памяти. Далее разработанные структуры и алгоритмы были объединены в классы и реализованы на языке программирования C++ в среде Microsoft Visual Studio в ОС Windows. Суммарный объём кода разработанных классов без учёта комментариев составил около тысячи строк. Тестирование алгоритмов производилось изолировано по мере разработки структуры.

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

Список литературы

1. John D.V. Lock-Free Linked Lists Using Compare-and-Swap. Symposium on Principles of Distributed Computing. 1995. 214-222 c.

2. Fraser K. Practical lock freedom // Cambridge University. Technical Report. 2004. №579.

3. Fraser K., Harris T. Concurrent programming without locks // ACM Transactions on Computer Systems. 2007. №25.

4. Maged M.M. Hazard Pointers: Safe Memory Reclamation for Lock-Free Objects // IEEE Transactions on Parallel and Distributed Systems. 2004. №6.

5. Alexandrescu A., Maged M.M. Lock-Free Data Structures with Hazard Pointers // C/C++ Users Journal. 2004.

6. Шилдт Г. Полный справочник по C++: Пер. с англ. М.: Издательский дом «Вильямс», 2006. 800 с.

7. Рихтер Дж. Windows для профессионалов: создание эффективных Win32-приложений с учетом специфики 64-разрядной версии Windows: Пер. с англ. СПб.: Питер; М.: Издательство «Русская Редакция», 2008. 720 с.

8. Lock-Free программирование - структуры данных, DATA-RACE, Ноябрь, 2010, http://www.data-race.com/2010/11/12/lock-free-программирование-структуры-данных/

9. Lock-free algorithms: The try/commit/(try again) pattern, MSDN blogs, 2011, http://blogs.msdn.com/b/oldnewthing/archive/2011/04/12/10152296.aspx

10. Lock-Free, Wait-Free, Obstruction-Free, Atomic-Free Algorithms, http://www.1024cores.net/home/in-russian/lock--wait--obstruction--atomic-free-algorithms

Размещено на Allbest.ru