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

상호 배제(mutual exclusion)

멀티 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘으로, 임계 구역으로 불리는 코드 영역에 의해 구현된다. = 하나의 프로세스가 공유 자원을 사용할 때 다른 프로세스의 접근을 막는 것이다.

• 데커 알고리즘, 피커슨 알고리즘, 제과점 알고리즘
• 상호배제는 교착상태의 4가지 필요조건 중 하나이다.
  1. 상호배제 - 배타적 통제권(동시 사용 불가)
  2. 점유대기 - 할당된 자원을 가진 상태에서 다른 자원을 기다림
  3. 비선점 - 자원을 뺏을 수 없음
  4. 순환대기 - 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 갖고 있음
• 교착 상태와 기아 상태가 발생할 수 있다.
  교착 상태(Deadlock) : 무한 대기
  기아 상태(Starvation) : 우선순위가 낮아 자원을 계속 할당 받지 못하는 상태
• 멀티 프로세스나 멀티 스레드 동기화에 사용된다.
  동기화(synchronize): mutual exclusion을 위해 실행을 제어하는 것. 뮤텍스, 세마포어, 모니터 등

임계 영역(Critical Section)

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

따라서 문제가 발생하지 않도록 한번에 하나의 프로세스만 이용하게끔 보장해야 하는 영역이다.

임계 영역의 문제를 해결하기 위해서는 아래 3가지 조건을 충족해야 한다.

1. 상호배제
   • 하나의 프로세스가 임계 영역에 들어가있다면 다른 프로세스는 들어갈 수 없어야 한다.
2. 진행
   • 임계 영역에 들어간 프로세스가 없는 상태에서 들어가려 하는 프로세스가 여러개라면 어느 것이 들어갈지 결정해주어야 한다.
3. 한정 대기
   • 다른 프로세스의 기아를 방지하기 위해, 한 번 임계 영역에 들어간 프로세스는 다음번 임계 영역에 들어갈 때 제한을 두어야 한다.

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

 

뮤텍스 (Mutex, 상호배제) Mutual Exclusion

뮤텍스 (출처 : https://m.blog.naver.com/qbxlvnf11/221362041286)

• 다른 프로세스 간 동기화에 사용된다.
• 공유된 자원의 데이터를 여러 스레드가 접근하는 것을 막는 것
• 임계영역(Critical Section)을 가진 스레드의 Running time이 서로 겹치지 않게 단독적으로 실행되게 하는 것
  • 임계 구역에 하나의 스레드만 접근 가능(일종의 binary semaphore)
  • 상태가 0, 1로 이진 세마포어라고 부르기도 함
• 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 Locking과 Unlocking을 사용
  • 한 스레드가 임계영역에 들어가기 위해서 lock을 하고, 나올 땐 unlock을 한다.

 

뮤텍스 알고리즘

1. 데커(Dekker) 알고리즘

• flag와 turn 변수를 통해 임계 구역에 들어갈 프로세스/스레드를 결정하는 방식
  • flag : 프로세스 중 누가 임계영역에 진입할 것인지 나타내는 변수
  • turn : 누가 임계구역에 들어갈 차례인지 나타내는 변수

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    while(flag[j]) { // 프로세스 j가 현재 임계 구역에 있는지 확인
        if(turn == j) { // j가 임계 구역 사용 중이면
            flag[i] = false; // 프로세스 i 진입 취소
            while(turn == j); // turn이 j에서 변경될 때까지 대기
            flag[i] = true; // j turn이 끝나면 다시 진입 시도
        }
    }
}

// ------- 임계 구역 ---------

turn = j; // 임계 구역 사용 끝나면 turn을 넘김
flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

2. 피터슨(Peterson) 알고리즘

• 데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있음

while(true) {
    flag[i] = true; // 프로세스 i가 임계 구역 진입 시도
    turn = j; // 다른 프로세스에게 진입 기회 양보
    while(flag[j] && turn == j) { // 다른 프로세스가 진입 시도하면 대기
    }
}

// ------- 임계 구역 ---------

flag[i] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

3. 제과점(Bakery) 알고리즘

• 여러 프로세스/스레드에 대한 처리가 가능한 알고리즘.
• 가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입한다.

while(true) {
    
    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의 번호표
    }
}

// ------- 임계 구역 ---------

number[i] = 0; // 임계 구역 사용 종료

 

세마포어 (Semaphore)

• 뮤텍스가 임계 영역에 들어가는 스레드가 하나라면, 세마포어는 복수개가 가능하다.
• wait과 signal을 통해 구현된다.
  • wait이 먼저 호출되어 임계영역에 들어갈 수 있는지 확인 or 먼저 실행되어야 하는 프로세스가 실행되는지 확인
  • 조건에 만족하면 wait을 빠져나와 임계영역으로 들어간다.
  • 이후 signal이 호출되어 임계영역에서 빠져나왔음을 알린다.

뮤텍스와 세마포어의 차이

우리(프로세스)가 방(자원)에 들어가려고 할 때, 뮤텍스는 방에 들어가기 위한 열쇠의 개수이며, 세마포어는 빈 방의 열쇠의 개수이다.

즉 뮤텍스는 한 사람이 빈 방에 대한 열쇠를 가지고 있어서 방에 들어간다면, 그 사람이 나와야만 다른 사람이 열쇠를 건네받아 방을 들어갈 수 있다.

반면 세마포어는 방이 네개면 열쇠도 네개일 것이고 한 사람이 들어갈 때마다 들어갈 수 있는 방은 하나씩 줄어들어 0개가 되면 빈 방이 나올때 까지 대기해야 하는 상황이다. 아무나 먼저 나와야만 방과 열쇠를 한개씩 얻어서 들어갈 수 있다.

• 세마포어는 자원의 상태를 나타내는 일종의 '변수'로써 소유 개념이 아니지만, 뮤텍스는 자원을 점유한 프로세스나 쓰레드가 잠시 소유하였다가 작업이 끝나면 반환하는 개념이다.
• 세마포어의 바이너리 값을 갖는 것이 뮤텍스이다.
• 세마포어는 뮤텍스가 될 수 있지만, 뮤텍스는 세마포어가 될 수 없다.
• 세마포어는 시스템 범위에 걸쳐있고 파일 시스템 상의 파일 형태로 존재한다. 반면, 뮤텍스는 프로세스 범위를 가지고, 프로그램이 종료될 때 자동으로 지워진다.
• 세마포어는 동기화 대상이 여러개일 때, 뮤텍스는 동기화 대상이 오로지 하나일때 사용된다.

모니터 (Monitor)

• 하나의 프로세스 내의 다른 스레드 간 동기화에 사용된다.
• 모니터는 프레임워크나 라이브러리 그 자체에서 제공된다.
• C언어에는 없고, Java에는 있다.
• 일련의 동기화 작업들이 캡슐화되어 있어서 synchronized, wait(), notify()등의 키워드를 통해 편하게 동기화 할 수 있다.
• 즉, 세마포어와 달리 wait, signal 설정 없이 함수 앞에 synchronized를 붙여주기만 하면 상호배제하여 함수의 작업을 수행한다.

뮤텍스와 모니터 차이

뮤텍스는 다른 프로세스간에 동기화 할 때 사용할 수 있고, 모니터는 하나의 프로세스 내에서 다른 스레드 간의 동기화에 사용된다.

 

참고

• m.blog.naver.com/qbxlvnf11/221362041286
• blog.naver.com/qbxlvnf11/221359852998
• wannabe-gosu.tistory.com/27
• about-myeong.tistory.com/34
• hombody.tistory.com/240
• https://dduddublog.tistory.com/25