[ OS ] Semaphores

 

Semaphores를 이용하면 lock과 conditon variable을 동시에 사용할 수 있다.

이런 Semaphores는 여러가지 용도로 사용할 수 있다.

 

 

int sem_init(sem_t *s, int pshared, unsigned int value)
// 가운데 인자에는 공유한는 프로세스개수, 마지막인자에는 초기값을 넣어 초기화하는 함수이다
int sem_wait(sem_t *s)  // s 를 1 감소시키고 s가 음수가 되면 재우는 함수
int sem_post(sem_t *s)  // s 를 1 증가시키고 큐에 자는애가 있으면 깨우는 함수


/*사용예시*/
sem_t m;
sem_init(&m, 0, 1); 
sem_wait(&m);
// critical section here
sem_post(&m);

 

 

1. Lock

 

스레드가 두개일 때 Semaphores가 동작하는 예시 이다.

 

이렇게 Semaphores는 Lock의 기능을 수행할 수 있다.

 

1. Ordering

다음 코드는 parent -> child -> parent :end 순서대로 출력하기 위한 코드이다.

Semaphores은 스레드들의 순서를 조정해줄 수 있다. 

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, 0); // what should X be?
	printf("parent: begin\n");
	pthread_create(&c, NULL, child, NULL);
	sem_wait(&s); 
	printf("parent: end\n");
	return 0;
}

실제로 위 코드가 실행될 수 있는 경우는 부모 스레드가 먼저 실행되는경우와 자식 스레드가 먼저 실행되는 경우 두가지가 있다. 하지만 Semaphores를 이용하여 두 경우 모두 원하는 순서대로 출력되도록 하였다.

 

두 케이스를 모두 확인해보겠다.

 

부모가 먼저 실행되었을 때

부모가 먼저 실행됐을 때를 보면 부모는parent를 출력 후 sem_wait()를 실행 시키고 함수는 s-- 를한다 s는 현재 0인 상태임으로 -1이 되게 되고 음수값을 갖게 되었으니 잠들게된다. 그러고 자식스레드가 실행되게 되는데 이는 child를 출력하고,  s++를 하고 잠든 부모를 깨운다. 깬 부모는 parent : end 를 출력하고 return 한다.

 

자식이 먼저 실행되었을 때

자식가 먼저 실행됐을 때를 보면 부모는 먼저 parent를 출력하고, 자식는 child 를 출력한 뒤 sem_post()를 실행 시키고 큐를 보지만 아무도 없어서 그냥 return 한다. 그러고 부모스레드가 sem_wait()를 실행하고 이는  s--를 한다. parent : end 를 출력하고 return 한다.

 

이렇게 어떤 경우가 있어도 원하는 순서대로 실행되도록 할 수 있다.

 

2. Producer/consumer problem

int buffer[MAX]; // bounded buffer
int fill = 0;
int use = 0;
sem_t empty, sem_t full;
// 몇개가 비었는지, 몇개가 찼는지

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

void *producer(void *arg) {
	int i;
	for (i = 0; i < loops; i++) {
		sem_wait(&empty);  // empty-- , 음수면 잠들기  
        sem_wait(&mutex);  //lock 역할도 필요함
		put(i);  // 큐에 하나 넣기
        sem_post(&mutex); 
		sem_post(&full);  // full++ , 잠들어있는 애 깨우기
	}
}
void *consumer(void *arg) {
	int i, tmp = 0;
	while (tmp != -1) {
		sem_wait(&full);   // full-- , 음수면 잠들기  
        sem_wait(&mutex); //lock 역할도 필요함
		tmp = get(); 
        sem_post(&mutex);
		sem_post(&empty);  // empty++ , 잠들어있는 애 깨우기
		printf("%d\n", tmp); 
	}
}


int main(int argc, char *argv[]) {
// ...
sem_init(&empty, 0, MAX); // MAX are empty
sem_init(&full, 0, 0); // 0 are full
// ...
}

 

3. Reader-writer lock

 

typedef struct _rwlock_t {
	// binary semaphore (basic lock)
	sem_t lock; // reader의 lock, 여러개가 접근하면 race condtion 생겨서
	// used to allow ONE writer or MANY readers
	sem_t writelock; // write의 lock
	int readers;  //현재 읽고 있는 스레드
} 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_writelock(rwlock_t *rw) {
	sem_wait(&rw->writelock);
}
void rwlock_release_writelock(rwlock_t *rw) {
	sem_post(&rw->writelock);
}

void rwlock_acquire_readlock(rwlock_t *rw) {
	sem_wait(&rw->lock);
	rw->readers++;  // 읽는 사람 증가
	if (rw->readers == 1)  
    	// 첫 열람자, 이후에 write가 들어오면 안됨, 한명이상 읽고있으면 write 잠구기
		sem_wait(&rw->writelock); // writelock이 0이었다면 잠들고 1이었다면 0으로 바꿈
	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);  
	sem_post(&rw->lock);
}

 

4. 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); // 0보다 작으면 잠듬
	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);
}