vlocks for Bare-Metal Mutual Exclusion

Voting lock의 목적

Voting Locks, 즉 `vlocks`는 메모리 시스템에 합리적이지만 최소한의 요구만 두는 단순한 저수준 mutual exclusion mechanism입니다.

하드웨어가 다른 동기화 수단을 제공하지 않고 일반 spinlock을 사용할 수 없는 상황에서, 서로 cache-coherent하지 않은 CPU 사이의 critical activity를 조정하도록 설계했습니다.

Vlock은 한 메모리 위치에 대한 write atomicity를 사용합니다. 각 CPU가 공통 메모리 위치에 고유 번호를 기록해 자신에게 투표하며, 모든 vote가 끝난 뒤 그 위치에서 보이는 최종 값이 winner를 식별합니다.

Election이 유한 시간 안에 모호하지 않은 결과를 내도록 CPU는 아직 winner가 없고 election도 시작되지 않은 것으로 보일 때만 선거에 참여합니다.

기본 알고리즘

다음 pseudo-code는 `currently_voting[]`으로 각 CPU의 참여 상태를 알리고 `last_vote`에 최종 후보를 기록하는 `vlock_trylock()`과, 값을 초기 상태로 되돌리는 `vlock_unlock()`을 보여 줍니다.

int currently_voting[NR_CPUS] = { 0, };
int last_vote = -1; /* no votes yet */

bool vlock_trylock(int this_cpu)
{
        /* signal our desire to vote */
        currently_voting[this_cpu] = 1;
        if (last_vote != -1) {
                /* someone already volunteered himself */
                currently_voting[this_cpu] = 0;
                return false; /* not ourself */
        }

        /* let's suggest ourself */
        last_vote = this_cpu;
        currently_voting[this_cpu] = 0;

        /* then wait until everyone else is done voting */
        for_each_cpu(i) {
                while (currently_voting[i] != 0)
                        /* wait */;
        }

        /* result */
        if (last_vote == this_cpu)
                return true; /* we won */
        return false;
}

bool vlock_unlock(void)
{
        last_vote = -1;
}

선거가 수렴하는 이유

`currently_voting[]` 배열은 CPU가 election 진행 여부를 판단하게 하며 Lamport's bakery algorithm [1]의 `entering` 배열과 비슷한 역할을 합니다.

Election이 시작된 뒤에는 underlying memory system의 atomicity가 winner를 고릅니다. 따라서 tie-breaker용 static priority rule이나 overflow할 수 있는 counter가 필요하지 않습니다.

`last_vote`가 모든 CPU에 globally visible하면 모든 CPU가 `currently_voting` flag를 지운 시점부터 그 값은 더 바뀌지 않는 하나의 값만 갖습니다.

공정성·확장성 한계와 계층형 투표

Vlock은 fair하도록 설계하지 않았습니다. 경합 상황에서는 lock 획득을 마지막으로 시도한 CPU가 이길 가능성이 가장 높습니다. 따라서 어떤 CPU가 이기는지는 중요하지 않고 고유한 winner 하나를 뽑는 것이 중요한 상황에 적합합니다.

유사한 메커니즘처럼 CPU 수가 많아지면 확장성이 좋지 않습니다. 필요하면 `4096 CPUs`의 다음 가상 예처럼 town, state, country 단계의 voting hierarchy로 vlock을 cascade할 수 있습니다.

/* first level: local election */
my_town = towns[(this_cpu >> 4) & 0xf];
I_won = vlock_trylock(my_town, this_cpu & 0xf);
if (I_won) {
        /* we won the town election, let's go for the state */
        my_state = states[(this_cpu >> 8) & 0xf];
        I_won = vlock_lock(my_state, this_cpu & 0xf));
        if (I_won) {
                /* and so on */
                I_won = vlock_lock(the_whole_country, this_cpu & 0xf];
                if (I_won) {
                        /* ... */
                }
                vlock_unlock(the_whole_country);
        }
        vlock_unlock(my_state);
}
vlock_unlock(my_town);

ARM 구현의 배열 packing 최적화

현재 ARM 구현 [2]은 기본 알고리즘보다 몇 가지 최적화를 더합니다. `currently_voting` 배열 원소를 가깝게 packing하면 경합 가능한 CPU 수가 충분히 적을 때 배열 전체를 한 transaction으로 읽어 외부 메모리 왕복 횟수를 줄일 수 있습니다.

ARM 구현에서는 다음 단일 load와 comparison을 사용할 수 있습니다.

LDR        Rt, [Rn]
CMP        Rt, #0

이는 다음처럼 byte를 하나씩 확인하는 코드에 해당합니다.

LDRB        Rt, [Rn]
CMP        Rt, #0
LDRBEQ        Rt, [Rn, #1]
CMPEQ        Rt, #0
LDRBEQ        Rt, [Rn, #2]
CMPEQ        Rt, #0
LDRBEQ        Rt, [Rn, #3]
CMPEQ        Rt, #0

이 최적화는 fast-path latency를 줄이고 경합 시 bus contention도 줄일 수 있습니다.

ARM memory system이 크기가 다른 overlapping memory access 사이의 coherency를 보장한다는 사실에 의존합니다. `currently_voting`의 어느 원소가 `Rt`의 어느 bit에 들어가는지는 중요하지 않으므로 endianness도 문제가 되지 않습니다.

CPU가 너무 많아 한 transaction으로 배열을 읽을 수 없으면 word-sized load의 단순 loop를 사용합니다. 그래도 byte를 개별적으로 읽는 것보다 transaction 수가 적습니다. 원칙적으로 `LDRD`나 `LDM`으로 더 집계할 수 있지만 초기 구현에서는 코드 단순성을 위해 시도하지 않았습니다.

캐시 제약과 0 초기화

Vlock은 현재 cache를 아직 켤 수 없는 CPU 사이의 조정에만 사용합니다. 따라서 cached memory에서 알고리즘을 실행할 때 필요할 많은 barrier를 구현에서 제거합니다.

경합 CPU가 모두 cache-coherent하지 않으면 한 CPU의 cache writeback이 다른 CPU가 쓴 값을 덮을 수 있으므로 packed `currently_voting` 배열은 cached memory에서 동작하지 않습니다. 모든 CPU가 cache-coherent하다면 일반 spinlock을 사용하는 편이 낫습니다.

`last_vote`의 "no votes yet" 값은 pseudo-code의 -1이 아니라 0입니다. 그러면 정적으로 할당한 vlock을 `.bss`에 두는 것만으로 unlocked state로 암묵 초기화할 수 있습니다. 어떤 CPU도 ID 0을 쓰지 않도록 이 변수를 설정할 때 각 CPU ID에 offset을 더합니다.

작성 배경과 라이선스

Dave Martin이 Linaro Limited에서 ARM 기반 big.LITTLE 플랫폼에 사용하려고 처음 만들고 문서화했습니다. Nicolas Pitre와 Achin Gupta가 검토와 의견을 제공했으며, Nicolas Pitre는 관련 mail thread에서 본문의 대부분을 수집하고 pseudo-code를 작성했습니다.

Copyright (C) 2012-2013 Linaro Limited. `linux/COPYING`에 정의된 GNU General Public License Version 2 조건으로 배포합니다.

참고 문헌

[1] Lamport, L. "A New Solution of Dijkstra's Concurrent Programming Problem", Communications of the ACM 17, 8 (August 1974), 453-455.

• https://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithmhttps://en.wikipedia.org/wiki/Lamport%27s_bakery_algorithm

[2] `linux/arch/arm/common/vlock.S`, www.kernel.org.