공평한 배타 제어
여기서는 공평한 배타 제어에 대해 설명한다.
먼저 컨텐션(contention) 이라는 개념을 이해할 필요가 있다. 컨텐션이란 여러 스레드가 동시에 같은 락을 획득하려고 경쟁하는 상황을 말한다. 컨텐션이 높을수록 스레드들이 락을 기다리는 시간이 길어지고 성능이 저하된다.
이러한 컨텐션 상황은 시스템 아키텍처에 따라 더욱 복잡해질 수 있다. 특히 비균일 메모리 접근(Non-Uniform Memory Access, NUMA) 와 같은 환경에서는 메모리와 CPU의 위치에 따라 메모리에 대한 접근 속도가 다르다. 예를 들어, CPU가 자신과 가까운 메모리에 접근할 때는 빠르지만, 원격 노드의 메모리에 접근할 때는 상대적으로 느리다.
이런 접근 속도의 차이는 락을 획득하는 난이도에도 영향을 미친다. 락이 저장된 메모리 위치와 가까운 CPU에서 실행되는 스레드는 락을 더 빨리 획득할 수 있는 반면, 원격 노드의 스레드는 상대적으로 불리한 위치에 있게 된다. 결과적으로 특정 스레드가 락을 반복적으로 획득하는 편향이 발생할 수 있다.
이러한 문제를 해결하기 위해 공평한 락(fair lock) 이 필요하다. 컨텐션이 높은 환경에서 공평한 락은 모든 스레드가 순서대로 락을 획득할 수 있도록 보장함으로써, NUMA로 인한 불균형을 완화하고 시스템의 예측 가능성을 높이며 기아 현상을 방지하는 데 도움이 된다.
약한 공평성을 보장하는 락
약한 공평성을 보장하는 배타 제어 알고리즘은 다음과 같이 동작한다.
락을 우선적으로 획득할 수 있는 스레드가 설정됨
우선 스레드는 순서대로 바뀜
예를 들면 스레드 1이 우선 스레드로 설정되면 스레드 1은 반드시 락을 획득한다. 락이 해제되면 다음 스레드가 우선 스레드가 되도록 설정된다. 다음 스레드가 스레드 2라고 하자. 그런데 여기서 스레드 2가 락 획득을 시도하지 않으면 어떻게 될까? 나머지 스레드들이 락 획득을 경합하고 다음 스레드 3을 우선 스레드로 설정한다.
약한 공평성을 보장하는 알고리즘을 코드로 구현하면 다음과 같다.
use std::cell::UnsafeCell;
use std::sync::atomic::{AtomicBool, AtomicUsize, Ordering, fence};
pub const NUM_LOCK: usize = 8;
const MASK: usize = NUM_LOCK - 1;
pub struct FairLock<T> {
waiting: Vec<AtomicBool>,
lock: AtomicBool,
turn: AtomicUsize,
data: UnsafeCell<T>,
}
pub struct FairLockGuard<'a, T> {
fair_lock: &'a FairLock<T>,
idx: usize,
}
그리고 다음 코드로 초기화와 락을 수행할 수 있다.
impl<T> FairLock<T> {
pub fn new(v: T) -> Self {
let mut vec = Vec::new();
for _ in 0..NUM_LOCK {
vec.push(AtomicBool::new(false));
}
FairLock {
waiting: vec,
lock: AtomicBool::new(false),
turn: AtomicUsize::new(0),
data: UnsafeCell::new(v),
}
}
pub fn lock(&self, idx: usize) -> FairLockGuard<T> {
assert!(idx < NUM_LOCK);
self.waiting[idx].store(true, Ordering::Relaxed);
loop {
if !self.waiting[idx].load(Ordering::Relaxed) {
break;
}
if !self.lock.load(Ordering::Relaxed) {
if let Ok(_) = self.lock.compare_exchange_weak(
false,
true,
Ordering::Relaxed,
Ordering::Relaxed,
) {
break;
}
}
}
fence(Ordering::Acquire);
FairLockGuard {
fair_lock: self,
idx,
}
}
다음은 언락을 구현한 코드이다.
impl<'a, T> Drop for FairLockGuard<'a, T> {
fn drop(&mut self) {
let fl = self.fair_lock;
fl.waiting[self.idx].store(false, Ordering::Relaxed);
let turn = fl.turn.load(Ordering::Relaxed);
let next_turn = if turn == self.idx {
(turn + 1) & MASK
} else {
turn
};
if fl.waiting[next].load(Ordering::Relaxed) {
fl.turn.store(next_turn, Ordering::Relaxed);
fl.waiting[next].store(true, Ordering::Release);
} else {
fl.turn.store((next + 1) & MASK, Ordering::Relaxed);
fl.lock.store(false, Ordering::Release);
}
}
}
까지가 락 획득 및 해제 알고리즘이다.
다음은 FairLock과 FairLockGaurd 타입에서 구현해야 할 트레이트다.
unsafe impl<T> Sync for FairLock<T> {}
unsafe impl<T> Send for FairLock<T> {}
impl<'a, T> Deref for FairLockGuard<'a, T> {
type Target = T;
fn deref(&self) -> &Self::Target {
unsafe { &*self.fair_lock.data.get() }
}
}
impl<'a, T> DerefMut for FairLockGuard<'a, T> {
fn deref_mut(&mut self) -> &mut Self::Target {
unsafe { &mut *self.fair_lock.data.get() }
}
}
Sync를 통해 스레드 사이에서 데이터를 공유할 수 있게 되었고, Send를 통해 스레드에서 소유권을 송수신할 수 있게 되었다.
공평한 락을 이용하는 예는 다음과 같다.
const NUM_LOOP: usize = 1000;
const NUM_THREADS: usize = 4;
fn main() {
let lock = Arc::new(FairLock::new(0));
let mut v = Vec::new();
for i in 0..NUM_THREADS {
let lock0 = lock.clone();
let t = std::thread::spawn(move || {
for _ in 0..NUM_LOOP {
let mut data = lock0.lock(i);
*data += 1;
}
});
v.push(t);
}
for t in v {
t.join().unwrap();
}
println!(
"Count = {} (expected = {})",
*lock.lock(0),
NUM_THREADS * NUM_LOOP
);
}
티켓락
약한 공평성을 보장하는 락은 유한 횟수 안에서 반드시 락을 획득한다. 그런데 반드시 락을 획득하는 것은 아니어도 경합을 줄이는 알고리즘도 존재하는데 티켓락도 그 중 하나이다.
티켓락의 구현은 다음과 같다.
use std::cell::UnsafeCell;
use std::ops::{Deref, DerefMut};
use std::sync::atomic::{AtomicUsize, Ordering, fence};
pub struct TicketLock<T> {
ticket: AtomicUsize,
turn: AtomicUsize,
data: UnsafeCell<T>,
}
pub struct TicketLockGaurd<'a, T> {
lock: &'a TicketLock<T>,
}
impl<T> TicketLock<T> {
pub fn new(v: T) -> Self {
TicketLock {
ticket: AtomicUsize::new(0),
turn: AtomicUsize::new(0),
data: UnsafeCell::new(v),
}
}
pub fn lock(&self) -> TicketLockGaurd<T> {
let t = self.ticket.fetch_add(1, Ordering::SeqCst);
while self.turn.load(Ordering::Relaxed) != t {}
fence(Ordering::Acquire);
TicketLockGaurd { lock: self }
}
}
impl<'a, T> Drop for TicketLockGuard<'a, T> {
fn drop(&mut self) {
self.ticket_lock.turn.fetch_add(1, Ordering::Release);
}
}
정리하자면 티켓락은 ticket과 turn이라는 2개 공유 변수가 있는데, ticket은 다음 티켓의 번호를 기억하는 변수이고, turn은 현재 실행이 허가된 티켓 번호다.
구현된 티켓 락의 함수에서, ticket획득 시 스핀을 수행하지 않는 것을 볼 수 있다. 이것이 컨텐션을 줄이는 역할을 한다.
MCS 락
티켓락에서는 아토믹 명령으로 접근하는 변수와 스핀 도중 접근하는 변수가 같았다. 그런데 메모리에 아토믹하게 접근하면 해당 메모리의 CPU 캐시가 배타적으로 설정되므로 대기 스레드의 해당 메모리를 읽을 떄 오버헤드가 발생할 가능성이 있다.
MCS락에서는 CAS 명령으로 큐의 가장 마지막에 스레드용 노드를 추가하고 스핀으로 감시할 변수는 별도로 준비한다. 즉, CAS에서 접근하는 변수는 아토믹하게 업데이트하지만 스핀으로 접근하는 변수는 일반적인 메모리 접근 명령을 이용한다.
CAS가 MCS에서 갖는 의미
MCS락에서 CAS는 두 가지 중요한 역할을 한다.
swap 연산: self.last.swap(ptr, Ordering::Relaxed)를 통해 자신을 큐의 마지막에 아토믹하게 추가한다. 이때 이전 마지막 노드의 포인터를 받아온다.
compare_exchange 연산: 락을 해제할 때 self.mcs_lock.last.compare_exchange(...)를 사용한다. 이는 "현재 자신이 마지막 노드인가?"를 확인하고, 맞다면 큐를 비우는 작업을 아토믹하게 수행한다.
핵심은 이런 CAS 연산은 큐 구조를 변경할 때만 사용하고, 각 스레드가 대기할 때는 자신의 locked 변수만 감시한다는 점이다. 이렇게 해서 캐시 경합을 최소화한다.
구현하자면 다음과 같은데
mcs.rs:
use std::cell::UnsafeCell;
use std::ops::{Deref, DerefMut};
use std::ptr::null_mut;
use std::sync::atomic::{AtomicBool, AtomicPtr, Ordering, fence};
pub struct MCSLock<T> {
last: AtomicPtr<MCSNode<T>>,
data: UnsafeCell<T>,
}
pub struct MCSNode<T> {
next: AtomicPtr<MCSNode<T>>,
locked: AtomicBool,
}
pub struct MCSLockGuard<'a, T> {
node: &'a mut MCSNode<T>,
mcs_lock: &'a MCSLock<T>,
}
unsafe impl<T> Sync for MCSLock<T> {}
unsafe impl<T> Send for MCSLock<T> {}
impl<T> MCSNode<T> {
pub fn new() -> Self {
MCSNode {
next: AtomicPtr::new(null_mut()),
locked: AtomicBool::new(false),
}
}
}
impl<'a, T> Deref for MCSLockGuard<'a, T> {
type Target = T;
fn deref(&self) -> &Self::Target {
unsafe { &*self.mcs_lock.data.get() }
}
}
impl<'a, T> DerefMut for MCSLockGuard<'a, T> {
fn deref_mut(&mut self) -> &mut Self::Target {
unsafe { &mut *self.mcs_lock.data.get() }
}
}
impl<T> MCSLock<T> {
pub fn new(v: T) -> Self {
MCSLock {
last: AtomicPtr::new(null_mut()),
data: UnsafeCell::new(v),
}
}
pub fn lock<'a>(&'a self, node: &'a mut MCSNode<T>) -> MCSLockGuard<T> {
node.next = AtomicPtr::new(null_mut());
node.locked = AtomicBool::new(false);
let guard = MCSLockGuard {
node,
mcs_lock: self,
};
let ptr = guard.node as *mut MCSNode<T>;
let prev = self.last.swap(ptr, Ordering::Relaxed);
if prev != null_mut() {
guard.node.locked.store(true, Ordering::Relaxed);
let prev = unsafe { &*prev };
prev.next.store(ptr, Ordering::Relaxed);
while guard.node.locked.load(Ordering::Relaxed) {}
}
fence(Ordering::Acquire);
guard
}
}
impl<'a, T> Drop for MCSLockGuard<'a, T> {
fn drop(&mut self) {
if self.node.next.load(Ordering::Relaxed) == null_mut() {
let ptr = self.node as *mut MCSNode<T>;
if let Ok(_) = self.mcs_lock.last.compare_exchange(
ptr,
null_mut(),
Ordering::Release,
Ordering::Relaxed,
) {
return;
}
}
while self.node.next.load(Ordering::Relaxed) == null_mut() {}
let next = unsafe { &mut *self.node.next.load(Ordering::Relaxed) };
next.locked.store(false, Ordering::Release);
}
}
lock 함수의 동작 과정
노드 초기화 (❶): 각 스레드는 자신의 노드를 깨끗한 상태로 만든다.
CAS로 큐에 추가 (❷): swap 연산으로 자신을 큐의 마지막에 원자적으로 추가한다. 이전 마지막 노드의 포인터를 받아온다.
대기 여부 결정 (❸): 이전 노드가 있으면 대기해야 한다.
대기 상태 설정 (❹): 자신의 locked를 true로 설정한다.
큐 연결 (❺): 이전 노드의 next가 자신을 가리키게 한다.
스핀 대기 (❻): 자신의 locked가 false가 될 때까지 대기한다. 여기서는 CAS가 아닌 일반 load를 사용한다!
drop 함수의 동작 과정
마지막 노드 확인 (❶): 다음 노드가 없으면 자신이 마지막일 가능성이 있다.
CAS로 큐 비우기 (❷): compare_exchange로 "자신이 여전히 마지막이면 큐를 비운다"를 원자적으로 수행한다. 이게 실패하면 새로운 노드가 추가되는 중이란 뜻이다.
다음 노드 대기 (❸): 다음 노드가 아직 큐 연결을 완료하지 않았다면 대기한다.
다음 노드 깨우기 (❹): 다음 노드의 locked를 false로 설정해서 실행 가능하게 한다.
main.rs:
use std::sync::Arc;
const NUM_LOOP: usize = 100000;
const NUM_THREADS: usize = 4;
mod mcs;
fn main() {
let n = Arc::new(mcs::MCSLock::new(0));
let mut v = Vec::new();
for _ in 0..NUM_THREADS {
let n0 = n.clone();
let t = std::thread::spawn(move || {
let mut node = mcs::MCSNode::new();
for _ in 0..NUM_LOOP {
let mut r = n0.lock(&mut node);
*r += 1;
}
});
v.push(t);
}
for t in v {
t.join().unwrap();
}
let mut node = mcs::MCSNode::new();
let r = n.lock(&mut node);
println!("COUNT = {} (expected = {})", *r, NUM_LOOP * NUM_THREADS);
}
정리
공평한 배타 제어는 컨텐션이 높은 환경에서 모든 스레드가 균등하게 락을 획득할 수 있도록 보장하는 방법이다. 특히 NUMA 같은 환경에서는 메모리 접근 속도 차이로 인한 불균형이 발생할 수 있는데, 공평한 락은 이런 문제를 완화한다.
약한 공평성을 보장하는 락은 우선 스레드를 순서대로 지정해서 공평성을 제공한다. 티켓락은 티켓 번호를 발급받고 자신의 차례를 기다리는 방식으로 동작하며, 티켓 획득 시 스핀을 수행하지 않아 컨텐션을 줄인다.
MCS락은 더 나아가 캐시 경합 문제까지 해결한다. 핵심은 CAS 연산을 큐 구조 변경에만 사용하고, 각 스레드가 대기할 때는 자신만의 변수를 감시하는 것이다. 이렇게 해서 아토믹 연산으로 인한 캐시 무효화를 최소화하고, 많은 스레드가 경쟁하는 환경에서도 좋은 성능을 유지할 수 있다.
결과적으로 이 세 가지 락은 각각 다른 수준의 공평성과 성능 특성을 제공한다. 시스템의 요구사항과 환경에 따라 적절한 락을 선택하는 것이 중요하다.
