언본일기

Peterson's Algorithm

onebone -

같은 일을 여러 사람이 하면 대개 일이 빨리 끝나게 된다. 비슷한 원리로 컴퓨터로 같은 일을 더 빨리 끝내고자 할 때 멀티 쓰레딩을 활용한다. 많은 쓰레드로 일을 빨리 끝낼 수 있다는 점은 좋지만 여러 쓰레드를 활용하는 코드를 조금이라도 짜봤다면 단일 쓰레드로 작업할 때는 일어나지 않았던 여러 문제점들이 발새아는 걸 알 수 있었을 것이다. 특히 자주 발생하는 문제는 여러 쓰레드가 동일한 메모리를 건드려서 프로그램의 상태가 메롱이 되는 경우인데, 가장 기초적인 해결법으로는 락을 사용해서 critical section임계 구역이라고 불리는 특정한 코드 부분에서는 최대 한 개 쓰레드만 접근이 가능하도록 하는 것이다. 이 포스트에서는 2개 쓰레드가 있는 상황에서 활용할 수 있는 Peterson's Algorithm에 대해서 작성할 것이다.

우선 Peterson's Algorithm의 전체 코드는 다음과 같다. 이때 ThreadID.get()은 현재 쓰레드의 ID(0 혹은 1; 쓰레드가 2개이므로 둘 중 하나가 반환됨)가 반환된다.

public class PetersonLock {
	private volatile boolean[] flag = new boolean[2];
	private volatile int victim;

	public void acquire() {
		int i = ThreadID.get();
		int j = 1 - j;
		flag[i] = true;
		victim = i;
		while (flag[j] && victim == i) {}
	}

	public void release() {
		int i = ThreadID.get();
		flag[i] = false;
	}
}

주목해서 봐야 하는 곳은 acquire()획득 메서드이다. flag[i] = true, victim = i, 그리고 while 문을 집중해서 보자. 간단하게 말해서

  • flag는 ‘쓰레드가 락을 acquire획득 하고 싶다'는 의미
  • victim로 설정되면 ‘해당 쓰레드가 기다리겠다’는 의미

로 생각하면 된다. 바로 밑에 따라오는 while 문은 이 사실을 생각하고 읽어보면 이해가 잘 될 것이다. 조금 유의해서 봐야할 부분은 while 문 안에 있는 flag[j]를 확인하는 부분인데, j는 다른 쓰레드의 ID이기 때문에 ‘다른 쓰레드가 접근하고 싶어하지 않는지’를 확인하고 있음을 알아두자. 조금 간단하게 얘기하자면 두 쓰레드가 동시에 임계 구역에 들어가고 싶어할 때 내가 양보를 해야 하는지 확인하고 있다고 생각하면 된다.

여기서 flag와 victim이 모두 필요한가 하는 의문이 들 수도 있다. 물론 모두 필요한 게 맞는데, 그 이유가 제대로 감이 오지 않는다면 짚고 넘어가보자. 우선 flag만 있는 경우를 생각해보자.

public class BrokenLock1 {
	private volatile boolean[] flag = new boolean[2];

	public void acquire() {
		int i = ThreadID.get();
		int j = 1 - i;
		flag[i] = true;
		while (flag[j]) {}
	}

	public void release() {
		int i = ThreadID.get();
		flag[i] = false;
	}
}

동작하는 걸 확인해보면 acquire()를 호출하면 자신의 쓰레드가 락을 획득하고 싶다고 한다 (i.e. flag[i] = true). 만약 다른 쓰레드가 이미 획득 시도를 해서 flag[j]가 true인 상태라면 release 될 때까지 기다린 다음에 임계 구역에 접근하게 된다. 언뜻 보면 별로 문제가 없어 보이지만 두 개 쓰레드가 완전히 동시에 락을 획득하려고 시도하면 문제가 생긴다. 다시 말해서 두 쓰레드가 동시에 flag[i] = true를 실행해버리면 while 문에서 두 쓰레드 모두 true를 보기 때문에 프로그램이 더 이상 진행하지 않는 문제를 마주하게 된다.

즉, victim은 두 개 쓰레드가 모두 획득하고 싶어할 때 어느 쓰레드가 기다려야 하는지 결정하는 역할을 한다. 양쪽 쓰레드가 모두 victim일 수는 없기 때문에 프로그램 전체적으로는 진행도가 생기게 되고 데드락은 발생하지 않는다.

그렇다면 반대로 victim만 사용한다면 어떻게 될까?

public class BrokenLock2 {
    private volatile int victim;
    
    public void acquire() {
        int i = ThreadID.get();
        victim = i;
        while (victim == i) {}
    }
    
    public void release() {
    	// intentionally empty...
    }
}

이번에는 직전의 예시와 반대로 쓰레드가 동시에 실행될 경우에는 문제가 되지 않는다. 하지만 반대로 나중에 실행되는 쓰레드는 victim이 더 이상 수정되지 않기 때문에 while 문에서 빠져나올 수 없음을 알 수 있다.

즉, flag는 다른 쓰레드가 락을 획득하려고 하지 않는다면 자신이 임계 구역에 접근할 수 있도록 도와주는 역할을 한다.

증명

그렇다면 이제 마지막으로 Peterson's Algorithm이 왜 항상 올바르게 작동하는지 증명을 해보도록 하자. 멀티 쓰레딩 같이 어려운 문제에서 직관은 믿을 만한 게 아니기 때문에 엄밀한 증명이 필요한 때가 많다.

우리가 일상적으로 쓰는 언어는 모호한 경우가 있기 때문에 좀 더 정확한 표현을 사용하고자 한다. 이 포스트에서는 다음과 같은 표현을 사용하고자 한다:

  • \(read_A(var=v)\) :: A 쓰레드에서 var 변수를 읽어서 v로 평가됨
  • \(write_A(var=v)\) :: A 쓰레드에서 var 변수에 v를 대입함
  • \(read_A(...) → write_B(...)\) :: A 쓰레드에서 값을 읽은 다음에 B 쓰레드에서 값을 읽음

증명을 시작하기 앞서 올바르게 작동하는 락을 만드려면 우선 critical section에 여러 쓰레드가 접근하는 것을 막는 mutual exclusion, 그리고 프로그램의 전체적인 진행도는 멈추지 않도록 deadlock-free, 그리고 선택적으로 모든 획득 시도는 언젠가 성공하는 starvation-free의 특성을 가지고 있어야 한다. 여기서는 mutual exclusion 증명을 다룰 것이다.

여기서 다시 전체 코드를 가져와보겠다. 증명 과정에 필요한데 맨 위까지 갔다 오는 건 불편할 테니 말이다.

public class PetersonLock {
	private volatile boolean[] flag = new boolean[2];
	private volatile int victim;

	public void acquire() {
		int i = ThreadID.get();
		int j = 1 - j;
		flag[i] = true;
		victim = i;
		while (flag[j] && victim == i) {}
	}

	public void release() {
		int i = ThreadID.get();
		flag[i] = false;
	}
}

증명을 위해서 이 알고리즘이 mutual exclusion을 만족하지 않는다고 가정해보자. 즉 A와 B 쓰레드가 동시에 임계 구역에 접근할 수 있다고 가정한다.

코드를 읽어보면 아래와 같은 순서가 보장된다는 것을 알 수 있다:

\(write_A(flag[A]=true)→write_A(victim=A)→read_A(flag[B])→read_A(victim)\)

\(write_B(flag[B]=true)→write_B(victim=B)→read_B(flag[A])→read_B(victim)\)

이 코드에서 victim을 마지막으로 설정한 게 B 쓰레드라고 가정해보자. 이 상황은 아래와 같이 표현할 수 있다:

\(write_A(victim=A)→write_B(victim=B)\)

B 쓰레드의 입장에서 생각했을 때 victim은 B로 설정되어 있으므로 임계 구역에 들어가려면 flag[A]==false여야 한다. flag[A]==true라면 while 문의 조건에 걸려서 acquire() 함수가 반환되지 않을 것이기 때문이다. 하지만 두 쓰레드가 모두 victim의 값에 손을 댔다는 건 flag의 값은 2개 모두 true라는 의미기 때문에 flag[A]는 false일 수가 없다. 따라서 이 알고리즘이 mutual exclusion을 만족하지 않는다는 가정은 틀렸다고 할 수 있다.

참고

이 포스트는 The Art of Multiprocessor Programming의 내용을 많이 참고했다. 더 자세한 내용은 이 책에 상세하게 설명되어 있으니 더 궁금하신 분들은 이걸 읽어보시면 좋을 것이다.