OS - 세마포어(Semaphore)와 뮤텍스(Mutex) (+ Race Condition)

공유 자원에 대해 여러 프로세스가 동시에 접근하면서, 결과값에 영향을 줄 수 있는 상태를 Race Condition(경쟁 상태)이라 한다.

공유 자원에 결함이 발생할 수 있음

 

Race Condition이 발생하는 경우와 해결 방법

1. 커널 작업을 수행하는 중에 인터럽트 발생
   • 문제점 : 커널모드에서 데이터를 로드하여 작업을 수행하다가 인터럽트가 발생하여 같은 데이터를 조작하는 경우
   • 해결법 : 커널모드에서 작업을 수행하는 동안, 인터럽트를 disable 시켜 CPU 제어권을 가져가지 못하도록 한다.
2. 프로세스가 'System Call'을 하여 커널 모드로 진입하여 작업을 수행하는 도중 문맥 교환이 발생할 때
   • 문제점 : 프로세스1이 커널모드에서 데이터를 조작하는 도중, 시간이 초과되어 CPU 제어권이 프로세스2로 넘어가 같은 데이터를 조작하는 경우
   • 해결법 : 프로세스가 커널모드에서 작업을 하는 경우 시간이 초과되어도 CPU 제어권이 다른 프로세스에게 넘어가지 않도록 함
3. 멀티 프로세서 환경에서 공유 메모리 내의 커널 데이터에 접근할 때
   • 문제점 : 멀티 프로세서 환경에서 2개의 CPU가 동시에 커널 내부의 공유 데이터에 접근하여 조작하는 경우
   • 해결법 : 커널 내부에 있는 각 공유 데이터에 접근할 때마다, 그 데이터에 대한 lock/unlock을 하는 방법

그밖에도 멀티 프로세스 / 멀티 스레드 환경에서 여러 프로세스나 스레드가 공통 전역변수에 접근할 경우에도 Race Condition이 발생할 수 있다.

 

그러한 문제를 해결하기 위해 아래 2가지 방법 중 한 가지를 선택하게 된다.

• 세마포어(Semaphore)
• 뮤텍스(Mutex)

세마포어는 동기화할 자원이 1개 이상일 때 사용하며, 뮤텍스는 동기화할 자원이 1개일 때 사용한다.

 

세마포어와 뮤텍스를 알아보기 전에 임계 구역을 알고가자.

임계 구역(Critical Section)

여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 부분을 의미한다.

 

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

• Mutual Exclusion (상호 배제)
  • 한 프로세스가 자신의 임계 구역이면, 다른 프로세스들은 임계 구역에 진입할 수 없다.
• Progress (진행)
  • 아무도 임계 구역에 있지 않다면, 진입하고자 하는 프로세스가 임계 구역에 진입하게 해줘야 한다. 즉, 아무도 임계 구역에 진입하지 못하면 안된다.
• Bounded Waiting (유한 대기)
  • 프로세스가 임계 구역에 진입하기 위해 무한정 기다리는 현상이 발생해서는 안된다.

이제 세마포어를 알아보자.

세마포어(Semaphore)

세마포어는 멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법이다.

 

세마포어의 연산은 P, V로 나눈다.

• P: 임계 구역에 들어가기 전에 수행
  • 프로세스 진입 여부를 자원의 개수(S)를 통해 결정한다.
• V: 임계 구역에서 나올 때 수행
  • 자원 반납을 알려서 대기 중인 프로세스를 깨운다.

구현 방법

P(S);

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

V(S);

procedure P(S)
    while S=0 do wait  --> S(사용 가능한 자원 수)가 0이면 대기한다.
    S := S-1   --> S에서 사용할 자원의 개수를 1 감소한다.
end P

--- 임계 구역 ---

procedure V(S) --> 현재상태는 S가 0임
    S := S+1   --> S를 다시 증가시켜서 자원이 존재하다는 것을 알린다.
end V

P와 V를 사용해서 임계 구역에 대한 상호배제를 구현한다. 이를 통해 한 프로세스가 P 혹은 V를 수행하고 있는 동안 프로세스가 인터럽트 당하지 않게 된다.

 

[예시]

1. A 프로세스에서 임계 구역에 진입하기 전에 S를 0으로 만든다.
2. B 프로세스에서는 S가 1이 될때 까지 기다린다.
3. A 프로세스가 임계 구역에서 나갈 때 S를 1로 변경한다.
4. B 프로세스가 임계 구역에 진입한다.

뮤텍스(Mutex)

뮤텍스는 임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술이다.

뮤텍스(Mutex): 상호 배제(Mutual Exclusion)의 약자

 

해당 접근을 조율하기 위해 lock과 unlock을 사용한다.

• lock: 현재 임계 구역에 들어갈 권한을 얻어온다.
  • 만약 다른 프로세스 / 스레드가 임계 구역을 수행 중이면 종료할 때까지 대기한다.
• unlock: 현재 임계 구역을 모두 사용했음을 알린다.
  • 대기 중인 다른 프로세스 / 스레드가 임계 구역에 진입할 수 있다.

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

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 = i; // 임계 구역 사용 끝나면 turn을 넘김
flag[j] = false; // flag 값을 false로 바꿔 임계 구역 사용 완료를 알림

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

프로세스 / 스레드가 두 개일때 상호 배제를 보장하는 알고리즘이다.

 

데커 알고리즘과 유사하지만, 상대방 프로세스/스레드에게 진입 기회를 양보하는 것에 차이가 있고 더 간단하게 구현되었다.

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

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

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

제과점(Bakery) 알고리즘

프로세스 / 스레드가 N개일 때 상호 배제를 보장하는 알고리즘이다.

 

가장 작은 수의 번호표를 가지고 있는 프로세스가 임계 구역에 진입한다.

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; // 임계 구역 사용 종료

 

참고

• https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Operating%20System/Semaphore%20%26%20Mutex.md
• https://jhnyang.tistory.com/101