[OS] Semaphore

운영체제(OS)

[OS] Semaphore

서노리 2022. 12. 4. 21:09

세마포어 (Semaphore) - 범용 세마포어

세마포어는 공유된 자원의 데이터 혹은 임계영역 등에 여러 프로세스 혹은 쓰레드가 접근하는 것을 막아주는 기법이다.

기본적인 작동 원리는 한 프로세스가 특정 신호를 수신할 때까지 wait 하도록 강제하는 것으로 다음과 같은 연산들에 의해 동작한다.

1. semInit

- 세마포어 변수를 음이 아닌 값으로 초기화를 수행한다.

2. semWait

- 세마포어 변수 값을 감소시킨다. 만약 값이 음수가 되면 호출한 프로세스는 블록된다. 그 외에는 정상적으로 프로세스를 수행한다.

3. semSignal

- 세마포어 변수 값을 증가시킨다. 만약 값이 양수가 아니면 semWait에 의해 블록된 프로세스들 중 하나를 깨운다.

typedef struct{
	int count;
	queue waitQueue;
} semaphore;

void semInit(semaphore s, int n)
{
	s.count = n;
}

void semWait(semaphore s)
{
	s.count--;
	if(s.count < 0){
		//요청한 프로세스를 s.waitQueue에 push
		//요청한 프로세스의 상태를 block으로 변경
	}
}

void semSignal(semaphore s)
{
	s.count++;
	if(s.count <= 0){
		//s.waitQueue에서 프로세스 1개를 pop
		//pop한 프로세스의 상태를 runnable로 변경 후 OS의 readyQueue에 push
	}
}

※ count 변수의 값이 음수인 경우, 그 절대값은 대기 큐에 있는 프로세스의 개수를 의미한다.

이진 세마포어 (Binary Semaphore 또는 Mutex)

뮤텍스 (Mutex)라고 흔히 불리는 이진 세마포어는 0과 1의 값만 갖는 세마포어를 뜻하며 다음과 같은 연산에 의해 동작한다.

1. semInitB

- 세마포어 변수를 0또는 1로 초기화한다.

2. semWaitB

- 세마포어 변수를 확인해 0일 경우 호출한 프로세스를 블록시키고, 1일 경우 값을 0으로 변경시킨 뒤 프로세스를 계속 수행한다.

3. semSignalB

- 블록된 프로세스가 있는지 확인하고, 있을 경우 해당 프로세스 중 하나를 깨우고, 없을 경우 세마포어 변수 값을 1로 설정한다.

typedef struct{
	enum {zero, one} value;
	queue waitQueue;
}binary_semaphore;

void semInitB(binary_semaphore s, int n)
{
	s.value = n;
}

void semWaitB(binary_semaphore s)
{
	if(s.value == 1)
		s.value = 0;
	else{
		//요청한 프로세스를 s.waitQueue에 push
		//요청한 프로세스의 상태를 block으로 변경
	}
}

void semSignalB(binary_semaphore s)
{
	if(s.waitQueue.empty())
		s.value = 1;
	else{
		//s.waitQueue에서 프로세스 1개를 pop
		//pop한 프로세스의 상태를 runnable로 변경 후 OS의 readyQueue에 push
	}
}

※ 강성 세마포어 (Strong Semaphore)

대기 큐에 연결된 프로세스들이 여러 개인 경우 어떤 프로세스를 깨울 것인지에 대한 문제에서 FIFO 방식을 사용하는 세마포어를 강성 세마포어라고 한다. 반면 방식을 특별히 명시하고 있지 않은 세마포어를 약성 세마포어라고 한다. 하지만 실제로 대부분의 OS는 강성 세마포어를 사용하며 이는 기아 문제가 발생하지 않고 구현에도 편리하기 때문이다.

세마포어를 이용한 상호 배제 문제

상호 배제 문제란 동일한 자원에 접근하려는 n개의 프로세스의 병행성을 처리하는 문제이다.

다음은 범용 세마포어를 사용해 상호 배제 문제를 처리하는 pseudo code이다.

semaphore s;

void P(int i)
{
	while(1){
		semWait(s);
		//임계 영역
		semSignal(s);
		//임계 영역 이후
	}
}

void main() {
	semInit(s, 1);
    	// P(1), P(2) ... P(n) 수행
}

semInit에서 세마포어 값 s를 1(자원의 개수)로 초기화한다.
최초로 semWait을 수행하는 프로세스가 s 값을 0으로 바꾸고 임계 영역에 들어간다.
임계 영역에 들어가고자 하는 다른 프로세스들은 블록되고, s 값을 1씩 감소시킨다.
임계 영역에 있던 프로세스가 semSignal을 호출하며 빠져나오면, s 값이 1 증가하고 블록되어 있던 프로세스들 중 하나가 대기 큐에서 나와 준비 큐로 이동한다.
프로세스가 운영체제에 의해 스케줄되면 임계 영역에 들어가게 된다.

세마포어를 이용한 생산자 소비자 문제

생산자 소비자 문제는 데이터를 만드는 생산자 프로세스가 자원을 생성해 공용 버퍼에 저장하고, 소비자 프로세스가 공용 버퍼에서 자원을 한 개씩 소비하는 상황의 병행성을 처리하는 문제이다. 조건으로는 공용 버퍼에는 동시에 단 하나의 프로세스만 접근할 수 있고, 공유 버퍼의 크기는 무한한 선형 배열로 구성되어 있다고 가정한다.

다음은 이진 세마포어를 이용하여 생산자 소비자 문제를 처리하는 pseudo code이다.

int n;                     //in-out의 값 즉, 현재 자원의 개수
binary_semaphore s;        //buffer의 접근을 제어하는 mutex
binary_semaphore delay;    //buffer가 비었는지를 확인해 소비를 제어하는 mutex

void producer(void)
{
	while(1){
		val = produce();       //자원 생산
		semWaitB(s);
		/*
			                     critical section start
		*/
		append(val);           //buffer에 push
		n++;
		if (n == 1)            //buffer.empty()==false가 된 상황
			semSignalB(delay);   //consumer 중 1개 block 해제
		/*
		                       critical section end
		*/
		semSignalB(s);
		}
	}
}

void consumer(void)
{
	//consumer가 producer보다 먼저 실행되는 상황(buffer.empty()==true)를 막기 위해 block
	semWaitB(delay);
	while(1){
		semWaitB(s);
		/*
		                     critical section start
		*/
		val = take();        //buffer에서 pop
		n--;
		/*
			                	critical section end
		*/
		semSignalB(s);
		consume(val);       //자원 소비
		if(n == 0)          //buffer.empty()==true가 된 상황
			semWaitB(delay); //block
	}
}

void main() {
	n = 0;
    semInit(s, 1);
    semInit(delay, 0);
    // producer, consumer 시작
}

이진 세마포어를 사용하여 생산자 소비자 문제를 처리하는 코드는 문제가 있다. while 루프가 한 번 도는 사이에 스케줄링이 발생하지 않을 보장이 없기 때문이다. 만약 consumer에서 semSignalB와 if(n==0) 사이에 스케줄링이 발생하여 producer가 실행될 경우 n은 0에서 1로 변경될 것이고, 다시 돌아왔을 때 if(n==0)을 만족하지 못하여 semWaitB가 실행되지 않을 것이다. 이를 다음과 같은 방법으로 해결할 수 있다.

sol 1) 보조 변수 사용

void consumer(void)
{
	int m;
	//consumer가 producer보다 먼저 실행되는 상황(buffer.empty()==true)를 막기 위해 block
	semWaitB(delay);
	while(1){
		semWaitB(s);
		/*
		                     critical section start
		*/
		val = take();        //buffer에서 pop
		n--;
		m = n;
		/*
			                	critical section end
		*/
		semSignalB(s);
		consume(val);       //자원 소비
		if(m == 0)         //buffer.empty()==true가 된 상황
			semWaitB(delay); //block
	}
}

n의 값이 변경되는 것을 막기 위해 임계 영역 내에서 보조 변수 m에 현재 n의 값을 저장하는 해결책이다.

sol 2) 범용 세마포어 사용

이진 세마포어가 아닌 범용 세마포어를 사용하면 애초에 해당 문제가 발생하지 않는다.

semaphore s;               //buffer의 접근을 제어하는 semaphore
semaphore n;               //buffer에 들어있는 자원의 개수를 제어하는 semaphore

void producer(void)
{
	while(1){
		val = produce();       //자원 생산
		semWait(s);
		/*
			                     critical section start
		*/
		append(val);           //buffer에 push
		semSignal(n);          //consumer 중 1개 block 해제
		/*
		                       critical section end
		*/
		semSignal(s);
		}
	}
}

void consumer(void)
{
	while(1){
		semWait(n);          //buffer.empty()==true일 때 실행되는 것을 방지하기 위해 block
		semWait(s);
		/*
		                     critical section start
		*/
		val = take();        //buffer에서 pop
		/*
			                	critical section end
		*/
		semSignal(s);
		consume(val);       //자원 소비
	}
}

int main(void(
{
	semInit(s, 1);
	semInit(n, 0);
	// producer, consumer 시작
}

변수 n과 delay를 하나의 범용 세마포어 n으로 사용한다. n의 값에 따라 delay 를 wait 또는 signal 하지 않고 무조건적으로 producer에서는 semSignal(n), consumer에서는 semWait(n)을 하게된다. n은 버퍼에 들어가 있는 자원의 개수를 의미함과 동시에 프로세스의 실행 순서를 보장하는 역할을 하게 된다. consumer들은 매 번 실행될 때마다 semWait(n)을 하게 된다. 따라서 producer에서 semSignal(n)과 semSignal(s)가 서로 순서가 바뀌어 semSignal(n)이 임계 영역 밖에서 수행된다고 하더라도 동일하게 실행된다. 왜냐하면 어차피 consumer들은 semWait(n)을 통해 block된 상태이기에 semSignal(n)이 호출되어야 수행될 수 있기 때문이다.

유한 버퍼를 이용한 생산자 소비자 문제

위의 모든 예제들은 무한한 크기의 버퍼를 사용한다는 가정에서 이루어졌다. 하지만 이는 실제로 불가능하기 때문에 대개 순환 큐로 구현된 버퍼를 사용하게 된다.

semaphore s;               //buffer의 접근을 제어하는 semaphore
semaphore n;               //buffer에 들어있는 자원의 개수를 제어하는 semaphore
semaphore b;               //유한 buffer를 관리하는 semaphore

void producer(void)
{
	int val;
	while(1){
		val = produce();       //자원 생산
		semWait(b);            //buffer.full()==true일 경우 block
		semWait(s);
		/*
			                     critical section start
		*/
		append(val);           //buffer에 push
		semSignal(n);          //consumer 중 1개 block 해제
		/*
		                       critical section end
		*/
		semSignal(s);
		}
	}
}

void consumer(void)
{
	int val;
	while(1){
		semWait(n);          //buffer.empty()==true일 때 실행되는 것을 방지하기 위해 block
		semWait(s);
		/*
		                     critical section start
		*/
		val = take();        //buffer에서 pop
		/*
			                	critical section end
		*/
		semSignal(s);
		semSignal(b);       //buffer.full()==false이므로 block된 producer 중 1개 unblock
		consume(val);       //자원 소비
	}
}

void main() {
	semInit(s, 1);
	semInit(n, 0);
	semInit(b, BUFFER_SIZE);
    // producer, consumer 시작
}

저작자표시

'운영체제(OS)' 카테고리의 다른 글

[OS] pthread (0)	2022.12.06
[OS] Deadlock (0)	2022.12.05
[OS] Lock (0)	2022.10.27
[OS] Concurrency (0)	2022.10.27
[OS] Page Placement Policy (페이지 배치 전략) (0)	2022.10.26

현재글[OS] Semaphore

파이썬 라이브러리, 다이나믹 프로그래밍, React.js, 구현, 탐색, 파이썬 문법, bfs, PL, 운영체제, 문자열, 머신러닝, OS, 그리디, c++, js, 프로그래밍언어, 알고리즘 이론, CV, 파일처리, 지능형시스템,

일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

선호:하다

[OS] Semaphore

세마포어 (Semaphore) - 범용 세마포어

이진 세마포어 (Binary Semaphore 또는 Mutex)

세마포어를 이용한 상호 배제 문제

세마포어를 이용한 생산자 소비자 문제

유한 버퍼를 이용한 생산자 소비자 문제

'운영체제(OS)' 카테고리의 다른 글

'운영체제(OS)'의 다른글

티스토리툴바

[OS] Semaphore

세마포어 (Semaphore) - 범용 세마포어

이진 세마포어 (Binary Semaphore 또는 Mutex)

세마포어를 이용한 상호 배제 문제

세마포어를 이용한 생산자 소비자 문제

유한 버퍼를 이용한 생산자 소비자 문제

'운영체제(OS)' 카테고리의 다른 글

'운영체제(OS)'의 다른글

관련글

티스토리툴바