Semaphore in Java

Semaphore

공유자원에 대한 접근을 제어하는 객체.
모든 thread는 자원에 접근하기 전에 semaphore로 부터 허가(permit)를 받아야 한다.
자원과 관련된 작업을 끝낸 후에는 반드시 semaphore에게 허가를 반환하고 나와야 한다.

 thread가 공유 자원에 접근하려고 함
              |
              v
    +----------------------+  semaphore로 부터 접근 허가 받음
	| semaphore.acquire(); |  허가될 때 까지 wait
    +----------------------+
              |
              v
     +--------------------+
     | 자원 접근, 작업 수행 |
     +--------------------+
              |
              v
    +----------------------+
    | semaphore.release(); |  semaphore가 허가 해제
    +----------------------+

제한된 수의 thread만이 semaphore에 의해 제어되는 공유 자원에 접근할 수 있다.

semaphore를 만들기 위해서 선택적 공정성 정책(optional fairness policy)와 함께 허가 개수(number of permits)를 명시해야 한다. task는 semaphore의 acquire() 메소드를 호출하여 허가를 얻고 release() 메소드를 호출하여 허가를 해제한다. 한번 허가를 얻으면 semaphore의 가능한 허가 개수(number of available permits)가 1 감소하고, 허가가 해제되면 가능한 허가 개수가 1 증가한다.

+----------------------------------+
|  java.util.concurrent.Semaphore  |
+----------------------------------+
| +Semaphore(numberOfPermits: int) |
| +Semaphore(numberOfPermits: int, |
|  fair: boolean)                  |
| +acquire(): void                 |
| +release(): void                 |
+----------------------------------+

fair: true or false
Semaphore의 fair가 true일 경우 이 semaphore는 thread들이 대기한 순서대로 허가를 준다. 이와 같은 방식은 starvation을 방지할 수 있지만, 성능이 저하된다(context switching overhead).

반대로 false일 경우 os의 scheduling 상황에 따라 허가를 주는 thread가 결정되므로 순서를 장담할 수 없다. 성능적인 장점이 있지만 starvation이 발생할 수 있다는 단점이 있다.

1개의 허가를 가진 semaphore는 상호 배제적 lock을 시뮬레이션 하는 것에 사용될 수 있다.
이전에 살펴봤던 Account 코드의 semaphore 버전과 함께 공부해보자.

  public static class Account {
    private static Semaphore semaphore = new Semaphore(1);
    private int balance = 0;

    public int getBalance() {
      return balance;
    }

    public void deposit(int amount) {
      try {
        semaphore.acquire(); // 허가 획득
      } catch (InterruptedException ex) {
        // 허가 획득 중 Interrupt 발생 처리
        throw new RuntimeException(ex);
      }
      
      // 허가 획득 성공
      try {
        int newBalance = balance + amount;

        Thread.sleep(5);

        balance = newBalance;
      } catch (InterruptedException ex) {
      } finally {
        semaphore.release(); // 허가 해제
      }
    }
  }

Lock과 Semaphore의 차이점
Lock은 소유권(ownership)이 존재하여 lock을 한 thread만이 unlock할 수 있었다. 그러나 Semaphore는 소유권 개념이 아니므로 Thread 1이 acquire()를 호출해도 Thread 2가 release() 할 수 있다.
(단, 상호 배제적 목적이라면 이렇게 사용하지 않음)

Deadlock

가끔 두개 이상의 thread들이 여러 개의 공유 객체에 lock을 받는 경우가 발생한다. 이 때 Deadlock이 발생할 수 있다.
Deadlock이란 한국어로는 교착 상태라고 하는데, thread들이 서로 상대방이 가진 자원을 기다리며 영원히 Block되는 상태를 말한다.

다음 4가지 조건(Coffman Condition)이 만족할 때, Deadlock이 발생할 수 있다.

1. 상호 배제 (Mutual exclusion):
   자원은 한 번에 하나의 thread만 접근 가능하다.
2. 점유 상태로 대기(Hold and wait):
   자원을 가진 상태에서 추가 자원을 기다린다.
3. 선점 불가 (No preemption):
   다른 thread가 자원을 강제로 회수할 수 없다.
4. 순환성 대기 (Circular wait):
   각 thread들이 서로의 자원을 순환적으로 대기한다.

2개의 thread와 2개의 object가 아래의 상황처럼 동작한다고 가정하자.

Step	Thread 1	Thread 2
1	synchronized (object1) {
2	// do something here	synchronized (object2) {
3	synchronized (object2) {	//do something here
4	// do something here	synchronized (object1) {
5	}	//do something here
6	}	}
		}

thread 1은 object 1에서 lock을 획득했다. 이후 thread 2는 object 2에서 lock을 획득했다.
이제 thread 1은 object 2의 lock을 얻기 위해 대기하고, thread 2는 object 1의 lock을 얻기 위해 대기한다.
영원히 서로를 기다리는 교착상태에 빠진 것이다.

이러한 교착 상태는 우리가 앞서 배운 방식들로 적절한 리소스 오더링을 한다면 피할 수 있는 문제이다.

다음과 같은 규칙이 추가된다면 위 상황이 해결될 듯 하다.
모든 thread는 object 1을 먼저 lock 하고, 그 후에 object 2를 lock 한다. (순환형 대기 방지)

---

<참고자료>
탁성우, "플랫폼기반프로그래밍", 부산대학교