운영체제 22. 락 기반의 병행 자료 구조

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

• 자료구조에 락을 추가하면 해당 자료구조를 경쟁 조건으로부터 안전한 쓰레드 사용(thread safe) 자료 구조로 만들 수 있다. 락이 어떤 방식으로 추가되었느냐에 따라 그 자료구조의 정확성과 성능이 좌우된다.

22.1 병행 카운터

• 카운터는 가장 간단한 자료구조 중 하나이다. 보편적으로 사용되는 구조이면서 인터페이스가 간단하다.
  • 간단하지만 확장성이 없다.
• 이 병행이 가능한 카운터는 간단하지만 정확하게 동작한다. 사실 이 카운터는 가장 간단하고 가장 기본적인 병행 자료 구조의 보편적인 디자인 패턴을 따른다. 자료구조를 조작하는 루틴을 호출할 때 락을 추가했고, 그 호출문이 리턴될 때 락이 해제되도록 하였다. 이 방식은 모니터(monitor)를 사용하여 만든 자료구조와 유사하다. 모니터 기법은 객체에 대한 메소드를 호출하고 리턴할 때 자동적으로 락을 획득하고 해제한다.
• 이성적으로 하나의 쓰레드가 하나의 CPU에서 작업을 끝내는 것처럼 멀티 프로세서에서 실행되는 쓰레드들도 빠르게 작업을 처리하고 싶을 것이다. 이와 같이 동작하는 것을 완벽한 확장성(perfect scaling)이라 한다. 완벽한 확장성이 담보되는 환경에서는 작업량이 CPU개수에 비례하여 증가하더라도 각 작업이 병렬적으로 처리되어 전체 완료 시간이 늘어나지 않는다는 것을 말한다.

확장성 있는 카운팅

근사 카운터(approximate counter)

• 근사 카운터는 하나의 논리적 카운터로 표현되는데, CPU 코어마다 존재하는 하나의 물리적인 지역 카운터와 하나의 전역 카운터로 구성되어 있다. 어떤 기기가 네 개의 CPU를 갖고 있다면 그 시스템은 네 개의 지역 카운터와 하나의 전역 카운터를 갖고 있다. 이 카운터들 외에 지역 카운터를 위한 락들과 전역 카운터를 위한 락이 존재한다.
• 근사 카운터의 기본 개념은 다음과 같다. 쓰레드는 지역 카운터를 증가시킨다. 이 지역 카운터는 지역 락에 의해 보호된다. 각 CPU는 저마다 지역 카운터를 갖기 때문에 CPU들에 분산되어있는 쓰레드들은 지역 카운터를 경쟁없이 갱신할 수 있다. 그러므로 카운터 갱신은 확장성이 있다.
• 쓰레드는 전역 카운터를 읽어서 카운터 값을 판단한다. 전역 카운터의 값은 주기적으로 지역 카운터 값을 반영하여 주기적으로 갱신되어야 한다. 전역 락을 사용하여 지역 카운터의 값을 전역 카운터의 값에 더하고, 그 지역 카운터의 값은 0으로 초기화 한다.
• 지역에서 전역으로 값을 전달하는 빈도는 정해놓은 S값에 의해 결정된다. S의 값이 작을수록 (갱신 빈도가 클수록) 카운터의 확장성이 없어지면, 갱신 빈도가 작을수록(S값이 클 수록) 전역 카운터 값과 실제 카운터 값이 일치하지 않을 확률이 커진다. 정확한 카운터 값을 계산하기 위해, 모든 지역 카운터와 전역 카운터에 대한 락을 획득한 후 계산하면 된다. 락 연산으로 인한 선능의 하락이 심각할 수 있다. 또 지역 카운터에 대한 락을 획득하는 순서를 적절히 제어하지 않으면 교착상태가 발생한다.

22.2 병행 연결 리스트

확장성 있는 연결 리스트

• 병행이 가능한 연결리스트를 갖게 되었지만 확장성이 좋지 않다는 문제가 있다. 병행성을 개선하는 방법 중 하나로 hand-over-hand locking(또는 coupling) 이라는 기법을 개발했다.
• 개념은 단순하다. 전체 리스트에 하나의 락이 있는 것이 아니라 개별 노드마다 락을 추가하는 것이다. 리스트를 순회할 때 다음 노드의 락을 먼저 획득하고 지금 노드의 락을 해제하도록 한다.
• 개념적으로는, 리스트 연산에 병행성이 높아지기 때문에 괜찮은 것처럼 보인다. 하지만 실제로는 간단한 락 방법에 비해 속도 개선을 기대하기가 쉽지 않다. 리스트를 순회할 때 각 노드에 락을 획득하고 해제하는 오버헤드가 매우 크기 때문이다. 아주 큰 리스트를 굉장히 많은 수의 쓰레드가 병행적으로 순회한다 해도 락을 하나만 사용하는 것보다 빠르기 어렵다. 차라리 일정 개수의 노드를 처리할 때마다 하나의 새로운 락을 획득하는 하이브리드 방식이 더 가치있어 보인다.

22.3 병행 큐

• 어떤 자료 구조를 병행연산에 대해 보호하기 위한 가장 쉬운 방법은 자료구조 전체에 락을 하나 두는것이다. 이 방법이 쉽기 때문에 많이 사용된다. 병행 큐는 다른 방법을 사용한다.
• 두 개의 락을 가지고 있는데, 하나는 큐의 헤드에, 다른 하나는 테일에 사용되는 것을 알 수 있다. 이 두 개의 락의 목적은 큐에 삽입과 추출연산에 병행성을 부여하는 것이다. 일반적인 경우에는 삽입 루틴이 테일 락을 접근하고 추출연산이 헤드 락 만을 다룬다.
• 큐 초기화 코드에 더미(dummy)노드 하나를 추가했다. 이 더미노드는 헤드와 테일연산을 구분하는데 사용되었다.
• 큐는 멀티 쓰레드 프로그램에서 자주 사용된다. 하지만 방금 다룬 락만 존재하는 큐는 실제 프로그램에서 사용할 수 없다. 큐가 비었거나 가득 찬 경우, 쓰레드가 대기하도록 하는 기능이 필요하다.