Preview

Труды Института системного программирования РАН

Расширенный поиск

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

https://doi.org/10.15514/ISPRAS-2018-30(3)-4

Аннотация

Состояния гонки (data race) возникает в многопоточной программе при одновременном обращении нескольких потоков к разделяемым данным. Существует два основных подхода к обнаружению гонок - статический анализ программы (без её запуска) и динамическое обнаружение гонок в процессе работы программы. Ранее авторами был предложен точный высокопроизводительный динамический подход к обнаружению гонок на основании специальным образом составленных синхронизационных контрактов - частичных спецификаций поведения классов и наборов методов целевого приложения в многопоточной среде. Данная статья рассматривает вопрос индустриального применения концепции синхронизационных контрактов на крупных нагруженных многопоточных приложениях. Предложены метод обработки контрактов и архитектура соответствующего модуля динамического детектора jDRD, выявлены основные проблемные места и потенциальные точки падения производительности, разработано техническое решение, лишённое подобных проблем.

Об авторе

В. Ю. Трифанов
Санкт-Петербургский государственный университет
Россия


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

1. Java Language Specification, Third Edition. Threads and Locks. Happens-before Order. http://docs.oracle.com/javase/specs/jls/se7/html/jls-17.html#jls-17.4.5

2. Netzer R., Miller B. What Are Race Conditions? Some Issues and Formalizations. ACM Letters on Programming Languages and Systems, 1(1), 1992, pp. 74–88.

3. Blackout Final Report, August 14, 2003, http://www.ferc.gov/industries/electric/indus-act/reliability/blackout/ch5.pdf

4. Leveson N., Turner C. S. An Investigation of the Therac-25 Accidents. In IEEE Computer, vol. 26, N 7, 1993, pp. 18–41.

5. Engler D., Ashcraft K. RacerX: Effective, Static Detection of Race Conditions and Deadlocks. Proceedings of the Nineteenth ACM Symposium on Operating Systems Principles, 2003, pp. 237–252.

6. Voung J., Jhala R., Lerner S. RELAY: Static Race Detection on Millions of Lines of Code. In ESEC/FSE, 2007, pp. 205–214.

7. Herlihy M., Shavit N. The Art of Multiprocessor Programming. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2008, 528 p.

8. Kahlon V., Sinha N., Kruus E., Zhang Y.: Static data race detection for concurrent programs with asynchronous calls. In Proceedings of the 7th Joint Meeting of the European Software Engineering Conference and the Foundations of Software Engineering, 2009, pp. 13–22.

9. Naik M., Aiken A., Whaley J. Effective Static Race Detection for Java. In Proceedings of the 2006 ACM SIGPLAN Conference on Programming Language Design and Implementation, 2006, pp. 308–319.

10. Radoi C., Dig D. Practical static race detection for java parallel loops. In Proc. of the 13th International Symposium on Software Testing and Analysis, ISSTA ’13, 2013. P.178–190.

11. Xie X., Xue J., Zhang J. Acculock: Accurate and Efficient Detection of Data Races. Softw. Practice Experience, vol. 43, no. 5, May 2013, pp. 543–576.

12. Burckhardt S., Musuvathi M. Effective program verification for relaxed memory models. In Proceedings of the 20th international conference on Computer Aided Verification, Berlin, Heidelberg, 2008. pp. 107–120.

13. Huynh T., Roychoudhury A. Memory model sensitive bytecode verification. Form. Methods Syst. Des., 31(3), 2007, pp. 281–305.

14. Boyapati C., Lee R., Rinard M. Ownership types for safe programming: preventing data races and deadlocks. In Proceedings of the 17th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, 2002, pp. 211–230.

15. Flanagan C., Freund S. Type inference against races. Sci. Comput. Program., Vol 64, January 2007, pp. 140–165.

16. Rose J., Swamy N., Hicks M. Dynamic inference of polymorphic lock types. Science of Computer Programming, 58(3), 2005, pp. 366–383.

17. Biswas S., Zhang M., Bond M., Lucia B. Valor: Efficient, Software-Only Region Conflict Exceptions. In OOPSLA, 2015, pp. 241–259.

18. Flanagan C., Freund S. FastTrack: Efficient and Precise Dynamic Race Detection. In ACM Conference on Programming Language Design and Implementation, 2009, pp. 121–133.

19. Kini D., Mathur U., Viswanathan M. Dynamic race prediction in linear time. SIGPLAN Not. 52(6), 2017, pp. 157–170.

20. Qi Y., Das R., Luo Z., Trotter M. MulticoreSDK: a practical and efficient data race detector for real-world applications. Proceedings Software Testing, Verification and Validation (ICST), IEEE, 21-25 March 2011, pp. 309–318.

21. Serebryany S., Iskhodzhanov T. ThreadSanitizer: Data race detection in practice. In Proceedings of the Workshop on Binary Instrumentation and Applications, 2009, pp. 62–71.

22. Serebryany K., Potapenko A., Iskhodzhanov T., Vyukov D. Dynamic race detection with LLVM compiler - compile-time instrumentation for ThreadSanitizer. In RV, 2011, Lecture Notes in Computer Science, vol 7186, pp. 110–114.

23. Yu M., Bae D., SimpleLock+: Fast and Accurate Hybrid Data Race Detection. Comput. J., vol. 59, no. 6, 2016, pp. 793–809.

24. Zhang T., Jung C., Lee D. ProRace: Practical Data Race Detection for Production Use. In Proceedings of the International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2017, pp. 149–162.

25. Bond M., Coons K., McKinley K. Pacer: Proportional Detection of Data Races. Proceedings of 2010 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2010), Toronto, June 2010, pp. 255–268.

26. Marino D., Musuvathi M., Narayanasamy S. LiteRace: Effective Sampling for Lightweight Data Race Detection. PLDI '09 Proceedings of the 2009 ACM SIGPLAN conference on Programming language design and implementation, Vol. 44, Issue 6, 2009, pp. 134–143.

27. Трифанов В.Ю. Обнаружение состояний гонки в Java-программах на основе синхронизационных контрактов. Компьютерные инструменты в образовании. №4, 2012, стр. 16-29.

28. Трифанов В.Ю, Цителов Д.И. Динамический поиск гонок в Java-программах на основе синхронизационных контрактов. Материалы конференции "Инструменты и методы анализа программ (TMPA-2013)", Кострома, 2013, стр. 273–285.

29. Трифанов В.Ю., Цителов Д.И. Язык описания синхронизационных контрактов для задачи поиска гонок в многопоточных приложениях. Программная инженерия. Т.8, N 6, 2017, стр. 250–257.

30. Elmas T., Qadeer S., Tasiran S. Goldilocks: A Race and Transaction-Aware Java Runtime. Proceedings of the 2007 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI'07), 2007, pp. 245–255.

31. Lamport L. Time, Clocks and the Ordering of Events in a Distributed System. Communications of the ACM, Vol. 21, Issue 7, 1978, pp. 558–565.

32. Intel Thread Checker, http://software.intel.com/en-us/intel-thread-checker/

33. Трифанов В.Ю. Динамическое обнаружение состояний гонки в многопоточных Java-программах. Дисс. на соискание степени канд. техн. наук. СПбГУ, 2013.

34. Liskov B., Wing J. A behavioral notion of subtyping. ACM Trans. Program. Lang. Syst. 16 (6). November 1994, pp.1811–1841.

35. Click C. A lock-free wait-free hash table. https://web.stanford.edu/class/ee380/Abstracts/070221_LockFreeHash.pdf

36. Гаврилова Т.А., Лещева И.А., Кудрявцев Д.В. Использование моделей инженерии знаний для подготовки специалистов в области информационных технологий. Системное программирование. 2012. Т. 7. № 1, pp. 90–105.

37. Кознов Д.В. Основы визуального моделирования. Интернет-Университет Информационных Технологий (ИНТУИТ). Москва, 2008.

38. Ольхович Л.Б., Кознов Д.В. Метод автоматической валидации UML-спецификаций на основе языка OCL. Программирование. 2003. Т. 29. № 6, стр. 44–50.

39. Иванов А., Кознов Д., Мурашева Т. Поведенческая модель RTST++. Записки семинара Кафедры системного программирования "Case-средства RTST++". 1998. № 1, стр. 37–52.

40. Луцив Д.В., Кознов Д.В., Басит Х.А., Терехов А.Н. Задачи поиска нечётких повторов при организации повторного использования документации. Программирование. 2016. № 4, стр. 39–49.

41. Кознов Д.В., Романовский К.Ю. Автоматизированный рефакторинг документации семейств программных продуктов. Системное программирование. 2009. Т. 4, стр. 128–150.


Рецензия

Для цитирования:


Трифанов В.Ю. Вопросы индустриального применения синхронизационных контрактов при динамическом поиске гонок в Java-программах. Труды Института системного программирования РАН. 2018;30(3):47-62. https://doi.org/10.15514/ISPRAS-2018-30(3)-4

For citation:


Trifanov V.Yu. Applying synchronization contracts approach for dynamic detection of data races in industrial applications. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2018;30(3):47-62. (In Russ.) https://doi.org/10.15514/ISPRAS-2018-30(3)-4



Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)