[병행성 #4] 세마포어

 

다양한 범주의 병행성 문제 해결을 위해서는 락과 조건 변수가 모두 필요하다. Edsger Dijkstra는 세마포어 라는 다양한 동기화 관련 문제를 해결하는 기법을 탄생하였다. 세마포어는 락과 컨디션 변수로 모두 사용할 수 있다.

세마포어 사용법

• 세마포어는 정수 값을 갖는 객체로서 두 개의 루틴으로 조작할 수 있다.
• sem_wait() / sem_post() 이다.
• 세마포어는 초기값에 의해 동작이 결정되기 때문에 값을 초기화 해야한다.

#include <semaphore.h<
sem_t s;
sem_init(&s, 0, 1);

• 세마포어 s를 선언 후, 3번째 인자로 1을 전달하여 세마포어의 값을 1로 초기화
• sem_init()의 두번 째 인자는 0이다. → 같은 프로세스 내의 쓰레드 간에 세마포어를 공유한다는 뜻
• 두번 째 인자에 다른 값을 넣어서 다른 프로세스 간에 동기화또한 제공 가능
• 초기화 된 후에 sem_wait()/sem_post() 라는 함수를 통해 세마포어를 다룰 수 있음.

int sem_wait(sem_t *s) {
 // decrement the value of semaphore s by one;
 // wait if value of semaphore s is negative;
 // 세마포어 s의 값을 1씩 줄입니다;
 // 세마포어 s의 값이 음수일 때 기다립니다;
}

int sem_post(sem_t *s) {
  // increment the value of semaphore s by one;
  // if there are one or more threads waiting, wake one;
  // 세마포어 s의 값을 1씩 증가시킵니다;
  // 대기 중인 스레드가 하나 이상 있는 경우, 하나를 깨웁니다;
}

• sem_wait() 함수는 세마포어의 값이 1이상 이면 즉시 리턴, 아니면 세마포어 값이 1이상 될 때 까지 호출자를 대기 시킨다.(sleep or spin)
• sem_post() 는 세마포어 값을 증가시키고 대기 중인 쓰레드 중 하나를 깨운다.
• 세마포어가 음수라면 그 값은 현재 대기 중인 쓰레드의 개수와 같다.

이진 세마포어(락)

• 세마포어로 락을 만들어보자.

sem_t m;
sem_init(&m, 0, X); // X로 세마포어를 초기화 하기, 이떄 X가 가져야할 값은?
sem_wait(&m);
// 임계 영역 부분은 여기에 배치
sem_post(&m);

• 세마포어의 초기 값은 1이 되어야 한다
• T0이 sem_wait()을 호출한다면, 세마 포어 값을 1 감소 시켜 0으로 만든다.
• 세마포어 값이 음수일 경우에만 대기 하므로 T0은 임계영역에 진입한다.
• T0이 락을 보유하고 있을 때 T1이 sem_wait()으로 임계 영역을 진입 시도 할 경우, 세마포어의 값이 -1이므로 대기한다.
• T0이 sem_post를 하면서 세마포어의 값이 0으로 되고, T1을 깨운다.

컨디션 변수로서 세마포어

컨디션 변수란 ? 스레드들이 어떤 조건이 만족될 때까지 대기하고, 조건이 바뀌면 깨어나게 해 주는 추상화된 동기화 객체

/*
다음과 같은 결과를 내기 위한 X는 ?
parent: begin
child
parent: end
*/

sem_t s;
void *child(void * arg) {
	printf("child\\n");
	sem_post(&s);
	return NULL;
}

int main(int argc, char *argv[]) {
	sem_init(&s, 0, X); // X의 값은 ??
	printf("parent: begin\\n");
	pthread_t c;
	Pthread_create(c, NULL, child, NULL);
	sem_wait(&s); // 대기
	printf("parent: end\\n");
	return 0;
}

• 세마포어의 초기 값은 0이 되어야 한다.
• 시나리오 1 (자식 프로세스 생성 후 자식 프로세스가 실행 시작 하지 않은 경우)
  • 부모 프로세스는 wait으로 인해 세마포어 값이 -1이 되고 대기한다.
  • 이후 자식 프로세스가 post를 통해 0으로 증가 시킨 후 부모를 깨운다.
• 시나리오 2 (부모 프로세스가 대기하기 전에 자식 프로세스가 실행이 종료된 경우)
  • 자식이 먼저 sem_post()를 통해 세마포어 값을 1로 증가시킨다.
  • 부모는 세마포어 값을 0으로 감소 시키고, 대기 없이 리턴한다.

생산자/소비자 문제

int buffer[MAX];
int full = 0;
int use = 0;

void put(int value) {
	buffer[fill] = value;
	fill = (fill + 1) % MAX
}

int get() {
	int tmp = buffer[use];
	use = (use + 1) % MAX;
	return tmp;
}

sem_t empty;
sem_t full;

void *producer(void *arg) {
	int i;
	for (i = 0; i< loops; i++) {
		sem_wait(&empty);  // P1
		put(i);            // P2
		sem_post(&full);   // P3
	}
}

void *consumer(void *arg) {
	int i, tmp = 0;
	while (tmp != -1) {
		sem_wait(&full);   // C1
		tmp = get();       // C2
		sem_post(&empty);  // C3
		printf("%d\\n", tmp);
	}
}

int main(int argc, char *argv[]) {
  // ...
  sem_init(&empty, 0, MAX); // MAX 버퍼는 비어 있는 상태로 시작
  sem_init(&full, 0, 0);     // ... 0이 가득 참
  // ...
}

버퍼 최대 크기가 1, 생산자와 소비자 쓰레드가 각 하나씩 있는 경우

• empty 와 full 이라는 두개의 세마포어를 사용하여, 버퍼 공간이 비었는지 채워졌는지를 표시한다.
• 생산자는 버퍼가 비워져서 데이터를 넣을 수 있기를 기다리고 마찬가지로 소비자는 데이터를 꺼내기 위해 버퍼가 채워지기를 기다린다.
• 소비자가 먼저 실행했다고 가정, C1라인의 sem_wait(&full)을 호출한다.
  • 변수 full의 값은 0으로 초기화 되었기 때문에 해당 명령으로 인해 full의 값은 -1로 감소, 소비자는 대기한다.
• 생산자가 실행하여 P1라인의 sem_wait(&empty)을 호출한다.
  • empty는 1로 초기화되었기 때문에 0으로 감소 되고, 계속 실행한다.
  • P3 라인의 sem_post(&full)을 호출하여 세마포어의 full의 세마포어 값을 -1에서 0으로 변경하고 소비자 쓰레드를 깨운다.
• 생산자가 계속 실행한다면 반복문을 돌아 P1 라인을 다시 실행하게 된다. 이때 empty 세마포어의 값이 0이므로 대기 상태로 들어간다.
• 또 소비자 쓰레드가 실행되면 sem_wait(&full)로 인해 버퍼가 찼다는 것을 확인하고 데이터를 소비한다.

버퍼 최대 크기가 1보다 크고, 생산자와 소비자 쓰레드들이 여러개 있는 경우

• 경쟁 조건이 발생한다.
• 두 생성자 쓰레드가 put()을 거의 동시에 실행시킨다면,
• fill 카운터 변수가 1로 변경하기 전에 인터럽트가 걸려, 데이터가 사라질 수 있다.

상호 배제의 추가

버퍼를 채우고, 버퍼에 대한 인덱스를 증가시키는 동적은 임계 영역이기 때문에 세마포어로 락을 추가하자

sem_t empty;
sem_t full;
sem_t mutex;

void *producer(void *arg) {
	int i;
	for (i = 0; i< loops; i++) {
		sem_wait(&empty);
		sem_wait(&mutex);  
		put(i);            
		sem_post(&mutex);
		sem_post(&full);   
	}
}

void *consumer(void *arg) {
	int i, tmp = 0;
	while (tmp != -1) {
		sem_wait(&full);   
		sem_wait(&mutex);
		tmp = get();
		sem_post(&mutex);       
		sem_post(&empty);  
		printf("%d\\n", tmp);
	}
}

int main(int argc, char *argv[]) {
  // ...
  sem_init(&empty, 0, MAX); // MAX 버퍼는 비어 있는 상태로 시작
  sem_init(&full, 0, 0);     // ... 0이 가득 참
  sem_init(&mutex, 0, 1);      // 락이기 때문에 1로 초기화
  // ...
}

 

출처 : 운영체제 아주쉬운 세가지 이야기