[OS] Semaphore란? (Feat.상호배제 방법 - 뮤텍스(Mutex)와 모니터(Monitor)까지) - 1편

세마포어(Semaphore)란?

멀티 프로그래밍 환경에서 공유 자원에 대한 접근을 제한하는 방법

공유된 자원의 데이터 혹은 임계구역(Critical Section) 등에 여러 Process 혹은 Thread가 동시에 접근하면서 발생될 수 있는 문제를 방지하기 위하여 한 번에 하나의 프로세스만 접근할 수 있도록 제한을 두는 방법입니다. 이를 위해 사용하고 있는 스레드나 프로세스의 수를 공통으로 관리하는 하나의 값(공유변수)을 이용해 상호 배제를 달성할 수 있도록 합니다.

 

세마포어 개념도

상호 배제(Mutual Exclusion)란?

멀티 프로그래밍에서 공유 불가능한 자원의 동시 사용을 피하기 위해 사용하는 알고리즘

임계 구역으로 불리는 코드 영역에 의해 구현된다.

= 하나의 프로세스가 공유 자원을 사용할 때 다른 프로세스의 접근을 막는 것이다.

• 상호 배제 알고리즘
  • 데커 알고리즘
  • 피커슨 알고리즘
  • 제과점 알고리즘
• 상호 배제는 교착상태의 4가지 필요조건 중 하나
  
  1. 상호 배제 : 배타적 통제권(동시 사용 불가)
  2. 점유 대기 : 할당된 자원을 가진 상태에서 다른 자원을 기다림
  3. 비선점 : 다른 프로세스가 선점하고 있는 자원을 뺏을 수 없음
  4. 순환대기 : 각 프로세스는 순환적으로 다음 프로세스가 요구하는 자원을 가지고 있는 상황
• 교착 상태와 기아 상태
  • 교착 상태 (DeadLock) : 무한 대기
  • 기아 상태 (Starvation) : 우선 순위가 낮아 자원을 계속 할당받지 못하는 상태
•  멀티 프로세스나 멀티 스레드 동기화에 사용된다
• 동기화 (Synchronize) : 상호 배제를 위해 프로세스/스레드들의 실행을 제어하는 것. 
  -> 여기에 세마포어, 뮤텍스, 모니터 개념이 적용된다

임계구역 (Critical Section) 이란?

공유자원에 접근하는 프로세스 내부의 코드 영역

임계구역

어떤 한 프로세스가 이 구역을 사용중일 때 다른 프로세스가 같은 구역을 사용(접근)하려 한다면 문제가 발생할 수 있다

따라서 문제가 발생하지 않도록 한번에 하나의 프로세스만 이용하게끔 보장해야 하는 영역이다.

• 임계 구역 문제 해결을 위한 3가지 조건
  1. 상호배제
     하나의 프로세스가 임계 구역에 들어가있다면 다른 프로세스는 들어갈 수 없어야 함
  2. 진행
     임계 영역에 들어간 프로세스가 없는 상태에서 들어가려 하는 프로세스가 여러개라면 어느 것이 들어갈 지 결정해주어야 함
  3. 한정 대기
     다른 프로세스의 기아(Starvation)을 방지하기 위해, 한 번 임계 구역에 들어간 프로세스는 다음번 임계 구역에 들어가려고 할 때 제한을 두어야 함
• 임계 구역의 동시 접근을 해결하기 위한 방법
  • 세마포어(Semaphore)
  • 락(Lock)
  • 모니터(Monitor)

세마포어 접근 함수 - wait(), signal()

wait과 signal을 통해 구현된다

(P 연산, V 연산이라는 말도 존재하는데, 여기에서 P,V란 wait과 signal이란 네덜란드에서 나온 것으로 의미는 동일하다.)

•  wait()
  • 동작 방식
    • 사용 가능한 공유 자원이 없다면 기다림
    • 사용 가능한 공유 자원이 있다면 세마포어 변수를 -1 처리한 후 사용
  • 임계 구역에 진입하기 전에 수행 (프로세스 진입 여부를 자원의 개수(S)를 통해 결정함)
• signal()
  • 동작 방식
    • 공유 자원을 모두 사용한 후에 세마포어 변수를 +1 처리함
    • 공유 자원 사용을 완료했다는 신호를 보냄
  • 임계 구역에서 나올 때 수행 ( 자원 반납 알림, 대기 중인 프로세스를 깨우는 신호)
  • UNIX의 signal 호출과는 다르다

// Shared Data
semaphore mutex; // 세마포어 변수 mutex의 초기값은 자원의 갯수를 의미.

// Process P
do {
	wait(mutex);
    	/* critical section */
        
	signal(mutex);
    	/* remainder section */	
} while (1);

• wait()과 signal()구현

// fun wait()
fun wait(S) {
	while(S <= 0);
    S--;
}

// fun signal()
fun signal(S) {
	S++;
}

위 방식의 문제점

• Busy-wait (Spin-lock) 현상이 여전히 존재한다
• Block & Wake-Up (Sleep Lock)방식으로 해결가능
  = 자원이 없을 때, Block 됐다가, 자원이 생기면 깨어남

Block / Wake-Up

Semaphore를 다음과 같이 정의했을 때

typedef struct
{
	int value;		// semaphore
	struct process *L;		// process wait queue
} Semaphores

Block과 Wake-Up을 다음과 같이 가정

• Block
  • 커널은 Block을 호출한 프로세스를 Suspend(지연)시킴
  • 이 프로세스의 PCB를 Semaphore에 대한 wait queue에 넣음
• Wakeup(P)
  • Block된 프로세스 P를 WakeUp 시킴
  • 이 프로세스의 PCB를 Ready queue로 옮김
  •  

• block/wakeup 버전의 wait(), signal()

P(S) {

	S.value--;		// Critical Section 들어갈 준비
	if(S.value < 0) {	// 음수면 못 들어감, Block 상태
		add this process to S.L;
        block();
	}
}

signal(S) {
	if(S.value <= 0) {		// 자원을 내놓았는데도
    	remove a process P from S.L;	// 자원이 0 이하라는 것은, 다른 누군가 (프로세스)가 잠들어있는 놈들이 존재한다는 것
        wakeup(P);
    }
}

여기서 음수라는 것은 누군가 자원을 쓰기 위해 기다리고 있다는 의미

 

Block / Wake-Up 과 Busy-wait의 장단점에 따른 적용 기준

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

세마포어의 두 가지 종류

1. 계수형 세마포어 (counting semaphore)

0과 1의 값을 가지는 이진형 세마포어(binary semaphore)와 달리, 풀에 있는 자원의 수와 같은 값으로 초기화 되는 동기화 기법

• 동작 메커니즘
  1. 세마포어는 Pool 자원 수와 같은 값으로 초기화
  2. P 호출이 발생할 때 마다 세마포어 1씩 감소, Pool 자원이 추가 할당되어 스레드에서 사용 표시
  3. V 호출은 세마포어 1씩 증가시켜 스레드가 자원을 Pool로 반납, 자원을 다른 스레드에 할당 가능 표시
  4. 세마포어가 0까지 줄어들었을 때 스레드가 P 호출 시 스레드는 V 통해 자원을 Pool로 반납 시까지 대기

계수형 세마포어 동작 개념도

 

• 구성 요소

구분	구성요소	세부 내용
계수범위	음수	세마포어에 정확한 -N개의 스레드 큐가 존재
	0	대기중인 스레드가 없으며, wait 연산은 호출 스레드를 큐에 추가
	양수	대기중인 스레드가 없으며, wait 연산은 호출 스레드를 큐에 추가 안함
연산자	wait()	세마포어 카운터 감소, 결과로 음수가 되고 호출 스레드는 큐에 삽입
	signal()	세마포어 카운터 증가, 결과로 양수가 되고 대기 중 스레드는 큐에서 제거

 

2. 바이너리 세마포어 (Binary Semaphore)

이진 세마포어의 값은 0과 1사이의 값만 가능하며 뮤텍스 락과 유사하게 동작함

• 동작 메커니즘
  • 상호 배제를 위해 신호 전달 메커니즘을 사용해서 잠금을 구현
  • 세마포어가 0이면 잠겨있고 1이면 잠금이 해제되어있는 것을 의미

세마포어 동기화 기법 비교

구분	이진형세마포어	계수형세마포어	뮤텍스
Internal States	2	N	2
User from ISRs	Yes	Yes	No
Ownership	No	No	Yes
Priority Inheritance	No	No	Yes
Initialization	없을 수도 있음	Counter >= 0	항상 가지지 않음
Queue 구성	FIFO or 우선순위	FIFO or 우선순위	우선순위

 

 

 

 

 

Reference

---

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

[OS] 프로세스 동기화(2)

http://blog.skby.net/%EA%B3%84%EC%88%98%ED%98%95-%EC%84%B8%EB%A7%88%ED%8F%AC%EC%96%B4-counting-semaphore/

계수형 세마포어 (Counting Semaphore) > 도리의 디지털라이프