Linearization은 프로그래머에게 어떤 의미인가?

라고 물으신다면 “생각을 편하게 하려고” 쓴다고 해두겠다.

예전에 간단히(?) 선형화 가능성(linearizability/linearization)에 대해서 포스팅 하나 했는데, 정의 말곤 딱히 의미가 없어뵈서 다시 한 번 포스팅을.

이 글에선 선형화/선형화 가능성을 프로그래머 입장에서 왜 따지는지 혹은 왜 따져야할지 생각해보겠다. 멀티스레드 프로그래밍을 하다보면 기본적으로 다음과 비슷한 류의 상황을 생각해야 된다.

Naive timing diagram

위 그림처럼 여러 개의 스레드가 공유 객체에 접근하는데, 그에 대한 접근이 “겹치게” 된다. 프로그래머는 겹치는 형태마다 자신의 생각한데로 동작할지를 고민해야 한다.(공유 객체를 짜는 사람도 / 쓰는 사람도 모두)

위처럼 아주 간단한 공유 큐를 쓰는 상황에서도, 저렇게 enq() 함수 두 개가 겹친 경우 두 아이템의 추가 순서를 쉽게 말할 수가 없다.[1] 물론 deq()의 경우도 두 스레드가 뭘 꺼내서 보게될지 말하기 힘들다. 그럼 이런 공유 큐를 만드는 프로그래머와 사용하는 프로그래머는 저게 겹치는 경우 4가지( A의 실행 구간이 B를 포함하는 경우 / A 의 실행 구간이 B와 겹치긴 하지만 먼저 끝나는 경우 /  이에 대한 거울상 두 가지)를 모두 생각해야 할까?

대부분의 실세계 문제들 중 저런 기본 재료들(building blocks)의 경우엔 사실상 선형화된 형태로 만들어져 있고, 무의식적으로(?)그렇게 쓰고 있다. 그림으로 그려보면 다음처럼 그린다. 차이점은 적당히 칠해놓은 동그란 점들 뿐이다.

Linearized timimng diagram

사실 이런 큐가 구현된걸 뜯어보면 대부분의 경우 — 그러니까 제대로 한 경우 — 저 점과 같은 부분이 있다.[2] 이런 선형화 지점(linearization point)에서 실제 코드는 뭘 하냐 하면,

  • compare-and-exchange나 compare-and-set 혹은 load-linked/store-conditional 같은 원자적인 하드웨어 명령을 쓰서 큐를 완전히 업데이트 하거나[3]
  • 적당한 lock을 써서 큐를 잠그고 아이템을 추가하거나 뺀 후에 락을 풀거나

혹은 뭔가 다른 연산을 써서, 다른 스레드 관점에서는 그 중간 과정을 볼 수 없지만, 그 연산이 끝나고 나면 유효한 큐 상태가 되는 무언가를 수행한다.

즉, 특정 쪼갤 수 없는 지점 하나에서 객체 상태를 완전히 업데이트 해버리면, 프로그래머는 저 지점들의 순서만 고민하면 된다.(실행 구간이 어떻게 겹치는지를 따지는게 아니라)  그리고 내용을 설명하진 않았지만, 이런 선형화 가능한 객체들은 서로 합성할 수 있다. 예를 들어서 선형화가능인 연결 리스트(linked list)가 있다면, 이걸 선형화 가능한 연산만(=효과가 쪼갤 수 없는 지점에서 나타나거나, 한 스레드 안에서만 보이는 연산) 써서 선형화 가능한 큐나 스택을 만들 수 있다.

물론 이 선형화/선형화 가능성이 프로그래밍 방법은 아니다. 이건 프로그램이 가질 수 있는 속성이라 이런 조건을 충족하게 — 많은 lock-free 알고리즘 처럼 — 코드를 짜면, 그 코드들 끼리 서로 호출할 때를 생각하기도 편하고, 순서 관계 고려도 쉽게 해줄 뿐이다.

요약하자면, 프로그래머의 관점에서, 선형화 가능성이란건 “다중 스레드 시나리오에서 경우의 수를 쉽게 따지게 해주는 (수학적인) 도구”다. 그리고 적당한 추상화 수준을 제공해서 이런 프로그램을 짜는걸 도와주는 기능도 한다.(합성이 되기에)

  1. 물론 딱 한가지 예외는 있다. enq(a) 가 완전히 끝나고 나서 enq(b) 가 실행되는 경우는 순차/비공유 큐랑 똑같다 []
  2. 물론 하나의 함수가 저런 지점을 하나만 갖는건 아니다. 실행 경로에 따라서 두 개 이상일 수도 있다 []
  3. 많은 non-blocking(lock-free) algorithm들의 선형화 지점은 이런 연산이다 []

Author: rein

나는 ...

7 thoughts on “Linearization은 프로그래머에게 어떤 의미인가?”

  1. Serializability 보다 더 강력한 정의군요. 선형화라는 개념은 제가 읽는 논문들(atomicity 버그 디텍션)에서는 보통 나오지 않은데 훨씬 수학적이고 이론적이네요. 역시나 POPL 논문으로 과거 출판되었군요.

    사실 serializability 개념이 이해하기가 훨씬 쉽습니다. 이걸로 접근해서 선형성으로 확장하는게 보통 프로그래머에게는 훨씬 좋을 것 같네요. 이해하는데 단 10분이면 되니깐요 -_-;

    http://pages.cs.wisc.edu/~shanlu/paper/micr-27-01-lu.pdf

    1. Serializability보다 유연하지만 / serializability보다 쉽게 verify 안되는 문제 인 것 같아요(제약조건이 적어서).
      Atomicity 가 좀 더 자주나오는건 기존의 OS/DB에서 더 잘 연구되어서가 아닐까 합니다 ~_~
      + 멀티스레드 프로그램이라고 하면 제약이 너무 적어서, DB에서처럼 “스케쥴러 자체를 통제”하지 못해서일 수도 있겠네요;

      이해하는 방향 자체는 말씀하신데로 하는게 좋아 보이긴 하네요 :)

  2. 사실 근본적으로 어려운 이유는 일단 Herlihy 선생님의 논문들이 PLDI처럼 좀 구현 중심보다는 이론 중심이다보니 아무래도 읽기 자체가 어렵기도 하지요. 저도 아키/컴파일러 쪽에서 일하다보니 이런 쪽으로 훈련이 안 되어 있습니다. PLDI/ASPLOS/PPoPP 쪽 논문 자체 분위기도 POPL 같은 것과는 매우 다르죠. 뭔가 수학적으로 깔끔하게 정의하고 그런 것이 거의 없습니다.

    제가 이야기하는 serializability는 DB와는 전혀 상관이 없고요(개념은 어느 정도 일치하지만), 멀티스레드 프로그램의 정확성을 테스트하는 쪽에서 나오는 개념입니다. Data race는 익히 잘 아실 것인데, data race만을 검출해서는 놓치는 멀티스레드 버그가 있습니다. 그래서 나온 것이 atomicity 버그이고요. data race에서 좀 더 확장시킨 것이고 보통 serializability로 설명합니다. 최근에는 data race 만 찾는 것보다 atomicity 위반을 찾는 툴이 대세이고요. 선형성 위반을 검출하는 프로그램이 있는지는 아는 바가 전혀 없군요.

    만약 글을, 정확한 멀티스레드 프로그램이 가져야할 조건이 무엇인가? 로부터 풀어나가면 훨씬 쉽게 이해할 겁니다. 실제 POPL 논문을 봐도 그렇게 시작하네요.

    1. 아 리플이 수정 안되니 조금 괴롭군요 :)

      Data race (단순히 공유 자원에 접근하는 복수개 이상의 R/W가 있는가?) -> Atomicity (한 줄로 쓰기는 너무 힘든데.. 공유 자원에 접근하는 두 스레드의 R/W의 조합과 같은 결과를 내는 직렬 순서가 있는가.. 각주 1의 내용이죠) -> 그리고 선형성.. 이렇게 접근하는 것이 쉽습니다. 바로 current object의 정확성을 위한 개념으로 선형성을 등장시키면 비전공자들은 (저 같이 data race, atomicity 논문 수십편 읽은 사람조차) @.@ 입니다 ㅎㅎㅎ

      암튼 저도 선형성에 대해서는 지금 껏 단 한번도 관심을 가지지 않았는데 시간 내서 조금 공부해봐야겠네요. 고마워요~

      1. 흠 저야말로 초본데 흐흐(…). object님이 이러시면 안되지 말입니다(??).
        저도 atomicity 는 좀 찾아서 읽어봐야겠네요. 댓글 감사합니다~

        ps. 근데 WP는 댓글 수정 기능이 코어에 포함이 안되어있어서 좀 난감합니다. 플러그인들이 있긴한데 좀 난잡(?)해서 -_-;

Leave a Reply