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

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

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*
LC**
Запись

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

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