[JAVA] 로 풀어본 '식사하는 철학자들' 문제 (2) - 세마포어

세마포어 (Semaphore)

---

 '세마포어' 란, 1965년 E.W 다익스트라가 고안한 개념으로서, down과, up 이라는 두개의 함수로 조작하는 정수변수이다. 다시 말하면 Mutual Exclusion(Mutex, 뮤택스)를 조금 더 고도화 하여 구현한 개념이라고 할 수 있는데, 임계영역에 대한 lock을 수행한다. 참고로 세마포어는 뮤택스이지만, 뮤택스라고 해서 모두 다 세마포어는 아니다. (필자가 이해 하기론..)

 어떤이는 세마포어를 열쇠고리에 걸려있는 열쇠의 갯수라고 표현 하더라. 흠.. 그것도 적절한 표현 인 것 같다. 세마포어에 대한 down 연산을 할때는 세마포어 값이 0보다 큰지 검사한다. 만약 그렇다면 이 값을 감소시키고, 스레드는 임계영역에 대한 수행을 계속한다. 만약 이 값이 0이면 스레드는 down의 수행을 완료하지 않고 즉시 잠들게 된다. 값을 검사하고, 변경하고, 경우에 따라 잠드는 이러한 모든 동작은 분할할 수 없는 하나의 원자적 행위(atomic action) 이다. 만약 이 연산에 원자성이 보장 되지 않는다면, 세마포어를 적용한다 하더라도 동시성의 경쟁조건(race condition)에 의한 교착상태가 해결된다는 보장을 할 수 없을 것이다.

 JAVA에도 세마포어 구현체가 있다. 동시성의 영웅, 더그 리(Doug Lee) 형님께서 구현하신 'java.util.concurrent.Semaphore' 클래스가 그것이다. 이 클래스는 down 연산에 'acquire' 메소드를, up 연산에는 'release' 메소드를 사용한다. 의미적으로는 이러한 네이밍이 좀 더 직관적인 것 같다.

 위 클래스의 인스턴스를 생성할때, 세마포어의 'permits', 그러니까 열쇠의 갯수를 생성자의 파라메터로 받는다. 그리고 앞서 말한 acquire 와 release 메소드를 통해서 해당 값을 변경한다. 필자가 예상하기로는 값 변경 작업에 'AtomicInteger' 와 같은 연산의 원자성을 보장하는 방식을 사용 할 것 같았는데, 소스를 살펴보니 아래와 같은 'compareAndSetState' 라는 메소드를 사용 한 것이 눈에 띄었다.

protected final boolean compareAndSetState(int expect, int update) {
    // See below for intrinsics setup to support this
    return unsafe.compareAndSwapInt(this, stateOffset, expect, update);
}

 간단하게 말하면 'expect' 값을 'update' 값으로 swap 하는 작업이다. 주석을 살펴보니, 정확히는 모르겠지만 AtomicInteger와 같은 명확한 방식을 사용하지 못했던 히스토리가 있었던 것 같다. 그래서 'the lesser of evils'(차악.. 이라고 읽으면 되려나?)로 native 라이브러리를 사용해서 구현 했다고 한다. 'Unsafe'라는 객체는 java doc 설명도 제대로 안나와 있어 자세히 살펴보진 않았지만 어쨌든 native 라이브러리 이고, 뭐 값을 조작하는 역할을 하는 것 같다.

세마포어의 적용

---

 서두가 좀 길었다. 그리고 본 단락은 짧을 것이다 -_-; 앞서 살펴본 '식사하는 철학자들' 문제에 세마포어를 적용해보자. 적용 방식은 아주 간단하다. 생각하고(think), 왼쪽 오른쪽 포크를 잡고(take), 먹고(eating), 양 포크를 다시 테이블위에 놓는(put) 행위중에서 'think' 의 바로 다음 5가지 동작을 이진(binary) 세마포어로 묶는 것이다.

먼저 static 변수로 세마포어를 정의한다.

class Philosopher implements Runnable {
    
    .
    .
    public static final Semaphore semaphore = new Semaphore(1);
    .
    .

'이진' 세마포어 이므로 'permits'의 값을 1로 설정한다. (1과 0의 값만 갖도록)

그리고 아래와 같이 철학자들의 행위를 세마포어로 묶어보자.

@Override
public void run() {
    while (true) {
        think();
        try {
            semaphore.acquire();

            takeFork(this.number);
            takeFork((this.number + 1) % 5);
            eat();
            putFork(this.number);
            putFork((this.number + 1) % 5);

            semaphore.release();
        } catch (InterruptedException e) {
            System.out.println("Exception occured!");
            e.printStackTrace();
        }
    }
}

포크를 잡는 행위와 스파게티를 먹는 행위, 그리고 포크를 다시 놓는 행위는 임계영역(critical region)이라고 할 수 있다. 이러한 임계영역을 이진 세마포어로 보호함 으로서 '상호배제' 매커니즘을 적용하면 교착 상태가 발생하지 않는다. 하지만 프로그램을 실행하고 보니 이상한 점이 보였다.

흠.. 그렇다. 뭔가 5명의 철학자가 골고루 스파게티를 먹는 것 같지 않다. 그리고 이론상, 5명의 철학자와 5개의 포크가 있다면 동시에 최대 2명의 철학자가 스파게티를 먹을 수 있어야 한다. 한마디로 지금의 상황은 CPU가 그만큼 효율적으로 스케줄링을 하고 있지 않다는 것이다. 따라서 세마포어에 열쇠의 갯수(permits)를 1에서 2로 늘려 보았다. 이제 더 이상 이진 세마포어는 아니다.

public static final Semaphore semaphore = new Semaphore(2);

그리고 다시 프로그램을 수행했다.

이제 조금 더 고른 스케줄링이 되는 것으로 보인다. 주의해야 할 점은 세마포어의 'permits' 값을 5 이상으로 한다면, 임계영역이 보호되는 것은 말짱 도루묵이라는 것이다. 이는 세마포어를 적용하지 않은 것과 같은 상황이다.

일단 세마포어는 여기까지..