세마포어(Semaphore)

bolee·2022년 8월 29일
운영체제(OS)
1

42seoul

목록 보기
22/27
post-thumbnail
post-custom-banner

세마포어란?

세마포어(semaphore)는 에츠허르 다익스트라(Edsger Wybe Dijkstra)가 제안한 교착 상태(DeadLock)에 대한 해법으로 두개의 원자적(Atomic) 함수로 제어되는 정수 변수로 멀티프로그래밍 환경에서 공유자원에 대한 접근 제어를 하는 방법으로 사용되며, 1개의 공유되는 자원에 제한된 개수의 프로세스(Process), 또는 스레드(Thread)만 접근할 수 있도록 한다.

교착 상태(DeadLock)
두 개 이상의 프로세스나 스레드가 서로 자원을 얻지 못해서 다음 처리를 하지 못하는 상태를 말한다. 즉, 무한히 다음 자원을 기다리게 되는 상태이다.
시스템적으로 한정된 자원을 여러 곳에서 사용하려고 할 때 발생한다.

원자성(Atomicity)
여러 개의 쓰레드(Thread)가 존재할 때, 특정 시점에서 어떤 메소드(Method)를 2개 이상의 쓰레드가 동시에 호출하지 못하는 것을 말한다.
이러한 원자성을 보장한 함수를 원자적 함수(Atomic Function)이라고 한다.

이 때, 세마포어의 카운트는 1 이상이며 카운트를 조절하여 진입 가능한 프로세스/스레드 수를 조절할 수 있다.

다만, 해당 방법은 모든 교착 상태에 대한 해답을 제시해 줄 수 없으나 교착 상태 해법에 대한 고전적인 해법으로 아직도 대다수의 운영 체제 과목 및 시스템 프로그래밍 과목에서 언급되는 개념이다.

이 방법으로 해결되는 대표적인 문제가 식사하는 철학자 문제다.

작동 원리

세마포어의 작동 원리는 상호 배제 알고리즘(Mutual Exclusion Algorithm)에 기반한다.

상호 배제 알고리즘(Mutual Exclusion Algorithm)
동시 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용되는 알고리즘으로, 임계 구역(Critical Section)에서 구현된다.

세마포어는 원자적(Atomic)으로 제어되는 정수 변수로, 일반적으로 세마포어의 값이 0이면 자원에 접근할 수 없도록 블럭(Block) 하고 0보다 크면 접근함과 동시에 세마포어의 값을 1 감소시킨다.
반대로 종료하고 나갈 때에는 세마포어의 값을 1 증가시켜 다른 프로세스가 접근할 수 있도록 한다.

여기서 접근되는 자원은 임계 구역(Critical Section)으로 이 설정에 따라서 프로그램의 퍼포먼스가 극단적으로 하락할 수 있어 사용에 세심한 주의가 필요하다.

임계 구역/영역(Critical Section)
여러 프로세스가 데이터를 공유하며 수행될 때, 각 프로세스에서 공유 데이터를 접근(Access)할 수 있도록 하는 프로그램 코드 부분이다.
즉, 여러 프로세스가 동일 자원을 동시에 참조하여 값(공유하는 변수명, 파일 등)이 오염될 위험 가능성이 있는 영역이다.
따라서 프로그래밍 시 성능 향상을 위해 임계영역을 최소화하는 설계를 해야 한다.

구성

세마포어 변수 S와 P 연산, V 연산으로 구성되어 있다.

세마포어 변수 S는 일반적으로 정수형 변수를 사용하며, 세마포어의 종류는 이진형 세마포어와 계수형 세마포어가 있다.

  • 이진형 세마포어(binary semaphore): 0 또는 1을 가진다. 즉, 1개의 공유 자원을 상호배제하며 이를 이용해 계수 세마포어를 구현할 수도 있다.
  • 계수형 세마포어(counting semaphore): 0과 양의 정수값을 가질 수 있따. 여러개의 공유 자원을 상호배제할 수 있다.

이러한 세마포어 변수 S는 P와 V라는 명령에 의해서만 접근할 수 있다.
(P와 V는 각각 try와 increment를 뜻하는 네덜란드어 Proberen과 Verhogen의 머릿글자를 딴 것이다.)
여기서 P 는 임계 영역을 사용하려는 프로세스들의 진입 여부를 결정하는 조작으로 Wait 동작이라고도 한다.
V 는 대기 중인 프로세스를 깨우는 신호(Wake-up)로 Signal 동작이라고도 한다.

P는 임계 구역에 들어가기 전에 수행되고, V는 임계 구역에서 나올 때 수행된다.
이때 변수 값을 수정하는 연산은 모두 원자성을 만족해야 한다. 즉, 한 프로세스(또는 스레드)에서 세마포어 값을 변경하는 동안 다른 프로세스가 동시에 이 값을 변경해서는 안 된다.

적용

Busy Waiting

최초에 제시된 방안으로 아무것도 하지 않는 빈 반복문을 계속 돌다가 임계 구역에 진입할 수 있을 때 진입하는 방식이다.

P(S) {
	while S <= 0;	// 아무것도 하지 않음 (반복문)
    S--;
}

V(S) {
	S++;
}

이 방법은 빈 반복문을 반복하기 때문에 계속적으로 Context Switching이 발생하며 이로 인하여 단일처리 다중프로세스 환경에서 처리 효율이 떨어진다.
또한, 어떠한 프로세스가 먼저 임계 구역에 진입을 할 수 있을지에 대한 처리를 할 수 없다는 단점도 존재한다.

Block-WakeUp

Busy Waiting의 단점을 보완한 방식으로, 프로세스를 재워 큐(wait queue)에 넣어 공유 자원을 관리한다.

Block(P)

  • 커널은 Block을 호출한 프로세스를 Suspend(지연)
  • 프로세스의 PCB(Process Control Block)를 Semaphore에 대한 wait queue에 넣음

Wakeup(V)

  • Block된 프로세스 P를 WakeUp 시킴
  • 이 프로세스의 PCB를 Ready queue로 옮김
P(S) {
	S--;
    if (S < 0)
    	// 해당 프로세스를 wait queue에 추가(Block)
}

V(S) {
	S++;
    if (S <= 0)
    	// wait queue에서 프로세스를 제거(WakeUp)
}

Busy Waiting vs Block-WakeUp

일반적으로 CPU 소모를 줄일 수 있는 Block-WakeUp 방식이 좋다.
그러나, Block-WakeUp 방식은 프로세스를 WakeUp하는 과정에서 발생하는 오버헤드가 존재한다.

따라서

  • critical section 길이가 길면, Block/wakeup이 적당
  • critical section 길이가 매우 짧으면, busy-wait 가 적당

주의점

P함수와 V함수의 동작은 독립적이기 때문에 잘못 사용하는 경우 문제가 발생한다.

  • P - 임계 구역 - P : 현재 프로세스가 임계 구역에서 빠져나갈 수 없게 된다. 또한 다른 프로세스들은 임계 구역에 들어갈 수 없으므로 교착 상태(Deadlock)가 발생한다.

  • V - 임계 구역 - P : 2개 이상의 프로세스가 동시에 임계구역에 들어갈 수 있으므로 상호 배제(Mutual Exclusion)를 보장할 수 없게 된다.

참고 자료

https://ko.wikipedia.org/wiki/%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4
https://gyoogle.dev/blog/computer-science/operating-system/DeadLock.html
https://jwprogramming.tistory.com/13
https://chelseashin.tistory.com/40
https://overcome-the-limits.tistory.com/340
https://heeonii.tistory.com/14
https://ko.wikipedia.org/wiki/%EC%83%81%ED%98%B8_%EB%B0%B0%EC%A0%9C
https://velog.io/@youngminss/OS-%ED%94%84%EB%A1%9C%EC%84%B8%EC%8A%A4-%EB%8F%99%EA%B8%B0%ED%99%942#block--wake-up

profile
bolee
이전 포스트

뮤텍스(Mutex)

다음 포스트

뮤텍스(Mutex) vs 세마포어(Semaphore)

post-custom-banner

0개의 댓글