[운영체제] 뮤텍스(Mutex), 세마포어(Semaphore), 모니터(Monitor)

상호배제(Mutual Exclusion) :

멀티 프로그래밍환경에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘으로, 임계 구역으로 불리는 코드 영역에 의해 구현된다.

* 하나의 프로세스가 공유 자원을 사용할 때 다른 프로세스의 접근을 막는 것

 

멀티 프로세스나 멀티 스레드 동기화에 사용 : 

동기화(Syncronize) : 상호배제를 위해 실행을 제어. * 뮤텍스, 세마포어, 모니터 등

---

상호배제 관련 내용은 아래 링크 참고

https://hojinjeong.tistory.com/245

[운영체제] 교착상태

---

임계영역(Critical Section)

공유자원에 접근하는 프로세스 내부의 코드 영역으로 어떤 한 프로세스가 이 영역을 수행중일 때, 다른 프로세스가 같은 영역을 수행한다면 문제가 발생할 수 있다.

 

* 공유자원 : 여러 프로세스가 공동으로 이용하는 변수, 메모리, 파일

 

이러한 문제가 발생하지 않도록 한번에 하나의 프로세스만 이용할 수 있도록 보장해야 하는 영역이다.

 

1. 상호배제

• 하나의 프로세스가 임계 영역에 들어가 있다면 다른 프로세스는 들어갈 수 없어야 한다.

2. 진행

• 임계 영역에 들어간 프로세스가 없는 상태에서 들어가려 하는 프로세스가 여러 개라면 어느 것이 들어갈지 결정해주어야 한다.

3. 한정 대기

• 다른 프로세스의 기아를 방지하기 위해, 한 번 임계 영역에 들어간 프로세스는 다음번 임계영역에 들어갈 때 제한을 두어야 한다.

 

임계영역의 동시접근을 해결하기 위한 방법으로 락(lock), 세마포어(semaphore), 모니터(monitor)등이 있다.

---

뮤텍스(Mutex)

 

멀티 프로그래밍 환경에서 자원에 대한 접근에 제한을 강제하기 위한 동기화 기법이다.

 

• 0 또는 1의 값을 가지는 이진 세마포어와 유사하다. *임계영역에 하나의 스레드만 접근 가능(Binary Semaphore)
• 공유된 자원의 데이터를 여러 스레드가 접근하는 것을 막는다.
• 임계영역을 가진 스레드들의 실행 시간을 서로 겹치지 않게 단독으로 실행하게 하는 기술
• 멀티 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 Locking과 Unlocking을 하용한다.

 

뮤텍스 알고리즘

 

데커(Dekker) 알고리즘 : flag와 turn 변수를 통해 임계영역에 들어갈 프로세스를 결정

• flag : 프로세스 중 누가 임계영역에 진입할 것인지를 나타내는 변수
• turn : 누가 임계영역에 들어갈 차례인지를 나타내는 변수

while(1) {               // 프로세스i의 진입 영역

  flag[i] = ture;        // 프로세스i가 임계구역에 진입하기 위해 진입을 알림

  while(flag[j]) {       // 프로세스j가 임계구역에 진입하려고 하는지 확인
    if (turn == j) {     // 프로세스j가 임계구역에 있다면
      flag[i] = flase;   // 프로세스i가 진입을 취소하고
      
      while (turn == j); // 프로세스i의 차례가 올 때까지 대기 함.
      
      flag[i] =ture;     // 차례가 넘어왔다면 진입을 알림.
    }
  }

// 임계영역

  turn = j;              // 임계구역의 사용이 끝났다면 차례를 프로세스j에게 넘김.
  flag[i] = false;       // 진입을 취소하여 임계구역 사용완료를 알림.
}

---

피터슨(Peterson) 알고리즘 : 데커 알고리즘과 유사하지만 상대방(다른 프로세스 또는 다른 스레드)에게 진입기회를 양보

while(1) {
  flag[i] = true;            // 프로세스i가 임계영역에 진입을 시도
  turn = j;                  // 다른 프로세스에 진입 기회를 양보
  while(flag[i] && turn==j); // 다른 프로세스가 진입을 시도하면 대기 아니면 진입
/* 이곳은 임계영역이다. */
...
flag[i] = false;           // 임계영역 사용 완료
...
}

---

램퍼드의 베이커리 알고리즘(Lamport's Bakery Algorithm) : 여러 개의 프로세스(혹은 스레드)에 대한 처리가 가능하다. 가장 작은 수의 번호표를 가지고 있는 프로세스가 입계영역에 진입한다.

while(1) {
...
  isReady[i] = true;                 // 번호표를 받을 준비
  number[i] = max(number[0~n-1]) +1  // 현재 실행 중인 프로세스 중 가장 큰 번호로 배정
  isReady[i] = false;                // 번호표 수령 완료
 
  for( j =0; j < n; j++ ) {          // 모든 프로세스에 대해 번호표를 비교한다.
    while( isReady[j] );               // 비교할 프로세스가 번호표를 받을 때까지 대기
    while(number[j] && number[j] < number[i] && j<i);
// 프로세스 j가 번호표를 가지고 있고,
// 프로세스 j의 번호표가 프로세스i의 번호표보다 작거나 같을 경우
// j가 i보다 작다면(프로세스 j가 i보다 먼저 온 프로세스이면)
// 프로세스 j의 종료(number[j]=0)까지 대기
}
/* 이곳은 임계영역이다. */
...
number[i] = 0;                     // 임계영역 사용 완료
...
}

---

세마포어 (Semaphore)

멀티 프로그래밍 환경에서 다수의 프로세스나 스레드가 n개의 공유 자원에 대한 접근을 제한하는 방법으로 사용되는 동기화 기법이다.

 

 

• 뮤텍스가 임계영역에 들어가는 스레드가 하나라면, 세마포어는 복수 개가 가능하다.
• 접근 가능한 공유 자원의 수가 1개일 때는 이진 세마포어로 뮤텍스와 유사하게 사용할 수 있다.
• 큐에 연결된 스레드를 깨우는 방식에 따라 강성 세마포어, 약성 세마포어로 구분된다.

* 강성 세마포어 : 큐에 연결된 스레드를 깨울 때 FIFO 정책.

* 약성 세마포어 : 큐에 연결된 스레드를 깨울 때 순서를 특별히 명시하지 않음.

• Signaling 메커니즘으로 Lock을 걸지 않은 스레드도 Signal을 보내 Lock을 해제할 수 있다.
• wait과 signal을 통해 구현한다.

* wait이 먼저 호출되어 임계영역에 들어갈 수 있는지 확인 / 먼저 실행되어야 하는 프로세스가 실행되는지 확인

* 조건에 만족하면 wait을 빠져나와 임계영역으로 들어간다.

* 이후 signal이 호출되어 임계영역에서 빠져나왔음을 알린다.

 

 

 

예시

counting semaphore 예시

• 서버에 프린터가 다섯 대 연결되어있고, 사용자는 프린터를 사용하기 위해 서버에 요청을 한다.
• 여기서 프린터 5대는 공유자원이다. 세마포어 5로 설정된다.
• 프린터를 사용자가 사용할 때마다 세마포어는 1씩 감소한다.
• 사용할 프린터가 없어지면 세마포어는 0이 되고, 누군가 프린터를 쓰고 반환하면 세마포어는 1증가하게 된다.
• 여기서 세마포어는 단순히 공유자원의 개수를 나타내는 변수이다.

semaphore 접근 함수 wait(), signal()

• 자원을 사용하고 반납하기 위해 제공되는 함수 *wait(), signal()
• 사용할 때, 세마포어를 감소해주고 반납할 때 세마포어를 증가시켜주는 함수
• 다만, 세마포어 자체가 공유자원이 되면 안되므로 쪼개지지 않는 함수로 구성된다.
• 공유자원을 보호하기 위해 세마포어를 사용핮는데 세마포어 자체가 공유자원이 되면 안되기 떄문이다.

공유 자원을 사용하려 했지만, 현재 사용할 수 있는 공유 자원이 없어 기다려야 한다. - wait()

비어있는 공유 자원이 있으면 기다리지 않고 사용한다.

현재 세마포어의 값이 0이라면, wait()이다.

 

공유자원을 사용하고 반납하면 세마포어 값을 증가시켜주어야 한다. 대기하고 있는 프로세스가 있다면 사용할 수 있다는 것을 알려줘야 하므로 신호를 보내준다. - signal()

---

세마포어와 뮤텍스의 차이점

• 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다.
• 뮤텍스는 동기화 대상이 1개일 경우에 사용하고, 세마포어는 동기화 대상이 n 개일 때 사용한다.
• 세마포어는 소유할 수 없으며, 뮤텍스는 소유할 수 있고 소유주가 그에 대한 책임을 진다.
• 뮤텍스는 Lock을 건 스레드만 Lock을 해제할 수 있지만, 세마포어는 Lock을 걸지 않은 스레드도 Signal()을 보내 Lock을 해제할 수 있다.

---

모니터

뮤텍스, 세마포어를 사용할 때 타이밍 오류가 발생할 수 있다. 예를 들어, wait(), signal() 연산의 순서가 바뀌는 경우, 임계영역이 끝나고 signal()대신 wait()이 호출되는 경우 오류가 발생하게 된다. 이를 보완한 것이 모니터이다.

* 모니터는 세마포어와 달리 wait(), signal() 설정을 해주지 않고, synchronized 키워드를 사용하면 알아서 상호배제하여 함수 작업을 수행한다.

• 모니터는 하나의 프로세스 내에서 다른 스레드 간의 동기화에 사용된다.
• 모니터는 C언어네는 없고 Java에는 있다.

 

 

프로세스 또는 스레드를 동기화하는 방법 중 하나이다. 모니터는 하나의 데이터마다 결합함으로써 동시에 두 개 이상의 스레드에 의해 접근할 수 없도록 막는 잠금 기능을 제공함으로써 동기화를 수행한다.

 

모니터는 두 개의 queue를 가지고 있다.

• 상호베타 큐(Mutial Exclusion Queue) : 공유자원에 하나의 프로세스만 진입하도록 하기 위한 큐이다. 공유 자원을 사용하는 스레드가 존재하면 상호베타 큐에 존재한다.
• 조건동기 큐(Conditional Synchronization Queue) : 공유자원의 Lock이 해제되기를 기다리는 스레드가 대기하는 큐이다.

 

모니터 원리

 

공유자원을 점유중인 프로세스(스레드)는 Lock을 가지고 있다. 공유자원을 점유 중인 프로세스가 있는 상황에서 다른 프로세스가 공유자원에 접근하려고 하면 외부 모니터 조건동기 큐에서 진입을 기다린다.

 

자바의 모든 객체는 모니터가 될 수 있다. 배타 동기는 synchronized 를 사용해서 지정할 수 있고, 조건 동기는 wait()함수와 notify() 함수, notifyAll() 함수를 사용한다. 배타 동기를 지정하는 함수들은 공통자원을 사용하고 있는 경우이다.

위의 흐름은 모니터는 하나의 프로세스(애플리케이션)내에 다른 스레드 간에 동기화할 때 사용된다.

 

 

 

• synchronized : Java의 스레드를 동기화할 때 사용하는 대표적인 기법

* 자바의 모든 인스턴스는 모니터를 가지고 있으며, 모니터를 통해 스레드 동기화를 수행한다.(Object 내부에 존재)

* 모니터의 라이프 사이클은 synchronized 키워드에 의존하기 때문에 인스턴스가 가지는 wait(), notifty(), notifyAll() 메소드는 모두 synchronized 블록에서만 유의미하다.

• wait() : 이 함수는 진입한 스레드를 조건 동기 queue에 블록을 시킨다.
• notify() : 이 함수는 위에서 블록된 함수를 깨우는데, 새로운 스레드가 실행하는 방식으로 깨우게 된다.
• notifyAll() : 이 함수는 모든 스레드를 깨우는 것으로 사용할 수 있다.

* 모니터의 경우 세마포어처럼 여러 자원을 이용할 수 없지만, 특정 작업이 완료되기를 기다리는 스레드가 있을 수 있기 때문에 이런 경우에 작업이 완료되면 모든 대기 스레드를 동시에 깨울 때 notiftyAll() 을 사용한다.

---

 

예시

자바에서 스레드를 동기화하는 방법으로 모니터가 사용되는데 synchronized 메소드가 선언된 객체와 synchronized블럭에 의해 동기화되는 모든 객체에 고유한 모니터가 결합이 되어 동기화 작업을 수행하게 된다.

 

---

세마포어와 모니터의 차이점

세마포어에 비해 모니터는 공유자원에 접근할 수 있는 키의 획득과 해제를 모두 처리해서 간단하다. 세마포어는 직접 키해제와 공유자원 접근처리를 해주어야 한다.

 

 

---

참고 :

https://about-myeong.tistory.com/34

[운영체제] 뮤텍스(Mutex) 세마포어(Semaphore) 모니터(Monitor)

https://dar0m.tistory.com/234

[OS] 상호배제 방법 : 뮤텍스, 세마포어, 모니터

https://steady-coding.tistory.com/557

[Java] 뮤텍스, 세마포어, 모니터

 

https://dev-splin.github.io/cs(computer%20science)/operating%20system/OS-Mutex,Semaphore,Monitor/ 

Operating System : 뮤텍스(Mutex) / 세마포어(Semaphore) / 모니터(Monitor)

 

https://preamtree.tistory.com/26

[IT 기술면접 준비자료] 상호배제(Mutual Exclusion)와 상호배제 알고리즘

https://yansigit.github.io/blog/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EA%B3%B5%EC%9C%A0%EC%9E%90%EC%9B%90%EA%B3%BC-%EC%9E%84%EA%B3%84%EA%B5%AC%EC%97%AD/

운영체제 - 공유자원과 임계구역

https://jhnyang.tistory.com/101

[운영체제]세마포어(semaphore) 완전 쉬운 이해! wait(), signal(), 이진, 계수형

https://velog.io/@thsamajiki/%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4-%EB%AE%A4%ED%85%8D%EC%8A%A4-%EB%AA%A8%EB%8B%88%ED%84%B0

세마포어, 뮤텍스, 모니터