Method of Mutual Exclusion

* 배경

앞서 제시한 상호배제의 해결 방법은 더 복잡한 문제에서 일반화하기 어렵다. 프로세스가 임계 영역에 진입할 수 없을 때는 진입 조건이 true가 될 때까지 반복적으로 조사하고 바쁜 대기를 하게 되어 프로세스를 낭비한다. 1965년 다익스트라가 새로운 동기화 도구인 세마포를 제안하여 진입 조건을 반복 조사하지 않고 true일 때 프로세스 상태를 확인하여 프로세스 사이클을 낭비하는 형태로 위 문제를 해결했다. 세마포는 사옿배제에 사용할 뿐만 아니라 다양한 연산의 순서도 제공

1. 세마포 개념과 동작

세마포는 값이 음이 아닌 정수인 플래그 변수 세마포 값은 true나 false로 네덜란드어의 축약 표현으로 P(검사 : Proberen)와 V(증가 : Verhogen) 연산과 관련되어 있다.

S : 세마포, 표준 단위 연산 P와 V로만 접근하는 정수 변수
- P : 프로세스를 대기하게 하는 wait 동작으로, 임계 영역에 진입하는 연산
- V : 대기 중인 프로세스를 꺠우기 위해 신호를 보내는 signal 동작으로, 임계 영역에서 탈출하는 연산
- P와 V 연산은 운영체제가 실행하고, 세마포를 인자로 명명한 임의의 프로세스가 요청한 시스템 호출을 하여 다음과 같이 정의
```
// S 값을 검사하여 양수이면 1을 감소. 검사, 인출, 감소, 저장 순서로 구성
P(S) : wait(S) { // S = 1로 초기화
          while (S <= 0); // 바쁜 대기, S > 0일 때까지 대기
          S--;
       }
// S를 1만큼 증가. 인출, 증가, 저장 순서로 구성
V(S) : signal(S) {
          S++; // 다른 프로세스의 접근 허용
       }
```
  P와 V 연산에 있는 세마포 S의 정수 값은 개별적으로 실행하고, 정수 변수와 비슷하지만 모든 변경 연산을 분할 없이 실행해야 한다. 그리고 프로세스가 세마포 값을 수정할 때는 다른 프로세스가 중단할 수 없고, 동일한 세마포 값을 동시에 수정할 수도 없다. 다시 말해 P와 V 연산을 종료할 때까지는 다른 프로세스가 두 연산을 수행하지 않도록 조정해야 한다.
  - 교착 상태를 피하기 위해 단일 머신 사이클에서 단일 동작으로 수행해야 한다.
  - 관례적으로 세마포가 0일 때 lock 또는 사용 중이고, 그렇지 않을 때 양의 값은 세마포를 사용할 수 있다는 의미 (세마포는 음의 값을 가질 수 없다.)
임계 영역을 구현하거나 스케줄링 제약 조건을 시행할 수 있다.
- 임계 영역은 보통 세마포를 사용하여 1로 초기화. 프로세스는 임계 영역에 진입하기 위해 wait(S)를 호출하여 임의의 다른 프로세스가 대기 조건을 통과하는 것을 방지할 수 있다. 그리고 해당 프로세스가 임계 영역을 종료하면 다음 프로세스가 임계 영역에 진입할 수 있도록 signal(S)를 호출한다.
- 때에 따라서 세마포를 1보다 큰 값으로 초기화하면 여러 프로세스가 한 번에 임계 영역에 진입할 수 있기 때문에 유용하다. (임계 영역의 데이터를 보호해야 할 때는 문제가 될 수 있지만, 생산자와 소비자 문제처럼 동시 사용 가능한 자원에서는 유용한 방법)
세마포는 아래와 같은 특정 유형의 공유 자원에 접근하려는 프로세스를 관리하는데 특히 유용하다.
- 세마포를 0으로 초기화하면 스케줄링 제한에 사용할 수 있어 모든 프로세스가 wait(S) 호출을 기다리는 동안 차단된다. 그리고 S++만 특정 조건에 부합하므로 signal(S)를 보내 대기 프로세스 중 하나를 실행하도록 허용한다.
세마포에 적용된 P와 V 연산은 상호배제 개념을 포함하므로 프로세스 n개의 임계 영역 문제를 다루는데 사용한다.
- 이와 같이 Pn 프로세스 n개가 1로 초기화한 세마포 mutex를 공유할 수 있다.
```
do {
  wait(mutex);
  // 임계 영역
  signal(mutex);
  // 나머지 영역
} while (1);
```
세마포는 동기화하는데 사용할 수도 있다.
- ```
// 프로세스 P1
S1;
signal(sync);
// 프로세스 P2
signal(sync);
S2;
```
  예를 들어, 명령문 S1이 있는 프로세스 P1과 명령문 S2가 있는 프로세스 P2를 수행 중이고, S1이 끝난 후에 S2를 수행하도록 구현해야한다고 할 때, 위와 같이 P1과 P2가 세마포 sync를 공유하고 프로세스 P1과 프로세스 P2에 각 명령문을 삽입하여 구현할 수 있다. 이 때, 세마포 sync를 0으로 초기화하면 프로세스 P1이 명령문 S1을 실행한 후 signal(sync)를 호출하여 프로세스 P2의 명령문 S2를 실행한다.

2. 세마포의 종류

세마포에는 계수 세마포와 이진 세마포가 있다.

(1) 이진 세마포

임계 영역과 같은 상호배제를 해결하기 위해 특별히 설계한 세마포 이진 세마포에서는 세마포 S를 상호배제에 사용하고, 1 또는 0으로 초기화하고 P와 V의 연산을 교대로 실행한다.

S를 1로 초기화하면 P 연산을 먼저 실행하고 이어서 V 연산을 실행하는 경우
S를 0으로 초기화하면 V 연산을 먼저 실행, 실행할 때 P와 V 연산을 모두 차단
이진 세마포는 처음 만들 때 사용 가능 상태
사용 불가능 상태로 초기화 할 수 있다. (0으로 초기화하면 이용할 수 없거나 비었다는 것을 의미한다.)

이진 세마포의 알고리즘

P(S) : S를 검사하여 양수이면 S를 0으로 재설정한 후 진행하고, 아니면 S를 준비 큐로 되돌린다.
V(S) : S를 1로 설정하고 준비 큐에 있는 프로세스를 시작한다.

이진 세마포의 상태 다이어그램

(2) 계수 세마포

생산자와 소비자 문제처럼 상호배제와 조건부 동기화를 해결하기 위해 설계한 세마포 count 변수(이 변수가 세마포가 된다.)를 자원의 사용 허가 값으로 사용하여 자원을 여러 번 획득하거나 해제할 수 있어 유한한 자원에 접근하는 것을 제어할 수 있다. count를 초기의 세마포 수(사용 가능한 자원 수)로 초기화 각 프로세스가 자원을 사용하려면 P 연산을 수행하고 S(count)를 감소(S–), 프로세스가 자원을 해제할 떄는 V 연산을 수행하고 S++

계수 세마포의 알고리즘

계수 세마포는 초기 count가 0이면 사용할 수 없는 상태로 생성, 0보다 크면 사용 가능한 상태로 생성된다.
이진 세마포처럼 계수 세마포도 계수 세마포가 필요한 모든 프로세스가 공유할 수 있는 전역 자원

계수 세마포의 상태 다이어그램

3. 세마포의 구현

세마포의 구조

struct semaphore {
  int count;
  queueType queue;
} S;

세마포의 연산

wait(S) {
  S.count--;
  if (S.count < 0) {
    S.queue.push(P); // Add this process, 프로세스를 준비 큐에 추가
    block(); // 프로세스 중단(일시 정지)
  }
  // 임계 영역
}
signal(S) {
  S.count++;
  if (S.count <= 0) {
    S.queue.remove(P); // 준비 큐에서 프로세스 ㅖ를 제거
    wakeup(P); // 신호를 보내 프로세스 P를 실행
  }
}

바쁜 대기 세마포에서는 절대 음수일 수 없지만, 여기서는 음수 값이 될 수 있다. 세마포 값이 음수이면 S의 실제 값은 세마포에서 기다리는 프로세스 수를 나타내는데, 이는 wait 연산에서 감산과 검사 순서를 맞바꾸면서 나타난다.

세마포의 주요 특징
- 원자(단위)적으로 수행
- 두 프로세스가 동시에 동일한 세마포에서 wait과 signal 연산을 할 수 없도록 해야 한다.
  - 단일 프로세서에서는 wait과 signal 연산 수행 중에 다른 프로세서의 명령어 실행이 끼어들지 않게 하기 위해 인터럽트를 금지한다.
  - 다중 프로세서 에서는 인터럽트를 금지할 수 없으므로, 다른 프로세스의 명령어가 임의의 방법으로 끼어들 수 있다. 게다가, 모든 프로세서에서 인터럽트를 비활성화하게 되면 심각한 성능 저하로 이어질 수 있다. 하드웨어가 임계 영역 문제에 특별한 명령을 제공하지 않으면 이를 소프트웨어적으로 해결해야 하는데, wait과 signal 연산으로는 바쁜 대기를 완전히 제거할 수 없으므로 응용 프로그램의 진입 영역에서 임계 영역까지 바쁜 대기를 제거해야 한다. 결국 바쁜 대기의 시기를 이동해야 하는 것이 최선. wait과 signal 연산이 임계 영역의 바쁜 대기를 제한할 수 있으므로 임계 영역은 항상 비어 있고 바쁜 대기가 거의 일어나지 않는 것처럼 보일 뿐, 실제로 바쁜 대기는 아주 짧은 기간 동안 일어난다. 하지만 어떤 응용 프로그램에서는 임계 영역이 아주 길거나 항상 점유되어 있는 상황이 발생할 수 있는데, 이 때는 바쁜 대기가 매우 비효율적이다.
- 단점
  - 세마포에서는 wait나 signal 연산을 생략하면 상호배제 문제가 발생하고, wait 연산을 시작하여 세마포를 사용하는 동안에는 프로세스가 다른 경로를 선택할 수 없기 때문에 대기하는 프로세스들이 교착 상태에 빠질 수 있다는 취약점이 발생한다. (프로세스는 한 번에 하나의 세마포만 대기할 수 있어 자원을 할당하는 상황에서 두 프로세스가 각각 자원을 하나씩 보유하고, 상대방의 자원을 사용하려고 대기하는 교착 생하는 가져올 수 있다.)

* Semaphore & Mutex (= Mutual Exclusion)

세마포어는 동시에 여러 개의 프로세스/스레드가 임계 구역에 접근할 수 있도록 카운트를 가지고 있는데 카운트가 1인 특별한 세마포어를 뮤텍스라고 한다.
일반적으로 뮤텍스는 프로세스 내부에서만 공유되는 반면, 세마포어는 특별히 옵션을 추가하지 않으면 여러 개의 프로세스에서 접근 가능하다.
다시 말해, 세마포어는 공유된 자원의 데이터에 여러 프로세스가 접근하는 것을 막고, 뮤텍스는 공유된 자원의 데이터에 여러 스레드가 접근하는 것을 막는다.
프로그래밍 시에는 한 프로세스 내부에서 여러 스레드의 임계 영역을 제어를 위해 사용되는 객체를 뮤텍스라고 한다.
Semaphore
Mutex