[자료 구조] 프로세스 동기화 #2 Semaphore& Mutex

https://veganwithbacon.tistory.com/171

[개념쌓기] 프로세스 동기화 #1 critical section

앞서 포스팅했던 글에서 프로세스 동기화에 대한 내용과 알고리즘 3가지에 대해 알아봤다.

이번 글에서는 세마포어와 뮤텍스에 대해서 알아보자.

 

공유자원을 안전하게 관리하기 위해 상호배제(Mutual exclusion)를 달성하는 기법이 필요한데,

뮤텍스와 세마포어가 이를 위해 고안된 기법으로 서로 다른 방식으로 상호배제를 달성한다.

----------------------------------------------------------------------------------------------------------------------------------------

---

본격적으로 설명하기에 앞서 세마포어와 뮤텍스의 차이에 대해 이해하고 가면 좀 더 이해하기 쉬울 것이다.

접기에 해당하는 글은 글을 퍼온것임을 밝힘

Mutex 뮤텍스

: 공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 하나의 Process 혹은 Thread가 접근하는 것을 막아줌 (동기화 대상이 하나)

 

임계구역(Critical Section)을 가진 스레드들의 실행시간(Running Time)이 서로 겹치지 않고 각각 단독으로 실행(상호배제_Mutual Exclution)되도록 하는 기술입니다. 

한 프로세스에 의해 소유될 수 있는 Key를 기반으로 한 상호배제 기법이고 Key에 해당하는 어떤 객체(Object)가 있으며, 이 객체를 소유한 스레드/프로세스만이 공유자원에 접근할 수 있습니다.

다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 동기화(Synchronization) 또는 락(Lock)을 사용함으로써 뮤텍스 객체를 두 스레드가 동시에 사용할 수 없습니다.

 

 

뮤텍스는 화장실이 하나 밖에 없는 식당과 비슷합니다. 화장실을 가기 위해서는 카운터에서 열쇠를 받아 가야 하며 당신이 화장실을 가려고 하는데 카운터에 키가 있으면 화장실에 사람이 없다는 뜻이고 당신은 그 열쇠를 이용해 화장실에 들어갈 수 있다고 가정합니다.

카운터에 열쇠가 없기 때문에 화장실에 사람이 있다는 뜻이며 화장실을 사용할 수 없습니다. 여자가 나올 때 까지 기다려야 합니다.

곧이어 다른 사람도 화장실에 가려고 카운터에 대기하고 있습니다. 앞사람이 화장실에서 나와 카운터에 키를 돌려놓았습니다. 이제 기다리던 사람들 중 맨 앞에 있던 사람이 키를 받아 화장실에 갈 수 있습니다. 

 

이것이 뮤텍스가 동작하는 방식입니다. 화장실을 이용하는 사람은 프로세스 혹은 쓰레드이며 화장실은 공유자원, 화장실 키는 공유자원에 접근하기 위해 필요한 어떤 오브젝트입니다. 즉, 뮤텍스는 Key에 해당하는 어떤 오브젝트가 있으며 이 오브젝트를 소유한 (쓰레드,프로세스) 만이 공유자원에 접근할 수 있습니다.

---

Semaphore 세마포어

: 공유된 자원의 데이터 혹은 임계영역(Critical Section) 등에 여러 Process 혹은 Thread가 접근하는 것을 막아줌 (동기화 대상이 하나 이상)

사용하고 있는 스레드/프로세스의 수를 공통으로 관리하는 하나의 값을 이용해 상호배제를 달성합니다. 공유 자원에 접근할 수 있는 프로세스의 최대 허용치만큼 동시에 사용자가 접근할 수 있으며, 각 프로세스는 세마포어의 값을 확인하고 변경할 수 있습니다.

자원을 사용하지 않는 상태가 될 때, 대기하던 프로세스가 즉시 자원을 사용하고. 이미 다른 프로세스에 의해 사용중이라는 사실을 알게 되면, 재시도 전에 일정시간 대기해야 합니다.

일반적으로 비교적 긴 시간을 확보하는 리소스에 대해 사용하게 됩니다. 

---

세마포어는 손님이 화장실을 좀 더 쉽게 이용할 수 있는 레스토랑입니다. 세마포어를 이용하는 레스토랑의 화장실에는 여러 개의 칸이 있고 화장실 입구에는 현재 화장실의 빈 칸 개수를 보여주는 전광판이 있다고 가정합니다. 

만약 당신이 화장실에 가고 싶다면 입구에서 빈 칸의 개수를 확인하고 빈 칸이 1개 이상이라면 빈칸의 개수를 하나 뺀 다음에 화장실로 입장해야 하며 나올 때 빈 칸의 개수를 하나 더해줍니다.

모든 칸에 사람이 들어갔을 경우 빈 칸의 개수는 0이 되며 이때 화장실에 들어가고자 하는 사람이 있다면 빈 칸의 개수가 1 혹은 양수로 바뀔 때까지 기다려야 합니다.

 

이처럼 세마포어는 공통으로 관리하는 하나의 값을 이용해 상호배제를 달성합니다. 세마포어도 아까와 똑같이 화장실이 공유자원이며 사람들이 쓰레드, 프로세스이다. 그리고 화장실 빈칸의 개수는 현재 공유자원에 접근할 수 있는 쓰레드,프로세스의 개수를 나타냅니다.

 

해당 글의 원본 출처 :

https://heeonii.tistory.com/14

---

------------------------------------------------------------------------------------------------------------------------------------

✅Mutex

: 상호배제(Mutual Exclusion)의 줄임말로,

동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘

 

Mutex의 특징

- 임계구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행(상호배제)되도록 하는 기술

- 한 프로세스에 의해 소유될 수 있는 Key를 기반으로 한 상호배제 기법 Key에 해당하는 어떤 객체(Object)가 있으며, 이 객체를 소유한 스레드/프로세스만 해당 공유자원에 접근할 수 있다

- 다중 프로세스들의 공유 자원에 접근을 조율하기 위해 동기화 또는 락을 사용

사용중인 프로세스나 스레드가 락(Lock)을 걸어 다른 프로세스나 스레드의 접근을 방지한다

(뮤텍스의 락은 본인만 해제가 가능하다)

- 뮤텍스는 프로세스단에서 관리된다

- 뮤텍스는 단 하나의 프로세스/스레드만 접근 가능하다 (뮤텍스 객체를 두 스레드가 동시에 사용불가)

---

lock : 현재 임계 구역에 들어갈 권한을 얻어옴

         (만약 다른 프로세스/스레드가 임계 구역 수행 중이라면 종료까지 대기한다)

 

unlock : 현재 임계 구역 사용을 완료했음을 알림

         (대기 중인 다른 프로세스/스레드가 임계 구역에 진입가능)

 

💡Mutex lock 간단 요약

Mutex lock을 하게 되면 한 변수에 동시 접근하지 않고 순차적으로 접근한다.

그러나 Mutex lock을 하지 않으면 스레드가 한 변수에 번갈아가며 접근한다.

 

뮤텍스는 상태가 0, 1로 이진 세마포어로 부르기도 한다

 

✅Semaphore

: 멀티 프로그래밍 환경에서 공유된 자원에 대한 접근을 제한하는 방법

Semaphore의 특징

- 공유 자원에 접근할 수 있는 프로세스의 최대 허용치만큼 동시에 사용자가 접근 가능

- 각 프로세스는 세마포어의 값을 확인하고 변경 가능하다

- 자원을 사용하지 않는 상태가 될 시, 대기 중이던 프로세스가 즉시  자원을 사용

- 이미 다른 프로세스에 의해 사용중이라는 사실을 알게 되면, 재시도 전에 일정시간 대기해야 한다

- 리소스를 사용중인 프로세스는 그 값을 확인하고, 자원을 사용하는 동안에는 그 값을 변경해 다른 리소스 요청자들이 대기하도록 해야한다

- 다른 프로세스들도 락을 자유롭게 확인하며 변경이 가능(뮤텕스는 락을 획득한 프로세스만이 락을 해제할 수 있다)

- 운영체제나 커널에 저장 및 변경

- 세마포어는 이진수를 사용하거나 추가적인 값을 가질 수 있다

- busy waiting을 피한다 & 다익스트라가 제안

 

일반적으로 세마포어는 메모리 공간을 공유하거나 파일들을 공유 액세스하기 위한 목적으로 사용된다.

 

✔semaphore의 동작 원리

세마포어의 동작 원리를 이해하려면, 세마포어 변수, semWait, semSignal 연산에 대해 알아야한다.

세마포어 변수는 일반적으로 정수형 변수를 사용한다. 이 정수 값은 접근할 수 있는 최대 허용치의 사용자 양을 말한다.

 

semWait 연산은 세마포어 값을 감소시키며, 만일 값이 음수가 되면 semWait을 호출한 프로세스는 블록된다.

이는 음수가 아니면 프로세스가 계속 수행될 수 있음을 의미한다.

 

semSignal 연산은 세마포어 값을 증가시키며, 만일 값이 양수가 아니면(0이거나 음수),
semWait 연산에 의해 블록된 프로세스들을 깨운다.

 

struct semaphore{
    int count;
        queueType queue;
};

void semWait(semaphore s){
     s.count--;
     if (s.ocunt < 0){
        /* 이 구역으로 들어온 의미는 현재 프로세스나 스레드가 공유 자원에 접근할 수 없다는 것 */
        /* 요청한 프로세스를 s.queue에 연결 */
        /* 요청한 프로세스를 블록 상태로 전이 시킨다 */
        }
}

void semSignal (semaphore s) {
    s.count ++;
    if(s.count <= 0) {
      /* count가 0보다 작거나 같다는 것은 대기하고 있는 프로세스(또는 스레드)가 존재한다는 것을 의미 */
      /* s.queue에 연결되어 있는 프로세스를 큐에서 제거 */
      /* 프로세스의 상태를 실행 가능으로 전이시키고 ready list에 연결 */
      }
 }

일반적인 세마포어는 위와 같은 형태로 되어있고, 이를 활용해 아래와 같이 구현가능하다.

const int n = /* 프로세스 개수 */;
semaphore s = 1;

void P (int i) {
   while (true){
      semWait(s);
      
      /* Crtical Section */
      
      semSignal(s);
      
      /* other Section(after Critical Section) */
      }
}

void main(){
     parbegin ( P(1), P(2), ....... P(n));
}

세마포어는 유지가능한 값의 범위에 따라 이진 세마포어와 범용 세마포어로 구분된다.

위에서 본 예시 세마포어를 카운팅(=계수형) 세마포어 (counting semaphore) 또는 범용 세마포어(general semaphore)라고 부른다. 세마포어의 초기값이 0이상의 수이다.

 

이진 세마포어는 세마포어의 초기 값이 0 또는 1만 가질 수 있는 세마포어이다.(뮤텍스를 이진 세마포어라 부를 수 있음)

 

이진형 세마포어는 0과 1의 값, 한 개의 공유자원을 상호배제한다.

계수형 세마포어는 0과 양의 정수, 여러 개의 공유자원을 상호배제한다.

 

추가로 세마포어는 큐에 연결된 프로세스를 깨우는 순서에 따라 강성 세마포어와 약성 세마포어로 나뉜다.

강성 세마포어 : 선입선출(FIFO) 정책을 사용하는 세마포어

약성 세마포어 : 순서를 명시하지 않는 세마포어

 

Mutex와 Semaphore의 차이?

>>> 세마포어는 공유 자원에 세마포어의 변수만큼의 프로세스(또는 스레드)까 접근가능

        뮤텍스는 오직 1개의 프로세스(또는 스레드)만 접근 가능

>>> 세마포어는 수행중인 프로세스가 아닌 다른 프로세스도 세마포어를 해제 가능

        뮤텍스는 락(lock)을 획득한 프로세스만 락을 해제할 수 있다