[Computer Science][Operating System] 세마포어(Semaphore) & 뮤텍스(Mutex) 🔒✨
공유 자원에 여러 프로세스가 동시에 접근하면서 문제를 일으킬 수 있다. 이때 공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한해야 한다. 이를 위해 세마포어와 뮤텍스가 사용된다.
세마포어란? 📏
세마포어는 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법이다. 여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근하는 프로그램 코드 부분을 임계 구역(Critical Section)이라고 한다.
임계 구역(Critical Section) 🚪
여러 프로세스가 동시에 공유 데이터에 접근할 경우 잘못된 결과를 초래할 수 있다. 따라서 한 프로세스가 임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야 한다.
세마포어 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문을 빠져나올 수 있고, 임계 구역으로 들어가 수행하게 된다.
뮤텍스란? 🔑
뮤텍스는 임계 구역을 가진 스레드들의 실행 시간이 서로 겹치지 않고 단독으로 실행되도록 하는 기술이다. 이는 상호 배제(Mutual Exclusion)의 약자이다. 뮤텍스는 lock과 unlock을 사용하여 접근을 조율한다.
- lock: 현재 임계 구역에 들어갈 권한을 얻는다. 만약 다른 프로세스나 스레드가 임계 구역을 수행 중이면 종료할 때까지 대기한다.
- unlock: 현재 임계 구역을 모두 사용했음을 알린다. 대기 중인 다른 프로세스나 스레드가 임계 구역에 진입할 수 있게 된다.
뮤텍스는 상태가 0과 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 = 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; // 임계 구역 사용 종료
}이 글은 세마포어와 뮤텍스의 개념 및 다양한 알고리즘을 통해 멀티프로세스 환경에서의 상호 배제 문제를 해결하는 방법을 설명한다. 이 내용을 통해 효율적인 프로그래밍을 위한 기초 지식을 쌓을 수 있다.
[1] GitHub - 세마포어(Semaphore) & 뮤텍스(Mutex) (https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer%20Science/Operating%20System/Semaphore%20%26%20Mutex.md)
[2] 티스토리 - [운영체제] Mutex 뮤텍스와 Semaphore 세마포어의 차이 (https://heeonii.tistory.com/14)
[3] 뭉게뭉게 클라우드 - [운영체제] 세마포어(Semaphore) & 뮤텍스(Mutex) (https://nice-engineer.tistory.com/entry/%EC%9A%B4%EC%98%81%EC%B2%B4%EC%A0%9C-%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4Semaphore-%EB%AE%A4%ED%85%8D%EC%8A%A4Mutex)
[4] velog - [OS]뮤텍스(Mutex)와 세마포어(Semaphore) (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)
