Concurrent Programming and `Linearization’

Concurrent Programming 혹은 병행 프로그래밍에서 겪게되는, 혹은 고민하게 되는 문제가 있다.

동시에 복수의 스레드가 뭔가 실행하고 있을 때 “순서”라는건 어떤 의미인가?

두 개 이상의 프로세서가 있는 시스템에서, 두 스레드가 하나의 공유 queue에 아이템을 집어넣었다. 이 두 스레드의 enq() 호출이 같은 시점에 호출되었다면 “순서”는 어떤 개념이 되는가?

각 순간을 적당히 잘라서 말하면 다음과 같은 순서라고 치자. (편의상 두 스레드를 A, B라고 치고 이 둘은 x, y를  빈 상태인 큐 q에 넣는다고 하겠다)

1. A가 q.enq(x)를 호출(invoke)
2. B가 q.enq(y)를 호출
3. B의 q.enq(y)가 true 반환
4. A의q.enq(x)가 true 반환
5. 결과적으로 q에는 [x, y] 형태로 아이템이 들어있다고 치자(x가 queue의 head 쪽).

이 때 순서를 어떤 식으로 정하는게 생각하기 편하고 / 프로그램을 검증(program correctness를 검증)하는데 편할까?

a. 호출 순서대로 생각해서 A의 enq(x)와 B의 enq(y)가 순서대로 일어난 걸로 생각한다
b. 응답 순서대로 생각해서 B의 enq가 먼저 일어난 걸로 생각한다.
c. q의 상태(삽입된 x, y의 상대적인 순서)에 달렸다

실제로 사용되는 방법은 c 이다.  이 때 배경에 깔려있는 아이디어가 선형화(linearization)인데 ((수학에서 말하는 선형화(특정 함수의 1차 근사)같은 것과는 관련이 없다. 여러 개의 스레드가 별도로 볼 시간 축을 하나의 시간 축에서 본다 정도의 의미가 된다)) 다음과 같은 정의/특징을 지닌다.

• 선형화할 수 있는(linerizable) 객체(혹은 타입?)의 모든 멤버 함수는 호출 시작(invocation) / 응답(response) 사이의 어느 시점에 그 효과가 원자적으로 나타난다
• 혹은 다시 말해서, 호출 시작 / 응답 사이의 어느 한 시점에 그 함수가 실행한 결과가 다른 스레드들에 “순간적으로” 보이게 만든다 ((이 지점을 linearization point라 부른다)) 

이런 성질을 가지면 동시에 진행 중인 중첩된 함수 호출들의 순서를 생각하기 매우 편하게 재배치 할 수 있다. 게다가 그 재배치가 인간의 직관에 부합하게 동작한다. 인간의 직관에 부합한다는 의미는, 생각하기 편한(?) 싱글 스레드 프로그램 처럼 동작한다는 것, 혹은 그렇게 생각하게 해주는 수단을 부여한다는 것.

이 “선형화”를 다음과 같은 방식으로 진행하게 되는데, 위에서 언급한 것을 포함해서 몇 가지 용어를 쓴다.

• 함수(혹은 객체의 메서드 or 멤버 함수) 호출(call)은 ‘메서드 호출 시작(method invocation)’과 ‘메서드 응답(method response)’로 구성된다.
• 어떤 객체(혹은 프로그램 전체 상태)의 순차 명세(sequential specification)란, 각 객체 상태에 대해 특정 메서드가 호출되었을 때 어느 상태로 가는지에 관한 정의다.
• History란 어떤 객체에 적용된 일련의 메서드 호출들의 목록이다.
• Sequential history는 단일 스레드가 일련의 메서드 호출을 했을 때 나타나는 유효한 history다.

병행 프로그래밍에서 객체를 쉽게 다루려면, 그 객체가 선형화 가능한 녀석이면 된다. 선형화 가능한지는 위의 용어를 사용해서, 다음과 같이 될 수 있는지 판단한다

1. History(의 메서드 시작/응답)를 재배열해서 sequential history로 바꿀 수 있으며,
2. 이 history는 sequential spec.을 만족하며,
3. 원본 history에서 특정 메서드 응답R0가 특정 메서드 호출 I1 보다 앞선다면, 재배열된 history에서도 R0가 I1보다 먼저 나와야 한다. ((이 조건은 먼저 완전히 끝난 I0, R0 쌍의 효과가 원자적인 것처럼 보이긴 하므로,  순차적으로는 I0, R0가 나온 후에야 I1 호출 시작이 나올 수 있단 소리다))

이 조건들이 만족되면 선형화가능한 객체(혹은 프로그램 상태)인 것이고, 이렇게 바꾼 sequential history로 프로그램을 다시 해석할 수 있다.  위의 예에서는 [] -> [x] -> [x, y] 순으로 q의 상태가 변해간 것으로 추정되기에, 단일 스레드에서 enq(x), enq(y)가 아예 순서대로 일어난 것처럼 생각할 수 있다.

이를 이용해서, 선형화 가능한 객체라면, 각 스레드가 실행하는 병행 함수는 어느 시점엔가 다른 스레드가 볼 수 있는 형태로 (완성된) 결과를 내놓고, 이 시점들을 기준으로 특정 이벤트가 일어난 걸 생각한다는 것이다. 함수 호출시작/응답은 응답 뒤에 다른 함수 호출이 없는 정지 기간(quiscent period)가 없는 이상 절대적인 기준이 되지 못한다는 점에 주의하자. ((그래서 함수 호출 시작이나 응답한 시간을 어떤 병행 이벤트를 하나의 시간축에 합쳐서 생각할 때는 덜 중요하게 생각한다))

실제 코드에서 이를 설명하는 것이나, 혹은 유용성을 자세히 설명하는건 다음 기회로(…)