세마포어
운영체제와 병렬 프로그래밍을 훑어보면 반드시 보게되는 개념인 Semaphore
다중 프로세스 환경에서 공유 자원에 대한 접근을 제어하는 동기화 도구입니다.
Semaphore 는 정수 값을 가진 변수라고 쉽게 말할 수 있습니다.
하지만 Simple is best 라는 말이 있듯, 이 변수가 프로세스 동기화 문제를 해결할때 중요한 역활을 합니다.
가장 기본적인 형태는 0과 1만 사용하는 Binary Semaphore 가 있습니다.
동작하는 방식
Semaphore 는 정수형 변수 S와 두가지 원자적 연산(P와 V)으로 구성됩니다.
P 연산 (Wait)
세마포어 값을 감소시킵니다.
임계 구역에 진입하기 전에 수행됩니다.
S > 0이면 S를 1 감소시키고 진입합니다.
S ≤ 0이면 프로세스를 대기시킵니다.
V 연산 (Signal)
세마포어 값을 증가시킵니다.
임계 구역에서 나올 때 수행됩니다.
S를 1 증가시킵니다.
대기 중인 프로세스가 있으면 하나를 깨웁니다.
구현 방식
세마포어는 두 가지 주요 방식으로 구현될 수 있습니다
Busy Waiting
- 프로세스가 계속 반복문을 돌며 진입 가능여부를 확인
- CPU 리소스를 낭비하는 단점이 존재
Block-Wakeup
- 프로세스를 대기 큐에 넣어 관리
- CPU 소모를 줄일 수 있지만, 프로세스 전환 오버헤드가 존재
분류
값의 범위에 따른 분류
Binary Semaphore
- 값이 0 또는 1만 가능합니다.
- 상호 배제(mutual exclusion)를 구현하는 데 주로 사용
- 본질적으로 뮤텍스(mutex)와 유사한 기능
- 아래의 코드에서 보면 true(1), false(0)와 Busy Waiting으로 구현
pub struct BinarySemaphore {
flag: Mutex<bool>,
cond: Condvar,
}
impl BinarySemaphore {
pub fn new() -> Self {
Self {
flag: Mutex::new(true),
cond: Condvar::new(),
}
}
pub fn acquire(&self) {
let mut flag = self.flag.lock().unwrap();
while !*flag {
flag = self.cond.wait(flag).unwrap();
}
*flag = false;
}
pub fn release(&self) {
let mut flag = self.flag.lock().unwrap();
*flag = true;
self.cond.notify_one();
}
}활용사례
- 상호 배제: 공유 자원에 대한 동시 접근을 방지
- 간단한 동기화: 두 스레드 간의 순서를 제어할 때 사용 가능
- 시그널링: 한 스레드가 다른 스레드에게 특정 이벤트의 발생을 알릴 때 사용할 수 있다.
- 데드락 방지: 적절히 사용하면 데드락을 방지하는데 도움이 된다.
Counting Semaphore
- 0 이상의 정수 값을 가질 수 있습니다.
- 여러 개의 리소스를 관리할 수 있는 세마포어 유형
- 주로 여러 인스턴스를 가진 자원을 관리하는 데 사용됩니다.
pub struct CountingSemaphore {
count: Mutex<usize>,
cond: Condvar,
}
impl CountingSemaphore {
pub fn new(count: usize) -> Self {
Self {
count: Mutex::new(count),
cond: Condvar::new(),
}
}
pub fn acquire(&self) {
let mut count = self.count.lock().unwrap();
while *count == 0{
count = self.cond.wait(count).unwrap();
}
*count -= 1;
}
pub fn release(&self) {
let mut count = self.count.lock().unwrap();
*count += 1;
self.cond.notify_one();
}
}활용사례
- 프린터 관리: 여러 대의 프린터를 공유할 때 사용할 수 있다.
- 주차장 관리: 주차 공간의 수를 세마포어 값으로 설정하여 관리할 수 있다.
- 버퍼 관리: 생산자-소비자 문제에서 버퍼의 가용 공간을 관리할 때 사용할 수 있다.
- 스레드 풀: 동시에 실행 가능한 작업의 수를 제한할 때 활용할 수 있다.
구현 방식에 따른 분류
Strong Semaphore
- 대기중인 프로세스나 스레드를 FIFO(First-In-First-Out) 순서로 관리하는 세마포어
- 0 이상의 정수 값(count)을 가질 수 있어 Counting Semaphore의 특성을 가집니다.
- 대기 중인 스레드를 큐(queue)로 관리하여 공정성을 보장합니다.
- Block-Wakeup 방식으로 구현되어 CPU 자원을 효율적으로 사용합니다.
pub struct StrongSemaphore {
count: Mutex<usize>,
queue: Mutex<VecDeque<Arc<Condvar>>>,
}
impl StrongSemaphore {
pub fn new(count: usize) -> Self {
Self {
count: Mutex::new(count),
queue: Mutex::new(VecDeque::new()),
}
}
pub fn acquire(&self) {
let mut count = self.count.lock().unwrap();
if *count == 0 {
let cvar = Arc::new(Condvar::new());
self.queue.lock().unwrap().push_back(cvar.clone());
while *count == 0 {
count = cvar.wait(count).unwrap();
}
}
}
pub fn release(&self) {
let mut count = self.count.lock().unwrap();
*count += 1;
if let Some(cvar) = self.queue.lock().unwrap().pop_front() {
cvar.notify_one();
}
}
}활용사례
- 작업 스케쥴링: 작업의 우선순위나 도착 순서를 고려한 스케쥴링에 사용
- 공정한 리소스 할당: Race Condition 에서 공정성을 보장
- 복잡한 동기화 시나리오: 여러 단계의 동기화가 필요한 경우
- Reader-Writer: 읽기 작업과 쓰기 작업간의 우선순위
- 병렬 알고리즘: 여러 스레드가 헙력하여 작업을 수행할 때 작업 분배와 결과 수집을 관리
Weak Semaphore
- Race Condition 에서 순서를 보장하지 않는 유형
- 0 이상의 정수 값(count)을 가질 수 있어 Counting Semaphore의 특성을 가집니다.
- 모든 대기 중인 스레드가 단일 조건 변수를 공유합니다.
- Block-Wakeup 방식으로 구현되어 있지만, 깨어나는 순서는 보장되지 않습니다.
pub struct WeakSemaphore {
count: Mutex<usize>,
cond: Condvar,
}
impl WeakSemaphore {
pub fn new(count: usize) -> Self {
Self {
count: Mutex::new(count),
cond: Condvar::new(),
}
}
pub fn acquire(&self) {
let mut count = self.count.lock().unwrap();
while *count == 0 {
count = self.cond.wait(count).unwrap();
}
*count -= 1;
}
pub fn release(&self) {
let mut count = self.count.lock().unwrap();
*count += 1;
self.cond.notify_all();
}
}활용사례
- 리소스 풀 관리: 데이터베이스 연결 풀이나 스레드풀 에서 사용 가능한 리소스 관리
- 작업 큐 시스템: 우선순위가 없는 작업 큐에서 작업 처리를 관리
- 이벤트 처리 시스템: 여러 이벤트 핸들러가 동시에 대기하는 시스템에서 사용
- 성능 중심 시스템: 엄격한 공정성보다 처리량이 더 중요한 시스템에서 사용
Timing Test
BinarySemaphore Timing Results:
Average wait time: 592 ms
Average execution time: 11 ms
CountingSemaphore Timing Results:
Average wait time: 51 ms
Average execution time: 11 ms
StrongSemaphore Timing Results:
Average wait time: 0 ms
Average execution time: 11 ms
WeakSemaphore Timing Results:
Average wait time: 51 ms
Average execution time: 11 ms-
실행 시간의 일관성
모든 세마포어 유형에서 평균 실행 시간이 11ms로 동일합니다. 이는 각 작업이 설계대로 약 10ms 동안 실행되었음을 보여줍 -
BinarySemaphore의 높은 대기 시간
BinarySemaphore가 가장 긴 대기 시간(592ms)을 보였습니다. 이는 한 번에 하나의 작업만 실행할 수 있는 BinarySemaphore의 특성 때문입 -
StrongSemaphore의 우수한 성능
StrongSemaphore는 0ms의 평균 대기 시간을 보여, 가장 효율적인 성능을 나타냈습니다. 이는 FIFO 방식으로 대기 중인 작업을 관리하는 StrongSemaphore의 특성이 이 테스트 시나리오에 가장 적합했음을 시사합니다. -
CountingSemaphore와 WeakSemaphore의 유사한 성능
CountingSemaphore와 WeakSemaphore는 동일한 평균 대기 시간(51ms)을 보였습니다. 이는 두 세마포어가 비슷한 방식으로 작업을 관리하고 있음을 나타냅니다.
결론
이번 테스트를 통해 각 세마포어 유형의 특성과 성능 차이를 명확히 확인할 수 있었습니다.
StrongSemaphore는 FIFO 방식으로 대기 중인 작업을 관리하여 가장 효율적인 성능을 보여주었으며,
이는 공정한 리소스 할당이 필요한 시나리오에 적합합니다.
반면, BinarySemaphore는 한 번에 하나의 작업만 처리할 수 있어 대기 시간이 길어졌습니다. 이는 상호 배제가 필요한 상황에 적합하지만, 성능 요구가 높은 환경에서는 주의가 필요합니다.
CountingSemaphore와 WeakSemaphore는 중간 정도의 성능을 보였으며, 여러 리소스를 동시에 관리해야 하는 경우 유용하게 사용될 수 있습니다. 특히, WeakSemaphore는 순서를 보장하지 않으므로 성능이 중요한 시스템에서 활용할 수 있습니다.
결론적으로, 세마포어를 선택할 때는 애플리케이션의 특성과 요구 사항을 고려해야 합니다. 각 세마포어 유형은 특정 상황에서 강점을 발휘하므로, 적절한 유형을 선택함으로써 시스템의 안정성과 효율성을 극대화할 수 있습니다.
Github: Semaphore
