티켓 잠금

컴퓨터 과학에서 티켓 잠금이란 "티켓"을 사용하여 중요한 섹션에 들어갈 수 있는 실행 스레드를 제어하는 스핀록의 일종인 동기화 메커니즘 또는 잠금 알고리즘입니다.

개요

티켓 큐 관리 시스템에서 사용되는 티켓 및 "Now Serving" 기호의 예.

티켓 잠금의 기본 개념은 티켓 큐 관리 시스템과 비슷합니다.이것은 많은 빵집이나 델리들이 손님을 줄을 서지 않고 도착하는 순서대로 접대하기 위해 사용하는 방법이다.일반적으로 고객이 도착 시 순차적으로 번호표를 뽑아주는 디스펜서 타입이 있습니다.디스펜서는 보통 그 위나 근처에 "숫자를 받아주세요"와 같은 팻말을 가지고 있습니다.또, 통상은, 현재 서비스 되고 있는 티켓 번호를 표시하는 다이나믹 사인(통상은 디지털)도 있습니다.다음 티켓 번호(고객)가 서비스될 준비가 될 때마다 "Now Subing" 기호가 증가하고 번호가 호출됩니다.이것에 의해, 대기하고 있는 모든 고객은, 큐 또는 줄의 선두에 몇명의 사람이 있는지 알 수 있습니다.

이 시스템과 마찬가지로 티켓락은 First In First Out(FIFO; 퍼스트 인 퍼스트 아웃) 큐 기반 메커니즘입니다.이것은 잠금 획득의 공정성의 이점을 추가하며 다음과 같이 동작합니다. 0으로 시작하는 두 개의 정수 값이 있습니다.첫 번째 값은 큐티켓이고 두 번째 값은 큐티켓입니다큐 티켓은 큐 내의 스레드 위치이며, 디큐 티켓은 현재 잠금(Now Serviceing)이 있는 티켓 또는 큐 위치입니다.

스레드가 도착하면 큐티켓을 아토믹하게 취득하여 증분합니다.이 조작의 원자성은 2개의 스레드가 동시에 같은 티켓 번호를 취득할 수 없도록 하기 위해 필요합니다.그런 다음 증분 전의 티켓 값을 큐 제거 티켓 값과 비교합니다.같은 경우 스레드는 크리티컬섹션에 들어갈 수 있습니다.동일하지 않은 경우 다른 스레드가 이미 critical 섹션에 있어야 하며 이 스레드는 busy-wait 또는 yield여야 합니다.스레드가 잠금으로 제어되는 크리티컬섹션을 벗어나면 디큐티켓이 아토믹하게 증가합니다.이것에 의해,^[1] 다음의 대기 스레드(순차적인 티켓 번호의 스레드)가 크리티컬섹션에 들어갈 수 있게 됩니다.

잠금 취득의 공정성

잠금 획득의 공정성 개념은 스레드가 잠금을 성공적으로 ^[2]획득하는 순서에 적용됩니다.어떤 유형의 공정성이 구현되면 다른 스레드에 유리한 잠금을 획득할 수 없기 때문에 스레드가 장기간 실행되지 않게 됩니다.공정성이 보장되지 않으면 스레드(또는 여러 스레드)가 다른 스레드보다 실행하는데 불균형적으로 오랜 시간이 걸릴 수 있습니다.이제 잠금 획득의 공정성 결여로 인해 스레드가 어떻게 과도하게 지연될 수 있는지를 보여주는 간단한 예를 제시하겠습니다.

3개의 스레드가 각각3개의 프로세서 중 하나로 실행되고 있는 경우, 공평성을 고려하지 않고 잠금을 사용하는 다음의 의사 코드를 실행하고 있다고 가정합니다.

하는 동안에 (1) {     잠그다 {         …         중대. 부분         …     }     언락 } 

다음으로 3개의 프로세서(P1, P2, P3)의 물리적인 배치에 의해 공유 잠금 변수 위치에 대한 메모리액세스 시간이 균일하지 않다고 가정합니다.3개의 프로세서의 잠금 변수에 대한 액세스 시간을 늘리는 순서는 P1 < P2 < P3 입니다.따라서 잠금을 획득할 때 항상 P1이 가장 유리하고 P2가 그 뒤를 이으며 P3가 가장 불리합니다.공정성이 보증되지 않은 상태에서 이 상황이 스레드 고갈로 이어지는 방법을 이들 3개의 프로세서에 의한 상기 의사 코드 실행의 다음 그림에 나타냅니다.

처음에는 잠금이 해제되고 세 개의 프로세서 모두 동시에 잠금이 획득됩니다(시간 1).P1은 잠금 접근 시간이 가장 빠르기 때문에 먼저 잠금을 취득하고 크리티컬 섹션에 들어갑니다.이제 P1이 임계 섹션에 있는 동안 P2와 P3가 회전합니다(시간 2).임계구간(시간 3)을 종료하면 P1은 잠금을 해제하고 잠금을 해제한다.P2는 P3보다 잠금 접근 속도가 빠르기 때문에 다음에 잠금을 취득하여 크리티컬 섹션(시간 4)으로 들어갑니다.P2가 크리티컬 섹션에 있는 동안 P1은 다시 한번 잠금을 획득하려고 시도하지만 획득할 수 없으며(Time 5), P3와 함께 스핀 대기하도록 강제한다.P2가 크리티컬 섹션을 종료하고 잠금을 해제하면 P1과 P3 모두 동시에 다시 취득을 시도한다(시간 6).단, 액세스 시간이 빠른 P1이 다시 승리하여 크리티컬섹션(타임7)에 들어갑니다.P3가 잠금을 취득할 수 없는 패턴은 P1 또는 P2 중 하나가 잠금을 취득하려고 하지 않을 때까지 무기한 계속됩니다.

이는 특정 상황에서 잠금 취득에 있어 일정 수준의 공정성을 보장할 필요가 있음을 보여준다.모든 잠금 장치가 공정성 수준을 보장하는 메커니즘이 있는 것은 아니며, 위에서 설명한 것과 유사한 상황이 발생할 가능성이 있습니다.공정성 보장을 구현하지 않는 잠금의 예는 아래의 잠금 비교 섹션을 참조하십시오.

티켓 록의 실장

Non-Uniform Memory Architecture(NUMA; 비균일 메모리 아키텍처) 시스템에서는 잠금 획득의 공정성을 일정 수준으로 보장하는 잠금 구현이 중요합니다.티켓 잠금은 원하는 속성을 추가하는 스핀록 구현입니다.다음 의사^[1][3] 코드는 잠금을 초기화하고 잠금을 취득하며 잠금을 해제하는 작업을 보여 줍니다.ticketLock_acquire에 대한 호출은 코드의 중요한 섹션 앞에 있고 ticketLock_release는 코드 뒤에 있습니다.각 프로세서는 각 프로세서의 my_ticket 값을 통해 차례를 추적합니다.

Yan Solihin의 의사 코드 예는 ^[1]아래 그림에 나와 있습니다.

ticketLock_init(인트 *next_displays(다음_displays), 인트 *now_serving(현재 서비스 중)) {     *now_serving(현재 서비스 중) = *next_displays(다음_displays) = 0; }  ticketLock_acquire(인트 *next_displays(다음_displays), 인트 *now_serving(현재 서비스 중)) {     my_my_my_my_my_my_my = fetch_and_inc(next_displays(다음_displays));     하는 동안에 (*now_serving(현재 서비스 중) != my_my_my_my_my_my_my) {} }  ticket Lock_release(인트 *now_serving(현재 서비스 중)) {     ++*now_serving(현재 서비스 중); } 

위의 의사 코드에 따라 프로세서가 로크를 취득하려고 할 때마다ticketLock_acquire(), fetch_and_inc 가 호출되어 next_inc 의 현재 값이 스레드 private my_inc 로 반환되고 공유 next_inc 가 증가합니다.취득과 인크리먼트는 아토믹하게 이루어지기 때문에 다른 동시접속 시행은 할 수 없다는 점에 주의해 주십시오.my_ticket이 수신되면 now_serving이 my_ticket과 일치하지 않는 동안 각 스레드는 while loop으로 회전합니다.now_serving이 특정 스레드의 my_ticket과 동일해지면 ticketLock_acquire()에서 돌아와 코드의 중요한 섹션을 입력할 수 있습니다.코드의 중요한 섹션 뒤에 스레드는 ticketLock_release()를 실행합니다.이것에 의해 now_serving이 증가합니다.이를 통해 다음 시퀀셜 my_ticket을 가진 스레드는 ticketLock_acquire()를 종료하고 critical ^[3]섹션에 들어갈 수 있습니다.my_ticket 값은 자물쇠에 스레드가 도착하는 순서대로 취득되므로 이후의 취득도 같은 순서로 취득할 수 있습니다.따라서 잠금 취득의 공정성이 확보되어 FIFO 순서가 적용됩니다.

다음 표는 4개의 프로세서(P1, P2, P3, P4)가 크리티컬섹션에 액세스하기 위해 경합하고 있는 시스템에서의 티켓락 동작의 예를 나타내고 있습니다."Action" 열과 함께 위의 의사 코드에 기반한 결과를 관찰할 수 있습니다.각 행에 대해 표시되는 변수 값은 지정된 액션이 완료된 후의 값입니다.이 예에서 주목해야 할 점은 4개의 프로세서가 잠금을 취득하려고 할 때 가장 먼저 도착한 프로세서만 실제로 잠금을 취득한다는 것입니다.첫 번째 시도에서는 잠금이 유지되는 동안 모든 후속 시도에서는 중요한 섹션에서 차례를 기다리는 프로세서의 대기열이 형성됩니다.그 후, 각각이 차례대로 잠금을 취득해, 이전 홀더가 떠날 때, 다음 줄의 사람이 잠금을 취득할 수 있도록 합니다.또, 다른 프로세서는, 다른 프로세서에 의한 락 취득/해제 순서중에 언제라도 도착해, 차례를 기다릴 수 있습니다.

잠금을 사용하기 전에 첫 번째 단계는 모든 잠금 변수(행 1)의 초기화입니다.next_ticket 및 now_serving을 0으로 초기화하면 잠금을 취득하려고 하는 첫 번째 스레드가 티켓0을 취득할 수 있게 되어 티켓이 now_serving과 일치하기 때문에 잠금을 취득할 수 있게 됩니다.따라서 P1이 잠금을 취득하려고 하면 즉시 성공하고 next_ticket이 1(Row 2)로 증가합니다.P3가 잠금을 취득하려고 하면 my_ticket에 대해 1이 되고 다음 티켓은 2로 증가하며 now_serving이 0이므로 대기해야 합니다(Row 3).다음으로 P2가 잠금을 취득하려고 하면 my_ticket에 대해 2가 되고 next_ticket은 3으로 증가하며 now_serving이 0이기 때문에 대기해야 합니다(4행).여기서 P1은 now_serving을 1로 증가시킴으로써 잠금을 해제하고 my_ticket 값이 1(Row 5)이기 때문에 P3은 잠금을 취득할 수 있습니다.이제 P3는 잠금을 해제하고 now_serving을 2로 증가시켜 P2가 잠금을 획득할 수 있도록 합니다(Row 6).P2가 잠금을 가지고 있는 동안 P4는 잠금을 취득하려고 시도하고 my_ticket 값 3을 취득하고 next_ticket을 4로 증가시키며 now_serving이 아직 2(Row 7)이므로 대기해야 합니다.P2가 잠금을 해제하면 now_serving이 3으로 증가하여 P4가 잠금을 취득할 수 있게 됩니다(Row 8).마지막으로 P4는 잠금을 해제하고 now_serving을 4(Row 9)로 증가시킵니다.현재 대기 중인 스레드에는 이 티켓 번호가 없기 때문에 다음 스레드에는 티켓이 4개 도착하고 즉시 잠금을 획득합니다.

잠금 장치 비교

Linux 커널 구현은 최신 머신에서의 단순한 테스트 및 설정 또는 교환 기반의 스핀록 알고리즘보다 지연 시간이 짧을 수 있습니다.다양한 유형의 스핀 기반 잠금 장치를 비교할 때는 아래 표를 참조하십시오.보다 기본적인 잠금 메커니즘은 고급 잠금 ^[1]메커니즘보다 제어되지 않은 대기 시간이 짧습니다.

이점

• 티켓 잠금이 다른 스핀록알고리즘에 비해 좋은 점 중 하나는 공평하다는 것입니다.대기 스레드는 dequeue 티켓 정수가 증가함에 따라 선입선출 방식으로 처리되므로 기아가 방지됩니다.
• 또한 티켓 잠금 알고리즘은 한 번에 1개의 스레드만 크리티컬섹션에 들어가려고 하기 때문에 천둥 무리 문제가 발생하는 것을 방지합니다.
• 어레이의 ^[1]개별 요소에서 스레드가 회전하는 어레이 기반 큐잉 잠금(ABQL)과는 달리 모든 스레드가 하나의 변수로 회전하기 때문에 스토리지가 반드시 문제가 되는 것은 아닙니다.

단점들

• 한 가지 단점은 잠금을 ^[1]해제하기 전에 모든 스레드가 회전하고 있는 값을 읽고 테스트하기 위해 추가 명령이 필요하기 때문에 제어되지 않은 지연이 더 크다는 것입니다.
• 티켓 잠금의 또 다른 큰 단점은 확장성이 없다는 것입니다.조사에 따르면 프로세서가 티켓락 시스템에 추가되면 성능이 기하급수적으로 ^[4]저하되는 것으로 나타났습니다.
• 또 다른 문제는 잠금을 해제하는 것입니다.모든 스레드는 하나의 변수로 회전하므로 잠금을 해제하면 δ(p) 무효화(및 δ(p) 수집)가 발생합니다.이는 모든 스레드가 해당 블록을 캐시에 새로고침하고 테스트를 수행하여 크리티컬섹션으로의 어드미티먼트를 판별해야 하기 때문입니다.^[1]

역사

티켓락은 1991년 ^[3]멜러-크럼메이와 스콧에 의해 도입되었다.이 알고리즘은 Linux 커널의 ^[5]장점 때문에 2008년에 도입되었지만, ^[6]단점이 있는 반가상화 환경에서는 생략되었습니다.2010년 7월^[update] 현재 반가상화에서 ^[7]티켓 잠금을 사용할 수 있도록 하는 작업이 진행 중입니다.2015년 3월 현재 이러한 유형의 잠금 스킴은 Red Hat Enterprise Linux에 ^[8]의해 시스템에 다시 적용되고 있습니다.

관련 작업

• Lamport의 베이커리 알고리즘은 유사한 개념의 "티켓" 또는 "카운터"를 사용하지만 원자 하드웨어 연산을 사용하지 않습니다.퍼포먼스가 아니라 폴트 톨러런스용으로 설계되어 있습니다.모든 프로세서가 릴리스 카운터를 계속 검사하는 것이 아니라 베이커리 록은 피어 ^[3]티켓 검사로 회전합니다.
• 큐 기반 스핀락은 웨이터 대기열을 유지하고 잠금 해제 작업 중에 ^[9]첫 번째 웨이터에게 잠금을 부여함으로써 공정성을 보장합니다.

「 」를 참조해 주세요.

• fetch-and-add, 티켓 잠금을 구현하기 위해 fetch-and-pass 대신 사용할 수 있는 또 다른 원자 명령

레퍼런스