[시스템프로그래밍/Linux] 10. POSIX-semaphore

1. Semaphore

Semaphore는 1960년대 Dijkstra에 의해 설계된 시스템 콜입니다. 

mutex와 마찬가지로 멀티스레드(또는 멀티프로세스) 환경에서 critical section의 공유 자원에 접근제어를 위해 사용합니다. 

 

semaphore의 기본적인 특징은 다음과 같습니다. 

• mutual exclusion(상호 배제)을 위한 block/wakeup 알고리즘
• 프로세스가 critical section에 접근하지 못한다면, 프로세스는 block 상태가 됨(block : Semaphore queue에 해당 프로세스를 등록하고, 프로세스는 CPU에서 release됨)
• 프로세스가 critical section을 이용한 후 빠져나올 때, waiting queue에 있는 프로세스를 깨움
• CPU time의 소모가 없음 (wait queue에 block과 wait에 대한 동작을 지원)
• waiting queue가 필수적임

 

2. Counting Semaphore

Counting Semaphore은 critical section에 접근할 수 있는 프로세스의 개수를 n개로 제한합니다. 

 

class Semaphore{
private:
	int value;	//현재 사용가능한 Semaphore의 수
	PCB* queue;	//Semaphore를 사용하려고 하는 processes
};

Semaphore::Semaphore(n){
	value = n;	//critical section에 접근할 수 있는 프로세스의 개수 n개로 제한
}

Semaphore::wait(){
	//originally name: "P" operation
	value--;
	if(value>0){
		block the calling process;
		add it to the wait queue of this semaphore;
	}
}

Semaphore::signal(){
	//originally name: "V" operation
	value++;
	if(value<=0){
		remove the first process from the wait queue;
		add it to the scheduling queue;
	}
}

 

• wait() : value>=0 일 경우 바로 semaphore를 얻을 수 있음 -> critical section 접근 가능
• signal() : 받았던 semaphore을 반환하고 value값을 증가시킴. value<=0일 경우, wait queue에 기다리는 프로세스가 있다면 wait queue에 가장 첫 프로세스를 깨우고 scheduling 큐에 넘겨서 semaphore 얻어서 작업 실행

 

3. Binary Semaphore

Binary Semaphore은 n=1인 Counting semaphore 입니다. 

 

class Semaphore{
private:
	int value;
	PCB* queue;
};

Semaphore::Semaphore(1){
	value = 1;
}

Semaphore::wait(){
	//originally name: "P" operation
	if(value==1)
		value = 0;
	else {
		//block the calling process;
		//add it to the wait queue of this semaphore;
	}
}

Semaphore::signal(){
	//originally name: "V" operation-
	if(queue is not empty){
		//remove the first process from the wait queue;
		//add it to the scheduling queue;
	}
	else
		value = 1;
}

 

• wait()
  • value == 1 : 아무도 semaphore를 얻고 있지 않음 -> 자신이 value-- 하고 semaphore 값을 얻어 다음 작업을 수행
  • value == 0 : 다른 프로세스가 이미 semaphore 점유 -> 해당 프로세스 block
• signal() : waiting queue가 비어있지 않다면 큐의 가장 첫 번째 프로세스를 반환

 

4. Mutex Exclusion by Semaphore

Mutex Exclusion(상호배제)는 binary/counting semaphore를 이용합니다. 

 

binary semaphore는 mutex와 동일한 방식으로 동작합니다. (lock을 얻은 스레드 하나만 공유 자원 접근 가능)

Semaphore S(1);   //global variable for mutual exclusion, initialized with 1

스레드/프로세스가 critical section에 접근하려고 할 때 먼저 S.wait()을 이용해 semaphroe을 얻어야 합니다.

공유자원 사용 이후 S.signal()을 이용해 semaphore을 반환해 주면 wait queue에서 기다리고 있던 다른 스레드/프로세스가 semaphore을 얻을 수 있습니다. 

 

5. Resource Allocation by a Counting Semaphore

n개의 프로세스(스레드)가 동시에 semaphore을 얻어서 작업을 수행하는 경우, 즉 동시에 실행할 수 있는 resource가 여러개 있을 경우 사용합니다. 

Semaphore Printer(3);   //in case that the system has 3 identical printers

예를들어 3개의 Printer를 동시에 사용하려고 한다면 Semaphore의 개수를 3으로 지정하면 됩니다. 

 

6. Synchronization with a Semaphore

프로세스들 간에 동기화를 위한 목적으로 Semaphore를 사용할 수도 있습니다.

여기서 동기화란, 프로세스들 간에 작업을 수행할 때 동일하게 어떤 한 구간까지 모든 프로세스가 도달하도록 기다리고, 프로세스가 모두 도달하면 동시에 작업을 수행하여 프로그램의 흐름을 맞추게 하는 것입니다. 

Semaphore Sync(0);   //global ver. with the initial value of 0

이는 semaphore의 초기값을 0으로 설정해줌으써 동작합니다.

semaphore의 값이 0이면 초기에 아무도 semaphore을 얻을 수 없어 signal을 만나기 전까지 wait queue에서 기다리게 됩니다. 

예를 들어 P1이 P0보다 wait-point에 더 일찍 도착하게 wait할 경우 P0는 wait에서 block된 상태이므로 P0에서 signal이 올 때 까지 작업을 수행해 주다가 signal에 도착하면 P1 프로세스를 해제시켜줄 수 있습니다. 

따라서 P1의 wait 다음의 작업들은 P0 signal 전의 작업들보다 먼저 수행될 수 없습니다.

 

8. POSIX SEMAPHORES

semaphore은 반드시 pthread 라이브러리와 연결되어야 합니다. 

 

Semaphore initialization

#include <semaphore.h>
int sem_init(sem_t *sem, int pshared, unsigned int value);

 

•  parameters
  • sem : semaphore 객체
  • pshared
    • 0 : 현재 프로세스 내에서만 사용됨
    • 0이 아님 : 여러 프로세스간 공유됨
  • value : semaphore의 초기 값

Semaphore wait operation

#include <semaphore.h>
int sem_wait(sem_t *sem);
int sem_trywait(sem_t *sem);

 

•  sem_wait()
  • 스레드가 semaphore을 얻을 때까지 기다림 (suspend)
  • semaphore을 얻으면 내부적으로 semaphore count가 자동감소
• sem_trywait()
  • non-blocking
  • 만약 현재 semaphore를 얻을 수 있다면(sem값이 0보다 크면) semaphore을 얻고 반환
  • semaphore을 얻을 수 없다면 즉시반환되지만 다시 세마포어를 얻으라는 error를 반환 (EAGAIN)

Semaphore post(signal) operations

#include <sekaphore.h>
int sem_post(sem_t* sem);
int sem_getvalue(sem_t *sem, int* sval);

 

•  POSIX에서 semaphore의 signal operation의 이름은 post
• sem_post()
  • 자동으로 semaphore의 count값을 증가시킴
  • 이 함수는 절대 block되지 않음. 비동기 signal handler에 의해 안전하게 사용됨
• sem_getvalue()
  • 현재 semaphore값이 얼만지 알아냄

Semaphore destruction

#include <semaphore.h>
int sem_destroy(sem_t* sem);

 

• sem에 의해 semaphore가 destroy됨
  • 해당 semaphore가 사용했던 resource를 해제
  • waiting중인 스레드가 없어야 함

 

9. Example: Mutual Exclusion using Semaphore

<semaphore.c>

#include <semaphore.h>
int cnt = 0;	//공유자원(shared variable)
static sem_t hsem;	//semaphore 객체 변수

int main(int argc, char *argv[]){
	pthread_t thread1;	//main에서는 2개의 스레드(thread1, thread2) 선언. 
	pthread_t thread2;
	
	if(sem_init(&hsem, 0, 1) < 0){	//사용하려고 하는 세마포어에 대해 초기화, local 프로세스에서만 semaphre사용, binary semaphore
		fprintf(stderr, "Semaphore Initialization Error\n");
		return 1;
	}
	pthread_create(&thread1, NULL, Thread1, NULL);
	pthread_create(&thread2, NULL, Thread2, NULL);
	pthread_join(thread1, NULL);
	pthread_join(thread2, NULL);
	printf("%d\n", cnt);
	sem_destroy(&hsem);
	
	return 0;
}

void* Thread1(void *arg){
	int i, tmp;
    for(i=0; i<1000; i++){
    	sem_wait(&hsem);
        tmp = cnt;
        usleep(1000);
        cnt = tmp+1;
        sem_post(&hsem);
    }
    printf("Thread1 End\n");
    return NULL;
}

void* Thread2(void *arg){
	int i, tmp;
    for(i=0; i<1000; i++){
    	sem_wait(&hsem);
        tmp = cnt;
        usleep(1000);
        cnt = tmp+1;
        sem_post(&hsem);
    }
    printf("Thread2 End\n");
    return NULL;
}