29. 락 기반의 병행 자료구조

운영체제: 가장 쉬운 세가지 이야기 - Operating Systems: Three Easy Pieces를 바탕으로 작성하였습니다.

---

 

락 기반의 병행 자료구조

- 락을 사용하지 않는 병행 자료구조도 존재한다!

- Correctness와 Performance의 관점에서 자료구조를 평가한다.

 

1. 병행 카운터

- 간단한 방식으로 모니터 기법과 유사한 방식을 사용한다. 즉 호출할 때 락 할당. 리턴 시 락을 해제한다.

- 매우 간단하나 성능 문제가 있다.

- 즉, 확장성없이 다수의 쓰레드로 카운팅 시 성능이 낮아진다.

 

1.1 확장성있는 카운팅

- 근사 카운팅 방식이 흔히 사용된다.

- 근사 카운팅 방식에서는 하나의 전역 카운터와 전역 락, CPU 마다 지역 카운터와 지역 카운터 락이 사용된다.

1. 각 CPU 내 지역 카운터와 락을 통해 쓰레드 간 경쟁없이 카운팅을 수행할 수 있다.

2. 일정 S값마다 전역 카운터 값을 CPU 중 하나의 지역 카운터 값을 통해 업데이트하고, 해당 지역 카운터 값을 초기화한다. S값은 Threshold와 같다.

3. 각 쓰레드는 전역 카운터 값을 통해 현재 카운터 값을 확인한다.

4. S값이 낮을수록 카운터의 정확도는 높아지나, 확장성이 떨어져 속도가 낮아진다. S값이 낮아질 수록 근사 카운팅을 하는 의미가 없어진다.

 

2. 병행 연결 리스트

- malloc()은 thread safe 하기 때문에 락/언락으로 소스 코드를 감쌀 필요가 없다.

- 리스트 갱신 코드만 락/언락으로 소스 코드를 감싼다.

 

2.1 확장성 있는 연결 리스트

- 하나의 리스트에 락을 거는 것이 아닌 노드마다 락을 건다.

- 여러 개의 쓰레드가 여러 노드를 병행 처리해 성능이 개선될 것 같지만 개별 노드 락/언락 비용 때문에 성능 개선을 기대하기 힘들다.

 

3. 병행 큐

- 자료구조 전체에 락을 두는 방법이 간단해서 가장 많이 사용된다.

- 조금 더 병행성이 좋은 방법으로, 큐의 head와 tail에 락을 거는 방법이 있다. 

 

4. 병행 해시 테이블

- 전체 자료구조가 아닌 리스트로 구현된 해시 버킷에 락을 건다.

- 확장성이 좋아 많이 사용된다.

 

ㅁ 락/언락 시 코드의 흐름에 주의

ㅁ 병행성 개선이 반드시 성능의 개선으로 이어지지는 않는다.

ㅁ 성능 개선은 성능에 문제가 있을 때만 진행한다.

ㅁ 미숙한 최적화(Knuth's Law): 간단한 것부터 시작한다. 성능에 문제가 있다고 판단되면 그 때 개선한다.