논블로킹 알고리즘

Non-blocking algorithm
논블로킹 I/O와 혼동하지 마십시오.

컴퓨터 과학에서, 어떤 스레드의 장애나 정지가 다른 [1]스레드의 장애나 정지를 야기할 수 없는 경우, 알고리즘을 논블로킹이라고 부릅니다.일부 연산에 있어서, 이러한 알고리즘은 기존의 블로킹 구현에 대한 유용한 대안을 제공합니다.논블로킹 알고리즘은 시스템 전체의 진척이 보증되어 있는 경우에는 록프리, 스레드 단위의 진척이 보증되어 있는 경우에는 대기 프리입니다."[2]비차단"은 2003년 방해-자유 도입 전까지 문헌에서 "잠금 없음"의 동의어로 사용되었습니다.

"비블로킹"이라는 단어는 "기존 콜을 재배치할 필요 없이" 릴레이 세트를 통해 연결을 라우팅할 수 있는 통신 네트워크를 설명하기 위해 전통적으로 사용되었습니다(Clos network 참조).또, 전화 교환기에 「불량이 없는 경우」는, 언제라도 접속할 수 있습니다( 「논블로킹 최소 스패닝 스위치」를 참조).

동기

주요 기사:잠금 장치의 단점

기존의 멀티 스레드 프로그래밍 방식은 잠금을 사용하여 공유 리소스에 대한 액세스를 동기화하는 것입니다.뮤텍스, 세마포어, 크리티컬섹션 등의 동기 프리미티브는 프로그래머가 코드의 특정 섹션이 동시에 실행되지 않도록 하는 메커니즘입니다.이러한 메커니즘으로 인해 공유 메모리 구조가 파손될 수 있습니다.한 스레드가 다른 스레드에 의해 이미 유지된 잠금을 획득하려고 하면 잠금이 해제될 때까지 스레드가 차단됩니다.

스레드를 차단하는 것은 여러 가지 이유로 바람직하지 않을 수 있습니다.분명한 이유는 스레드가 차단되어 있는 동안에는 아무것도 달성할 수 없기 때문입니다.블록된 스레드가 높은 우선순위 또는 실시간 태스크를 실행하고 있었을 경우 진행이 중지되는 것은 매우 바람직하지 않습니다.

다른 문제는 덜 명백하다.예를 들어 잠금 간의 특정 상호 작용으로 인해 교착 상태, 라이브 잠금 및 우선 순위 반전과 같은 오류 상태가 발생할 수 있습니다.또한 잠금 장치를 사용하면 병렬의 기회를 크게 줄일 수 있는 거친 잠금 장치와 보다 세심한 설계가 필요한 세분화된 잠금 장치 간의 균형을 유지할 수 있으며 잠금 오버헤드를 증가시키고 버그가 발생하기 쉽습니다.

블로킹 알고리즘과는 달리 논블로킹알고리즘은 이러한 단점을 겪지 않고 인터럽트 핸들러에서 사용해도 안전합니다.프리엠프트된 스레드를 재개할 수 없는 경우에도 계속 진행할 수 있습니다.이와는 대조적으로 상호 배제로 보호되는 글로벌 데이터 구조는 인터럽트 핸들러에서 안전하게 접근할 수 없습니다.프리엠프트된 스레드는 잠금을 유지하는 스레드일 수 있기 때문입니다.그러나 이는 중요한 [3]섹션 동안 인터럽트 요청을 마스킹함으로써 쉽게 수정할 수 있습니다.

록 프리 데이터 구조를 사용하여 성능을 향상시킬 수 있습니다.록 프리 데이터 구조는 시리얼 실행보다 병렬 실행에 소요되는 시간을 늘려 멀티코어 프로세서의 성능을 향상시킵니다.이는 [4]공유 데이터 구조에 대한 액세스를 시리얼화할 필요가 없기 때문입니다.

실행

예외는 거의 없지만 논블로킹알고리즘은 하드웨어가 제공해야 하는 원자성 읽기-수정-쓰기 프리미티브를 사용합니다.그 중 가장 주목해야 할 것은 Compare and Swap(CAS; 비교 및 스왑)입니다.크리티컬 섹션은 거의 항상 이러한 프리미티브에 표준 인터페이스를 사용하여 구현됩니다(일반적으로 크리티컬섹션은 이러한 프리미티브를 사용하여 구현되어도 블로킹됩니다).1990년대에는 모든 논블로킹 알고리즘이 허용 가능한 성능을 달성하기 위해 기본 기본 요소를 사용하여 "네이티브하게" 작성되어야 했습니다.그러나 소프트웨어 트랜잭션 메모리의 신흥 분야는 효율적인 논블로킹 [5][6]코드를 작성하기 위한 표준 추상화를 약속하고 있습니다.

스택, 큐, 세트 및 해시 테이블과 같은 기본 데이터 구조를 제공하는 데도 많은 연구가 수행되었습니다.이를 통해 프로그램은 스레드 간에 데이터를 비동기적으로 쉽게 교환할 수 있습니다.

또한, 일부 논블로킹 데이터 구조는 특별한 원자 원소가 없어도 구현될 수 있을 정도로 취약합니다.다음과 같은 예외가 있습니다.

  • 싱글 리더 싱글 라이터 링 버퍼 FIFO는 사용 가능한 부호 없는 정수 타입 중 하나의 오버플로를 균등하게 나누는 크기를 가지며 메모리 장벽만을 사용하여 무조건 안전하게 구현될 수 있다.
  • 1명의 라이터와 임의의 수의 리더를 사용한 읽기-복사-업데이트(리더는 대기자 없이, 라이터는 메모리를 회수할 때까지 잠금이 해제됩니다).
  • 여러 라이터와 임의의 수의 독자를 대상으로 한 읽기-복사-업데이트(리더는 대기자 없음, 일반적으로 여러 라이터는 잠금으로 연재하며 장애물이 없습니다).

일부 라이브러리는 내부적으로 잠금 없는 [7][8][9]기술을 사용하지만 잠금 없는 코드를 올바르게 [10][11][12][13]기술하기는 어렵습니다.

논블로킹 알고리즘에는 일반적으로 일련의 읽기, 읽기, 변경, 쓰기 명령이 신중하게 설계된 순서로 포함됩니다.컴파일러를 최적화하면 작업을 적극적으로 재배치할 수 있습니다.메모리 장벽이 CPU에 재주문하지 않도록 지시하지 않는 한, 최신 CPU의 대부분은 이러한 조작을 재배치하는 경우가 많습니다(「정합성이 약한 모델」이 있습니다.C++11 프로그래머는std::atomic에<atomic>및 C11 프로그래머는<stdatomic.h>둘 다 컴파일러에 이러한 명령을 다시 적용하지 않도록 지시하고 적절한 메모리 [14]장벽을 삽입하도록 지시하는 유형과 기능을 제공합니다.

대기 자유

대기 자유는 시스템 전체의 throughput 보장과 기아 자유 보장을 결합한 가장 강력한 비차단적 진보 보장입니다.모든 조작에 동작이 [15]완료되기 전에 알고리즘이 실행하는 스텝 수에 제한이 있는 경우 알고리즘은 대기 상태가 아닙니다.이 속성은 실시간 시스템에 매우 중요하며 성능 비용이 너무 높지 않으면 언제든지 사용할 수 있습니다.

1980년대에[16] 모든 알고리즘이 대기 없이 구현될 수 있다는 것이 입증되었고, 범용 구성이라고 불리는 직렬 코드에서 많은 변환이 입증되었다.단, 그 결과 발생하는 퍼포먼스는 일반적으로 순수 블로킹 설계와 일치하지 않습니다.이후 여러 논문이 범용 시공의 성능을 향상시켰지만, 여전히 그 성능은 블록 설계를 훨씬 밑돌고 있다.

여러 논문이 대기 없는 알고리즘을 만드는 것의 어려움을 조사했다.예를 들어, 널리 이용 가능한 원자 조건부 프리미티브인 CAS와 LL/SC는 스레드 수가 선형적으로 증가하는 메모리 비용 없이 많은 공통 데이터 구조의 기아 없는 구현을 제공할 수 없는 것으로 나타났습니다[17].

그러나 실제로는 공유 메모리의 스레드당 저장소의 캐시 라인 또는 배타적 예약 과립(ARM에 최대 2KB)을 소비하는 것은 실제 시스템에서 비용이 많이 들지 않습니다(일반적으로 논리적으로 필요한 저장소의 양은 단어이지만 물리적으로 동일한 캐시 라인에서 CAS 작업을 수행하는 데 있어 w.d.충돌하지 않고 동일한 전용 예약 과립 내 LL/SC 작업이 충돌하므로 물리적으로[citation needed] 필요한 저장소의 양이 더 커집니다).

2011년까지는 연구 및 실무 모두에서 대기 없는 알고리즘이 드물었다.단, 2011년 Kogan과 Petrank는[18] CAS 프리미티브에 대기 큐빌딩을 제시했습니다.일반적으로 공통 하드웨어에서 사용할 수 있습니다.이들의 구축은 마이클과 [19]스콧의 잠금 해제 대기열을 확장시켰는데, 이는 실제로 자주 사용되는 효율적인 대기열입니다.Kogan과 Petrank의[20] 후속 논문은 대기 알고리즘을 빠르게 만드는 방법을 제공했으며, 이 방법을 사용하여 대기 대기열을 잠금 없는 것과 거의 같은 속도로 만들었습니다.Timnat과 Petrank의[21] 후속 논문은 잠금 없는 데이터 구조에서 대기 없는 데이터 구조를 생성하는 자동 메커니즘을 제공했습니다.따라서 현재 많은 데이터 구조에서 대기 시간 없이 구현할 수 있습니다.

잠금 프리

잠금 프리덤을 사용하면 개별 스레드가 부족해질 수 있지만 시스템 전체의 throughput은 보증됩니다.프로그램 스레드가 충분히 오랜 시간 실행되었을 때 스레드 중 적어도 하나가 진행되면 알고리즘은 잠기지 않습니다(진행의 합리적인 정의를 위해).모든 대기 알고리즘은 잠기지 않습니다.

특히, 1개의 스레드가 정지되어 있는 경우, 록프리 알고리즘은 나머지 스레드가 계속 진행되도록 보증합니다.따라서 두 스레드가 동일한 뮤텍스 잠금 또는 스핀 잠금을 경쟁할 수 있는 경우 알고리즘은 잠금이 해제되지 않습니다(잠금이 유지되는 스레드 중 하나를 일시 중단하면 두 번째 스레드는 차단됩니다).

일부 프로세서에 의한 동작이 한정된 수의 스텝으로 성공하는 경우가 무한히 많으면 알고리즘은 잠기지 않습니다.예를 들어, 만약N프로세서가 작업을 실행하려고 합니다.N프로세스는 한정된 수의 절차로 작업을 완료하는 데 성공하며 다른 프로세스가 실패하여 실패 시 재시도할 수 있습니다.wait-free와 lock-free의 차이점은 각 프로세스에 의한 wait-free 동작은 다른 프로세서에 관계없이 한정된 수의 스텝으로 성공이 보장된다는 것입니다.

일반적으로 잠금 없는 알고리즘은 자체 조작 완료, 방해 조작 지원, 방해 조작 중단 및 대기라는 4가지 단계로 실행할 수 있습니다.자신의 수술을 완료하는 것은 동시에 도움을 받고 낙태를 할 수 있기 때문에 복잡하지만, 언제나 가장 빠른 완성의 길이다.

장애물이 발생했을 때 언제 지원, 중단 또는 대기할지에 대한 결정은 컨텐션 관리자의 책임입니다.이는 매우 단순하거나(우선도가 높은 작업을 지원하거나, 우선순위가 낮은 작업을 중단하거나), 스루풋을 개선하거나, 우선순위가 높은 작업의 지연을 줄이도록 최적화될 수 있습니다.

올바른 동시 지원은 일반적으로 잠금 프리 알고리즘에서 가장 복잡한 부분이며 종종 실행 비용이 많이 듭니다. 보조 스레드의 속도가 느려질 뿐만 아니라 공유 메모리의 메커니즘 덕분에 보조 스레드가 여전히 실행 중일 경우 속도가 느려집니다.

방해를 받지 않다

방해 자유는 자연적 무차단 진행 보장 중 가장 약한 것입니다.알고리즘은 어느 시점에서든 한정된 수의 스텝에 대해 격리된 상태로 실행되는(즉, 모든 방해 스레드를 매달아 놓은 상태) 단일 스레드가 [15]동작을 완료할 경우 장애물이 없다.모든 잠금 없는 알고리즘은 장애물이 없습니다.

장애물이 없는 경우 부분적으로 완료된 작업만 중단하고 변경 사항을 롤백해야 합니다.동시 지원을 끊으면 검증이 훨씬 더 쉬운 알고리즘이 생성되는 경우가 많습니다.컨텐션 매니저는 시스템의 지속적인 라이브 잠금을 방지하는 작업을 수행합니다.

일부 장애물이 없는 알고리즘은 데이터 구조에서 한 쌍의 "일관성 마커"를 사용합니다.데이터 구조를 읽는 프로세스는 먼저 하나의 일관성 마커를 읽은 후 관련 데이터를 내부 버퍼로 읽고 다른 마커를 읽은 후 마커를 비교합니다.두 마커가 동일한 경우 데이터가 일관됩니다.데이터 구조를 업데이트하는 다른 프로세스에 의해 판독이 중단되면 마커가 동일하지 않을 수 있습니다.이 경우 프로세스는 내부 버퍼 내의 데이터를 폐기하고 다시 시도합니다.

「 」를 참조해 주세요.

레퍼런스

  1. ^ Göetz, Brian; Peierls, Tim; Bloch, Joshua; Bowbeer, Joseph; Holmes, David; Lea, Doug (2006). Java concurrency in practice. Upper Saddle River, NJ: Addison-Wesley. p. 41. ISBN 9780321349606.
  2. ^ Herlihy, M.; Luchangco, V.; Moir, M. (2003). Obstruction-Free Synchronization: Double-Ended Queues as an Example (PDF). 23rd International Conference on Distributed Computing Systems. p. 522.
  3. ^ Butler W. Lampson; David D. Redell (February 1980). "Experience with Processes and Monitors in Mesa". Communications of the ACM. 23 (2): 105–117. CiteSeerX 10.1.1.142.5765. doi:10.1145/358818.358824. S2CID 1594544.
  4. ^ 기욤 마르세, 칼 킹스포드입니다"k-mer 발생의 효율적인 병렬 계수를 위한 빠르고 잠금 없는 접근법"생물정보학(2011) 27(6): 764-770. doi:10.1093/btr011 "젤리피쉬 머 카운터"
  5. ^ Harris, Tim; Fraser, Keir (26 November 2003). "Language support for lightweight transactions" (PDF). ACM SIGPLAN Notices. 38 (11): 388. CiteSeerX 10.1.1.58.8466. doi:10.1145/949343.949340.
  6. ^ Harris, Tim; Marlow, S.; Peyton-Jones, S.; Herlihy, M. (June 15–17, 2005). "Composable memory transactions". Proceedings of the 2005 ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP '05 : Chicago, Illinois. New York, NY: ACM Press. pp. 48–60. doi:10.1145/1065944.1065952. ISBN 978-1-59593-080-4.
  7. ^ libcds - 잠기지 않는 컨테이너 및 안전한 메모리 회수 스키마의 C++ 라이브러리
  8. ^ liblfds - C로 작성된 잠금 없는 데이터 구조 라이브러리
  9. ^ 동시성 키트 - 논블로킹 시스템 설계 및 구현용 C 라이브러리
  10. ^ 허브 서터."Lock-Free Code: A False Sense of Security". Archived from the original on 2015-09-01.
  11. ^ 허브 서터."Writing Lock-Free Code: A Corrected Queue". Archived from the original on 2008-12-05.
  12. ^ 허브 서터."일반화 동시 큐 쓰기"
  13. ^ 허브 서터.'잠금 문제'
  14. ^ 브루스 도슨입니다"ARM 및 잠금 없는 프로그래밍"
  15. ^ a b 앤서니 윌리엄스."안전성: 오프: C++ 원자력으로 자신의 발을 쏘지 않는 방법" 2015. 페이지 20.
  16. ^ Herlihy, Maurice P. (1988). Impossibility and universality results for wait-free synchronization. Proc. 7th Annual ACM Symp. on Principles of Distributed Computing. pp. 276–290. doi:10.1145/62546.62593. ISBN 0-89791-277-2.
  17. ^ Fich, Faith; Hendler, Danny; Shavit, Nir (2004). On the inherent weakness of conditional synchronization primitives. Proc. 23rd Annual ACM Symp.on Principles of Distributed Computing (PODC). pp. 80–87. doi:10.1145/1011767.1011780. ISBN 1-58113-802-4.
  18. ^ Kogan, Alex; Petrank, Erez (2011). Wait-free queues with multiple enqueuers and dequeuers (PDF). Proc. 16th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 223–234. doi:10.1145/1941553.1941585. ISBN 978-1-4503-0119-0.
  19. ^ Michael, Maged; Scott, Michael (1996). Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms. Proc. 15th Annual ACM Symp. on Principles of Distributed Computing (PODC). pp. 267–275. doi:10.1145/248052.248106. ISBN 0-89791-800-2.
  20. ^ Kogan, Alex; Petrank, Erez (2012). A method for creating fast wait-free data structures. Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 141–150. doi:10.1145/2145816.2145835. ISBN 978-1-4503-1160-1.
  21. ^ Timnat, Shahar; Petrank, Erez (2014). A Practical Wait-Free Simulation for Lock-Free Data Structures. Proc. 17th ACM SIGPLAN Symp. on Principles and Practice of Parallel Programming (PPOPP). pp. 357–368. doi:10.1145/2692916.2555261. ISBN 978-1-4503-2656-8.

외부 링크