[Operating System] 세마포어(Semaphore) & 뮤텍스(Mutex)

공유 자원?

• 여러 스레드가 공유 자원에 접근 시 race condition이 발생
  • 프로그램의 안정성과 일관성을 해치게 될 것
• 공유 자원 접근 시 아래와 같은 문제가 발생
  1. 일관성이 없는 데이터
     • 두 개 이상의 스레드가 동시에 공유 자원을 변경하거나 읽을 때 서로 다른 데이터를 읽게되어 다른 정보를 제공 받을 수 있다. 
  2. 데드락(Deadlock)
     • 두 개 이상의 스레드가 서로 다른 자원을 점유하고, 서로 상대방 자원을 기다릴 때 교착 상태가 발생할 수 있다.
  3. 성능 저하
     • 스레드간의 경쟁 상태로인해 성능이 저하된다.
• 위와 같은 상황을 방지하기 위해 동기화 기법인 뮤텍스나 세마포어를 통해 하나의 스레드만이 공유 자원에 접근하도록 한다.

세마포어(Semaphore)

• 세마포어는 리소스의 상태를 나타내는 간단한 카운터로 생각할 수 있다.
• 일반적으로 비교적 긴 시간을 확보하려는 리소스에 대해 이용하게 된다.
• 유닉스 시스템의 프로그래밍에서 세마포어는 운영체제의 리소스를 경쟁적으로 사용하는 다중 프로세스에서 행동을 조정하거나 동시화 시키는 기술이다.
• 멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법이다.

세마포어의 P, V 연산

• P : 임계 구역에 들어가기 전에 수행
  • 프로세스의 진입 여부를 자원의 개수(S)를 통해 결정
• V : 임계 구역에 나올 때 수행
  • 자원 반납 알림, 대기 중인 프로세스를 깨우는 신호
• 구현 방법

P(S);

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

V(S);

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

--- 임계 구역 ---

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

• 이를 통해, 한 프로세스가 P 혹은 V를 수행하고 있는 동안 프로세스가 인터럽트 당하지 않게 한다.
• P와 V를 통해 임계 구역에 대한 상호배제 구현이 가능하게 되었다.
• 연산 방법
  • 최초 S의 값이 1이고, 해당 임계 구역을 수행할 프로세스 A, B가 있다고 가정
  • 먼저 도착한 A가 P(S)를 실행하여 S를 0으로 만들고 임계 구역에 들어감
  • 그 뒤에 도착한 B가 P(S)를 실행하지만 S가 0이므로 대기 상태에 빠짐
  • A가 임계 구역 수행을 마치고 V(S)를 실행하면 S는 다시 1이 된다.
  • B는 P(S)에서 while을 빠져나올 수 있고, 임계 구역에 들어가 작업을 수행함

세마포어 예시

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

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

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

뮤덱스(Mutex)

• 상호 배제(Mutual Exclusion)의 약자이다.
• 공유된 자원이나 임계 구역 같은 곳에 스레드의 실행 시간이 서로 겹치지 않게 하나의 프로세스 또는 스레드가 접근하는 것을 막는다.

• 한 프로세스에 의해 소유될 수 있는 key를 기반으로 한 상호배제 기법이다.
• key에 해당하는 어떤 객체가 있으며, 이 객체를 소유한 스레드나 프로세스만이 공유 자원에 접근할 수 있다.
• 해당 접근을 조율하기 위해 lock과 unlock을 사용한다.
• lock
  • 현재 임계 구역에 들어갈 권한을 얻어옴
  • 만약 다른 프로세스/스레드가 임계 구역 수행 중이면 종료할 때까지 대기
• unlock
  • 현재 임계 구역을 모두 사용했음을 알림
  • 대기 중인 다른 프로세스/스레드가 임계 구역에 진입할 수 있음
• 뮤텍스는 상태가 0, 1로 이진 세마포어로 부르기도 함

뮤텍스 알고리즘

데커(Deker) 알고리즘

• 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로 바꿔 임계 구역 사용 완료를 알림

피터슨(Peterson) 알고리즘

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

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

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

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

제과점(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; // 임계 구역 사용 종료
}

뮤텍스 예시

• 뮤텍스는 화장실이 하나밖에 없는 식당과 비슷하다.
• 화장실에 가기 위해서는 카운터에서 열쇠를 받아 가야하며 화장실에 가려고 하는데 카운터에 키가 있다면 화장실에 사람이 없다는 뜻이다.

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

• 다른 사람도 화장실을 이용하고자 카운터에서 대기 하고 있다.
• 앞사람이 화장실에서 나와 열쇠를 반납하였으며, 대기하고 있던 사람 중 가장 앞에 있는 사람은 열쇠를 가지고 화장실을 이용할 수 있다.

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

• 동기화 대상의 갯수 차이
  • 뮤텍스는 동기화 대상이 오직 하나이다.
  • 세마포어는 변수만큼의 프로세스 접근이 가능하여 하나 이상이다.
• 세마포어는 lock을 소유할 수 없지만 뮤텍스는 책임을 가지는 대신 lock을 소유를 할 수 있다.
  • 그 이유는 뮤텍스 의 상태는 0,1 이 두개 뿐이기 때문이다.

 

 

 

 

출처

https://velog.io/@dodozee/%EB%AE%A4%ED%85%8D%EC%8A%A4Mutex%EC%99%80-%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4Semaphore

[OS]뮤텍스(Mutex)와 세마포어(Semaphore)

https://heeonii.tistory.com/14

[운영체제] Mutex 뮤텍스와 Semaphore 세마포어의 차이

https://github.com/gyoogle/tech-interview-for-developer

GitHub - gyoogle/tech-interview-for-developer: 👶🏻 신입 개발자 전공 지식 & 기술 면접 백과사전 📖