Semaphore: 수기 신호
Mutex: Mutual Exclusion
공유된 자원의 데이터는 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 둬야 한다.
-> 세마포어
세마포어: 멀티프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법
임계 구역 (Critical Section)
프로세스에서 공유 데이터에 접근하기 위해 짜여진 코드 부분
임계 구역을 수행할 때는 다른 프로세스가 접근하지 못하도록 해야한다.
세마포어 P, V 연산
P: 임계 구역 들어가기 전 수행 (프로세스 진입 여부를 자원의 개수를 통해 결정)
V: 임계 구역에서 나올 때 수행 (자원 반납 알림, wait 중인 프로세스 깨움)
예시 상황
- A 프로세스가 먼저 도착하여 P(S)를 실행하면 S는 0이 되고 A는 임계구역에 들어갑니다.
- 이후 도착한 B 프로세스는 P(S)를 실행하려 하지만 S가 0이므로 B는 대기 상태에 머무릅니다.
- A가 임계구역에서의 작업을 완료하고 V(S)를 실행하면 S는 다시 1이 됩니다.
- 이후, B는 P(S)에서 while문을 빠져나와 임계구역으로 들어가 작업을 수행하게 됩니다.
뮤텍스
임계 구역을 가진 스레드들이 서로 실행시간이 겹치지 않도록 각각 단독으로 실행되게 하는 기술
Lock과 unLock을 사용한다.
Lock: 현재 임계 구역에 들어갈 권한을 얻어옴 (다른 프로세스 or 스레드가 임계 구역 수행 중이면 종료할 때까지 대기)
unLock: 현재 임계 구역을 모두 사용했음을 알림 (대기 중인 다른 프로세스 or 스레드가 임계 구역에 진입할 수 있음)
뮤텍스는 상태가 0 or 1 -> '이진 세마포어'
뮤텍스 알고리즘
- 데커 알고리즘
데커 알고리즘은 두 개의 프로세스만을 위한 솔루션으로, 서로 다른 시간에 임계 영역에 들어갈 수 있도록 하는데 사용됩니다. 각 프로세스는 서로의 행동을 확인하고 기다림으로써 상호 배제를 달성합니다.
flag: 어떤 프로세스가 임계영역에 진입할 것인지
turn: 누가 임계 구역에 들어갈 차례인지 - 피터슨 알고리즘
피터슨 알고리즘은 두 개의 프로세스가 임계 영역에 동시에 들어가는 것을 방지하는 알고리즘이며, 데커 알고리즘을 개선한 것입니다. 프로세스는 '플래그 설정->순서 결정->임계 영역 진입->플래그 해제'의 순서로 작동합니다.
데커와 유사하지만 상대방 프로세스 or 스레드에게 진입 기회를 양보라는 차이점 있음. - 제과점 알고리즘
제과점 알고리즘은 램포트가 고안한 알고리즘으로, 두 개 이상의 프로세스를 처리할 수 있습니다. 이 알고리즘은 번호표 시스템에 비유할 수 있으며, 각 프로세스에 번호를 부여하여 순서를 정합니다. 번호가 가장 낮은 프로세스가 임계 영역에 먼저 진입하게 됩니다.
