동기화 및 데이터 경쟁 없음
동기화 메커니즘은 공유 데이터에 안전하게 접근할 수 있도록 동시 스레드를 조정하며, 데이터 경쟁 없음은 동시 프로그램의 예측 가능성을 높이는 속성입니다.
Definition
동기화는 공유 자원에 대한 순서 지정 또는 상호 배제를 강제하기 위한 동시 활동의 조정이며, 데이터 경쟁 없음은 두 스레드가 개입하는 동기화 없이 적어도 하나가 쓰기 작업을 수행하면서 동일한 메모리 위치에 동시에 접근하지 않는 속성입니다.
Scope
이 주제는 공유 상태에 대한 동시 접근을 올바르게 만드는 메커니즘과 속성들을 다룹니다: 상호 배제, 잠금, 세마포어 및 모니터, 조건 변수, 잠금 없는(lock-free) 및 대기 없는(wait-free) 알고리즘, 트랜잭션 메모리, 선행 발생(happens-before) 관계, 그리고 데이터 경쟁 감지. 또한 교착 상태, 원자성, 그리고 프로그램이 데이터 경쟁 없이 유지되기 위해 필요한 규율에 대해서도 다룹니다.
Core questions
- 상호 배제는 어떻게 달성되며 그 위험(교착 상태, 기아 상태)은 무엇입니까?
- 잠금 기반 동기화와 잠금 없는 동기화의 차이점은 무엇입니까?
- 선행 발생(happens-before) 관계는 데이터 경쟁을 어떻게 정의합니까?
- 데이터 경쟁은 어떻게 자동으로 감지될 수 있습니까?
Key theories
- 상호 배제
- Dijkstra의 동시 제어 문제 해결책은 상호 배제를 기본적인 동기화 요구 사항으로 확립하여, 임계 구역이 동시에 실행되지 않도록 보장합니다.
- 트랜잭션 메모리
- Herlihy와 Moss는 메모리 작업 그룹이 원자적으로 실행되는 트랜잭션 메모리를 제안했으며, 이는 동시 데이터 구조를 구축하기 위한 세분화된 잠금에 대한 구성 가능한 대안을 제공합니다.
- 선행 발생(Happens-before) 및 동적 경쟁 감지
- Lamport의 선행 발생(happens-before) 관계를 기반으로 한 Eraser 감지기는 잠금 규율을 확인하여 데이터 경쟁을 동적으로 찾는 방법을 보여주었으며, 이는 자동화된 경쟁 감지의 예시입니다.
Clinical relevance
올바른 동기화는 신뢰할 수 있는 동시 및 병렬 소프트웨어에 필수적입니다. 데이터 경쟁은 실제에서 가장 찾기 어려운 버그 중 일부를 유발합니다. 경쟁 감지기, 트랜잭션 메모리, 그리고 규율 있는 동기화 패턴은 신뢰할 수 있는 다중 스레드 시스템을 구축하기 위한 핵심 도구입니다.
History
Dijkstra의 1965년 상호 배제 해결책과 그 후의 세마포어는 동기화의 기초를 세웠고, 이어서 Hoare와 Brinch Hansen의 모니터가 등장했습니다. Lamport의 1978년 선행 발생(happens-before) 관계는 현대 경쟁 정의의 기반이 됩니다. Herlihy와 Moss는 1993년에 트랜잭션 메모리를 도입했으며, Eraser(1997)와 같은 동적 경쟁 감지기와 이후의 선행 발생 도구들은 동시성 디버깅의 표준이 되었습니다.
Debates
- 잠금 방식 대 잠금 없는 방식 및 트랜잭션 방식
- 설계자들은 단순하지만 교착 상태와 낮은 구성 가능성에 취약한 전통적인 잠금 기반 동기화와, 복잡성 또는 오버헤드 비용으로 구성 가능성과 진행 보장을 개선하는 잠금 없는 알고리즘 및 트랜잭션 메모리 사이에서 논쟁합니다.
Key figures
- Edsger Dijkstra
- Leslie Lamport
- Maurice Herlihy
- C. A. R. Hoare
- Stefan Savage
Related topics
Seminal works
- dijkstra1965
- herlihy1993
- savage1997
- lamport1978
Frequently asked questions
- 데이터 경쟁이란 무엇입니까?
- 데이터 경쟁은 두 스레드가 동일한 메모리 위치에 동시에 접근하고, 적어도 하나의 접근이 쓰기이며, 접근이 동기화에 의해 순서가 지정되지 않아 대부분의 메모리 모델에서 정의되지 않거나 예측 불가능한 동작을 초래할 때 발생합니다.
- 잠금 기반 동기화와 잠금 없는 동기화의 차이점은 무엇입니까?
- 잠금 기반 동기화는 상호 배제를 사용하여 한 번에 하나의 스레드만 임계 구역에 진입하도록 하는 반면, 잠금 없는 동기화는 원자적 연산을 사용하여 잠금을 보유하지 않고도 일부 스레드가 항상 진행하도록 보장하여 교착 상태를 방지합니다.