1. 개요
자료 구조에 락을 추가하면 해당 자료 구조를 경쟁조건으로부터 안전한 자료 구조로 만들 수 있다.
락이 어떤 방식으로 추가되었느냐에 따라 그 자료 구조의 정확성과 성능이 좌지우지된다.
2. 병행 카운터
카운터는 가장 간단한 자료 구조 중 하나이다.
간단하지만 정확하게 동작한다.
하지만 스레드 개수가 늘어날수록 성능은 더 나빠지기만 한다.
이상적으로는 하나의 스레드가 하나의 CPU에서 작업을 끝내는 것처럼 멀티프로세서에서 실행되는 스레드들도 빠르게 작업을 처리하고 싶을 것이다.
이와 같이 동작하는 것을 완벽한 확장성(perfect scaling)이라 한다.
완벽한 확장성이 담보되는 환경에서는 작업양이 CPU의 개수에 비례하여 증가하더라도 각 작업이 병렬적으로 처리되어 전체 완료 시간이 늘어나지 않는 것을 말한다.
확장성 문제를 해결하기 위해 근사 카운터(approximate counter)라고 불리는 기법이 개발되었다.
근사 카운터는 하나의 논리적 카운터로 표현되는데, CPU 코어마다 존재하는 하나의 물리적인 지역 카운터와 하나의 전역 카운터로 구성되어 있다.
어떤 기기가 4개의 CPU를 가지고 있다면 그 시스템은 4개의 지역 카운터와 1개의 전역 카운터를 가지고 있다.
3. 병행 연결 리스트
이제 조금 더 복잡한 구조인 연결 리스트를 다뤄보자.
매우 드문 경우지만, malloc()의 실패할 경우에 미묘한 문제가 생길 수 있다.
그런 경우가 발생한다면 실패를 처리하기 전에 락을 해제해야 한다.
병행이 가능한 연결 리스트를 갖게 되었지만 확장성이 좋지 않다는 문제가 있다.
병행성을 개선하는 방법 중 하나로 hand-over-hand locking이라는 기법을 개발했다.
개념은 단순하다.
전체 리스트에 하나의 락이 있는 것이 아니라 개별 노드마다 락을 추가하는 것이다.
하지만 실제로는 간단한 락 방법에 비해 속도 개선을 기대하기가 쉽지 않다.
리스트를 순회할 때 각 노드에 락을 획득하고 해제하는 오버헤드가 매우 크기 때문이다.
4. 병행 큐
어떤 자료 구조를 병행연산에 대해 보호하기 위한 가장 쉬운 방법은 자료 구조 전체 락을 하나 두는 것이다.
큰 락인 셈이다.
이 방법이 많이 사용된다.
쉽기 때문이다.
두 개의 락이 있는데, 하나는 큐의 헤드에, 다른 하나는 테일에 사용되는 것을 알 수 있다.
이 두 개 락의 목적은 큐에 삽입과 추출 연산에 병행성을 부여하는 것이다.
큐는 멀티 스레드 프로그램에서 자주 사용된다.
하지만 방금 다룬 락만 존재하는 큐는 실제 프로그램에서 사용할 수 없다.
큐가 비었거나 가득 찬 경우, 스레드가 대기하도록 하는 기능이 필요하다.
유한 큐를 만드는 법에 대해 다음 장에서 다룰 것이다.
5. 병행 해시 테이블
많이 사용되는 병행 자료 구조인 해시 테이블을 다루면서 이번 장의 논의를 마무리짓고자 한다.
성능이 우수한 이유는 전체 자료 구조에 하나의 락을 사용한 것이 아니라 해시 버켓마다 락을 사용하였기 때문이다.
이렇게 하면 병행성이 좋아진다.
