[42Seoul] Philosophers : 뮤텍스와 세마포어

이번 과제는 Dining Philosophers Problems (철학자들의 만찬 문제)를 Mutex를 사용해 멀티스레드를 구현하는 문제이다.

Dining Philosophers Problems 이란?

철학자들의 만찬문제는 n명의 철학자가 원형 테이블에 앉아있으며 양쪽에는 포크가 놓여져 있고 테이블의 중간에는 음식이 있다.

각 철학자는 양쪽의 포크를 모두 집어야만 음식을 먹을 수 있으며 일정시간 음식을 먹지 못하면 죽는다.

음식을 다 먹으면 포크를 내려놓고 생각을 시작하며 일정시간 생각이 끝나면 다시 포크를 들고 음식을 먹는다.

여기서 철학자는 process / thread 가 되며 포크는 공유자원이 된다. 

 

이 문제는 교착 상태(Deadlock)을 잘 설명하는 예시이며 교착 상태가 발생할 수 있는 4가지 필요조건을 모두 만족한다.

교착상태의 4가지 필요조건

1. Mutual Exclusion - 상호 배제

 하나의 자원은 한번에 하나의 프로세스(스레드)만 사용할 수 있다.

2. Non-preemptible - 비선점

 다른 프로세스(스레드)가 사용 중인 자원을 강제로 뺏을 수 없다.

3. Hold and wait - 보유하고 기다린다.

 자원을 Hold 한 상태로 다른 자원을 기다린다. 

4. Circular wait 

서로 순환하면서 자원을 기다린다.

 

이 4가지 필요 조건 중 하나라도 해당하지 않는다면 데드락은 발생하지 않는다.

 

[사용 함수]

gettimeofday

C언어에서 코드 수행 시간을 측정할 수 있는 함수

초 와 마이크로 초를 지원한다.

#include <sys/time.h>
int gettimeofday(struct timeval *tv, struct timezone *tz);

struct timeval {
    time_t      tv_sec; // 초
    suseconds_t tv_usec; // 마이크로초
}

pthread_create

새로운 thread를 생성하는 함수, thread의 주소 값과 시작할 함수를 매개로 받는다.

성공적으로 생성 될 경우 0을 리턴한다.

gcc에 기본적으로 라이브러리가 포함되어있지 않아 컴파일 시에 -lptheard를 옵션으로 주어야 한다.

int pthread_create(pthread_t * thread, // 스레드 식별자
                   const pthread_attr_t * attr, // 스레드 특성
                   void * (*start_routine)(void *), // 실행할 함수
                   void *arg); // start_routine의 매개변수

pthread_create()를 사용해 생성된 스레드는 메인스레드가 종료되면 함께 종료가 되며 그 과정에서 메모리를 자동으로 회수하지 않아 메모리 누수가 발생한다.

pthread_create() 에제

#include <pthread.h>
#include <stdio.h>
#include <unistd.h>

void *print_log(void *i)
{
	printf("Start %d thread\n", *(int *)i);
	sleep(1);
	printf("End %d thread\n", *(int *)i);
	return i;
}

int main()
{
	pthread_t thread[3];
	int check_return;
	for (int i = 0; i < 3; i++)
	{
		check_return = 
        pthread_create(&thread[i], NULL, print_log, (void *)&i);
		if (check_return != 0)
			return 0;
	}
	sleep(10);
}

그래서 pthread_detach 혹은 pthread_join을 사용해 생성된 스레드를 메인스레드로부터 분리시켜서 종료 시 자동으로 할당된 메모리를 반납 할 수가 있다.

pthread_detach vs pthread_join

그렇다면 pthread_detach 함수와 pthead_join 함수는 무엇이 다를까

먼저 두 함수의 원형을 보자.

int pthread_detach(pthread_t th);

int pthread_join(pthread_t th, void **thread_return);

 

pthread_detach 함수는 th 스레드를 받아 메인스레드로부터 분리해주며 스레드가 종료 시 자동으로 자원을 반환하게 된다. 

 

pthread_join 함수는 매개변수로 스레드가 리턴할 값을 받아 올 수 있으며 th 스레드를 받아 해당 스레드가 종료될 때까지 기다렸다가 종료가 되면 그 다음 스레드를 진행한다. 즉 스레드의 종료까지 메인스레드가 대기해주는 blocking 함수인 것을 확인 할 수 있다.

 

두 함수 모두 스레드가 종료되면 할당된 자원을 반납하는 것을 보장한다.

성공하면 0을 리턴한다.

 

이제 mutex 객체를 생성해 임계구역에 lock을 걸어보자.

pthread_mutex_init

mutex lock을 위한 mutex 객체를 초기화시키는 함수이다.

첫번째 인자 mutex 객체를 초기화 시키고 attr 특성을 지정할 수 있다.

정상 작동 시 0을 리턴한다.

int pthread_mutex_init(pthread_mutex_t * mutex,
const pthread_mutex_attr *attr);

pthread_mutex_destory

mutex의 사용이 끝나면 모든 자원을 해제시켜준다.

int pthread_mutex_destroy(pthread_mutex_t *mutex);

pthead_mutex_lock

Critical Section 내에 하나의 thread만 접근할 수 있도록 lock을 걸어준다.

임계구역 내에 다른 thread가 들어오려 시도 한다면 별도의 

int pthread_mutex_lock(pthread_mutex_t *);

pthread_mutex_unlock

lock을 해제시켜준다. 즉 임계구역의 종료를 나타낸다.

int pthread_mutex_unlock(pthread_mutex_t *);

Mutex vs  Semaphore

뮤텍스와 세마포어의 차이점은 임계구역에 들어갈 수 있는 개수를 정할 수 있다는 것이다.

뮤텍스는 하나의 임계구역에 하나의 스레드/프로세스 만 들어갈 수 있다면 세마포어는 다수의 스레드/세마포어가

접근 할 수 있다.

뮤텍스를 사용해 임계구역에 lock을 걸게 되면 해당 자원을 얻으려 대기하는 프로세스는 무한 대기를 돌기 때문에 busywaiting 문제가 있다.

 

세마포어는 변수 당 readyqueue 하나가 할당이 되어 semaphore는 busywaiting 문제를 해결했다.

기다려야 하는 프로세스는 block(asleep) 상태가 된다.

다만 대기 큐에 대한 wake-up 순서는 랜덤이 된다.

P()와 V()로 해당 자원을 확인하고 해제 해줄 수 있다.

• P() : (Probern 검사) == 자원을 차지하는 것 

P(S){
	if (S > 0)
	then S<- S - 1;
	else wait one the queue Qs;
}

• V() : Verhofen(증가) == 자원을 반납하는 것

V(S){
	if (waiting preocesses on Qs)
	then wakeup one of them;
	else S <- S + 1;
}

 

 

Bonus

보너스에서는 철학자가 스레드가 아닌 프로세스이며 세마포어를 이용해 구현해야한다.

규칙

• 모든 포크는 테이블 가운데에 있다.
• 메모리의 상태는 알 수 없고 사용가능한 포크의 수는 세마포어로 표현한다.
• 각 철학자는 프로세스로 이루어져 있어야 하고, 메인 프로세스는 철학자가 되면 안된다.

POSIX semaphore 함수

세마포어는 이름이 있는 세마포어와 익명 세마포어가 있다.

익명 세마포어는 sem_init으로 생성할 수 있으며 이름 없는 세마포어보다 더 빠르게 동작한다.

sem_open

세마포어를 생성하고 세마포어 구조체 포인터를 받아온다

sem_t * sem_open( const char * sem_name, int oflags,
		/*optional*/ mode_t mode , 
        /*optional*/ unsigned int value);

parameters

• sem_name : 세마포어의 이름
• oflags : 세마포어 생성을 위한 flag 지정한다. O_CREAT로 설정 된다
• mode : 세마포어에 접근하는 권한을 설정한다. 기본적으로 0644를 사용한다.
• value : 세마포어의 초기 값을 결정한다.

int sem_close(sem_t *sem);

sem_wait

P() 기능에 해당한다.

자원의 수를 하나 줄이며 만약 차지 가능한 자원이 없다면 자원이 반납 될 때 까지 대기한다.

int sem_wait(sem_t *sem);

sem_post

V() 기능에 해당한다.

자원을 반납하여 세마포어의 갯수를 늘려준다.

int sem_post(sem_t *sem);

sem_unlink

세마포어를 삭제한다. 이름있는 세마포어를 삭제할 때 사용할 수 있다.

int sem_unlink(const char *name);

waitpid

pid_t waitpid(pid_t pid, int *status, int options);

 

최적화

이 프로젝트의 핵심은 최대한 context switch에 소요되는 시간을 줄이고 임계구역을 구분하여 deadlock이 발생하지 않도록 설계하는 것이다.

처음 코드를 짤때 포크를 집는 행위 자체에 mutex lock을 설정하였다. 모든 스레드가 집을 때 마다 lock에 걸리기 때문에 그만큼 대기하는 시간이 길어져 딜레이가 생겼다.

그래서 fork 배열을 생성 하나의 포크당 뮤텍스를 생성해 따로 해당 철학자가 포크를 집었는지를 확인 하는 변수가 없이 mutex 그 자체로 확인하게 수정하였다.

먹는 시간과 자는 시간이 정해진 시간에 죽거나 종료하게 하려면 계속해서 해당 시간이 되었는지 확인을 해주어야 했다.

usleep 함수를 사용할 시에는 usleep이 호출되고 종료될 때 바로 해당 시간을 체크하는 것이 아닌 대기열에 들어가며 나오는 시간에서 딜레이가 크게 생겨 정확한 시간을 측정하지 못하는 것을 확인하였다.

block 상태에서 발생하는 딜레이를 줄이기 위해 최대한 usleep을 사용하지 않고 구현하였다.