Locked Data Structure (Concurrency Data Structure)
reference: https://pages.cs.wisc.edu/~remzi/OSTEP/
How to use locks in data structure?
- Concurrent Counters(단일 변수)
- Concurrent Linked lists(연결 리스트)
- Concurrent Queues(큐)
- Concurrent Hash Tables(해시 테이블)
Concurrent data structure?
- Thread safe
- Correctness and Performance -> 정확성을 보장하면서 동시에 성능이 너무 나빠지면 안됨 .
1. Counter with Locks
싱글 스레드인 경우 문제되지 않는다.
하지만 다중 쓰레드의 경우 문제 발생. 예를 들어 c->value++; 만 해도 최소 3개의 기계 명령어가 필요하다. 1) load, 2) add, 3) store
counter_t 구조체에 lock 변수 필드를 추가한다.
counter_t 구조체를 초기화하는 과정에는 lock 변수 초기화도 포함되어 있다.
경쟁 상태가 발생할 수 있는 c->value++, c->value--; 그리고 대입 statement에 lock, unlock을 사용하여 임계영역으로 설정하고 상호배제를 구축한다.
concurrent counter 관련 추가 고려
Traditional 방식 vs Sloppy 방식 => 본문에선 생략
2. Concurrent Liked Lists
(Coarse-grained)
(1) 힙 영역을 할당받아 새로운 노드를 생성하는 것과 (2) 새로운 노드를 리스트에 추가하는 것까지 포함하여 임계영역으로 설정하였다.
(Fine-grained)
하지만 실제 경쟁상태가 발생할 수 있는 것은 (2) 새로운 노드를 리스트에 추가하는 부분이다. 이를 임계영역으로 두어 영역을 축소하여 상호배제를 구축한다.
3. Concurrent Queues
큐에 새로운 원소가 들어오게 하는 Enqueue 함수에는 큐의 tail에 있는 원소를 새로운 큐로 대체하는 작업이 필요하다. 이 구간은 경쟁 상태가 발생할 수 있으므로 임계영역으로 두어 상호배제를 구축한다.
큐에 가장 먼저 들어온 원소(큐의 head에 위치)를 빼내는 Dequeue 함수에는 head에 있던 원소를 빼고, 그 다음 위치에 있는 원소를 head에 다시 위치시키는 작업이 필요하다. 이 부분 역시 경쟁 상태가 발생할 수 있으므로 임계영역으로 설정한다.
4. Concurrent Hash Table
체인법으로 구현된 해시 테이블에 각 버킷에는 연결 리스트가 붙어있다. '2. Concurrent Liked Lists' 에서 구현한 대로 이 리스트에 상호배제를 구현해야 안전한 해시 테이블 자료구조가 만들어진다.
