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

Jeongyeon Park·2022년 12월 27일

OS 기본 개념

목록 보기

7/7

Shared Memory(공유 메모리)의 자원에 여러 개의 프로세스/스레드가 동시에 접근할 경우, Critical Section Problem이 발생할 수 있다.
따라서 공유 자원을 안전하게 관리하기 위해 Mutual Exclusion(상호 배제) 를 보장해야 하는데, 이 때 Semaphore(세마포어) 혹은 Mutex(뮤텍스) 방식을 선택할 수 있다.

Critical Section (= 공유 변수 영역)
여러 개의 프로세스/스레드가 데이터를 공유하며 실행될 때, 각 프로그램 코드 중 공유 자원에 접근하는 부분

각 프로세스가 자신의 Critical Section에 진입하기 위해 접근 허가를 요청하는 코드 부분을 Entry Section(입장 구역), Critical Section 코드 실행을 완료했음을 알리는 코드 부분을 Exit Section(퇴장 구역)이라고 한다.

Semaphore (세마포어)

1. Semaphore이란?

멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법

어떤 공유 자원에 동시에 접근할 수 있는 프로세스/스레드의 개수를 나타내는 값을 두어 상호 배제(Mutual Exclusion)을 달성하는 기법
Synchronization(동기화)를 위해 Wait, Signal 2개의 Atomic Operation 사용
wait 호출 시 semaphore의 count가 1씩 감소, count가 0 이하가 되면 lock (이외의 프로세스/스레드가 critical section을 실행할 수 없는 상태)
Critical Section 실행을 마친 프로세스/스레드가 signal 호출 시 semaphore의 count가 1씩 증가, count가 1 이상이 되면 다음 번 프로세스/스레드가 자신의 critical section 실행

2. Semaphore 예제

struct Semaphore{
    int count;
    queue<process> q; 
    // Critical Section에 접근하려는 process/thread의 PCB/TCB
};

P(Semaphore s){
    if(s.count <= 0){
        // 요청을 보낸 process/thread p를 Queue에 저장
        s.q.push(1);
        block();
    }
    
    else
        s.count = s.count - 1;
}

V(Semaphore s){
    // Critical Section을 실행하던 process/thread가 실행 완료 signal을 보냈을 때,
    // 설정된 Semaphore count 숫자 만큼의 process/thread가 기존에 critical section을 수행중이었다면
    // 현재 queue에서 대기 중인 process/thread 중 하나에게 critical section을 수행하도록 허용
    if(s.count <= 0 && !s.q.empty()){
        Process p = s.q.front();
        s.q.pop();
        wakeup(p);
    }
    
    else
        s.count = s.count + 1;
}

Mutex (뮤텍스)

1. Mutex란?

Critical Section을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되도록 하는 방법

하나의 프로세스/스레드에 의해 소유될 수 있는 Key를 기반으로 한 Mutual Exclusion 기법
Locking 메커니즘으로, Key에 해당하는 어떤 객체를 소유한 오직 하나의 프로세스/스레드만 동일 시점에 Lock을 걸고 Critical Section 수행 가능
해당 프로세스/스레드만 Critical Section 수행 완료 후 Lock 해제 가능

2. Mutex 예제

1) Dekker 알고리즘

flag와 turn 변수를 사용해 critical section에 들어갈 프로세스/스레드를 결정하는 방식

flag : 프로세스/스레드의 critical section 진입 여부
turn : 현재 critical section 실행 중인 프로세스/스레드

flag[i] = true; // 프로세스 i가 critical section 진입 시도
    
while(flag[j]) { // 프로세스 j가 현재 critical section에 진입해있고
    if(turn == j) { // critical section을 수행하고 있는 경우
        flag[i] = false; // 프로세스 i 진입 취소
            
        while(turn == j){}; 
        // j의 critical section 수행이 종료될 때까지 대기
            
        flag[i] = true; 
        // j의 critical section 수행이 종료되면 다시 i가 critical section 진입 시도
    }
}

// ------- Critical Section 코드 ---------
...
turn = i; // critical section 수행 종료 시 대기 중인 다른 프로세스로 turn 변경
flag[j] = false; // critical section 수행 완료

2) Peterson 알고리즘

Dekker 알고리즘과 유사하게 flag와 turn 변수 사용, critical section 진입 시도 시 다른 프로세스에게 먼저 lock을 걸 수 있는 기회를 양보하는 방식

flag[i] = true; // 프로세스 i가 critical section 진입 시도
turn = j; // 다른 프로세스 j가 먼저 진입할 수 있도록 양보
while(flag[j] && turn == j) {};
// j가 critical section을 수행하는 동안 대기

// ------- Critical Section 코드 ---------

flag[j] = false; // critical section 수행 완료

3) Bakery 알고리즘

N개(N>2)의 프로세스/스레드에 대한 처리가 가능한 알고리즘으로, critical section에 진입하고자 하는 프로세스/스레드에 번호를 부여하고 가장 번호가 작은 프로세스가 critical section에 진입

Critical section 진입 요청 시, 처음에는 현재 대기 중인 프로세스/스레드 중 가장 큰 번호를 부여받음

choosing[i] = 1; // 스레드 i의 critical section 진입 요청

// 현재 대기중인 스레드들의 번호 중 최대값 탐색
int max_number = 0;
for (int i = 0; i < THREAD_COUNT; ++i) {
	int num = numbers[i];
    max_number = num > max_number ? num : max_number;
}

// 스레드 i에게 기존 최대값보다 더 큰 번호 부여
numbers[i] = max_number + 1;

choosing[i] = 0; // 번호 부여 완료

// 다른 스레드 탐색 
for (int other = 0; other < THREAD_COUNT; ++other) {
    while (choosing[other]) {};
  
    // 번호가 부여된(critical section 진입 대기 중인) 스레드이면서
    // 스레드 i보다 작은 번호를 갖고 있는 경우
    while (numbers[other] && numbers[other] < numbers[i] && other < i) {};
    // 해당 스레드가 critical section을 먼저 수행하는 동안 대기
}

// ------- Critical Section 코드 ---------

numbers[other] = 0; 
// critical section 수행을 완료했으므로 번호 초기화

References

Jeongyeon Park

이전 포스트