주의
Common problems in multi-core programming, Part 2: Heavily contended locks 중 핵심만 발췌 번역한 글이다.
과도한 잠금 경합
경쟁 조건을 방지하려고 잠금을 사용하면, 잠금에 대한 경합이 지나치게 발생하여 성능 문제가 불거질 수 있다. 잠금은 고속도로의 통행료 징수소와 같다. 징수원이 처리하는 속도보다 차가 빨리 도착하면 징수소 뒤로 차가 쌓이고 교통이 정체된다.
우선순위 역전 (Priority Inversion)
스레드에 우선순위를 지정하는 스레드 구현도 있다. 소프트웨어 스레드 모두를 돌리기에 하드웨어 스레드가 부족하면 우선순위가 높은 소프트웨어 스레드가 우선권을 가진다.
예를 들어, 전경(Foreground) 작업이 배경(Background) 작업보다 우선순위가 높을 수도 있다. 우선순위는 유용하지만 역설적이게도 낮은 우선순위의 스레드 때문에 높은 우선순위의 스레드가 돌지 못하는 상황이 되기도 한다.
우선순위가 낮은 스레드가 가진 잠금을 우선순위가 높은 스레드가 획득해야 할 때, 스케줄러는 잠금이 풀릴 때까지 차단된 스레드의 우선순위를 올린다. 실제로 화성 탐사선 패스파인더의 문제도 우선순위 상속을 손 봐서 해결했다.
뮤텍스에 할당하는 우선순위에 상한값을 두는 방식도 있다. 상한 값은 해당 뮤텍스를 쥐게 될 스레드가 가질 수 있는 가장 높은 우선순위이다.
스레드가 뮤텍스를 획득하면 해당 스레드의 우선순위는 그 즉시 상한 값으로 뛰어올라 뮤텍스를 쥐고 있는 내내 유지된다. 우선순위 상한 스키마는 스레드의 우선순위를 높이는데 열중한다. 반면 우선순위 상속 스키마는 게을러서 필요한 상황이 아니면 스레드의 우선순위를 높이지 않는다.
윈도우의 뮤텍스는 기본적으로 우선순위 상속을 지원한다. Pthreads 의 뮤텍스는 우선순위 상속과 우선순위 상한 중 어느 것도 지원하지 않는다. 두 규약 모두 pthreads 표준에선 선택사항이다. 구현에 따라서 지원할 수도, 그렇지 않을 수도 있다.
경합이 심한 잠금
경합이 심한 잠금을 겪게 되었을 때 프로그래머의 첫 번째 반응은 더 빠른 잠금이 필요해이다. 실제로 일부 잠금 구현은 느리기로 악명 높다. 더 빠른 잠금도 존재한다. 하지만 잠금이 얼마나 빠르던 간에 잠금은 본질적으론 스레드를 직렬화해야 한다. 잠금이 더 빠르면 상수 비율만큼 성능이 나아진다. 하지만 성능 확장성이 개선되진 않는다. 성능 확장성을 개선하려면 잠금을 없애거나 경합을 분산시켜야 한다.
앞서 교차 잠금에 관해 이야기하며 자원을 복제하여 잠금을 제거하는 기법을 언급하였다. 상황만 적절하다면 아주 좋은 방법이다.
특정 자원에 대한 잠금을 제거하지 못할 때는 자원을 분할(Partition)하고 분할된 부분마다 잠금을 따로 두는 방법을 고려하자. 분할은 경합을 여러 개의 잠금으로 분산시키는 효과가 있다. 예를 들어, 다수의 스레드가 동시에 삽입을 시도하는 해시 테이블 구현을 생각해보자.
경쟁 조건을 방지하는 단순한 접근 방법은 잠금을 하나 두고 테이블 전체를 보호하는 것이다. 이 잠금은 한 번에 한 스레드만 테이블에 접근하게 한다. 이러한 방법의 단점은 모든 스레드가 잠금 하나를 두고 경합을 벌여야 하고, 여기가 병목지점이 될 수 있다는 것이다. 이와는 달리 하위 테이블로 구성된 배열을 두고, 하위 테이블마다 잠금을 따로 두는 대안도 있다.
해싱 함수를 이용해 키와 하위 테이블을 엮으면 된다. 해시 함수가 키에 맞는 하위 테이블 인덱스를 반환하면 해당 스레드가 어느 테이블로 가야할 지 알 수 있다.
키 삽입은 하위 테이블 중 하나에 키를 해싱하는 일에서 시작된다. 그런 후 하위 테이블의 잠금을 붙잡고 있는 동안 그 하위 테이블에 삽입한다. 좋은 해시 함수가 있고 하위 테이블이 충분히 있다면, 같은 하위 테이블을 두고 경쟁하지 않을 것이며 따라서 동일한 잠금에 대해 경합을 벌이지 않는다.
잠금 여러 개를 활용해 경합을 분산시키는 아이디어는 세밀한 잠금으로 발전한다. 예를 들어, 해시 테이블은 일반적으로 여러 버켓을 모은 배열로 구현된다. 버켓마다 동일한 배열 요소로 해싱되는 키가 여럿 있다. 세밀한 잠금에서는 버켓마다 잠금을 둘 수도 있다.
이런 식으로 다수의 스레드가 동시에 병렬적으로 서로 다른 버켓에 접근 가능하다. 이 방식은 버켓의 개수가 고정되었을 때 구현하기 쉽다. 버켓의 개수가 늘어나면 문제는 복잡해진다. 배열의 크기를 다시 조정하려면 배열의 크기를 다시 조정하는 스레드뿐만 아니라 다른 스레드도 모두 필요하기 때문이다.
곧 설명할 테지만 단일 작성기 및 다중 판독기 (Reader-Writer) 잠금이 이런 문제를 풀 때 도움이 된다. 다른 문제도 있는데 버켓이 아주 작으면 잠금의 공간 부하가 주요 문제로 부상한다.
읽기는 많고 쓰기가 드문 데이터 구조라면, 단일 작성기 및 다중 판독기 잠금이 경합을 푸는데 도움이 될지 모른다. 단일 작성기 및 다중 판독기 잠금에선 작성기(Writer)와 판독기(Reader)를 구분한다. 여러 개의 판독기는 동시에 잠금을 획득할 수 있다. 하지만 한번에 단 하나의 판독기만 잠금을 획득할 수 있다. 작성기가 잠금을 확보한 동안에는 판독기(들)는 잠금을 얻지 못한다. 반대로 판독기가 잠금을 확보한 동안에는 작성기가 잠금을 얻지 못한다. 판독기는 작성기와 경합을 벌이지 판독기끼리는 경합을 벌이지 않는다.
앞서의 세밀한 해시 테이블 논의로 돌아가면, 동적으로 버켓 배열의 크기를 조정해야 할 때는 단일 작성기 및 다중 판독기 잠금이 도움이 된다. 구현 가능한 예를 들어보자. 테이블은 배열의 크기와 위치를 명시하는 배열 디스크립터로 구성된다. 작성기-판독기 뮤텍스가 이러한 구조를 보호한다. 버켓마다 자기만의 뮤텍스를 두는 것이다.
버켓에 접근하려면, 스레드마다 잠금이 둘 필요하다. 배열 디스크립터에 대한 판독기 잠금과 버켓의 뮤텍스에 대한 잠금 말이다. 버켓을 수정하려 할 때라도 스레드는 작성기 잠금이 아닌 판독기 잠금을 획득한다. 왜냐하면 판독기-작성기 뮤텍스가 버켓이 아닌 배열 디스크립터를 보호하기 때문이다.
어떤 스레드가 배열의 크기를 조정해야 할 때는 판독기-작성기 뮤텍스에 대한 작성기 잠금을 요청한다. 잠금을 허락 받으면, 경쟁 조건을 유발하지 않고도 배열 디스크립터를 안전하게 수정할 수 있다. 이 방법의 전반적인 장점이라면 배열의 크기를 다시 조정하는 동안에도 다른 버켓에 접근하는 여러 스레드는 계속해 일을 해나갈 수 있다는 것이다.
주요 단점이라면 스레드가 잠금을 하나가 아닌 둘이나 확보해야 한다는 것이다. 경합이 심하지 않은 테이블이라면 이러한 잠금 오버헤드의 증가가 되려 향상된 동시성의 이점을 압도해버린다.
작성기를 쓸 일이 별로 없다면, 단일 작성기 및 다중 판독기 잠금은 경합을 상당히 줄여준다. 하지만 단일 작성기 및 다중 판독기에는 제약이 있다. 판독기가 너무 자주 들어오면, 메모리 경합 문제를 겪을지 모른다. 단일 작성기 및 다중 판독기은 판독기 간의 잠금이 중간 정도일 때 매우 유용하다. 하지만 경합이 심할 때는 도움이 되지 않을지 모른다.
심한 경합을 다루는 좋은 방법은 병렬적으로 분해하여 경합을 낮추는 것이다. 예를 들어, 하위 테이블을 고정된 개수만큼 두되, 하위 테이블마다 세밀한 잠금을 두는 것도 가능하다.
