스핀록

Spinlock

소프트웨어 공학에서 스핀록은 그것을 획득하려고 하는 스레드가 잠금 장치가 가능한지 반복적으로 확인하면서 루프("스핀")로 간단히 대기하게 하는 잠금이다.스레드는 활성 상태를 유지하지만 유용한 작업을 수행하고 있지 않기 때문에, 그러한 잠금 장치를 사용하는 것은 일종의 바쁜 기다림이다.일단 획득한 스핀록은 일반적으로 명시적으로 해제될 때까지 유지되지만, 일부 구현에서는 (잠금을 잡고 있는) 스레드가 차단되거나 "수면"될 경우 자동으로 해제될 수 있다.

운영 체제 프로세스 일정 변경이나 컨텍스트 전환으로 인한 오버헤드를 피하기 때문에 스레드가 단기간만 차단될 가능성이 높은 경우 스핀록이 효율적이다.이러한 이유로 운영체제 커널은 종종 스핀록을 사용한다.그러나 스핀락은 다른 스레드가 실행되지 않고 일정 조정이 필요할 수 있기 때문에 더 오랫동안 보관하면 낭비가 된다.스레드가 잠금 장치를 오래 유지할수록 잠금 장치를 유지하는 동안 OS 스케줄러에 의해 스레드가 중단될 위험이 커진다.이렇게 되면 다른 나사산은 "회전"(반복적으로 잠금 장치를 획득하려고 시도)하게 되고, 잠금 장치를 고정하는 나사산은 잠금 해제 쪽으로 진전되지 않는다.그 결과는 자물쇠를 잡고 있는 실이 다 끝나고 풀 수 있을 때까지 무기한 연기된다.특히 단일 프로세서 시스템에서는 동일한 우선 순위의 각 대기 스레드가 자물쇠를 고정하는 스레드가 최종적으로 완성될 때까지 양자(스레드가 실행될 수 있는 할당 시간) 회전하는 데 낭비될 가능성이 높다.

프로그래머들은 동시에 자물쇠에 접근할 수 있는 가능성을 고려해야 하기 때문에 회전 자물쇠를 올바르게 구현하는 것은 어려운 일이며, 이것은 경주 조건을 야기할 수 있다.일반적으로 그러한 구현은 원자 시험 및 설정 운영과 같은 특수한 조립 언어 지침만으로 가능하며, 진정한 원자 작동을 지원하지 않는 프로그래밍 언어에서는 쉽게 구현될 수 없다.[1]그러한 연산이 없는 아키텍처에서, 또는 높은 수준의 언어 구현이 필요한 경우, 예를 들어 피터슨의 알고리즘과 같은 비원자 잠금 알고리즘을 사용할 수 있다.그러나 이러한 구현에는 스핀록보다 많은 메모리가 필요할 수 있으며, 잠금 해제 후 진행을 허용하는 데 더 느릴 수 있으며, 고장난 실행이 허용될 경우 높은 수준의 언어로 구현이 불가능할 수 있다.

구현 예

다음 예제는 스핀록을 구현하기 위해 x86 어셈블리 언어를 사용한다.모든 Intel 80386 호환 프로세서에서 작동한다. 

; Intel 구문  잠긴:                      ; 잠금 변수.1 = 잠금, 0 = 잠금 해제.      dd      0  spin_lock:      영화를 찍다     이삭스, 1          ; EAX 레지스터를 1로 설정하십시오.      xchg.    이삭스, [잠긴]   ; EAX 레지스터와 원자적으로 교환                              ; 잠금 변수.                              ; 이것은 항상 자물쇠에 1을 저장하여 남겨둔다.                              ; EAX 레지스터의 이전 값.      시험하다    이삭스, 이삭스        ; 스스로 EAX를 시험한다.무엇보다도 이 유언은                              ; EAX가 0일 경우 프로세서의 제로 플래그를 설정하십시오.                              ; EAX가 0이면 잠금장치가 해제되고                              그냥 잠갔어.                              그렇지 않으면 EAX는 1이고 우리는 자물쇠를 획득하지 않았다.      jnz     spin_lock       ; Zero 플래그가 있는 경우 MOV 명령으로 돌아가기                              ; 설정되지 않음; 이전에 잠금이 잠겨 있었으므로                              잠금이 풀릴 때까지 회전해야 한다.      되받아치다                     ; 잠금이 획득되었으므로 호출로 돌아가십시오.                              ; 기능.  spin_properties:      xor     이삭스, 이삭스        ; EAX 레지스터를 0으로 설정하십시오.      xchg.    이삭스, [잠긴]   ; EAX 레지스터와 원자적으로 교환                              ; 잠금 변수.      되받아치다                     ; 자물쇠가 풀렸다.

상당한 최적화

위의 간단한 구현은 x86 아키텍처를 사용하는 모든 CPU에서 작동한다.그러나 다음과 같은 여러 가지 성능 최적화가 가능하다.

나중에 x86 아키텍처를 구현할 때 spin_unlock은 더 느리게 잠긴 XCHG 대신 잠금 해제된 MOV를 안전하게 사용할 수 있다.MOV가 완전한 메모리 장벽이 아님에도 이를 뒷받침하는 미묘한 메모리 순서 규칙 때문이다.그러나 일부 프로세서(일부 Cyrix 프로세서, Intel Pentium Pro의 일부 개정판(버그로 인해), 초기 Pentium 및 i486 SMP 시스템)는 잘못된 작업을 수행하며 잠금으로 보호되는 데이터가 손상될 수 있다.대부분의 비 x86 아키텍처에서는 명시적 메모리 장벽 또는 원자 명령(예시)을 사용해야 한다.IA-64와 같은 일부 시스템에는 필요한 메모리 순서를 제공하는 특별한 "잠금 해제" 지침이 있다.

CPU 간 버스 트래픽을 줄이려면 잠금 장치를 획득하려는 코드가 변경된 값을 읽을 때까지 아무 것도 쓰지 않고 읽기를 반복해야 한다.MESI 캐싱 프로토콜 때문에, 이것은 잠금을 위한 캐시 라인이 "공유"가 되게 하고, CPU가 잠금을 기다리는 동안 버스 트래픽이 눈에 띄게 없다.이러한 최적화는 MESI가 매우 광범위하기 때문에 CPU당 캐쉬가 있는 모든 CPU 아키텍처에 효과적이다.하이퍼 스레드 CPU에서 일시 중지rep nop잠금 장치가 회전하는 동안 다른 스레드에서 작동할 수 있음을 코어에서 암시함으로써 추가 성능을 제공한다.[2]

트랜잭션 동기화 확장 및 기타 하드웨어 트랜잭션 메모리 명령 집합은 대부분의 경우 잠금을 대체하는 역할을 한다.자물쇠는 여전히 예비로 필요하지만, 그것들은 프로세서가 원자력 운영의 전체 블록을 처리하도록 함으로써 성능을 크게 향상시킬 수 있는 잠재력을 가지고 있다.이 기능은 glibc와 같은 일부 뮤텍스 구현에 내장되어 있다.x86의 HLE(Hardware Lock Elision)는 약화되었지만 역호환되는 TSE 버전이며, 여기서는 호환성을 잃지 않고 잠금을 위해 사용할 수 있다.이 특별한 경우에 프로세서는 두 개의 스레드가 실제로 서로 충돌할 때까지 잠그지 않기로 선택할 수 있다.[3]

테스트의 간단한 버전은cmpxchgx86 또는 에 대한 지시__sync_bool_compare_and_swap많은 유닉스 컴파일러에 내장되어 있다.

최적화가 적용되면 샘플은 다음과 같이 보일 것이다.

; in C: while()!___bool_nd_and_build_na_nd(&built, 0, 1) 동안 __builtin_ia32_built(); spin_lock:     영화를 찍다     ecx, 1             ; ECX 레지스터를 1로 설정하십시오. 재시도:     xor     이삭스, 이삭스           ; cmpxchg가 EAX와 비교하기 때문에 EAX를 0으로 한다.     엑스콰이어 자물쇠를 채우다 cmpxchg [잠긴], ecx                                ; 원자로 결정: 잠금이 0이면 ECX를 여기에 쓰십시오.                                ; XACQUIRE는 우리가 잠금을 획득하고 있다는 것을 프로세서에 암시한다.     제를      밖으로                ; 잠근 경우(이전 값은 EAX: 0과 같음) 반환 일시 중지:     영화를 찍다     이삭스, [잠긴]      ; EAX에 잠긴 판독값.     시험하다    이삭스, 이삭스           ; 이전과 같이 제로 테스트를 수행하십시오.     JZ      재시도하다              0이면 재시도할 수 있다.     대변을 보다 끄떡없다                    ; CPU에 우리가 스핀루프에서 기다리고 있다고 말해, 그것이 가능한지.                                ; 다른 실을 지금 작업한다.또한 "일시 중지"로 기록된다.     jmp     잠시 멈추다              ; 계속 체크-pausing을 한다. 아웃:     되받아치다                        ; 모두 끝났다.  spin_properties:     XRELEASE 영화를 찍다 [잠긴], 0   ; 메모리 주문 규칙이 적용된다고 가정하여                                ; "잠금 해제" 힌트가 있는 잠금 변수.     되받아치다                        ; 자물쇠가 풀렸다.

대안

스핀록의 주된 단점은 잠금장치를 획득하기 위해 기다리는 동안 다른 곳에서 생산적으로 소비될 수 있는 시간을 낭비한다는 것이다.이를 피하는 방법에는 두 가지가 있다.

  1. 잠금을 획득하지 마십시오.많은 상황에서, 예를 들어 스레드 또는 CPU당 데이터를 사용하고 인터럽트를 비활성화함으로써 잠금이 필요하지 않은 데이터 구조를 설계할 수 있다.
  2. 기다리는 동안 다른 스레드로 전환하십시오.여기에는 일반적으로 잠금을 기다리는 스레드의 대기열에 현재 스레드를 연결한 후 유용한 작업을 수행할 준비가 된 다른 스레드로 전환하는 작업이 포함된다.이 계획은 또한 모든 스레드가 결국 그들이 획득한 자물쇠를 포기하고 어떤 스레드가 먼저 진행되어야 하는지에 대한 일정을 결정할 수 있는 한 자원 기아 현상이 발생하지 않도록 보장한다는 장점이 있다.실시간 운영 체제에서 사용할 수 있는 스위칭을 전혀 수반하지 않는 스핀록을 원시 스핀록이라고도 한다.[4]

대부분의 운영 체제(솔라리스, Mac OS X 및 FreeB 포함)SD) "어댑티브 뮤텍스"라는 하이브리드 접근 방식을 사용한다.현재 실행 중인 스레드에 의해 잠긴 자원에 접근하려고 할 때는 스핀록을 사용하되, 스레드가 현재 실행 중이 아니면 절전 모드를 사용하자는 생각이다.(단일 프로세서 시스템에서는 항상 후자가 해당된다.)[5]

OpenBSD는 스핀록을 티켓 잠금으로 대체하여 선착순 행동을 강제하려 했으나, 이로 인해 커널의 CPU 사용량이 증가하고 Firefox와 같은 대형 애플리케이션은 훨씬 느리게 되었다.[6][7]

참고 항목

참조

  1. ^ Silberschatz, Abraham; Galvin, Peter B. (1994). Operating System Concepts (Fourth ed.). Addison-Wesley. pp. 176–179. ISBN 0-201-59292-4.
  2. ^ "gcc - x86 spinlock using cmpxchg". Stack Overflow.
  3. ^ "New Technologies in the Arm Architecture" (PDF). Archived (PDF) from the original on 2019-04-02. Retrieved 2019-09-26.
  4. ^ Jonathan Corbet (9 December 2009). "Spinlock naming resolved". LWN.net. Archived from the original on 7 May 2013. Retrieved 14 May 2013.
  5. ^ Silberschatz, Abraham; Galvin, Peter B. (1994). Operating System Concepts (Fourth ed.). Addison-Wesley. p. 198. ISBN 0-201-59292-4.
  6. ^ Ted Unangst (2013-06-01). "src/lib/librthread/rthread.c - Revision 1.71". Archived from the original on 2021-02-27. Retrieved 2022-01-25.
  7. ^ Ted Unangst (2016-05-06). "tedu comment on Locking in WebKit - Lobsters".

외부 링크