뮤텍스와 세마포어 (Mutex and Semaphore)

뮤텍스와 세마포어의 정의 그리고 뮤텍스의 세가지 알고리즘(데커, 피터슨, 베이커리) 그리고 뮤텍스와 세마포어의 차이점 까지 알아보자.😉

여러 프로세스가 동시에 공유 데이터에 접근할 때 접근 순서에 따라 실행 결과가 달라지는 상황에 놓인 프로세스들을 경쟁 상태 (reace condition)에 있다고 한다. 이러한 경쟁 상태를 예방하려면 병행 프로세스들을 동기화해야 하는데, 이는 임계 영역을 이용한 상호배제로 구현할 수 있다.

임계 영역

여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분

여기서 뮤텍스와 세마포어가 바로 상호배제의 방법들 중 하나이다.

뮤텍스 (Mutex)

제어되는 섹션에 하나의 스레드만 허용하기 때문에 해당 섹션에 접근하려는 다른 스레드를 강제적으로 막는 상호배제기법

• MUTual EXclusion, 상호배제
• 다중 프로세스들의 공유 리소스에 대한 접근을 조율하기 위해 locking과 unlocking을 사용한다. 즉, 쉽게 말하면 뮤텍스 객체를 두 스레드가 동시에 사용할 수 없다는 의미!
  • lock: 현재 임계 구역에 들어갈 권한을 얻어옴 (만약 다른 프로세스/ 스레드가 임계 구역 수행 중이면 종료할 때까지 대기)
  • unlock: 현재 임계 구역을 모두 사용했음을 알림.(대기 중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있음)

뮤텍스를 보다 쉽게 실생활 예로 생각해보자, 뮤텍스는 화장실이 하나 뿐이 없는 식당 과 비슷하다.

프로세스(사람) 은 자원에 접근하기 위해서는 열쇠(lock)을 얻고 화장실(자원)을 쓴다. 그리고 다쓰고 키(unlock)를 반납한다.

간단히 설명하자면 이렇다. 그리고 뮤텍스에서 3가지 알고리즘을 살펴보자.

1. 데커(Dekker) 알고리즘

데커의 알고리즘에서는 각 프로세스는 플래그를 설정할 수 있고, 다른 프로세스를 확인한 후 플래그를 재설정할 수도 있다. 프로세스가 임계 영역에 진입하고 싶으면 플래그를 설정하고 차례를 기다린다. 즉, 임계 영역에 다른 프로세스가 이미 있으면 해당 프로세스를 종료할 때까지 while문 에서 순환한다. 그리고 프로세스간의 순서를 나타내는 turn 변수를 사용한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

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. 피터슨 알고리즘

데커와 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있다. 그리고 피터슨 알고리즘 같은 임계구역 문제에 대한 소프트웨어 해결책은 최신 컴퓨터 아키텍처에서 제대로 작동하지 않는다고 한다.

1
2
3
4
5
6
7
8
9
10

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

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)

먼저, 세마포어란 공유 자원에 대한 접속을 제어하기 위해 최대 허용치만큼 접근 요청을 가능하게 하여 카운트를 세서 카운트가 0이 되면 대기하도록 하여 상호배제를 달성하는 기법이다.

앞의 방법들과 차이점을 설명해보자면,

앞서 제시한 상호배제의 해결 방법은 좀 더 복잡한 문제에서는 일반화되기 어렵다. 또 프로세스가 임계 영역에 진입할 수 없을 때 진입 조건이 true가 될 때까지 반복적으로 조사하고 바쁜 대기를 하기 때문에 프로세스를 낭비한다. 따라서, 진입 조건을 반복 조사하지 않고 true일 때 프로세스 상태를 확인한다면 프로세서 사이클을 낭비하지 않을 것이다.

이또한, 위의 뮤텍스와 같이 실생활 예로 살펴보자.

위의 그림은 카운팅 세마포어(counting semaphore)를 쉽게 이해할 수 있는 예시이다. 즉, 유한한 개수를 가진 자원에 대한 접근을 제어하는데 사용할 수 있다. 그리고 다른 방법은 이진 세마포어(binary semaphore) 가 있다. 세마포어의 초기 값이 0또는 1만 가질 수 있는 세마포어 이다. (뮤텍스가 이진 세마포어와 비슷한 것이라 생각하면 된다)

세마포어에 더 자세히 이해하기 위해서는 wait(), signal(), 0 에 대해 이해해야한다. 각 자원을 사용하려는 프로세스는 세마포어에 wait() 연산을 수행하고 세마포어의 값은 감소하게 된다. 프로세스가 자원을 방출 할 때는 signal() 연산을 수행하고 세마포어는 증가하게 된다. 그리고 세마포어의 값이 0 이 되면 모든 자원이 사용중임을 나타내고 이후 자원을 사용하려는 프로세스는 세마포어 값이 0보다 커질 때 까지 봉쇄된다.

그리고 wait() 연산은 P 라하고, signal() 연산은 V 라고 명칭한다.

구현 방법

1
2
3
4
5

P(S);

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

V(S);

1
2
3
4
5
6
7
8
9
10
11

//wait
procedure P(S)   --> 최초 S값은 1임
    while S=0 do wait  --> S가 0면 1이 될때까지 기다려야 함
    S := S-1   --> S를 0로 만들어 다른 프로세스가 들어 오지 못하도록 함
end P

--- 임계 구역 ---
//signal
procedure V(S) --> 현재상태는 S가 0임
    S := S+1   --> S를 1로 원위치시켜 해제하는 과정
end V

예시

최초 S 값은 1이고, 현재 해당 구역을 수행할 프로세스 A, B가 있다고 가정하자

1. 먼저 도착한 A가 P(S)를 실행하여 S를 0으로 만들고 임계구역에 들어감
2. 그 뒤에 도착한 B가 P(S)를 실행하지만 S가 0이므로 대기 상태
3. A가 임계구역 수행을 마치고 V(S)를 실행하면 S는 다시 1이 됨
4. B는 이제 P(S)에서 while문을 빠져나올 수 있고, 임계구역으로 들어가 수행함

뮤텍스와 세마포어의 차이

• 뮤텍스 락과 같이 세마포어를 사용하여 상호배제를 제공할 수 있다. 하지만 뮤텍스 락은 락의 사용 여부를 나타내는 이진 값을 가지지만, 세마포어는 정수 값을 가지므로 다양한 동기화 문제를 해결하는데 사용될 수 있다.
• 세마포어는 공유 자원에 세마포어의 변수만큼의 프로세스(또는 쓰레드)가 접근할 수 있다. 반면에 뮤텍스는 오직 1개만의 프로세스(또는 쓰레드)만 접근할 수 있다.
• 현재 수행중인 프로세스가 아닌 다른 프로세스가 세마포어를 해제할 수 있다. 하지만 뮤텍스는 락(lock)을 획득한 프로세스가 반드시 그 락을 해제해야 한다.