Critical Section -4-

이번에는 n개의 프로세스와 s개의 자원에 대해 CSP를 해결할 수 있는 고전적인 해법, 세마포어에 대하여 알아보도록 하자. 세마포어는 다익스트라가 고안한 교착상태에 대한 해법(알고리즘)이다. 동작 메커니즘은 아래와 같다.

• 두 개의 atomic한 함수가 존재해서
• 정수 변수를 조작
• 이 변수를 통해 공유자원에 대한 접근을 제어함.

---

세마포어 pseudo-code

typedef struct{
	int value; 
    struct process *list; 
}semaphore;

wait(semaphore* S){
	S->value--;
    if(S->value < 0){
    	//add this process to S->list
        sleep(); //wait queue
    }
}

signal(semaphore* S){
	S->value++; 
    if(S->value <=0 ){
    	//remove a process P from S->list
        wakeup(P); 
    }
}

wait/signal 함수는 atomic하게 동작한다. 즉, 어떤 프로세스가 S에 대해 접근해서 ++, -- 연산을 할 때, 다른 프로세스들은 해당 구조체 변수 S에 접근이 불가능하다. 다시 말하자면, 한 번에 한 프로세스만 S에 접근할 수 있다.

wait 함수: 세마포어 구조체 S의 value는 사용 가능한 자원들의 인스턴스 숫자를 의미한다. 예를 들어, n개의 프로세스가 s개의 공유 자원에 접근한다고 가정하자. 각각의 프로세스들은 세마포어의 s의 숫자를 줄이고 s 값이 0보다 큰 경우, 즉 세마포어로 제어권을 획득한 경우 wait 함수를 탈출하게 된다. 0보다 작은 경우에는 사용 가능한 세마포어가 없어 wait list에 들어가게 되고, sleep() 함수를 호출해서 해당 프로세스는 waiting queue로 빠지게 된다.

signal 함수: 세마포어 구조체 S의 value가 0 보다 작거나 같으면, list의 프로세스를 꺼내서 wait queue에서 깨운다.

세마포어를 동기화에 사용하기

프로세스 $P_1$과 $P_2$가 concurrent하게 실행 되고 있다고 가정하자. 그리고 프로세스 $P_2$의 코드 $S_2$가 $P_1$의 코드 $S_1$ 이후에 실행 되어야 한다고 가정하자. 이 때 세마포어를 사용해서 두 프로세스를 동기화 할 수 있다.

	void p_1(){
    	S_1;
    	signal(synch); 
    }
    
    void p_2(){
    	wait(synch);
        S_2;
    }

최초 synch가 0으로 초기화 됐다고 가정하고, 위의 슈도 코드를 해석해보자.

1. synch가 0이므로 $P_2$는 busywaiting 혹은 wait queue에 들어가게 된다.
2. $P_1$에서 $S_1$을 실행한 후 signal을 호출한다.
3. signal 함수에서 synch를 1로 바꾼다.
4. $P_2$가 wait을 탈출하고 $S_2$를 실행한다.

위와 같은 방식으로 프로세스 $P_1$의 코드와 $P_2$의 코드가 동기적으로 호출될 수 있다.

예제 코드는 아래와 같다.

세마포어를 이용한 동기화 예제코드

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h> 

sem_t sem = 0; 

void thread01Request(){
	printf("thread1 hello\n");
    sem_post(&sem); 
    pthread_exit(0); 
}

void thread02Response(){
	sem_wait(&sem);
    printf("thread2 received thread1 hello."); 
    pthread_exit(0); 
}

int main(){
	pthread_t tid1,tid2;
    sem_init(&sem, 0 ,1); 
	
    pthread_create(&tid1, NULL, thread01Request, NULL);
    pthread_create(&tid2, NULL, thread02Response, NULL);
    
    pthread_join(tid1, NULL);
    pthread_join(tid2, NULL);
    
    sem_destroy(&sem);
}

예제 코드 실행 결과는 아래와 같다.

---

세마포어 예제코드

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <semaphore.h> 

int sum = 0;
sem_t sem;

void* counter1(void* param){
	for(int k=0; k<10000; k++){
    	//entry section 
        sem_wait(&sem);
        //critical section 
        sum++; 
        //exit section 
        sem_post(&sem); 
    }
	pthread_exit(0); 
}

void* counter2(void* param){
	for(int k=0; k<10000; k++){
    	//entry section 
        sem_wait(&sem);
        //critical section 
        sum--; 
        //exit section 
        sem_post(&sem); 
    }
	pthread_exit(0); 
}

int main(){
	pthread_t tid[6];  
    sem_init(&sem,0,6);
    //create threads
	for(int i=0; i<6; i++){
    	if(i%2 == 0)
  			pthread_create(&tid[i], NULL, counter1 , NULL);
    	else
        	pthread_create(&tid[i], NULL, counter2 , NULL);
    }
    //join threads
    for(int i=0; i<6; i++){
		pthread_join(tid[i],NULL);
  	}
    printf("sum : %d \n", sum); 
}

6개의 세마포어를 만들어서 6개의 스레드가 해당 세마포어를 획득한 후에 공통 변수 sum에 접근한다. 위의 예제 코드 실행 결과는 아래와 같다.

racing condition이 생겼다. 왜 그럴까? 6개의 세마포어가 있어서, 각 6개의 스레드가 전부 세마포어를 획득한 후 sum 변수에 동시접근할 수 있게 된다. 즉, 접근하려는 공통 리소스는 sum이라는 변수 하나이고, 이 변수에 대해 접근을 통제하는 세마포어가 6개이므로 각각의 스레드는 세마포어를 하나씩 획득한 후에 동시에 sum에 접근할 수 있게 된다. 그렇다면 이 racing condition을 어떻게 없앨 수 있을까? 세마포어를 하나로 바꿔주면 된다. 세마포어가 하나만 존재하면 각 스레드 중 세마포어를 획득한 스레드 하나 만이 공통 자원인 sum 변수에 접근해서 해당 변수에 read/write를 할 수 있게 된다.

    //sem_init(&sem,0,6);
    sem_init(&sem,0,1);

위의 코드로 바꿔주면,

예상값인 0으로 잘 떨어지게 된다.