Tips
0. 프로젝트 요약
In this project, you will learn the basics of threading a process. You will
learn how to make threads. You will discover the mutex.
프로세스 스레딩의 기본, 스레드를 만드는 방법, 뮤텍스
1. Mandatory
•
규칙
◦
한명 또는 여러명의 철학자가 둥근 테이블에 앉아서 3가지 행동을 한다. (먹기, 생각하기, 자기)
◦
한 행동을 하고있으면 나머지 행동은 하지 않는다.
◦
둥근 테이블 중앙에는 스파게티 한 그릇이 있다.
◦
테이블에는 포크가 있다.
◦
스파게티는 양손에 포크를 쥐고 먹어야한다.
◦
철학자는 굶주리면 안된다.
◦
모든 철학자는 먹어야한다.
◦
철학자는 서로 얘기하지 않는다.
◦
철학자는 다른 철학자가 죽는지 알지 못한다.
◦
철학자가 다 먹고 나면 포크를 내려놓고 꿀잠잔다.
◦
철학자가 잠을 다 자고 나면 생각하기를 시작한다.
◦
철학자가 한명 죽으면 시뮬레이션이 멈춘다.
•
인자 (Argument) 아래와 같은 순서로 주어진다.
◦
nubmer_of_philosophers : 철학자 인원, 포크 개수
◦
time_to_die : 밀리초 단위, 마지막 식사 또는 시뮬레이션 시작 이후로 time_to_die 밀리 초 이후로 죽는다.
◦
time_to_eat : 밀리초 단위, 철학자가 먹는데 걸리는 시간. 이 시간동안 포크 2개를 가지고 있는다.
◦
time_to_sleep : 밀리초 단위, 철학자가 자는데 걸리는 시간
◦
number_of_times_each_philosopher_must_eat: 옵션, 모든 철학자가 적어도number_of_times_each_philosopher_muset_eat 만큼 먹었다면, 시뮬레이션이 종료된다.
•
각각 철학자는 1부터 number_of_philosophers 만큼 숫자가 주어진다.
•
철학자 N 은 N - 1 과 N + 1 사이에 앉아있다. 철학자 1 은 철학자 number_of_philosophers 옆에 있다.
•
철학자가하는 행동은 다음과 같이 출력된다. (X 는 철학자 번호)
◦
timestamp_in_ms X has taken a fork
◦
timestamp_in_ms X is eating
◦
timestamp_in_ms X is sleeping
◦
timestamp_in_ms X is thinking
◦
timestamp_in_ms X died
•
출력되는 문장은 다른 문장과 겹치거나 얽히면 안된다.
•
철학자가 죽을때는 실제로 출력되기 까지 10ms 이상 걸리면 안된다.
•
철학자는 죽는걸 피해야한다.
•
포크는 철학자 사이에 하나씩 있다.
•
포크가 복사되는걸 방지 하기 위해서 포크의 상태를 mutex 로 보호해야한다.
•
각 철학자는 쓰레드 이어야한다.
•
요약
◦
철학자는 둥근 테이블에 모여 앉아있는데 각 철학자 사이에는 포크 하나씩 있다.
◦
철학자는 먹고 자고 생각하기를 한다.
◦
근데 먹을때는 포크2개로 스파게티를 먹어야한다.
◦
따라서 한명이 먹고있을때는 다른 한명은 먹지 못한다.
◦
그러다가 철학자 한명이 굶어 죽으면 시뮬레이션이 종료된다.
2. 사용 가능 함수
이미 아는 함수
•
memset, printf, malloc, free, write
모르는 함수
usleep
function
지정한 마이크로초만큼 프로세스를 대기시킨다
#include <unistd.h>
void usleep(useconds_t useconds);
C
복사
parameters
•
unseconds : 대기할 마이크로 초
useconds_t는 [0,1000000]사이의 값을 가지는 unsigned int 타입의 정수이다.
return value
•
없음
example
#include <stdio.h>
#include <unistd.h>
int main(void)
{
unsigned int useconds;
useconds = 1000000; // 100만 : 1초
usleep(useconds);
printf("done!\n");
return (0);
}
C
복사
gettimeofday
function
현재 시스템 시간을 기준으로 시, 분, 초 등 원하는 시간을 가져올 수 있는 함수
#include <sys/time.h>
#include <unistd.h>
int gettimeofday(struct timeval *tv, struct timezone *tz);
C
복사
parameters
•
tv : 현재 시스템 시간을 저장하기 위한 구조체
struct timeval
{
long tv_sec; // 초
long tv_usec; // 마이크로초
}
C
복사
•
tz : 타임존을 설정하기 위한 변수
하지만 현재는 사용되지 않으며 해당 인자는 항상 NULL로 두면 된다.
하지만 현재는 사용되지 않으며 해당 인자는 항상 NULL로 두면 된다. struct timezone
{
int tz_minuteswest: // 그리니치 서측분차
int tz_dsttime // DST 보정타입(일광 절약시간)
}
C
복사
return value
•
성공 시 : 0
•
실패 시 : -1
example
#include <stdio.h>
#include <time.h>
#include <sys/time.h>
#include <unistd.h>
int main() {
struct timeval tv;
double begin, end;
// 시작하는 시간 받아오기
gettimeofday(&tv, NULL);
begin = (tv.tv_sec) * 1000 + (tv.tv_usec) / 1000 ;
// 시간 측정을 진행할 부분
usleep(1500000);
// 끝나는 시간 받아오기
gettimeofday(&tv, NULL);
end = (tv.tv_sec) * 1000 + (tv.tv_usec) / 1000 ;
// 출력
printf("Execution time %f\n", (end - begin) / 1000);
return (0);
}
C
복사
pthread_create
function
새로운 쓰레드를 생성한다
#include <pthread.h>
int pthread_create(pthread_t * thread, pthread_attr_t *attr,
void * (*start_routine)(void *), void * arg);
C
복사
새로운 쓰레드는 아래 조건중 하나에 의하여 종료됩니다.
•
pthread_exit(3), pthread_exit 를 호출하여 리턴값을 지정합니다.
•
start_routing() 함수를 리턴합니다. 이것은 pthread_exit(3)를 호출하는것과 동일합니다.
•
pthread_cancel(3) 함수에 의한 쓰레드 취소
•
어떠한 쓰레드에서 exit(3)을 호출하거나 main 쓰레드에서 return을 하는경우,해당 프로세스의 모든 쓰레드는 종료됩니다.
parameters
•
*thread : 반환값을 저장할 쓰레드 식별자
•
*attr : 쓰레드와 관련된 특성을 지정하기 위한 용도
•
*(start_routine)(void*) : 쓰레드가 실행시킬 함수 포인터
•
*arg : start_routine 에 들어가는 매개변수
return value
•
성공 시 : thread에 쓰레드 식별번호를 저장한 후, 0 리턴
•
실패 시 : 0이 아닌 에러코드값
example
#include <pthread.h>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
// 쓰레드 함수
void *test(void *data)
{
int i;
int a = *(int *)data;
printf("data -> : %d\n", a);
for (i = 0; i < 1000000; i++)
{
printf("%d\n", i*a);
}
return (void *)(size_t)(i * 100);
}
int main()
{
int a = 100;
pthread_t thread_t;
int status;
// 쓰레드를 생성한다.
if (pthread_create(&thread_t, NULL, test, (void *)&a) < 0)
{
perror("thread create error:");
exit(0);
}
/* < 테스트 1 >
** 쓰레드가 종료되기를 기다린후
** 쓰레드의 리턴값을 출력한다.
** pthread_join(thread_t, (void **)&status); <- 테스트시 주석 해제
*/
/* < 테스트 2 >
** 쓰레드가 실행되는 도중에 중단시키면 어떤 일이 벌어지는지 확인한다.
** usleep(1); <- 테스트시 주석 해제
*/
/* < 결과 출력 >
** pthread_join함수를 사용하면, status에는 쓰레드가 실행시킨 함수의 리턴값이 들어간다
** 만약 2번 테스트로 중간에 쓰레드를 종료시키면 비어있는 값이 저장된다.
*/
printf("Thread End %d\n", status);
return 1;
}
C
복사
pthread_detach
function
실행중인 쓰레드를 메인 쓰레드에서 분리시킨다
쓰레드가 그냥 종료된다고 해서 자원이 free 되지 않기 때문에
join이나 detach를 무조건 해야한다.
쓰레드가 detach 되면 해당 쓰레드의 join 호출은 실패한다.
detach 하는 시점에서 쓰레드가 종료되면서 자원이 free 되는것이 아닌, 메인 쓰레드에서 detach 되고 나중에 쓰레드가 종료 될때 알아서 자원을 free 하는것이다.
#include <pthread.h>
int pthread_detach(pthread_t th);
C
복사
parameters
•
th : 쓰레드
return value
•
성공 시 : 0
•
실패 시 : 0 이 아닌 값
example
#include <pthread.h>
#include <stdio.h>
#include <unistd.h>
#include <stdlib.h>
// 쓰레드 함수
// 1초를 기다린후 아규먼트^2 을 리턴한다.
void *t_function(void *data)
{
char a[100000];
int num = *((int *)data);
printf("Thread Start\n");
sleep(5);
printf("Thread end\n");
}
int main()
{
pthread_t p_thread;
int thr_id;
int status;
int a = 100;
printf("Before Thread\n");
thr_id = pthread_create(&p_thread, NULL, t_function, (void *)&a);
if (thr_id < 0)
{
perror("thread create error : ");
exit(0);
}
// 식별번호 p_thread 를 가지는 쓰레드를 detach
// 시켜준다.
pthread_detach(p_thread);
pause();
return 0;
}
C
복사
pthread_join
function
쓰레드가 종료되는걸 기다린다. (쓰레드 종료는 해당 쓰레드가 종료되거나 리턴될때이다.)
쓰레드가 종료된다고해서 쓰레드 자원이 free 되지 않기 때문에 join 함수를 반드시 호출해야한다.
#include
int pthread_join(pthread_t th, void **thread_return);
C
복사
parameters
•
th : 쓰레드 식별 번호
•
thread_return : 쓰레드에서 반환된 값
return value
•
성공 시 : 0
•
실패 시 : 0이 아닌 에러코드 값
◦
ESRCH : 잘못된 쓰레드 식별 번호 일경우
◦
EINVAL : 쓰레드가 이미 detached 상태인경우
example
#include <pthread.h>
#include <stdlib.h>
// 쓰레드 함수
void *test(void *data)
{
int i;
int a = *(int *)data;
for (i = 0; i < 10; i++)
{
printf("%d\n", i*a);
}
return (void *)(i * 100);
}
int main()
{
int a[10] = 100;
pthread_t thread_t;
int *status;
// 쓰레드를 생성한다.
if (pthread_create(&thread_t, NULL, test, (void *)&a) < 0)
{
perror("thread create error:");
exit(0);
}
// 쓰레드가 종료되기를 기다린후
// 쓰레드의 리턴값을 출력한다.
pthread_join(thread_t, (void **)&status);
printf("Thread End %d\n", status);
return 1;
}
C
복사
pthread_mutex_init
function
뮤텍스란 ? 쓰레드가 공유하는 데이터 영역을 보호하기 위해서 사용하는 도구
뮤텍스 객체를 초기화 시키는데 사용한다.
#include <pthread.h>
int pthread_mutex_init(pthread_mutex_t * mutex,
const pthread_mutex_attr *attr);
C
복사
parameters
•
mutex : 초기화 시키는 mutex 객체
•
attr : 뮤텍스 특징 정의
◦
뮤젝트 종류
▪
fast (디폴트 값)
▪
recurisev
▪
error checking
return value
•
성공 시 : 0
•
실패 시 : -1
example
#include <pthread.h>
pthread_mutex_t mutex_lock;
int g_count = 0;
void *t_function(void *data)
{
pthread_mutex_lock(&mutex_lock);
g_coutn = 0;
for (int i = 0 ; i < 3 ; i++)
{
}
pthread_mutex_unlock(&mutex_lock);
}
int main()
{
pthread_t p_thread;
int state;
int a;
pthread_mutex_init(&mutex_lock, NULL);
pthread_create(&p_thread, NULL, t_function, (void *)&a);
...
pthread_join(&pthread, (void **)&status);
}
C
복사
pthread_mutex_destory
function
pthread_mutex_init 으로 생성된 뮤텍스 객체에 대해서
뮤텍스객체를 제거한다. 이때 mutex 는 반드시 unlock 상태이어야한다.
#include <pthread.h>
int pthread_mutex_destroy(pthread_mutex_t *mutex);
C
복사
parameters
•
mutex : 뮤텍스
return value
•
성공 시 : 0
•
실패 시 : errno
◦
EINVAL → mutex가 잘못 초기화 되었다.
◦
EBUSY→ mutex가 lock 상태이다.
example
#include <pthread.h>
pthread_mutex_t mutex_lock;
int main()
{
pthread_t p_thread;
pthread_mutex_init(&mutex_lock, NULL);
...
pthread_mutex_destroy(&mutex);
}
C
복사
pthread_mutex_lock
function
pthread_mutex_lock()는 (임계영역에 진입하기 위함)뮤텍스 잠금을 요청한다. 만약 뮤텍스의 최근 상태가 unlocked라면 쓰레드는 잠금을 얻고 임계영역에 진입하게 되고 리턴한다. 다른 쓰레드가 뮤텍스 잠금을 얻은 상태라면 잠금을 얻을 수 있을 때까지 기다리게 된다.
#include <pthread.h>
int pthread_mutex_lock(pthread_mutex_t *mutex);
C
복사
parameters
•
mutex : critical section에 접근해 데이터를 수정하려고 하는 mutex
return value
•
성공 시 : 0
•
실패 시 : errno
◦
EINVAL → mutex가 잘못 초기화 되었다.
◦
EDEADLK → 이미 잠금을 얻은 쓰레드가 다시 잠금을 요청할 때
pthread_mutex_unlock
function
pthread_mutex_unlock()는 뮤텍스잠금을 되돌려준다. 만약 fast 뮤텍스라면 pthread_mutex_unlock()는 언제나 unlocked 상태를 되돌려준다. recursive 뮤텍스라면 잠겨있는 뮤텍스의 수를 감소시키고 이 수가 0이 된다면 뮤텍스잠금을 되돌려주게 된다.
#include <pthread.h>
int pthread_mutex_unlock(pthread_mutex_t *mutex);
C
복사
parameters
•
mutex : mutex가 lock하고 있던 critical section의 잠금을 해제한다
return value
•
성공 시 : 0
•
실패 시 : errno
◦
EINVAL → mutex가 잘못 초기화 되었다.
◦
EPERM → mutex가 lock상태가 아니다.
example
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
int mails = 0;
pthread_mutex_t mutex;
void* routine(){
for (int i=0;i<1000000;i++){
pthread_mutex_lock(&mutex);
mails++;
pthread_mutex_unlock(&mutex);
}
}
int main(){
pthread_t p1, p2;
pthread_mutex_init(&mutex, NULL);
if (pthread_create(&p1, NULL, &routine, NULL) != 0)
return 1;
if (pthread_create(&p2, NULL, &routine, NULL) != 0)
return 2;
if (pthread_join(p1, NULL) != 0)
return 3;
if (pthread_join(p2, NULL) != 0)
return 4;
pthread_mutex_destroy(&mutex, NULL);
printf("Number of mails : %d\n", mails);
return 0;
}
C
복사
3. Mutex와 Semaphore
이번 과제는 본격적으로 멀티 쓰레드에 대한 공부를 진행하는 과제이다. 하나의 프로세스에는 1개 이상의 스레드가 존재할 수 있다. 이때 각각의 스레드는 code, data, files영역을 공유하고, 독립적인 stack영역을 가지며, 독립적으로 실행된다. (즉, 전역 변수와 static 변수를 공유한다)
이렇게 자원을 공유하는 멀티 쓰레드 프로그래밍을 할때 가장 우선적으로 고려야하는 상태가 있다.
바로 race condition이다.
code, data, stack, heap 영역race condition
race condition이란 두개 이상의 프로세스가 공통 자원을 병행적으로 읽거나 쓰는 동작을 할 떄, 공용 데이터에 대한 접근이 어떤 순서로 이루어지는지에 따라 그 실행 결과가 달라지는 상황을 말한다. 즉, 두개의 쓰레드가 하나의 자원을 놓고 서로 사용하려고 경쟁하는 상황이다.
이 때, 경쟁 프로세스들은 세가지 제어 문제에 직면한다.
1.
Mutual exclution
Race condition을 막기 위해서는 두 개 이상의 프로세스가 공용 데이터에 동시에 접근을 하는 것을 막아야 한다. 즉, 한 프로세스가 공용 데이터를 사용하고 있으면 그 자원을 사용하지 못하도록 막거나, 다른 프로세스가 그 자원을 사용하지 못하도록 막으면 이 문제를 피할 수 있다. 이것을 상호 배제(mutual exclusion)라고 부른다.
2.
Deadlock & Starvation
그러나 위와 같은 상호 배제를 시행하면 추가적인 제어 문제가 발생한다. 하나는 교착상태 즉 여기서 말하는 Deadlock이다. 프로세스가 각자 프로그램을 실행하기 위해 두 자원 모두에 엑세스 해야 한다고 가정할 때 프로세스는 두 자원 모두를 필요로 하므로 필요한 두 리소스를 사용하여 프로그램을 수행할 때까지 이미 소유한 리소스를 해제하지 않는다. 이러한 상황에서 두 프로세스는 교착 상태에 빠지게 되는 문제가 발생할 수 있다.
이 제어 문제는 ‘기아 상태’라고도 한다. 이러한 문제는 프로세스들이 더 이상 진행을 하지 못하고 영구적으로 블록되어 있는 상태로, 시스템 자원에 대한 경쟁 도중에 발생할 수 있고 프로세스 간의 통신 과정에도 발생할 수 있는 문제이다. 두 개 이상의 작업이 서로 상대방의 작업이 끝나기만을 기다리고 있기 때문에 결과적으로는 아무것도 완료되지 못하는 상태가 되게 된다.
이러한 문제들을 해결할 수 있는 방법으로 Mutex와 Semaphore가 있다.
Mutex
공유된 자원의 데이터를 여러 스레드가 접근하는 것을 막는 방법이다. 즉, Critical Section(각 프로세스에서 공유 데이터를 엑세스하는 프로그램 코드 부분)을 가진 쓰레드들의 Running time이 서로 겹치지 않게 각각 단독으로 실행되게 하는 기술이다. 다중 프로세스들이 공유 리소스에 대한 접근을 조율하기 위해 locking과 unloking을 사용하는데, 다시 말해서 상호배제를 함으로써 두 쓰레드가 동시에 사용할 수 없다는 뜻이다.
Semaphore
공유된 자원의 데이터를 여러 프로세스가 접근하는 것을 막는 것이다. 또한 세마포어는 리소스의 상태를 나타내는 간단한 카운터라고 할 수 있는데, 일반적으로 비교적 긴 시간을 확보하는 리소스에 대해 이용하게 되며, 운영체제의 리소스를 경쟁적으로 사용하는 다중 프로세스에서 행동을 조정하거나 동기화 시키는 기술이다. 다시 말해서 하나의 스레드만 들어가게 할 수도 있고 여러 개의 스레드가 들어가게 할 수 있다. 이것이 뮤텍스와의 차이이다.
4. 접근
•
포크를 int 로 두고, 0이면 아무도 안집은것, 1 이면 누군가 집은것으로 하였다.
•
이떄, 값을 접근(읽기, 쓰기) 할떄마다 뮤텍스 lock 을 걸고 값에 접근하도록 하였다.
•
그리고 이런 포크들을 공유 자원에 배열로 넣어두었다.
첫번째
•
설명
◦
모든 철학자가 왼쪽 포크를 먼저 잡고, 오른쪽 포크를 잡는다
•
문제
◦
모두가 왼쪽만 잡고있어서 데드락이 걸리고
◦
아무것도 못하고 그냥 죽어버린다
•
해결
◦
데드락을 해결해야한다.
두번째
•
설명
◦
모든 철학자가 양쪽 포크가 모두 유효한지 확인하고, 둘다 유효하다면 포크를 집도록 하였다.
◦
이렇게 양쪽 포크를 모두 확인하고 집으면, 데드락이 안걸릴거라고 생각했다.
•
문제
◦
양쪽 포크가 유효하다고 판단하고 포크를 잡는 그 사이에
◦
누군가가 포크를 잡아버리면 포크가 복사되버리는 문제가 생긴다
◦
위의 사진처럼, 3 번과 4 번이 동시에 포크를 집는 상황이 발생한다.
•
해결
◦
위의 사진처럼, LOAD 와 STORE 가 lock이 걸려있는 상태 에서 둘다 진행이 되야한다.
◦
즉, 포크가 유효하다고 판단하고 포크를 잡는 과정이 전체가 뮤텍스 락을 걸어둬야한다.
◦
데드락을 해결하는 새로운 방법을 찾는다.
세번째
•
뮤텍스 락을 건상태에서, 포크가 유효한지 확인도하고, 유효하다면, 집기까지 한다.
5. Debug 하는법
•
테스트
◦
./philo 5 610 200 200 : 무한루프
◦
./philo 5 410 200 200 : 죽음
◦
./philo 4 410 200 200 : 무한루프
◦
./philo 200 410 200 200 : 무한루프
◦
./philo 199 610 200 200 : 무한루프
•
평가 표
◦
1 800 200 200, the philosopher should not eat and should die!
◦
5 800 200 200, no one should die!
◦
5 800 200 200 7, no one should die and the simulation should stop when all the philosopher has eaten at least 7 times each.
◦
4 410 200 200, no one should die!
◦
4 310 200 100, a philosopher should die!
◦
Test with 2 philosophers and check the different times
•
무한루프 안돌고 자꾸 죽을때
◦
./philo 5 610 200 200 > log 로 log 파일 저장한다
◦
cat log | grep " $(cat log | grep dead | cut -d " " -f 2) " 로 마지막에 죽은 철학자의 행동을 따라가볼수있다.
◦
또는 아래의 링크에서 시각적으로 확인할 수 있다.
◦
Context Switching 이 제대로 일어나고 있는지, 한 쓰레드에만 몰빵하지 않는지 꼭 확인할것!
◦
위의 경우, 무한루프가 계속 돌아서 다른 쓰레드한테 자원이 충분히 돌지 않았을수있다.
◦
무한루프를 독점하지말고, usleep 을 줘서 다른 쓰레드한테 자원이 돌아갈수있도록 하자.
•
leak 확인하는 방법
◦
valgrind --leak-check=full ./philo 1 800 200 200
◦
-g3 -fsanitize=address
•
쓰레드 갯수 확인하는법
◦
ps | grep philo | cut -d ' ' -f 1 | xargs -I % ps -M % | grep -v USER |
wc -l
6. Reference
코드 참고
