(11) 세마포어(Semaphore) & 뮤텍스(Mutex)

1. 세마포어 & 뮤텍스란?

1-1) 정의

멀티 프로세스 / 멀티 스레드 환경에서는 같은 데이터에 동시에 접근하면 문제가 발생할 수 있는데,

이때 공유 자원을 안전하게 접근하는 방식의 제한을 주는 것이 

세마포어와 뮤텍스라고 할 수 있음

참조 : https://korshika.tistory.com/150

(10) 경쟁 상태 ( Race Condition )

 

1-2) 임계구역 ( Critical Section )

여러 프로세스/스레드가 공유 데이터를 사용할 때, 코드에서 공유 데이터를 접근하는 직접적인 부분을 지칭

> 데이터 정합성을 유지하기 위해(공유데이터를 여러 부분에서 동시에 사용하거나 하여 데이터가 손상(?)되면)

   이 임계구역이 한곳에서 수행될 때 다른 프로세스/스레드의 접근을 막아야 함

 

 

2. 세마포어

2-1) 정의

멀티프로그래밍/스레딩 환경에서 공유자원에 대한 접근을 wait / signal 방식으로 제한하며,

wait에 접근한 프로세스/스레딩이 아닌 다른 프로세스/스레드가 signal로 lock을 해제할 수 있는 방식

 

2-2) P, V 연산

P : 임계구역 들어가기 전에 수행( 프로세스 진입 여부를 자원의 개수(S)를 통해 결정 )

V : 임계구역에서 나올 때 수행( 자원반납 알림, 대기중인 프로세스를 깨우는 신호 )

 

> Syntax

P(S);

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

V(S);

> 예시 persudo code

※ 자원 개수 0 이하가 되면 lock이 걸림

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임, signal이 들어오면 S + 1
    S := S+1      --> S를 1로 원위치시켜 해제하는 과정
end V

한 프로세스가 P혹은 V를 수행하고 있는 동안 프로세스가 인터럽트 당하지 않게 되고,

P, 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문을 빠져나올 수 있고, 임계구역으로 들어가 수행함

※ 세마포어가 상호배제를 통한 dead-lock 유발과 다른점

모든 자원에 대해 접근시 semaphore를 이용하도록 하고, 프로세스 / 스레드 수행 전 필요되는 모든 semaphore를 

가지지 못한 경우 semaphore를 모두 해제하고 다시 경쟁하도록 만들어 플래그처럼 사용하고

다른 프로세스/스레드와 동기화 하게 하는 것

보통 timeout을 설정하여 획득여부를 판단하고, 모두 획득을 하였으면 task run, 아니라면 자원 반환하도록

현재는 대부분의 커널에서 지원하도록 되어있음

 

> Psudo code

Task1()
{
task 2에게 신호를 보낸다
task 2로부터 신호를 기다린다
작업을 계속한다.
}

Task2()
{
task 1에게 신호를 보낸다
task 1 로 부터 신호를 기다린다.
작업을 계속한다.
}

참조 : https://jbear.tistory.com/entry/%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4%EB%A5%BC-%EC%9D%B4%EC%9A%A9%ED%95%9C-Deadlock-%ED%83%88%EC%B6%9C%EA%B3%BC-Synchronization

세마포어를 이용한 Deadlock 탈출과 Synchronization

 

 

3. 뮤텍스

3-1) 정의

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

상호배제 ( Mutual Exclusion ) 의 약자로, 해당 접근을 조율하기 위해 lock과 unlock을 사용

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

 

3-2) 작동 방식

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

 

3-3) 알고리즘

1. 데커 알고리즘

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

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

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

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

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

 

3. 재과점 알고리즘

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

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://gyoogle.dev/blog/computer-science/operating-system/Semaphore%20&%20Mutex.html

세마포어(Semaphore) & 뮤텍스(Mutex) | 👨🏻‍💻 Tech Interview