• 합의 객체
  • non-blocking알고리즘을 만들기 위해 필요한 객체
• 합의 수
  • non-blocking알고리즘을 만드는 능력
• 만능성
  • 모든 알고리즘을 멀티스레드 무대기로

합의 객체는 논 블로킹 자료구조를 만들기 위한 객체이다. 멀티스레드 자료구조를 만들기 위해서는 atomic memory가 필요하다. 하지만 이 atomic 메모리만 갖고는 못 만든다. 그래서 합의 객체가 필요하다.

합의 객체는 논 블로킹 알고리즘을 만드는데 필요한 객체이다.

합의 수는? 합의 객체의 종류는 수 없이 많이 있다. 종류라기보단 구현, 구현마다 다 능력이 다르다. 합의 객체 구현하는데 두개 스레드까지 할 수 있냐 3개? 10개? 무한대 스레드까지 할 수 있을까? 이게 능력이다.

만능성은 모든 알고리즘은 wait free로 만들어주는 알고리즘이다.

• 시중에 팔고있는 컴퓨터의 메모리는 멀티코어 프로그래밍에서는 믿을 놈이 못 된다.
• 하지만 우리는 atomic를 사용해서 atomic하게 사용할 수 있다.
  • 모든 자료구조를 다 atomic하게 만들 수 없다.
  • T의 크기가 커질경우 내부적으로 mutex로 구현된다.

모든 자료구조를 atomic 하게 만들 수 없다.

동기화

• 동기화
  • 자료구조의 동작을 Atomic하게 구현하는 것.
• 동기화를 구현하기 위해서는 디본 동기화 연산ㄴ들을 사용해야 한다.
• 이 기본 동기화 연산들은 무대기 혹은 무잠금이어야 한다.
  • 그렇지 않는 무대기나 무잠금 동기화를 구현할 수 없다.

자료구조의 동작을 아토믹하게 구현. 자료구조는 내부 메모리하고 메소드 두개로 구현되어 있다.

동기화는 이 메소드의 동작을 멀티스레드에서 아토믹하게 돌아가게 하는 것이다. 그냥 자료구조는 멀티 스레드에서 안 돌아갈 확률이 높은데, 메소드를 동기화 시키면 동기화 된 메소드를 사용하면 멀티스레드에서 아토믹하게 돌아간다.

그럼 어떻게 동기화를 구현할 것이가? 그게 문제다. 메소드를 구현하기 위해서 우리는 메소드에 사용되는 연산 하나하나도 동기화 된 연산이어야 한다. 자료구조의 메소드를 락프리로 만들기 위해서는 그 메소드를 구현하는 기본 오퍼레이터 연산들도 다 무대기나 무잠금이어야 한다.

합의

• 합의
  • 기본 동기화 연산을 제공하는 가상의 객체
  • 기본 동기홤 연산 : decide
    • 선언
      • Type_t decide(Type_ t value)
    • 동작
      • n개의 스레드가 decide를 호출한다.
      • 각각의 스레드는 한 번 이하로만 호출한다.
      • decide는 모든 호출에 대해 같은 값을 반환한다.
      • decide가 반환하는 값은 전달된 value중 하나이다.
      • atomic하고 wait free로 동작한다.

전에는 CAS로 구현(못)했는데 정말 CAS가 필요할까?

일단 CAS 대신 합의라는 기능을 사용해보자. 합의라는 객체를 제공하고 연산을 제공하는 객체다. 그래서 합의 객체를 만들어보면, 그건 decide 연산을 제공하고 이걸 통해 우린 동기화를 시도할거다.