[MP] Lock-Free List

Lock의 문제

• Deadlock
• Priority inversion: priority가 낮은 프로세스가 락을 잡고 있을 때 priority가 높은 프로세스가 기다리는 문제
• Convoying effect: lock 때문에 느린 프로세스가 락을 걸고 놓지 않으면 나머지 프로세스들이 밀리는 문제
• Async-signal safety: malloc()을 하는 중 이 프로세스가 signal에 의해 interrupt를 당하고, signal handler가 또 memory allocation을 하면 서로 꼬이는 문제가 발생 + Lock을 건다면 deadlock이 발생할 수 있음
• Kill-tolerance: unlock()을 try ... catch 블럭에서 finally블럭에 두어야 한다.
• Pre-emption tolerance
• Overall performance

Highly-Concurrent Application

• 일반적인 lock-free algorithm을 구상하는 것은 어렵다.

• 네 가지 패턴

  • Fine-grained Synchronization
  • Optimistic Synchronization
  • Lazy Synchronization
  • Lock-Free Synchronization

Fine-Grained Synchronization

• 노드 단위로 락을 거는 방법
• Linked List에서는 다음 노드까지 락을 걸어야 한다.

• Thread A가 a를 삭제하고 Thread B가 b를 삭제하려고 한다고 하자.
• A는 head에 lock을 걸었고, B는 a에 lock을 걸었다.
• 각자 next node를 바꾸고 나면 아래와 같이 되어 실패하게 된다.

• 따라서 Hand-over-hand locking을 걸어 이 문제를 해결해야 한다. 지우고자 하는 노드까지 lock을 거는 것.

Optimistic Synchronization

• Traversal(Read) 중에는 lock을 걸지 않고, 추가하거나 삭제해야하는 위치를 찾으면 lock을 거는 방식
• 하지만 read 이후 lock을 걸기 전에 해당 노드가 삭제되거나 변형될 수 이기에, lock을 건 이후에 validation 작업이 필요함.
  

(이런 문제가 발생할 수 있기에)

Lazy Synchronization

• Optimistic과 거의 비슷하나, validation 과정에서 전체 리스트를 순회하지 않는다.

• 노드 삭제는 문제가 될 수 있으니 실제로 삭제하지 않고, 일단은 logical하게만 삭제하는 것이다.
  

• 이는 Validation 과정에서 이전 노드와 현재 노드가 mark되어있는지만 확인하면 된다.
  

• Serializability, Linearizability

Lock-Free List

• 오직 compareAndSet() instruction만 사용한다.

CAS(X, old_value, new_value):
	if(X == old_value):
    	X = new_value
        return true
    else
    	return ERR

여러개의 Thread가 b를 업데이트하려고 할 떄 CAS 연산에 의해 단 하나만 성공하게 된다.

• head -> a -> b -> c -> e 에서 c를 삭제하고, c와 e사이에 d를 추가하는 연산을 동시에 수행한다고 해보자.
• c를 삭제하는 Thread는 c.invalid = true로 바꾸고, CAS(b.next, &c, &e)를 수행한다.
• d를 추가하는 Thread는 if(c.invalid == false)인지 확인하고, CAS(c.next, &e, &d)를 수행한다.

만약 d를 추가하는 Thread가 c.invalid == false를 확인한 뒤 suspend되면, 아래와 같은 현상이 발생한다.

이를 해결하기 위해 mark-bit와 pointer를 결합한다.

pointer는 64bits이지만, 실제로는 48bits만 주소를 나타내기 위해 사용된다. 따라서 mark-bit를 나머지 16bits 중 하나로 넣어줄 수 있다.

이렇게 하면 if(c.invalid == false) 를 생ㄴ략할 수 있고, 하나의 CAS 연산으로 d를 추가할 수 있게 되면서 문제가 해결된다.

이렇게 mark-bit와 address가 결합된 형태를 AtomicMarkableReference라고 부른다.

Performance

• 읽기 비율이 높을 때
  

• 읽기 비율이 낮을 떄
  

• 읽기 비율에 따른 성능
  

Concurrent Lock-Free Queue

• Enqueue를 할 때 tail의 next를 새로운 노드로 바꾸고, tail을 enqueue node로 바꾸는 연산은 atomic하지 않다. (흰색 노드는 sentinel)

In computer programming, a sentinel node is a specifically designated node used with linked lists and trees as a traversal path terminator. This type of node does not hold or reference any data managed by the data structure.

• 이 상태에서 노란색 노드를 dequeue하면 tail은 sentinel node가 되어 파란색 노드는 사라진다.

{복습 필요}

ABA problem

• 재활용이 어려운 이유?
• 요약하면 free pool을 사용하면 이상한 문제가 발생할 수 있다.

ABA problem - Solution