Lock Free?

Lock free가 진짜 락이 없다는 뜻은 아닙니다. Lock free는 하나의 작업은 꼭 완료가 된다는 조건이래요.
(one of the ongoing operation is completed someday)

비슷한 조건으로

Obstruction free : 하나의 쓰레드만 실행 될 때 그 작업은 무조건 완료됨
Wait free : 모든 작업이 꼭 완료됨

가 있습니다.

하나의 작업이 꼭 완료가 된다는 것이 무슨 뜻일까요? 반례로 생각해봅시다. 여러 쓰레드가 락으로 보호된 어딘가에 접근합니다. 근데 락 먹은 쓰레드가 락 안 뱉고 멈추었다 하면 그 어딘가에 접근하는 모든 쓰레드는 완료될 수 없겠지요.

하지만 락 프리 스트럭쳐에서는 하나가 어느 곳에서나 멈추어도 최소 다른 어떤 쓰레드는 작업을 완료할 것이라는 겁니다. 여기에 Wait free까지 적용된다면 모든 쓰레드가 작업을 완료할 수 있을 거고요.

이런 락 프리 스트럭쳐는 당연히 만들기 어렵겠지요. 락 프리 스트럭쳐가 만들기 어려운 이유는

무작위적인 쓰레드 pause/stall
데드락/라이브락

등이 있답니다.

그래서 이러한 문제를 해결하기 위해 Single instruction commit을 사용합니다. 이를 통해 최소 하나의 쓰레드는 잘 돌아간다는 것을 보증한다네요.

이를 위해 CAS를 이용합니다. CAS는 이 글을 읽을 사람들은 다 알거라 생각하고 넘어갈게요. CAS를 사용하면 저 위에 두가지 문제를 직면하지 않아도 됩니다.

Lock free DS

Treiber's stack

Treiber's stack은 stack top을 head로 가지는 Singly linked-list입니다. Stack이기에 push, pop, is_empty 세가지 메소드를 가지고 있습니다.

push

먼저 새로 push할 노드를 만듭니다.

let mut n = Owned::new(Node {
    data: ManuallyDrop::new(t),
    next: Atomic::null(),
});

n.next에 현재 head를 넣고, n을 현재 스택의 head와 CAS해줍니다. 즉, head가 n.next와 같을 때만 n과 head를 바꿀 수 있는 거죠. 이렇게 해야 없는 노드를 가리키거나 head가 아닌 노드를 가리키지 않겠죠?
만약 CAS가 실패했다면, head를 다른 스레드에서 변경했을 것입니다. 그래서 head를 다시 받아와 다시 이 작업을 반복해줍니다.

pop

head와 그 다음 next를 불러옵니다.
```
let head = self.head.load(Ordering::Acquire, &guard);
let h = unsafe { head.as_ref() }?;
let next = h.next.load(Ordering::Relaxed, &guard);
```
push랑 pop 모두 self.head만 CAS해주기에 h.next는 변하지 않습니다. 그래서 Relaxed로 가져와도 돼요.

head가 변하지 않았으면 next로 바꾸어줍니다.

if self
    .head
    .compare_exchange(head, next, Ordering::Relaxed, Ordering::Relaxed, &guard)
    .is_ok()

CAS실패했다면 다른 스레드에서 변경했다는 뜻이니 처음부터 다시 시행합니다.

Reutrning ownership? ManuallyDrop?

Michael-Scott's queue

Michael-Scott's queue는 head와 tail을 가지는 Singly linked-list입니다.
특이한 점은 head는 항상 dummy를 가리킨다는 것입니다.

Tail이 stale한 상태가 될 수 있다는데 뭘까요??

Queue이기에 push 와 try_pop 메소드가 존재합니다.

push

push는 세 단계로 진행됩니다.

tail을 불러옵니다.

let tail = self.tail.load(Ordering::Acquire, guard);
// Attempt to push onto the `tail` snapshot; fails if `tail.next` has changed.
let tail_ref = unsafe { tail.deref() };
let next = tail_ref.next.load(Ordering::Acquire, guard);

tail이 진짜 tail인지 확인하고 아니면 tail을 업데이트하고 처음부터 다시 시작합니다.

// If `tail` is not the actual tail, try to "help" by moving the tail pointer forward.
if !next.is_null() {
    let _ = self.tail.compare_exchange(
        tail,
        next,
        Ordering::Release,
        Ordering::Relaxed,
        guard,
    );
    continue;
}

일단 tail.next가 null이라면 tail이 진짜 tail일 확률이 높겠죠?
그래서 cas를 실행합니다.

if tail_ref
    .next
    .compare_exchange(
        Shared::null(),
        new,
        Ordering::Release,
        Ordering::Relaxed,
        guard,
    )
    .is_ok()
{
    // try to move the tail pointer forward.
    let _ = self.tail.compare_exchange(
        tail,
        new,
        Ordering::Release,
        Ordering::Relaxed,
        guard,
    );
    break;
}

이 CAS가 성공하면, 큐에 new노드가 삽입된 상황일테니 tail포인터를 업데이트해줍니다.
tail은 어차피 다른 곳에서도 업데이트가 되니깐 실패해도 상관없어요. 단지 push를 효율적으로 하기 위해 도와주는
포인터일 뿐이니까요.

pop

먼저 tail이 head인지, 즉 안에 아무것도 없고 둘 다 dummy노드를 가리키는지 확인합니다.
```
let tail = self.tail.load(Ordering::Relaxed, guard);
if tail == head {
    let _ = self.tail.compare_exchange(
        tail,
        next,
        Ordering::Release,
        Ordering::Relaxed,
        guard,
    );
}
```
만약 그렇다면, cas를 통해 tail을 늘려 줍시다. 이 작업은 오직 tail=head일 경우에만
의미가 있다 보니 ordering을 빡빡하게 줄 필요가 없습니다.

그러면 이제 head가 tail과 다른 곳을 가리킬테니 head를 변경해 pop을 진행합니다.

if self
    .head
    .compare_exchange(head, next, Ordering::Release, Ordering::Relaxed, guard)
    .is_ok()
{
    // Since the above `compare_exchange()` succeeded, `head` is detached from `self` so
    // is unreachable from other threads.
    // SAFETY: `next` will never be the sentinel node, since it is the node after
    // `head`. Hence, it must have been a node made in `push()`, which is initialized.
    //
    // Also, we are returning ownership of `data` in `next` by making a copy of it via
    // `assume_init_read()`. This is safe as no other thread has access to `data` after
    // `head` is unreachable, so the ownership of `data` in `next` will never be used
    // again as it is now a sentinel node.
    let result = unsafe { next_ref.data.assume_init_read() };
    // SAFETY: `head` is unreachable, and we no longer access `head`. We destroy `head`
    // after the final access to `next` above to ensure that `next` is also destroyed
    // after.
    unsafe {
        guard.defer_destroy(head);
    }
    return Some(result);
}

주석에 적혀 있는대로 next는 null일 수는 있어도 센티넬일 수는 없습니다.
만약 null이라면 위에 1번 작업을 시작하기도 전에 let next_ref = unsafe { next.as_ref() }?;때문에 리턴이 되었을 것이고요.

그래서 우리가 해야하는 것은 head를 버리고, next를 새로운 헤드로 만든 뒤, next의 내용물을 빼내서 return해주는 것입니다.
그러면 next였던 노드는 새로운 센티넬 노드가 되는 것이고요.