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) 사이의 어느 시점에 그 효과가 원자적으로 나타난다
  • 혹은 다시 말해서, 호출 시작 / 응답 사이의 어느 한 시점에 그 함수가 실행한 결과가 다른 스레드들에 “순간적으로” 보이게 만든다[2] 

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

 

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

  • 함수(혹은 객체의 메서드 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보다 먼저 나와야 한다.[3]

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

 

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

 

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

  1. 수학에서 말하는 선형화(특정 함수의 1차 근사)같은 것과는 관련이 없다. 여러 개의 스레드가 별도로 볼 시간 축을 하나의 시간 축에서 본다 정도의 의미가 된다 []
  2. 이 지점을 linearization point라 부른다 []
  3. 이 조건은 먼저 완전히 끝난 I0, R0 쌍의 효과가 원자적인 것처럼 보이긴 하므로,  순차적으로는 I0, R0가 나온 후에야 I1 호출 시작이 나올 수 있단 소리다 []
  4. 그래서 함수 호출 시작이나 응답한 시간을 어떤 병행 이벤트를 하나의 시간축에 합쳐서 생각할 때는 덜 중요하게 생각한다 []

Published by

rein

나는 ...

8 thoughts on “Concurrent Programming and `Linearization’”

  1. 저는 c 방법을 사용 하고 있는데, 멀티 쓰레드에서 c방법으로 들어간 객체가 쓰레드에서 그 순서에 맞게 뽑아 올순 있어도 연산을 뽑아온 순서로 처리 하지 않는다. 라는 경험 아래 “독립적이지 않으면 피보는구나” 싶었습니다.

    다음에 설명하는 것을 주의깊게 읽겠습니다.

  2. 세라비 / DB의 트랜잭션보다는 좀 더 객체간의 상호연관이 강할 때 쓰기 좋은 모델입니다. 굳이 Java Memory Model이 아니어도 구현할 수 있는 방법이긴 합니다. 몇 가지 조건만 충족되면 되는거라(…)

    Rica / …좀 더 자세히 설명해보지

    최익필 / c의 방법이 경험적으로도 꽤나 잘 통하는(?)방법입니다.

  3. 상호연관은 무슨 말씀이신지 모르겠지만, 기본적인 생각의 틀 자체가 DB의 Transaction Isolation (http://en.wikipedia.org/wiki/Isolation_(database_systems) ) 얘기랑 비슷한 것 같아서요.

    어느 시점에 transaction의 결과가 보일 것인가, transaction이 serialization이 가능한가? 와 같은 얘기.

    이런 걸 Programming Language 쪽에서 잘 하려면 Software/Hardware Transactional Memory 개념이 정착되면 될 것 같다는 생각이 드네요.

  4. 세라비 / 비슷하지만 다릅니다. 트랜잭션의 visibility(혹은 commitment)와 비슷하지만 다릅니다(이건 별도 포스팅 예정입니다).

    그리고 STM/HTM이 없어도 못하는건 아닙니다. 대다수의 lock 기반 혹은 CAS 기반 프로그래밍에서도 이 개념이 녹아있습니다(신경 안쓰거나 관심없는 것 뿐이지)

  5. 말씀하신 것은 일반적인 이야기이고, isolation이나 STM은 범용적으로 사용하기 좋게 특수화된 시나리오들이겠죠.

  6. Pingback: rein's world

Leave a Reply