어레이 기반 대기열 잠금
Array Based Queuing Locks | 이 글은 독자들에게 혼란스럽거나 불명확할 수 있다.(2016년 12월)(이과 시기 |
 |
ABQL(Array-Based Queuing Lock)은 스레드가 고유한 메모리 위치에서 회전하도록 하는 고급 잠금 알고리즘으로, 잠금 획득의 공정성과 확장성을 향상시켰다.
개요
동기화는 공유 메모리[1] 멀티프로세서의 설계와 프로그래밍에서 중요한 이슈다.잠금 구현의 일반적인 문제는 프로세서가 공유 동기화 플래그 또는 메모리 위치에서 회전하기 때문에 네트워크 경합이 높다는 것이다.따라서 경합하는 프로세서의 수 측면에서 자물쇠의 확장성이 현저히 감소한다.
Array Based Queuing Lock은 잠금 해제 시 하나의 프로세서만이 잠금을 획득하려고 시도하여 캐시 누락 수를 감소시키는 티켓 잠금 알고리즘의 확장이다.이 효과는 모든 프로세서가 고유한 메모리 위치에서 회전하도록 함으로써 얻을 수 있다.[2]잠금 메커니즘을 설명하는 데 사용되는 한 가지 비유는 선수가 대기열의 다음 선수에게 바통을 물려주는 릴레이 경주로, 한 번에 한 선수만 바통을 획득하도록 하는 것이다.
또한 ABQL은 FIFO(선입선출) 대기열 기반 메커니즘을 사용함으로써 잠금 획득의 공정성을 보장한다.또한, 하나의 프로세서만이 잠금 릴리스에서 캐시 누락을 유발하기 때문에 무효화 양은 티켓 기반 잠금 구현보다 훨씬 적다.
실행
어레이 기반 대기열 잠금 구현의 최우선 요구 사항은 모든 스레드가 고유한 메모리 위치에서 회전하도록 하는 것이다.이는 잠금에 대해 경합하는 스레드 수와 동일한 길이의 배열로 달성된다.어레이의 요소는 값 1을 취하는 첫 번째 요소를 제외하고 모두 0으로 초기화되므로 대기열의 첫 번째 스레드에 의한 성공적인 잠금 획득이 보장된다.잠금 해제 시, 홀드는 어레이의 다음 요소를 1로 설정하여 대기열에 있는 다음 스레드에 전달된다.요청은 FIFO 순서에 따라 스레드에 부여된다.
유사 코드 예는 아래 나열되어 있다.[3]
ABQL_init(인트로 *next_snow, 인트로 *can_can) { *next_snow = 0; 을 위해 (인트로 i = 1; i < 맥스사이즈; i++) can_can[i] = 0; can_can[0] = 1; } ABQL_acquire(인트로 *next_snow, 인트로 *can_can) { *my_properties = fetch_and_inc(next_snow); 하는 동안에 (can_can [*my_properties] != 1) ; } ABQL_release (인트로 *can_can) { can_can[*my_properties + 1] = 1; can_can[*my_properties] = 0; // 다음 시간에 대비 } 위의 유사 코드에서 ABQL을 구현하기 위해서는 can_serve, next_ticket, my_ticket 등 3가지 변수가 도입된다.각각의 역할은 아래에 설명되어 있다.
- can_temp 어레이는 잠금 수집을 위해 대기 중인 스레드가 회전하는 고유한 메모리 위치를 나타낸다.
- next_lights는 새 스레드에 할당된 다음 사용 가능한 티켓 번호를 나타낸다.
- my_message는 대기열에 있는 각 고유 스레드의 티켓 스레드를 나타낸다.
초기화 방법(ABQL_init)에서는 next_ticket 변수가 0으로 초기화된다.첫 번째 요소를 제외한 can_serve 어레이의 모든 요소가 0으로 초기화된다.어레이 can_serve의 첫 번째 요소를 1로 초기화하면 대기열의 첫 번째 스레드에 의한 성공적인 잠금 획득이 보장된다.
획득 방법은 원자 연산 fetch_and_inc를 사용하여 새 스레드가 회전하는 데 사용할 수 있는 다음 사용 가능한 티켓 번호(이후 티켓 번호가 1씩 증가)를 가져온다.my_ticket 값이 이전 스레드에 의해 1로 설정될 때까지 대기열의 스레드는 그 위치에서 회전한다.잠금 장치를 획득하면 나사산이 코드의 중요 섹션으로 들어간다.
스레드에 의한 잠금이 해제되면 어레이 can_serve의 다음 요소를 1로 설정하여 다음 스레드로 컨트롤이 전달된다.자물쇠를 얻기 위해 기다리던 다음 스레드는 이제 그렇게 성공적으로 할 수 있다.
ABQL의 작업은 스레드가 임계 섹션에 한 번만 들어간다는 가정 하에 4개의 프로세서가 임계 섹션에 진입한다고 가정하여 아래 표에 설명될 수 있다.
| 실행 단계 | can_can | 평. | |||||
|---|---|---|---|---|---|---|---|
| 처음에 | 0 | [1, 0, 0, 0] | 0 | 0 | 0 | 0 | 모든 변수의 초기 값은 0임 |
| P1: fetch_and_inc | 1 | [1, 0, 0, 0] | 0 | 0 | 0 | 0 | P1이 잠금을 시도하고 성공적으로 획득함 |
| P2: fetch_and_inc | 2 | [1, 0, 0, 0] | 0 | 1 | 0 | 0 | P2 잠금 획득 시도 |
| P3: fetch_and_inc | 3 | [1, 0, 0, 0] | 0 | 1 | 2 | 0 | P3 잠금 획득 시도 |
| P4: fetch_and_inc | 4 | [1, 0, 0, 0] | 0 | 1 | 2 | 3 | P4 잠금 획득 시도 |
| P1: can_serve[1] = 1; can_sn[0] = 0 | 4 | [0, 1, 0, 0] | 0 | 1 | 2 | 3 | P1이 잠금을 해제하고 P2가 잠금을 획득함 |
| P2: can_serve[2] = 1; can_sn[1] = 0 | 4 | [0, 0, 1, 0] | 0 | 1 | 2 | 3 | P2가 잠금을 해제하고 P3가 잠금을 획득함 |
| P3: can_serve[3] = 1; can_sn[2] = 0 | 4 | [0, 0, 0, 1] | 0 | 1 | 2 | 3 | P3가 잠금을 해제하고 P4가 잠금을 획득함 |
| P4: can_serve[3] = 0 | 4 | [0, 0, 0, 0] | 0 | 1 | 2 | 3 | P4가 잠금을 해제한다. |
성능 메트릭
다음과 같은 성능 기준을 사용하여 잠금 구현을 분석할 수 있다.
- 비경합 잠금 획득 지연 시간 - 스레드 간에 경합이 없을 때 스레드가 잠금을 획득하는 데 걸리는 시간으로 정의된다.다른 잠금 구현에 비해 상대적으로 많은 수의 명령이 실행되기 때문에 ABQL의 비내용 잠금 획득 지연 시간이 높다.
- 트래픽 - 이것은 잠금 시 경합하는 스레드 수에 따라 달라지는 생성된 버스 트랜잭션의 수로 정의된다.잠금 해제에서는 캐시 블록이 1개만 무효화되므로 캐시 누락이 1개 발생한다.이것은 훨씬 적은 버스 교통량을 초래한다.
- 공정성 - 잠금을 획득하기 위해 대기 중인 모든 프로세서가 요청이 발행되는 순서대로 잠금을 획득할 수 있도록 보장한다.개별 메모리 위치에서 각 스레드가 회전하는 상태에서 잠금을 획득하기 위해 대기 중인 스레드 때문에 공정성이 보장된다.
- 저장 - 잠금 메커니즘의 처리에 필요한 메모리 양.스토리지 요구사항은 어레이 can_serve의 크기가 증가함에 따라 스레드 수에 따라 확장된다.
이점
- ABQL은 각 잠금 획득 또는 릴리스가 1개의 캐시 누락만 트리거하여 캐시 누락으로 인해 캐시 블록만 발생하여 블록을 다시 로드하므로 향상된 확장성을 제공한다.
- 잠금 획득의 공정성은 스레드가 발행되는 순서에 따라 스레드가 성공적으로 잠금을 획득할 수 있도록 하는 큐의 사용으로 보장된다.
단점들
- 즉시 잠금을 획득할 준비가 되지 않은 스레드는 잠금을 대기 중인 모든 스레드의 대기 시간을 증가시키므로 ABQL을 일시 중단할 수 있는 스레드(절전 또는 컨텍스트 스위치)와 함께 사용하지 마십시오.
참고 항목
참조
- ^ "Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors".
- ^ https://cs.unc.edu/~html/html/html.pdf
- ^ Solihin, Yan (2009). Fundamentals of parallel computer architecture : multichip and multicore systems. pp. 265–267. ISBN 978-0-9841630-0-7.
