Egloos | Log-in
F/OSS study
F/OSS study
[Linux] ticket spin lock
Linux: 2.6.30
arch: x86


spin lock은 mutiprocessor system에서
여러 processor가 동시에 critical section에 진입하지 못하도록 하는 synchronization 기법이다.
한 processor가 lock을 가지고 있으면 다른 processor들은 unlock될 때까지 busy-wait하다가
lock을 차지하기 위해 동시에 lock 변수에 접근(write)한다.

여기서 두 가지 문제가 발생할 수 있는데
첫 번째는 각 processor 간에 lock을 획득하는 순서를 보장할 수 없기 때문에
먼저 spin lock을 기다리던 processor가 더 나중에 lock을 얻을 수도 있다는 것이다.
때문에 spin lock은 공정하지 못하다.

또 하나의 문제는 성능에 관련된 것으로
cache coherency로 인해 한 processor가 lock 변수에 write를 하게되면
다른 모든 processor의 cache line이 invalidate된다.
따라서 contention이 심한 경우 lock을 얻은 processor에서도 반복적으로 cache miss가 발생하여
실행 성능이 매우 나빠질 수 있다. (보통 lock 변수와 데이터는 같은 line에 놓여있을 것이다.)

ticket spin lock은 이를 개선하기 위해 2.6.25 버전부터 도입된 것으로
lock을 기다리는 각 processor들은 자신 만의 ticket을 부여받고
자기 차례가 돌아오는 경우에만 write를 시도하므로
순서대로 lock을 얻을 수 있으며 전체적으로 cache miss 횟수를 줄일 수 있다.

그럼 코드를 살펴보자.
spin_lock()은 다음과 같이 정의되어 있다.

/* include/linux/spinlock.h */
#define spin_lock(lock)            _spin_lock(lock)

/* kernel/spinlock.c */
void __lockfunc _spin_lock(spinlock_t *lock)
{
    preempt_disable();
    spin_acquire(&lock->dep_map, 0, 0, _RET_IP_);
    LOCK_CONTENDED(lock, _raw_spin_trylock, _raw_spin_lock);
}

먼저 커널 선점 기능을 disable한 후에 spin_acquire()를 호출하는데
이는 CONFIG_LOCKDEP가 선택된 경우 lock을 얻으려는 processor의 정보를 기록하기 위한 것이다.
LOCK_CONTENDED의 경우도 비슷한데 CONFIG_LOCKSTAT이 설정되지 않은 경우에는
단순히 _raw_spin_lock()을 호출하는 코드로 확장된다.
_raw_spin_lock도 CONFIG_DEBUG_SPINLOCK이 설정되지 않았다면
단순히 __raw_spin_lock()을 호출하는 코드로 확장된다.
__raw_spin_lock 계열의 함수는 architecture-specific 함수로 x86의 경우 다음과 같이 정의된다.

static __always_inline void __raw_spin_lock(raw_spinlock_t *lock)
{
    __ticket_spin_lock(lock);
}

static __always_inline int __raw_spin_trylock(raw_spinlock_t *lock)
{
    return __ticket_spin_trylock(lock);
}

static __always_inline void __raw_spin_unlock(raw_spinlock_t *lock)
{
    __ticket_spin_unlock(lock);
}

위에서 볼 수 있듯이 단순히 ticket_spin_lock 계열의 함수를 호출하는 방식으로 구현되어 있다.
먼저 간단한 unlock의 경우부터 살펴보기로 하자.
ticket spin lock은 processor의 수가 256 개를 넘어가는 머신의 경우를 구분하여 구현되어 있는데
여기서는 이 부분은 무시하고 NR_CPUS 값이 256 이하인 경우 만을 살펴볼 것이다.
따라서 spin lock을 기다라는 모든 processor의 정보는 한 byte 내에 포함할 수 있다. (TICKET_SHIFT = 8)

static __always_inline void __ticket_spin_unlock(raw_spinlock_t *lock)
{
    asm volatile(UNLOCK_LOCK_PREFIX "incb %0"
             : "+m" (lock->slock)
             :
             : "memory", "cc");
}

unlock은 단순히 raw_spinlock_t 구조체의 slock 변수를 1 증가시키는 일만 수행한다.
여기서 주의깊게 살펴보아야 할 부분은 incb로 최하위 바이트의 값 만을 증가시킨다는 것이다.

slock 변수는 개념적으로 두 부분으로 나누어지는데
위에서 언급한대로 NR_CPUS가 256보다 작은 경우에는 하위 두 바이트를 사용하며
상위 바이트는 lock을 기다리는 processor들을 위한 ticket 값이고 (next)
하위 바이트는 현재 lock을 가지고 있는 processor의 ticket 값이다. (owner)

unlock()이 호출되면 현재 processor가 lock을 반환한다는 의미이므로
다음 processor가 lock을 얻을 수 있도록 owner ticket을 증가시킨다.
lock은 자기가 보관하고 있는 next ticket 값과 owner ticket 값이 일치하는 경우에 얻는다.

static __always_inline void __ticket_spin_lock(raw_spinlock_t *lock)
{
    short inc = 0x0100;

    asm volatile (
        LOCK_PREFIX "xaddw %w0, %1\n"
        "1:\t"
        "cmpb %h0, %b0\n\t"
        "je 2f\n\t"
        "rep ; nop\n\t"
        "movb %1, %b0\n\t"
        /* don't need lfence here, because loads are in-order */
        "jmp 1b\n"
        "2:"
        : "+Q" (inc), "+m" (lock->slock)
        :
        : "memory", "cc");
}

이 코드는 (동기화와 관련된 문제를 제외하면) 개념적으로 아래와 같다.

static __always_inline void __ticket_spin_lock(raw_spinlock_t *lock)
{
    short inc = 0x100;
    short tmp = (short) lock->slock;
    lock->slock += inc;

    while ((tmp >> 8) != (tmp & 0xFF)) {
        cpu_relax();
        tmp = (tmp & 0xFF00) | (unsigned char) lock->slock;
    }
}

우선 lock->slock 값을 읽어오고 동시에 next ticket을 증가시킨다. (lock; xaddw)
읽어온 slock의 상위 바이트는 현재 processor의 ticket 값으로 저장하고
동시에 다음 processor가 lock을 얻기 위한 ticket을 증가시키는 것이다.
이는 LOCK_PREFIX가 붙어있으므로 atomic하게 수행된다.

그리고는 증가시키기 전의 slock 변수에서 next와 owner ticket이 동일한지 검사한다. (cmpb %h0, %b0)
만약 같다면 현재 processor가 lock을 얻은 것이므로 loop을 종료하고 critical section에 진입한다.
그렇지 않다면 계속 slock의 owner ticket 값을 갱신한 후 다시 검사한다. (movb %1, %b0)
즉, unlock이 수행된 후에 lock을 얻기 위해 다시 lock 변수를 write하지 않아도 된다!

trylock()은 slock 값을 먼저 살펴본 후 lock을 얻을 수 있는 경우에만 slock 변수를 write한다.

static __always_inline int __ticket_spin_trylock(raw_spinlock_t *lock)
{
    int tmp, new;

    asm volatile("movzwl %2, %0\n\t"
             "cmpb %h0,%b0\n\t"
             "leal 0x100(%k0), %1\n\t"
             "jne 1f\n\t"
             LOCK_PREFIX "cmpxchgw %w1,%2\n\t"
             "1:"
             "sete %b1\n\t"
             "movzbl %b1,%0\n\t"
             : "=&a" (tmp), "=&q" (new), "+m" (lock->slock)
             :
             : "memory", "cc");

    return tmp;
}

이 코드는 개념적으로 아래와 같다.

static __always_inline int __ticket_spin_trylock(raw_spinlock_t *lock)
{
    int tmp, new;

   tmp = (short) lock->slock;
    if ((tmp >> 8) != (tmp & 0xFF)) {
        return 0;

    new = tmp + 0x100;
    if (tmp == (short) lock->slock) {
        lock->slock = new;
        tmp = 1;
    } else {
        tmp = 0;
    }
    return tmp;
}

먼저 현재 slock 변수의 값을 읽어서 lock을 기다리는 processor가 있는지 확인한다. (movzwl %2, %0)
이는 next ticket과 owner ticket이 다른 경우이므로 바로 0을 return한다. (cmpb %h0, %b0)
그렇지 않다면 next ticket을 1 증가시켜두는데 (leal 0x100(%k0), %1)
이는 tmp(%0)의 값을 new(%1)로 옮기고 new 값을 증가시키는 작업을 한 번에 처리해주는 hack이다.

그 동안 slock값이 바뀌지 않았다면 증가시킨 값으로 갱신한다. (lock; cmpxchgw %w1,%2)
이도 LOCK_PREFIX가 붙어있으므로 atomic하게 수행된다.
cmpxchg의 결과는 ZF 플래그에 저장되므로 이 값을 읽어서 new 변수의 최하위 바이트에 저장하고 (sete %b1)
이를 다시 tmp 변수에 옮긴 후 return한다. (movzbl %b1,%0)
by namhyung | 2009/10/17 19:27 | Kernel | 트랙백 | 핑백(1) | 덧글(9)
트랙백 주소 : http://studyfoss.egloos.com/tb/5144295
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Linked at spinlock –.. at 2015/12/18 09:20

... in_lock, spin_lock_irq, spin_lock_irqsave란 무엇인가 Linux Spinlock Internals | LinuxInternals.org ticket spin lock | F/OSS stydy Improving ticket spinlocks | LWN.net Ticket spinlocks | LWN.net Ticket lock ... more

Commented by ahtz at 2010/11/22 22:18
따라서 contention이 심한 경우 lock을 얻은 processor에서도 반복적으로 cache miss가 발생하여
실행 성능이 매우 나빠질 수 있다. (보통 lock 변수와 데이터는 같은 line에 놓여있을 것이다.)
--> 잘 이해가 안가요... 쫌 더 설명해 주심 감사하겠습니다.
일단 용어가... processor가 아니고 process겠죠..(task, thread 든지)

제가 이해하는 상황은요..
경쟁이 심한 경우는, 일단 어떤 놈이 락을 가지고 있던 아니면 아무도 가지고 있지 않을 때 여러 놈이 가지려고 할 경우 두 경우가 있겠죠..
이 경우에, 락을 이미 어떤 놈이 가지고 있는 상태라면 락변수의 데이터를 갱신하지 못하므로 일단 캐쉬 미스가 생기지 않을거라고 봅니다.
캐쉬에 직접 쓰는 것이 아니고 일단 메모리에 쓰던 말던 해야 발생하는 상황이니까요..(라이트백의 경우)
라이트 뚜루의 경우에는 일단 L1캐쉬는 건들 수 있을지 몰라도 메모리는 못건들죠, 이미 어떤 프로세스가 가지고 있으니...
그래서 설명하신 글이 이해가 안가요. 꼭 좀 자세한 설명 부탁 드려요.
Commented by namhyung at 2010/11/23 11:34
먼저 다음과 같은 구조체가 있다고 가정해 보겠습니다.

struct {
spinlock_t lock;
struct list_head list;
}

lock은 list를 보호하기 위해 사용되며 아마도 같은 cache line 상에 놓일 것입니다.
MP 시스템에서 여러 CPU (혼동을 줄이기 위해 processor 대신 CPU라고 표현하겠습니다)에서 실행되는 task들이
동시에 동일한 구조체 영역에 접근하는 경우라면 모두 spin lock을 얻으려고 lock 필드의 값을 바꾸려고 시도하지만
이는 atomic하게 처리되므로 오직 맨 처음에 시도한 하나의 CPU(에서 실행하는 task. 이하 생략) 만 성공하고 나머지는 실패할 것입니다.

성공한 CPU는 (lock으로 보호되는) list에 접근하게 되는데 이 list 필드는 lock을 얻은 순간에는 cache에 있을테지만
이 후에 lock을 얻기 위해 시도하는 다른 CPU들이 계속 lock 필드를 write하기 때문에 cache coherency protocol에 의해
해당 cache line이 invalidate되고 따라서 같은 line에 속한 list 필드도 cache에서 제거되므로 메모리에 접근하게 되는 것입니다.
(이를 false sharing이라고 하지요.)

알고계시겠지만 MESI protocol에 의해 한 CPU에서 특정 데이터를 write하려고 하면
다른 CPU들의 해당 cache line이 invalidate 됩니다. 이건 write-through던 write-back이던 상관없구요
다만 write-through cache의 경우는 cache에 데이터를 쓰면 메모리에도 같이 쓰게 되는 것이고
write-back cache의 경우에는 cache line이 evict되는 경우에 메모리에 쓰도록 미루는 것입니다.
Commented by ahtz at 2010/11/24 16:36
답변 감사드려요.
또 질문 있습니다.

그래서 spin lock 과 같이 동기화를 위한 글로벌 변수는 volatile 로 접근하지 않나요?
항상 메모리에서만 읽고 쓰도록, 캐쉬를 사용하지 못하게 하는거죠.

다시 남형(namhyung)님께서 말씀하신 대로 생각하면요,
(*** 캐쉬에 spinlock 변수가 있다고 가정을 해야 합니다.)
코어(C) 0-3 까지 있다고 가정하구요, 각 코어의 L1 cache를 $라고 하구요, SpinLock - SL

여러 코어가 스핀락을 얻으려고 경쟁하는 상황
C0-$SL
C1-$SL
C2-$SL
C3-$SL

C1이 먼저 요청해서 써버린 상황
C0-$SL- invalidated by C1's success
C1-$SL- updated
C2-$SL- invalidated by C1's success
C3-$SL- invalidated by C1's success

그런데 여기서 C0, C2, C3 가 계속 spinlock을 얻으려고 값을 쓰기 때문에

C0-$SL- write
C1-$SL- invalidated by C0's write, invalidated by C2's write, invalidated by C3's write,
C2-$SL- write
C3-$SL- write

이라는 말씀이시죠?

예시하신 프로그램을 따르면요, 캐쉬를 업데이트하는 구문이 없어보이는데요...

1. C0 ~ C3 이 모두 __ticket_spin_lock을 호출하게 됩니다.
2. C1이 먼저 실행했다면 이라기 보다 다음 ticket값이 C1의 ticket값과 동일하다면,
while((tmp >> 8) != (tmp & 0xFF)) 에서 성공해서 critical section에 들어갑니다.
3. 나머지 C2 ~ C3는 모두 while loop 안에서 기다리므로 instruction을 보면 더 이상 캐쉬에 대한
쓰기 동작은 없어보이는데요? C1이 unlock하는 경우에나 캐쉬에 쓰는 동작이 발생할거라 생각합니다.

바로 여기서 의문이 이겁니다.
lock을 얻은 processor에서도 반복적으로 cache miss가 발생하여
--> critical section 안에서 lock과 관련한 참조는 없으니까 캐쉬에 있을 lock에 대한 캐쉬 미스는 없지 않나요?

실행 성능이 매우 나빠질 수 있다. (보통 lock 변수와 데이터는 같은 line에 놓여있을 것이다.)
lock 변수와 데이터는 같은 캐쉬 라인에 놓여 있습니다. - 동의합니다. 특별히 메모리 변수로 하지 않는한...
하지만 캐쉬 미스가 없기 때문에 실행 성능과는 관계가 없을 듯 한데요...

tmp는 __ticket_spin_lock 함수 안의 스택 변수이고요,
lock->slock은 전역변수겠죠. 아주 특별한 경우을 제외하면,
캐쉬에다 가져오는 변수는 스택 변수와 volatile로 선언하지 않고 루프내에서 자주 참조하는 친구들을 가져온다고
알고 있어요. (틀릴 수도 있음.)
만약 lock->slock을 캐쉬에 가져와 놨다고 (가정) 생각해서 while 안의 tmp 값이 틀리니까 lock->slock 이 틀리구나!
생각해서 캐쉬 미스라고 판단하고, 메모리에서 가져온다고 말씀하시는 건지요?
그런데 캐쉬 미스는 접근하려는 주소가 있는지 없는지로 판단하는 거지 저장된 값으로 판단하는게 아니라고 압니다.
그래서... 캐쉬 미스는 발생하지 않을거고 그냥 계속 지가 갖고 있는거랑 비교하면서 기다릴거 같거든요.
C1이 마침내 티켓값을 올리면 그제서야 다른 애들 캐쉬가 업데이트되고 하겠죠. 그때도 캐쉬 미스는 없고
캐쉬 컨트롤러가 각 코어의 L1을 업데이트 하겠죠. 컨트롤러가 어떻게 만들어졌냐에 따르겠지만...


제가 내공이 딸려서 이 정도밖에 상상이 안되네요.

그럼 또 즐거운 답변 부탁 드릴게요 ^^;
Commented by namhyung at 2010/11/25 00:42
먼저 volatile에 대해서 말씀드리자면
volatile은 컴파일러 단에서 instruction 생성 시에 영향을 주는 것이며 cache 사용에 영향을 주지는 못합니다.
(사실 C 언어 자체에 cache에 대한 개념이 없기 때문에 이를 제어할 방법도 없을 것입니다.)
단지 해당 변수를 읽을 때 register를 이용하여 이전 값을 보관해 두는 최적화를 수행하지 말고
항상 메모리에 접근하도록 적절한 instruction을 생성하는 역할을 하는 것입니다.
하지만 CPU가 instruction을 실행할 때 해당 데이터가 cache에 있다면 메모리 접근 없이 cache의 데이터를 사용할 것입니다.

또한 언급하신 내용은 이 글에서 설명하는 ticket lock이 구현되기 이전에 해당하는 내용이므로
ticket lock 구현과 비교하시면 당연히 맞지 않습니다.. ^^;;

또한 말씀하신대로 cache controller가 어떻게 구현되어 있느냐에 따라 다를테지만
제가 알기론 x86에서는 기본적으로 별다른 제약이 없는 한 모든 메모리 접근은 cache에 올라가고
write 시에는 다른 CPU들의 cache line이 invalidate되는 것으로 알고 있습니다.
lock->slock을 반복적으로 읽을 때 lock이 걸린 상태라면 계속 cache hit가 일어날 것이므로 cache의 데이터를 읽을 테지만
unlock이 되는 순간 cache가 invalidate되므로 메모리 접근이 발생하여 (자동으로) 변경된 데이터를 읽어올 것입니다.
물론 false sharing으로 인해서도 cache miss가 발생할 수 있습니다.
Commented by ahtz at 2010/11/24 16:42
그런데 멀티코어 환경에서 꼭 스핀락을 써야 하나요? 딴거 효과적인건 없을까요?
자주 쓰시는 이메일 있으심 좀 알려주세요, 덧글이 너무 길어질듯해서요...
Commented by namhyung at 2010/11/25 00:49
리눅스 커널 소스를 보면 spin lock 이외에도 많은 종류의 동기화 기법들이 사용되고 있습니다.
각각의 장단점이 있으니 사용하려는 목적이나 환경에 따라 가장 적합한 것을 선택하여 사용하시면 됩니다.

개인적으로 답변을 드리기에는 제 지식도 미천하고 상황에 따라 답변이 늦어지거나 못 해드릴 수도 있으니
저보다 더 뛰어난 분들이 많은 웹 상의 다른 장소에 질문하시는 것이 더 좋지 않을까 싶습니다.
http://kldp.org 혹은 http://iamroot.org 정도를 추천드립니다.
Commented by ahtz at 2010/11/25 19:25
많은 도움 되었습니다. ^^
Commented by JUNE at 2014/05/28 07:55
많은 도움이 되었습니다 감사합니다..
ahtz분께도 감사드립니다... 두분에서 질문하고 답변하는 상황에서도 얻을수잇는게 많았습니다.
Commented by zeze at 2015/03/20 10:42
namhyung님, ahtz님, 좋은 글과 질답 고맙습니다. 여러 번 읽고 되새기며 적용해 봐야 겠어요~!

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
patch CARM SMP build vcs scm glibc perf C blktrace sed block-layer computer-architecture kernel gcc elf git emacs CAaQA3 bash memory linux documentation script synchronization compiler algorithm binutils awk x86
전체보기
이글루 파인더

최근 등록된 덧글
http://serbaserbiinfoterkini56..
by cakra at 09/22
informsi yang bagus dan b..
by cakra at 09/16
informsi yang bagus dan be..
by pordanaia at 08/05
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X