스핀 잠금 구현이 올바르고 최적입니까?

스핀 잠금 구현이 올바르고 최적입니까?

저는 아주 작은 중요한 부분을 보호하기 위해 스핀락을 사용하고 있습니다.경합은 매우 드물게 발생하므로 일반 뮤텍스보다 스핀 잠금이 더 적합합니다.

현재 코드는 다음과 같고 x86 및 GCC를 가정합니다.

volatile int exclusion = 0;

void lock() {
    while (__sync_lock_test_and_set(&exclusion, 1)) {
        // Do nothing. This GCC builtin instruction
        // ensures memory barrier.
    }
}

void unlock() {
    __sync_synchronize(); // Memory barrier.
    exclusion = 0;
}

그래서 궁금한게 있어요.

• 이 코드가 맞습니까?상호 배제를 올바르게 보장합니까?
• 모든 x86 운영 체제에서 작동합니까?
• x86_64에서도 작동합니까?모든 운영 체제에서?
• 최적인가요?
  • 비교와 스왑을 사용하는 스핀락 구현을 본 적이 있지만 어느 것이 더 나은지는 잘 모르겠습니다.
  • GCC 아토믹 빌트인 문서(http://gcc.gnu.org/onlinedocs/gcc-4.1.2/gcc/Atomic-Builtins.html) 에 따르면 다음과 같은 것들도 있습니다.__sync_lock_release저는 기억 장벽에 대한 전문가가 아니기 때문에 이것을 대신 사용해도 괜찮은지 잘 모르겠습니다.__sync_synchronize.
  • 저는 경합이 없는 경우에 최적화하고 있습니다.

나는 논쟁에 대해 전혀 신경 쓰지 않습니다.며칠에 한 번씩 스핀 잠금을 잠그려고 시도하는 다른 스레드가 1개 또는 2개 있을 수 있습니다.

나한테는 괜찮아 보이는데요.그런데, 여기 논쟁의 경우에도 더 효율적인 교과서적 구현이 있습니다.

void lock(volatile int *exclusion)
{
    while (__sync_lock_test_and_set(exclusion, 1))
        while (*exclusion)
            ;
}

그래서 궁금한게 있어요.

* Is it correct?

언급된 맥락에서, 저는 그렇다고 대답할 것입니다.

* Is it optimal?

그것은 어려운 질문입니다.휠을 재창조함으로써 다른 구현으로 해결된 많은 문제도 재창조할 수 있습니다.

• 저는 당신이 잠금 단어에 접근하려고 시도하지 않는 실패 시 낭비 루프를 예상합니다.

• 잠금 해제에서 전체 차단기를 사용하려면 릴리스 의미론만 있으면 됩니다(그래서 mf 대신 itanium에서 st1.rel을 사용하거나 powerpc에서 alwsync를 사용하도록 __sync_lock_release를 사용합니다.).여기서 사용되는 장벽의 유형이 x86 또는 x86_64에만 관심이 있거나 별로 중요하지 않습니다(그러나 HP-IPF 포트용 인텔의 Itanium으로 이동할 위치가 있다면 이를 원하지 않을 것입니다).

• 일반적으로 폐기물 루프 앞에 놓았던 일시 중지(pause) 명령이 없습니다.

• 당신이 무언가를 원하거나, 반쯤 자포자기하거나, 심지어 바보 같은 잠을 원할 때.만약 당신이 이것이 당신을 구매할 수 있는 성능이 정말로 필요하다면, 후텍스 제안은 아마도 좋은 것일 것입니다.성능이 필요한 경우 이 코드를 유지 관리할 수 있을 정도로 성능이 저하됩니다.

릴리스 장벽이 필요하지 않다는 의견이 있었습니다.릴리스 장벽은 컴파일러에게 다른 메모리 액세스를 "장벽" 주변에서 섞지 않도록 하는 명령어 역할을 하기 때문에 x86에서도 그렇지 않습니다.sm(":: "memory")을 사용하면 얻을 수 있는 것과 매우 유사합니다.

* on compare and swap

x86에서 sync_lock_test_and_set은 암시적 잠금 접두사가 있는 xchg 명령어에 매핑됩니다.확실히 가장 컴팩트하게 생성된 코드(예: int 대신 "잠금 단어"에 바이트를 사용하는 경우)이지만 LOCK CMPXCHG를 사용한 경우보다 정확합니다.비교 및 스왑을 사용하면 고급 알고리즘에 사용할 수 있습니다(예: 첫 번째 "웨이터"에 대한 메타데이터에 대한 0이 아닌 포인터를 실패 시 잠금 단어에 삽입).

질문에 대한 답변:

1. 괜찮아 보여요
2. OS가 GCC를 지원하고 GCC 기능이 구현되어 있다고 가정합니다. 이는 모든 x86 운영 체제에서 작동합니다.GCC 문서는 경고가 특정 플랫폼에서 지원되지 않을 경우 경고가 생성될 것임을 시사합니다.
3. x86-64에 대한 구체적인 내용은 없는데, 왜 그런지 모르겠습니다.이것은 GCC가 지원하는 모든 아키텍처로 확장될 수 있지만, x86이 아닌 아키텍처에서 이를 달성하는 더 최적의 방법이 있을 수 있습니다.
4. 를 사용하는 것이 조금 더 나을 수 있습니다.__sync_lock_release()에 시대에unlock() .하지만, 논쟁이 거의 없을 것이라는 당신의 주장을 가정하면, 그것은 나에게 좋게 보입니다.

최신 버전의 Linux에서 "빠른 사용자 공간 뮤텍스"라는 futex를 사용할 수 있습니다.

적절하게 프로그래밍된 후텍스 기반 잠금은 잠금이 경합되는 경우를 제외하고는 시스템 호출을 사용하지 않습니다.

스핀락을 사용하여 최적화하려는 비경쟁적인 경우, 퓨텍스는 커널 시스템 호출 없이 스핀락처럼 작동합니다.잠금이 경합되면 대기 중이 아닌 커널에서 대기가 발생합니다.

다음 CAS 구현이 x86_64에 맞는 것인지 궁금합니다.i7 X920 노트북(Fedora 13 x86_64, gcc 4.4.5)에서 거의 두 배 더 빠릅니다.

inline void lock(volatile int *locked) {
    while (__sync_val_compare_and_swap(locked, 0, 1));
    asm volatile("lfence" ::: "memory");
}
inline void unlock(volatile int *locked) {
    *locked=0;
    asm volatile("sfence" ::: "memory");
}

정확성에 대해서는 언급할 수 없지만, 질문 본문을 읽기도 전에 당신의 질문 제목이 빨간 깃발을 들었습니다.동기화 기본 요소는 정확성을 보장하기가 매우 어렵습니다...가능하면 잘 설계/유지 관리된 라이브러리(예:pthreads 또는 boost::boost)를 사용하는 것이 좋습니다.

몇 가지 잘못된 가정이 있습니다.

첫째, SpinLock은 리소스가 다른 CPU에서 잠겨 있는 경우에만 의미가 있습니다. 리소스가 동일한 CPU에서 잠겨 있는 경우(단일 프로세서 시스템에서는 항상 해당됨), 리소스 잠금 해제를 위해 스케줄러를 이완시켜야 합니다.스케줄러가 작업을 자동으로 전환하기 때문에 현재 코드는 단일 프로세서 시스템에서 작동하지만 리소스 낭비입니다.

멀티프로세서 시스템에서는 동일한 현상이 발생할 수 있지만 작업이 한 CPU에서 다른 CPU로 마이그레이션될 수 있습니다.즉, 작업이 다른 CPU에서 실행되도록 보장하는 경우 스핀 잠금을 사용하는 것이 올바른 방법입니다.

두 번째로, 잠금 해제 시 뮤텍스를 잠그는 속도가 스핀락만큼 빠릅니다.뮤텍스 잠금(및 잠금 해제)은 뮤텍스가 이미 잠긴 경우에만 느립니다(매우 느림).

그래서, 당신의 경우, 저는 뮤텍스를 사용하는 것을 제안합니다.

한 가지 개선 사항은 TATAS(테스트 및 테스트 및 세트)를 사용하는 것입니다.CAS 작업을 사용하는 것은 프로세서에 매우 비용이 많이 들기 때문에 가능하면 피하는 것이 좋습니다.또 다른 것은 우선 순위 반전이 발생하지 않도록 해야 합니다(우선 순위가 높은 스레드가 잠금을 획득하려고 하는 동안 우선 순위가 낮은 스레드가 잠금을 해제하려고 하면 어떻게 됩니까?예를 들어 Windows의 경우 이 문제는 궁극적으로 스케줄러가 우선 순위 상승을 사용하여 해결하지만, 최근 20번의 시도에서 잠금을 획득하지 못한 경우(예:

스핀락 구현의 효율성을 높이기 위해 잠금 수집이 실패할 때마다 스케줄러에 양보할 수 있습니다.

void lock() {
    while (__sync_lock_test_and_set(&exclusion, 1)) yield(-1) ;
}

잠금 해제 절차에는 메모리 장벽이 필요하지 않습니다. x86에 정렬된 단어가 있는 한 제외에 대한 할당은 원자적입니다.

(32/64)는 스토어 스레드에 되는 것이 될 수 x86은 스토어가 먼저 스토어 버퍼에 배치되어 다른 스레드에 대해 표시되는 것이 지연될 수 있다는 점을 제외하고는 순서를 변경하지 않습니다.그리고 아직 메모리로 플러시되지 않은 경우 저장소를 수행한 다음 동일한 변수에서 읽는 스레드가 저장소 버퍼에서 읽힙니다.그래서 당신이 필요한 것입니다.asm컴파일러 순서 변경을 방지하는 문입니다.다른 스레드의 관점에서 볼 때 한 스레드가 잠금을 필요한 시간보다 약간 길게 유지할 위험이 있지만 경합이 발생하지 않는 경우에는 문제가 되지 않습니다.실은.pthread_spin_unlock내 시스템(linux x86_64)에서 이와 같이 구현됩니다.

내 시스템은 또한 구현됩니다.pthread_spin_lock사용.lock decl lockvar; jne spinloop;사용하는 대신에xchg(그것이 무엇입니까?__sync_lock_test_and_set사용), 하지만 실제로 성능 차이가 있는지는 모르겠습니다.

언급URL : https://stackoverflow.com/questions/1383363/is-my-spin-lock-implementation-correct-and-optimal