Оценка производительности алгоритмов синхронизации в средах исполнения с легкими потоками на языке С++

Введение. Традиционно, многопоточные структуры данных разрабатывались и тестировались для вызовов из потоков операционной системы. Однако в последнее время в языках программирования появилась альтернатива — легкие потоки (иначе известные, как асинхронные вызовы, и корутины). Такие потоки бывают двух видов со стеком и без него. В настоящей работе рассмотрены стековые корутины. Основное преимущество легких потоков заключается в меньшем количестве накладных расходов. В отличие от потоков операционной системы, в стандартной библиотеке языка С++ отсутствует реализация стековых легких потоков. Они предоставляются несколькими библиотеками, отличающимися: планированием исполнения потока, способом хранения данных в памяти и интерфейсом использования. Кроме того, переиспользование существующего кода невозможно из-за необходимости явной разметки кода точками переключения контекста, отсутствие которых может приводить к взаимной блокировке легких потоков. Для ограничения области исследования рассмотрен конкретный вид многопоточных примитивов — мьютекс (иначе известный, как взаимное исключение). 
Метод. Выполнен анализ нескольких библиотек для работы с легкими потоками: Argobots, Boost Fibers, Userver. На основе оценки их функциональности, разработан трехступенчатый механизм ожидания, использующий активное ожидание, переключение контекста, а также способы приостановки и возобновления легкого потока. Описание механизма включает предложение об общем способе его внедрения в известные алгоритмы мьютексов. Механизм служит дополнительным слоем абстракции между библиотеками легких потоков и мьютексами, позволяя реализовывать их в общем виде. Из-за отсутствия существующих решений, был создан инструмент для тестирования и оценки производительности модифицированных мьютексов. 
Основные результаты. С помощью предложенного метода ряд известных мьютексов был адаптирован для вызовов из легких потоков. Для тестирования получившихся примитивов разработан инструмент, позволяющий интегрировать произвольные реализации легких потоков и учитывающий специфику работы с ними. В результате была измерена пропускная способность адаптированных мьютексов с помощью нового инструмента на специальном сценарии, отражающем особенности кооперативной многозадачности. 
Обсуждение. В перспективе планируется формирование библиотеки, включающей все известные реализации мьютексов, адаптированных под вызовы из легких потоков. Это позволит провести детальное сравнение производительности этих алгоритмов в зависимости от: библиотеки легких потоков, алгоритмов планировщика и архитектуры процессора. Ожидается, что детальный анализ поведения существующих алгоритмов позволит создать новую реализацию мьютекса, работающего наиболее эффективно на вызовах из легких потоков.

1. Moore G.E. Cramming more components onto integrated circuits // Electronics. 1965. V. 38. N 8. P. 114–117.

2. Sutter H. The free lunch is over: a fundamental turn toward concurrency in software // Dr. Dobb’s Journal. 2005. V. 30. N 3. P. 202–210.

3. Olukotun O.A., Hammond L., Laudon J.P. Chip Multiprocessor Architecture: Techniques to Improve Throughput and Latency. Morgan & Claypool Publishers, 2007. 145 p.

4. Lameter C. NUMA (Non-Uniform Memory Access): An Overview: NUMA becomes more common because memory controllers get close to execution units on microprocessors // Queue. 2013. V. 11. N 7. P. 40–51. https://doi.org/10.1145/2508834.2513149

5. Seo S., Amer A., Balaji P., Bordage C., Bosilca G., Brooks A., et al. Argobots: a lightweight low-level threading and tasking framework // IEEE Transactions on Parallel and Distributed Systems. 2018. V. 29. N 3. P. 512–526. https://doi.org/10.1109/tpds.2017.2766062

6. Castello A., Gual R.M., Seo S., Balaji P., Quintana-Orti E.S., Pena A.J. Analysis of threading libraries for high performance computing // IEEE Transactions on Computers. 2020. V. 69. N 9. P. 1279–1292. https://doi.org/10.1109/tc.2020.2970706

7. Tanenbaum A.S., Bos H. Modern Operating Systems. ‎ Pearson, 2014. 1136 p.

8. Rudolph L., Segall Z. Dynamic decentralized cache schemes for mimd parallel processors // ACM SIGARCH Computer Architecture News. 1984. V. 12. N 3 . P. 340–347. https://doi.org/10.1145/773453.808203

9. Mellor-Crummey J.M., Scott M.L. Algorithms for scalable synchronization on shared-memory multiprocessors // ACM Transactions on Computer Systems. 1991. V. 9. N 1. P. 21–65. https://doi.org/10.1145/103727.103729

10. Craig T.S. Building FIFO and Priorityqueuing Spin Locks from Atomic Swap. Technical Report TR 93-02-02. Department of Computer Science, University of Washington, 1993. 29 p.

11. Chabbi M., Fagan M., Mellor-Crummey J. High performance locks for multi-level NUMA systems // ACM SIGPLAN Notices. 2015. V. 50. N 8. P. 215–226. https://doi.org/10.1145/2858788.2688503

12. Dice D., Kogan A. Compact NUMA-aware locks // Proc. of the 14th EuroSys Conference. 2019. P. 1–15. https://doi.org/10.1145/3302424.3303984

13. Shanley T. x86 Instruction Set Architecture. MindShare Press, 2010. 1568 p.

14. Oberhauser J., Oberhauser L., Paolillo A., Behrens D., Fu M., Vafeiadis V. Verifying and optimizing the HMCS lock for Arm servers // Lecture Notes in Computer Science. 2021. V. 12754. P. 240–260. https://doi.org/10.1007/978-3-030-91014-3_17

15. Goodacre J., Sloss A.N. Parallelism and the ARM instruction set architecture // Computer. 2005. V. 38. N 7. P. 42–50. https://doi.org/10.1109/mc.2005.239

16. Bartel J. Non-preemptive multitasking // The Computer Journal. 1988. V. 30. P. 37–39.

17. Karsten M., Barghi S. User-level threading: Have your cake and eat it too // Proc. of the ACM on Measurement and Analysis of Computing Systems. 2020. V. 4. N 1. P. 1–30. https://doi.org/10.1145/3379483

18. Madsen O.L. Using coroutines for multi-core preemptive scheduling // Proc. of the 11th Workshop on Programming Languages and Operating Systems. 2021. P. 46–52. https://doi.org/10.1145/3477113.3487271

19. Shiina S., Iwasaki S., Taura K., Balaji P. Lightweight preemptive user-level threads // Proc. of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 2021. P. 374–388. https://doi.org/10.1145/3437801.3441610

20. Donovan A.A., Kernighan B.W. The Go Programming Language. Addison-Wesley Professional, 2015. 400 p.