Introduction to Wait-free Algorithms in C++ Programming - Daniel Anderson - CppCon 2024

Visit cppcon.org for details on next year's conference. CppCon sponsors have made it possible to record and freely distribute over 1000 sessions from the first CppCon in 2014 to the present. We hope you enjoy them!

CppCon

CppCon 2024에서의 무대 소개 및 발표 주제 소개

발표자 Daniel은 CMU에서 알고리즘 강의를 하는 강사임.

주로 비동시 알고리즘을 가르치지만, 개인적으로 동시성 알고리즘에 관심이 많음.

발표에서는 동시성 및 락프리 프로그래밍의 기본 개념을 간략히 복습하고, 락프리 디자인 패턴을 살펴봄.

웨이트프리 알고리즘의 개념을 정의하고, 예시를 통해 디자인 아이디어를 설명함.

간단한 벤치마킹 결과도 제시할 예정임.

웨이트프리 알고리즘의 필요성: 

‘스티키 카운터’ 데이터 구조를 예시로 사용하며, 이는 카운터를 증가 및 감소시키지만 0에서 멈추는 구조임.

지원해야 하는 연산은 카운터 증가(0이 아닌 경우), 카운터 감소, 카운터 값 읽기임.

스티키 카운터는 C++ 표준 라이브러리의 공유 포인터, 특히 약한 포인터 락에 사용됨.

원자적 메모리 관리 및 데이터 구조에 유용하며, 발표자의 작년 C++ 발표에서 사용된 예시임.

락(Lock)의 문제점과 웨이트프리 알고리즘의 필요성

락을 사용하면 스레드 안전성을 확보할 수 있지만, 성능 저하를 야기할 수 있음.

한 스레드가 락을 획득한 채 작업을 하지 않으면 다른 스레드가 대기하게 되어 성능 저하가 발생함.

락은 동시성을 제거하여 동시성 문제를 해결하지만, 성능에 부정적인 영향을 미칠 수 있음.

성능 측정은 추측이 아닌 실제 벤치마킹을 통해 이루어져야 함.

동시 알고리즘의 진행 보장(Progress Guarantees)에 대한 정의

블로킹(Blocking): 진행 보장 없음.

장애물 자유(Obstruction Freedom): 단일 스레드가 독립적으로 실행 시 유한 단계 내에 완료됨.

락프리(Lock-free): 최소한 하나의 스레드가 진행됨.

웨이트프리(Wait-free): 모든 스레드가 진행됨.

웨이트프리 알고리즘 구현을 위한 접근 방식

락 알고리즘과 비교하여 웨이트프리 알고리즘의 우수성을 보임.

원자적(atomic) 변수를 사용하여 스레드 안전성을 확보함.

비교-교환(compare-exchange) 루프를 사용하여 카운터 증가 연산을 구현함.

원자적 fetch-and-subtract 연산을 사용하여 카운터 감소 연산을 구현함.

락프리 구현은 비교-교환 루프를 사용하지만, 웨이트프리 알고리즘이 아님.

웨이트프리 알고리즘은 무한 비교-교환 루프를 포함하지 않음.

원자적 읽기-수정-쓰기 연산(compare-and-exchange, fetch-and-add, atomic exchange)을 사용함.

스레드 간의 협업을 통해 경쟁을 줄이고, 모든 스레드가 진행될 수 있도록 함.

웨이트프리 디자인의 핵심은 다른 스레드의 작업을 돕는 것임.

카운터의 비트를 활용하여 스레드 간의 동기화를 수행함.

웨이트프리 알고리즘의 성능 벤치마킹 및 결론

원자적 공유 포인터를 사용한 실험에서 웨이트프리 카운터가 락프리 카운터보다 우수한 성능을 보임.

다양한 작업 부하(workload)에 대한 벤치마킹이 필요하며, 단일 벤치마킹 결과만으로 결론을 내려서는 안 됨.

작업 부하에 따라 웨이트프리 알고리즘이 항상 우수한 성능을 보이는 것은 아님.

알고리즘의 성능은 작업 부하(읽기/쓰기 비율, 스레드 수)에 따라 달라짐.

성능은 추측이 아닌 벤치마킹을 통해 검증되어야 함.

Introduction to Wait-free Algorithms in C++ Programming - Daniel Anderson - CppCon 2024

Introduction to Wait-free Algorithms in C++ Programming - Daniel Anderson - CppCon 2024

스크립트