📗 관련 포스팅
동기화 포스팅에서 언급된 방법 중 하나인 세마포어 Semaphore에 대한 포스팅이다.
세마포어 Semaphore
동기화 방법 중 하나이며, 간단하게 가장 큰 특징을 2가지로 본다면 다음과 같다.
📌 Semaphore의 가장 큰 특징 2가지
1. 2개 이상의 프로세스 간 실행 제어도 가능하다.
2. 세마포어 변수S를 사용하여 임계 영역에 진입하는 프로세스의 갯수를 조절한다.
세마포어는 wait()와 signal() 연산을 사용한다. 이는 P()/V()로 불리기도 한다.
해당 포스팅에선 wait()와 signal()로 사용한다.
또한, wait()와 signal()은 indivisible(atomic) operations라 가정한다.
따라서, 여러 프로세스가 동시에 wait()를 실행 중에 있지 않는다.
indivisible(atomic) operation : 한 번 실행되면 중단없이 끝까지 실행이 되는 연산
세마포어의 역할은 상호 배제와 동기화(실행 순서 제어)이다.
wait(mutex); // mutex : 세마포 변수
// critical section
signal(mutex);
// remainder section다음과 같은 코드는 앞서 본 동기화 포스팅에서 비슷한 형태이며 상호 배제를 진행하고 있음을 알 수 있다
위 그림과 같이 Process i에서 signal(S)이 호출되어야지만 Process j가 wait(S)를 호출할 수 있다.
이는 프로세스의 실행 순서를 제어하는 것이다.
Binary Semaphore vs Couting Semaphore
세마포어 방식은 2가지로 분류가 가능하다
- Binary Semaphore : 최대 1개 프로세스만 접근 가능, mutex locks라고도 불린다.
- Counting Semaphore : 최대 n개 프로세스 접근 가능
앞서 설명하였듯이 세마포어는 여러 개의 프로세스 동기화가 가능하였다.
최대 접근 가능한 프로세스의 갯수로 분류를 나누는데, 이 때 중요하게 쓰이는 개념이 세마포어 변수 S이다
결론만 간단하게 말하면
- Binary Semaphore : 세마포어 변수 S가 1또는 0값을 가진다.
- Counting Semaphore : 세마포어 변수 S가 동기화 가능한 프로세스의 갯수 N만큼 가질 수 있다.
세마포어 변수 S에 대한 내용은 Busy waiting vs Non-Busy waiting에서 추가로 다룬다.
Busy waiting vs Non-Busy waiting
세마포어는 Busy waiting한 방법과 Non-Busy waiting한 방법이 있다.
1. Busy waiting한 세마포어
wait(S){
while S<=0; // busy waiting
S--;
}
signal(S){
S++;
}다음 코드는 간단하게 wait()와 signal()의 구현 코드라 생각하자.
wiat(S)에서 S<=0일 경우 busy waiting을 하게 된다.
즉, 한 프로세스가 실행은 되지만 그 동안 아무 일도 하지 않고 해당 반복문만 도는 것이다.
2. Non-Busy waiting한 세마포어
앞서 보았듯이 프로세스가 실행은 되지만 아무 일도 하지 않은 채 반복문만 무의미하게 도는 Busy waiting의 문제가 있었다.
이를 해결하기 위해 Non-Busy waiting 세마포어는 프로세스가 wait()를 호출하여 대기 상태로 들어갈 때 프로세스를 block시켜 버린다.
그리고 프로세스가 다시 실행되어야할 때는 wake up을 시켜 프로세스를 깨운다.
정리하면 다음과 같다.
📌 Non-busy waiting에 사용되는 연산
1. wait() = block
프로세스를 Ready Queue ➡ Waiting Queue(대기 큐)로 이동시키고, 프로세스를 blocked 상태로 바꾸어 실행이 되지 않도록 한다.2. signal() = wake up
프로세스를 Waiting Queue ➡ ReadyQueue로 이동시켜, 프로세스가 실행되도록 한다.
1) wait()
wait(S){
S--;
if(S < 0){
해당 프로세스를 waiting Queue로 이동
block();
}
}2) signal()
signal(S){
S++;
if(S <= 0){
waiting Queue에서 프로세스를 하나 꺼낸다.
wakeUp(P); // 해당 프로세스를 깨운다.
}
}위의 코드에서 볼 수 있듯이
wait() 실행 시 S의 값을 줄인 다음, S의 값이 0보다 작을 시 해당 프로세스는 block된다.
signal() 실행 시 S의 값을 늘린 다음, S의 값이 0보다 같거나 클 시 해당 프로세를 깨운다.
📌 wait(), signal() 함수로 세마포어 변수를 조절해 프로세스의 실행을 제어한다.
앞서 본 Binary Semaphore와 Counting Semaphore의 개념과 Non-busy waiting의 wait(), signal()을 결합시켜 세마포어의 동작을 이해해보자.
1. Binary Semaphore
Binary Semaphore는 S의 값이 0또는 1이다.
S의 초기값은 최대 실행될 수 있는 프로세스의 갯수 1개와 같은 1로 설정한다.
이 상태에서 Process i가 실행되어wait(S)를 호출한다.
이 상황에서 Process i의 실행이 멈추고 Process j가 실행된다고 해보자.
그렇다면, 세마포어 변수S = -1이 될 것이다.
따라서, Process j는 Waiting Queue로 들어갈 것이다. 따라서, Process j는 blocked 상태가 되며 다음 Ready Queue에 있는 Process i를 실행한다.
Ready Queue에 있는 Process i를 실행하게 되면 다음과 같이S = 0이 될 것이다.
그리고 Waiting Queue에 있는 Process j를 깨워 실행한다.
2. Counting Semaphore
Counting Semaphore는 S 값이 최대 접근 가능한 프로세스 갯수 n가 같다.
아래의 예시는 최대 접근 가능한 프로세스를 2개라 하고, 총 4개의 프로세스가 실행된다고 가정해보자.
Process A,B,C,D가 순차적으로 실행된다면 다음과 같은 상황이 이어질 것이다.
Binary Semaphore와 Counting Semaphore의 예제를 통해 알 수 있는 사실은
- Busy waiting Semaphore일 경우, S는 음수가 될 수 없다.
- Non-Busy waiting Semaphore일 경우, S는 음수가 될 수 있으며, S가 음수일 때 S의 절대값은 Waiting Queue에 있는 프로세스의 개수이다.
Busy waiting Semaphore는 wait() 함수 내부에서 S--를 맨 마지막에 수행하고
Non-Busy waiting Semaphore는 wait() 함수 내부에서 S--를 맨 처음에 수행한다.
따라서, Non-Busy waiting Semaphore는 S가 음수가 가능한 것이다.
📌 그렇다면 Busy waiting Semaphore는 무조건 안 좋을까?
Busy waiting Semaphore는 다음과 같은 특징이 있다.
- 구현 코드가 짧다.
- 프로세스들이 임계 영역에 드물게 차지하면 busy waiting은 거의 없다
- 임계영역에 접근하여 실행 중인 프로세스의 locked opreation이 짧다면 busy waiting은 효율적인 해결책이 된다.
Non-Busy waiting처럼 프로세스를 block/wake up할 경우에는 문맥 교환 오버헤드가 발생하기 때문에, 문맥 교환 오버헤드가 더 비용이 클 경우 Busy waiting이 더 좋다!
세마포어 사용 시 주의사항
1. incorret order
signal(mutex) ... wait(mutex)wait()-signal() 순서를 지켜야 한다.
2. duplicated use
wait(mutex) ... wait(mutex)중복된 호출을 하지 말아야 한다.
3. Ommiting of wait(mutex) or signal(mutex)
wait()와 signal() 연산 중 하나 혹은 둘다 빠드리지 않아야 한다.
4. DeadLock & Starvation
📌 DeadLock(교착 상태) : 둘 이상의 프로세스가 서로의 작업이 완료되기를 기다림. 서로가 보유한 자원을 요구하는 사오항
📌 Starvation(기아) : 한 프로세스가 필요한 자원을 할당받지 못하고 무한히 대기하는 상황
DeadLock과 Starvation은 연관있는 문제이긴하나
Starvation은 우선순위가 더 높은 프로세스가 먼저 실행되어 waiting queue에서 계속 대기하는 무한 대기의 문제가 발생한다.
또한, DeadLock은 시스템 전체가 멈추지만, Starvation은 starved processes를 제외한 시스템은 정상적으로 작동한다.
