Concurrent Programming and `Linearization’
Concurrent Programming 혹은 병행 프로그래밍에서 겪게되는, 혹은 고민하게 되는 문제가 있다.
동시에 복수의 스레드가 뭔가 실행하고 있을 때 “순서"라는건 어떤 의미인가?
두 개 이상의 프로세서가 있는 시스템에서, 두 스레드가 하나의 공유 queue에 아이템을 집어넣었다. 이 두 스레드의 enq() 호출이 같은 시점에 호출되었다면 “순서"는 어떤 개념이 되는가?
각 순간을 적당히 잘라서 말하면 다음과 같은 순서라고 치자. (편의상 두 스레드를 A, B라고 치고 이 둘은 x, y를 빈 상태인 큐 q에 넣는다고 하겠다)
- A가 q.enq(x)를 호출(invoke)
- B가 q.enq(y)를 호출
- B의 q.enq(y)가 true 반환
- A의q.enq(x)가 true 반환
- 결과적으로 q에는 [x, y] 형태로 아이템이 들어있다고 치자(x가 queue의 head 쪽).
이 때 순서를 어떤 식으로 정하는게 생각하기 편하고 / 프로그램을 검증(program correctness를 검증)하는데 편할까?
- 호출 순서대로 생각해서 A의 enq(x)와 B의 enq(y)가 순서대로 일어난 걸로 생각한다
- 응답 순서대로 생각해서 B의 enq가 먼저 일어난 걸로 생각한다.
- q의 상태(삽입된 x, y의 상대적인 순서)에 달렸다
실제로 사용되는 방법은 c 이다. 이 때 배경에 깔려있는 아이디어가 선형화(linearization)인데1 다음과 같은 정의/특징을 지닌다.
- 선형화할 수 있는(linerizable) 객체(혹은 타입?)의 모든 멤버 함수는 호출 시작(invocation) / 응답(response) 사이의 어느 시점에 그 효과가 원자적으로 나타난다.
- 혹은 다시 말해서, 호출 시작 / 응답 사이의 어느 한 시점에 그 함수가 실행한 결과가 다른 스레드들에 “순간적으로” 보이게 만든다. 이 지점을 linearization point라 부른다.
이런 성질을 가지면 동시에 진행 중인 중첩된 함수 호출들의 순서를 생각하기 매우 편하게 재배치 할 수 있다. 게다가 그 재배치가 인간의 직관에 부합하게 동작한다. 인간의 직관에 부합한다는 의미는, 생각하기 편한(?) 싱글 스레드 프로그램 처럼 동작한다는 것, 혹은 그렇게 생각하게 해주는 수단을 부여한다는 것.
이 “선형화"를 다음과 같은 방식으로 진행하게 되는데, 위에서 언급한 것을 포함해서 몇 가지 용어를 쓴다.
- 함수(혹은 객체의 메서드 or 멤버 함수) 호출(call)은 ‘메서드 호출 시작(method invocation)‘과 ‘메서드 응답(method response)‘로 구성된다.
- 어떤 객체(혹은 프로그램 전체 상태)의 순차 명세(sequential specification)란, 각 객체 상태에 대해 특정 메서드가 호출되었을 때 어느 상태로 가는지에 관한 정의다.
- History란 어떤 객체에 적용된 일련의 메서드 호출들의 목록이다.
- Sequential history는 단일 스레드가 일련의 메서드 호출을 했을 때 나타나는 유효한 history다.
병행 프로그래밍에서 객체를 쉽게 다루려면, 그 객체가 선형화 가능한 녀석이면 된다. 선형화 가능한지는 위의 용어를 사용해서, 다음과 같이 될 수 있는지 판단한다
- History(의 메서드 시작/응답)를 재배열해서 sequential history로 바꿀 수 있으며,
- 이 history는 sequential spec.을 만족하며,
- 원본 history에서 특정 메서드 응답R0가 특정 메서드 호출 I1 보다 앞선다면, 재배열된 history에서도 R0가 I1보다 먼저 나와야 한다.2
이 조건들이 만족되면 선형화가능한 객체(혹은 프로그램 상태)인 것이고, 이렇게 바꾼 sequential history로 프로그램을 다시 해석할 수 있다. 위의 예에서는 [] -> [x] -> [x, y] 순으로 q의 상태가 변해간 것으로 추정되기에, 단일 스레드에서 enq(x), enq(y)가 아예 순서대로 일어난 것처럼 생각할 수 있다.
이를 이용해서, 선형화 가능한 객체라면, 각 스레드가 실행하는 병행 함수는 어느 시점엔가 다른 스레드가 볼 수 있는 형태로 (완성된) 결과를 내놓고, 이 시점들을 기준으로 특정 이벤트가 일어난 걸 생각한다는 것이다. 함수 호출시작/응답은 응답 뒤에 다른 함수 호출이 없는 정지 기간(quiscent period)가 없는 이상 절대적인 기준이 되지 못한다는 점에 주의하자.3