정의
락(lock)은 임계 구역 앞뒤에서 획득·해제되는 공유 변수다. 잠김 여부를 담고, 대개 누가 쥐고 있는지와 누가 기다리는지까지 함께 담아, 구역 안에 실행 흐름이 하나만 있도록 만든다.[1]
락은 임계 구역을 지키는 수단 가운데 특권 연산에 기대지 않고 여러 프로세서에서도 성립하는 쪽이다. 대신 구현이 까다롭다 — 락을 만드는 코드 자체가 경쟁의 대상이기 때문이다.
락 변수와 소유자
획득 호출은 락이 비어 있으면 그것을 잡고 임계 구역으로 들어간다. 이때의 실행 흐름을 락의 소유자(owner)라 부른다. 소유자가 쥐고 있는 동안 다른 흐름이 같은 락에 획득을 호출하면 그 호출은 반환하지 않는다. 소유자가 해제하면 락은 다시 비고, 기다리던 흐름이 있으면 그중 하나가 락을 얻어 구역에 들어간다.[1]
POSIX가 이 자료형에 붙인 이름이 뮤텍스(mutex)다. 락을 건 스레드가 소유자가 되고, 소유하지 않은 스레드가 해제를 시도하면 오류가 반환되거나 정의되지 않은 동작이 된다 — 어느 쪽인지는 뮤텍스 유형과 robust 속성이 정한다.[2] 잠근 쪽만 풀 수 있다는 이 규칙은 뒤에 볼 우선순위 프로토콜들이 성립하는 전제이기도 하다 — 지금 누가 락을 쥐고 있는지 알아야 그 흐름의 우선순위를 조정할 수 있기 때문이다.
플래그만으로 부족한 이유
플래그 변수 하나를 두고 보통의 적재·저장 명령으로 읽고 쓰는 구현을 생각해 보자. 획득에서 플래그가 0인지 검사하고 0이면 1로 세운 뒤 들어가고, 해제에서 0으로 되돌린다. 이 코드에는 두 가지 문제가 있다.[1]
정확성 문제가 먼저다. 흐름 하나가 플래그를 검사한 직후 값을 쓰기 전에 선점되면, 다른 흐름도 같은 0을 보고 플래그를 1로 세운다. 되돌아온 첫 흐름은 자기 검사 결과를 믿고 마찬가지로 1을 세운다. 둘 다 임계 구역에 들어가므로 상호 배제라는 가장 기본적인 요구부터 깨진다. 검사와 설정 사이가 갈라진다는 점에서 이것은 경쟁 상태 그 자체이고, 락을 만들려는 코드가 다시 임계 구역이 되는 순환에 빠진다.
성능 문제는 그다음이다. 기다리는 흐름이 while 루프에서 플래그를 끝없이 다시 읽는 회전 대기(spin-waiting)를 하게 되는데, 이 시간은 그대로 낭비다.
원자적 명령
순환을 끊는 것은 하드웨어다. 검사와 설정을 한 명령 안에 묶어 주면 그 사이에 다른 흐름이 끼어들 수 없다.
test-and-set 명령은 주소에 새 값을 저장하면서 저장 전의 값을 반환한다. 획득은 이 명령으로 1을 써 보고 반환값이 0이었을 때만 성공으로 친다. compare-and-swap 명령은 주소의 값이 기대값과 같을 때만 새 값을 쓰고, 성공 여부와 무관하게 원래 값을 돌려주므로 호출한 쪽이 결과를 알 수 있다. 이런 지원은 1960년대 초 Burroughs B5000 같은 초기 다중 프로세서에 이미 있었고 오늘날은 단일 CPU 시스템에도 있다.[1]
획득 실패 시 거동
락을 얻지 못했을 때 무엇을 하느냐로 락의 성격이 갈린다.
회전 락(spin lock)은 락이 풀릴 때까지 계속 확인하며 돈다. 단일 프로세서에서는 이 선택이 비싸다. 락을 쥔 흐름이 임계 구역 안에서 선점되면 나머지 흐름들이 차례로 실행되면서 각자 타임 슬라이스를 통째로 회전에 쓰고 CPU를 놓는다. 선점 스케줄러가 아예 없다면 도는 흐름이 CPU를 내놓지 않으므로 락은 영영 풀리지 않는다.[1] 반대로 여러 코어에서 스레드 수가 코어 수와 비슷하고 임계 구역이 짧다면, 락을 쥔 쪽이 다른 코어에서 계속 진행하다 곧 풀어 주므로 회전에 드는 낭비가 작다.
재우는 쪽은 획득에 실패한 흐름을 대기 큐에 넣고 재운 뒤, 해제 시점에 큐에서 하나를 깨운다. 회전으로 CPU를 태우지 않고 다음 차례를 통제할 수 있어 굶주림도 막을 수 있지만, 재우고 깨우는 운영체제 지원이 필요하고 깨어나는 데 드는 지연이 붙는다. 두 방식을 섞은 2단계 락(two-phase lock)은 잠깐 돌아 보고 그동안 풀리지 않으면 잠든다.
회전 락과 우선순위
락 세분도
락을 몇 개 둘지는 설계 선택이다. 어떤 임계 구역이든 하나의 큰 락으로 지키는 굵은 세분도(coarse-grained) 전략은 락 변수가 하나뿐이라 다루기 쉽지만, 서로 무관한 자원을 만지는 흐름끼리도 서로를 막는다. 자료와 자료구조마다 다른 락을 두는 가는 세분도(fine-grained) 전략은 동시에 락 안에 있을 수 있는 흐름을 늘려 동시성을 높인다.[1]
대가는 복잡도다. 락이 여러 개가 되면 한 흐름이 여러 락을 겹쳐 잡는 상황이 생기고, 잡는 순서가 흐름마다 어긋나면 교착이 된다.[3] 실시간 시스템에서는 여기에 하나가 더 붙는다 — 락 하나가 지키는 자원이 많을수록 그 락을 쥔 태스크가 임계 구역에 머무는 시간이 길어지고, 그 시간이 같은 락을 기다리는 다른 태스크의 지연을 좌우한다. 그 지연에 계산 가능한 상한을 주는 방법은 우선순위 상속 프로토콜에서 다룬다.