Lock-Free List

Bard·약 11시간 전
0

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

profile
The Wandering Caretaker

0개의 댓글