[OSTEP 운영체제 정리] - semaphore

 

세마포어란?

🌼 동기화 기법 🌼
세마포어는 락과 컨디션 변수로 모두 사용할 수 있다. 정수값을 갖는 객체로서 두 개의 루틴으로 조작가능(초기화 포함은 3개)
세마포어는 초기값에 의해 동작이 결정된다. ➡️ 사용하기 전에 제일 먼저 값을 초기화 해야함

 

POSIX semaphores

- int sem_init(sem_t *s, int pshared, unsigned int value)

  두번째 인자는 모든 예제에서 0이다. ➡️ 이 값은 같은 프로세스 내의 쓰레드 간에 세마포어를 공유한다는 것을 의미

  0이 아니라면 세마포어는 프로세스 간에 공유되며, 공유 메모리 영역에 위치해야 한다.

- int sem_wait(sem_t *s)

  세마포어 값이 1이상이면 함수는 즉시 리턴, 아니면 값이 1이상이 될 때까지 호출자를 대기시킨다.

  세마포어 s의 값을 1 감소

  세마포어 s의 값이 음수가 되면 대기

  ‼️헷갈린다. ( 1보다 클경우 값만 줄이고, 음수일 경우 대기 상태 ㄱ ㄱ) 다수의 쓰레드들이 호출 가능하기에,
  대기큐에는 다수의 쓰레드 존. 재할 수 있음 대기하는 방법 : 회전 or 재우기

- int sem_post(sem_t *s)

  세마포어 s의 값을 1 증가

  대기 중인 스레드가 하나 이상 있으면, 그 중 하나를 깨운다.

 

✅ 세마포어가 음수라면, 그 값은 현재 대기 중인 쓰레드의 개수와 같다.

Binary Semaphores : Lock

세마포어 적용 to Lock

세마포어를 락으로 쓸 수 있다. 락은 두개의 상태만 존재하므로 이진 세마포어라고 한다.

sem_t m;
sem_init(&m, 0, 1); // 세마포어를 1로 초기화
sem_wait(&m);
// 임계영역 부분은 여기에 배치
sem_post(&m);

핵심은 세마포어의 초기 값 ⇒ 1로 초기화sem_wait() sem_post() 쌍으로 임계영억 부분을 둘러쌈

컨디션 변수로서의 세마포어

sem_t s;

void * child(void *arg) {
	printf("child\\n");
	sem_post(&s); // 시그널 전달: 자식의 동작이 끝남
	return NULL;
}

int main(int argc, char *argv[]) {
	pthread_t c;
	sem_init(&s, 0, X); // X의 값은 무엇이 되어야 할까?
	printf("parent: begin\\n");
	pthread_create(&c, NULL, child, NULL);
	sem_wait(&s); // 자식을 여기서 대기
	printf("parent: end\\n");
	return 0;
}

부모 프로세스는 자식 프로세스 생성 후 sem_wait() 를 호출하여 자식의 종료를 대기한다. 자식은 sem_post() 를 호출하여 종료되었음을 알린다.

세마포어 값을 무엇으로 초기화 할까❓✅ 정답 : 0

 

두가지 상황이 발생할 수 있다. ( 사례1, 사례2 )

사례 1 : 자식 프로세스 생성후, 아직 자식 프로세스가 실행을 시작하지 않는 경우

  자식이 sem_post() 를 호출하기 전에 부모가 sem_wait() 를 호출할 것이다. 부모 프로세스는 자식이 실행될 때까지 대기해야한다.

  이를 위해서 wait() 호출 전에 세마포어 값이 0보다 같거나 작아야한다. 때문에 0이 초기 값이 되어야 한다.
  부모가 실행되면 세마포어 값을 감소시키고(-1됨) 대기한다. 자식이 실행되었을 때 sem_post() 를 호출하여
  세마포어의 값을 0으로 증가시킨 후 부모를 깨운다.

  부모가 sem_wait() 에서 리턴을 하여 프로그램을 종료 시킨다.

사례2 :부모 프로세스가 sem_wait()를 호출하기 전에 자식 프로세스의 실행이 종료된 경우

  이 경우, 자식이 먼저 sem_post() 를 호출하여 세마포어의 값을 0 → 1로 증가시킨다. 부모가 실행할 수 있는 상황이 되면 sem_wait() 를 호출한다.

  세마포어 값이 1인 것을 발견할 것이다. 부모는 세마포어 값을 0으로 감소시키고 sem_wait() 에서 대기 없이 리턴한다.

 

‼️ 두 사례 모두 의도한 결과를 만든다

Producer/Consumer Problem

int buffer[MAX]; // bounded buffer
int fill = 0;
int use = 0;

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

int get() {
	int tmp = buffer[use]; //g1
	use = (use + 1) % MAX; //g2
	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이 가득 참
	// ...
}

생산자, 소비자 쓰레드 각 하나씩, CPU도 하나 🤩 소비자가 먼저 실행했다고 가정, C1 에 도달

 

  empty = MAX / full = 0 초기화 wait()를 통해 full이 -1 ⇒ 생산자 대기상태

  그후 생산자 쓰레드 실행(P1) , wait호출 empty = 1이어서, 감소시키고(0) 버퍼에 값을 넣음

  생산자가 post를 실행하여 full 값을 증가시 킨다(0), 후에 생산자 쓰레드 깨우기(준비상태 ㄱ)

 

MAX값이 1보다 크고(MAX=10), 생산자와 소비자 쓰레드가 여러개 있다고 가정 ⇒ Race Condition 발생

두생산자가 put()을 거의 동시에 호출했다고 하면 처음 값이 다시 새로운 값으로 대체될 수 있다….

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

void *consumer(void *arg) {
	int i;
	for (i = 0; i < loops; i++) {
		sem_wait(&mutex); //c0
		sem_wait(&full);
		int tmp = get();
		sem_post(&empty);
		sem_post(&mutex); //c4
	}
}

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

이진 세마포어와 락을 추가 ‼️ 
하지만 이래도 동작안돼 ,,, 왜냐 DeadLock 즉 교착 상태 발생

 

생산자 소비자 쓰레드 하나씩 있다 가정
소비자가 먼저 실행, c0 획득후 c1 호출 BUT 아직 데이터가 없기 때문에 소비자는 대기해야한다.

 

⇒ ?? 락을 난 아직 가지고 있는데?, 소비자가 계속 락을 가진다.
이상태로 생산자를 호출하게 되면 wait 실행

 

이미 소비자가 mutex를 갖고 있으면서 다른 full 시그널 발생되길 기다린다.

그런데 시그널을 발생시킬 생산자가 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;
	for (i = 0; i < loops; i++) {
		sem_wait(&full);
		**sem_wait(&mutex);**
		int tmp = get();
		**sem_post(&mutex);**
		sem_post(&empty);
	}
}

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

Reader-Writer Locks

삽입 연산이 없다는 보장만 된다면 다수의 검색 작업을 동시에 수행할 수 있다. 이를 위해 만들어진 락이다.

Reader : rwlock_acquire_readlock() /  rwlock_release_readlock()

Writer : rwlock_acquire_writelock() /  rwlock_release_writelock()

typedef struct _rwlock_t {
	sem_t lock; // 이진 세마포어(기본 락)
	sem_t writelock; // 하나의 쓰기 또는 다수의 읽기 락을 위한 락
	int readers; // 임계 영역 내에 읽기를 수행 중인 reader의 수
} rwlock_t;

void rwlock_init(rwlock_t *rw) {
	rw->readers = 0;
	sem_init(&rw->lock, 0, 1);
	sem_init(&rw->writelock, 0, 1);
}
void rwlock_acquire_readlock(rwlock_t *rw) {
	sem_wait(&rw->lock);
	rw->readers++;
	if (rw->readers == 1)
		sem_wait(&rw->writelock); // 읽기용 락이 writelock을 획득
	sem_post(&rw->lock);
}
void rwlock_release_readlock(rwlock_t *rw) {
	sem_wait(&rw->lock);
	rw->readers--;
	if (rw->readers == 0)
		sem_post(&rw->writelock); // 마지막으로 읽기용 락이 writelock 해제
	sem_post(&rw->lock);
}

void rwlock_acquire_writelock(rwlock_t *rw) {
	sem_wait(&rw->writelock);
}

void rwlock_release_writelock(rwlock_t *rw) {
	sem_post(&rw->writelock);
}

의도대로 동작은 되지만 단점이 있다. ⇒ 공정성 문제

상대적으로 쓰기 쓰레드가 불리하다. 쓰기 쓰레드에게 기하 현상이 발생하기 쉽다.

해결 방법: 쓰기 쓰레드가 대기 중일떄는 읽기 쓰레드가 락을 획득하지 못하도록 한다.

How To Implement Semaphores

typedef struct __Sem_t {
int value;
pthread_cond_t cond;
pthread_mutex_t lock;
} Sem_t;
// only one thread can call this
void Sem_init(Sem_t *s, int value) {
s->value = value;
Cond_init(&s->cond);
Mutex_init(&s->lock);
}

void Sem_wait(Sem_t *s) {
Mutex_lock(&s->lock);
while (s->value <= 0)
Cond_wait(&s->cond, &s->lock);
s->value--;
Mutex_unlock(&s->lock);
}
void Sem_post(Sem_t *s) {
Mutex_lock(&s->lock);
s->value++;
Cond_signal(&s->cond);
Mutex_unlock(&s->lock);
}

The Dining Philosophers

5명의 철학자와 5개의 포크가 번갈아 놓여있다 가정

철학자 상태는 두가지

• 식사할 때 : 자신의 왼쪽과 오른쪽에 있는 포크를 들어야 식사 가능
• 생각할 때 : 포크가 필요 없다.

이 포크를 잡기 위한 경쟁과 그에 따른 동기화 문제가 병행 프로그래밍에서 다루려는 문제이다.

 

 

//철학자의 동작을 나타낸다.
while (1) {
	think();
	getforks();
	eat();
	putforks();
}

// helper functions
int left(int p) { return p; }
int right(int p) {
return (p + 1) % 5;
}

주요 쟁점: getfork() 와 putfork()의 루틴을 작성하되 교착 상태의 발생을 방지,
어떤 철학자도 굶주리면 안되고, 병행성이 높아야한다. ( == 가능한 많은 철학자가 동시에 식사할 수 있어야한다.)

 

left : 철학자 p가 자신의 왼쪽의 포크를 잡는다.

right : 철학자 p가 자신의 오른쪽의 포크를 잡는다.

 

문제를 해결하기 위해 세마포어가 필요하다.

각 포크마다 한개씩 , 총 5개가 있고 sem_t fork[5]로 정의한다.

락으로 사용하니, 세마포어는 1로 초기화, 철학자는 자신의 순번(p)를 알고 있다고 가정

void getforks() {
	sem_wait(forks[left(p)]);
	sem_wait(forks[right(p)]);
}

void putforks() {
	sem_post(forks[left(p)]);
	sem_post(forks[right(p)]);
} 

포크가 필요할 때 단순히 락을 획득하는 구조, 왼쪽획득⇒ 오른쪽 획득 식사 끝나면 putfork()를 통해 포크를 놓는다.

 

*문제점 : 교착상태*

왼쪽 포크를 잡을 때, 다른 철학자가 오른쪽 포크를 잡았다면,
각 철학자는 하나의 포크만 들고서 다른 하나의 포크를 잡게 되기를 평생 기다린다.

⇒ Deadlock

A Solution: Breaking The Dependency, 의존성 제거

최소한 하나의 철학자가 다른 순서로 포크를 집도록하면 된다. 여기선 철학자 4만 포크를 다른 순서로 획득한다.

void getforks() {
	if (p == 4) {
		sem_wait(forks[right(p)]);
		sem_wait(forks[left(p)]);
	} else {
		sem_wait(forks[left(p)]);
		sem_wait(forks[right(p)]);
	}
} 

세마포어 구현

typedef struct __Sem_t {
	int value;
	pthread_cond_t cond;
	pthread_mutex_t lock;
} Sem_t;

// 오직 하나의 쓰레드만 이 문장을 호출할 수 있다.
void Sem_init(Sem_t *s, int value) {
	s->value = value;
	Cond_init(&s->cond);
	Mutex_init(&s->lock);
}

void Sem_wait(Sem_t *s) {
	Mutex_lock(&s->lock);
	while (s->value <= 0)
			Cond_wait(&s->cond, &s->lock);
	s->value--;
	Mutex_unlock(&s->lock);
}

void Sem_post(Sem_t *s) {
	Mutex_lock(&s->lock);
	s->value++;
	Cond_signal(&s->cond);
	Mutex_unlock(&s->lock);
}

 

---

[출처]
https://github.com/remzi-arpacidusseau/ostep-translations/blob/master/korean/README.md

ostep-translations/korean/README.md at master · remzi-arpacidusseau/ostep-translations

 

해당 책을 기반으로 정리하였습니다.