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. Результат запуска тестирующей программы для метода опасных

указателей при заранее неизвестном числе потоков

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