서론
42서울을 시작한지 벌써 1년이 다 되어간다. 42서울과 학교를 병행하며 정신없이 시간을 보내서 그런지 시간이 너무 빠르게 지나갔다.
지난 11개월 동안은 시간에 치여 42서울의 과제들을 빠르게 해결하는 것에 초점을 두었다. 그러다 보니 과제를 해결하며 배운 내용들이 금방 머리에서 사라져 갔다.
학습한 내용들을 블로그에 기록해야겠다고 늘 다짐했지만, 바쁘다는 핑계로 실행에 옮기지 않았었다. 이제부터는 과제를 끝낸 후 기억하고 싶은 내용들을 꼭 기록해보겠다.
Philosophers란?
Philosophers는 식사하는 철학자라는 유명한 운영체제 문제를 바탕으로 만들어진 과제로, Multi threading에서의 교착상태를 이해하기 위해 만들어졌다. 교착상태란 운영체제 또는 소프트웨어의 잘못된 자원 관리로 인하여, 둘 이상의 프로세스 또는 스레드들이 아무것도 진행하지 않는 상태로 서로 영원히 대기하는 상황을 말한다.
아래의 4가지 조건을 모두 만족하면 Deadlock 상태가 된다.
- 상호 배제 (Mutual exclusion)
- 점유 상태로 대기 (Hold and wait)
- 선점 불가 (No preemption)
- 순환성 대기 (Circular wait)
4가지 조건을 하나하나 살펴보며 Philosophers에서 기억하고 싶은 포인트들을 기록하겠다.
Deadlock조건을 살펴보기전에 빠르게 Philosophers가 어떤 과제인지 자세하게 알아보자.
Philosophers에는 n명의 철학자와 n개의 포크가 있다. 철학자들은 원형으로 앉아 있고, 철학자들 사이에 포크가 존재한다. 철학자들이 음식을 먹기위해서는 자신의 왼쪽, 오른쪽에 있는 포크를 둘 다 집어야 한다. 단, 포크는 한번에 한 철학자만 사용할 수 있다. 양쪽의 포크를 집은 철학자는 일정시간 식사를 한 후 일정시간 잠을 잔다. 잠에서 깨어난 후에는 다시 포크를 집을 때 까지 생각을 하며 기다린다. 일련의 과정에서 일정시간 이상 밥을 먹지 못하면 철학자는 죽게된다.
Deadlock의 4가지 조건
1. 상호배제(Mutual exclusion)
상호배제는 자원 자체를 동시에 쓸 수 없으며, 반드시 한 번에 하나의 프로세스만이 해당 자원을 사용할 수 있는 경우를 일컫는다. 사실 상호배제가 없으면 교착 상태는 발생하지 않는다. 그렇다면 왜 상호배제가 필요할까?
그 이유는 여러 쓰레드가 동시에 한 메모리에 접근할 때, 상호배제가 없다면 읽기/쓰기 순서가 꼬여 의도치 않은 결과가 발생할 수 있기 때문이다. 예를 들어 A와 B가 인터넷 뱅킹으로 10000원이 있는 계좌 X에서 1000원씩 인출한다고 생각해보자. 상호배제가 없으면 A가 X에서 1000원을 인출하는 도중 B의 인출도 처리될 수 있다. 이렇게 되면 A의 출금으로 인한 계좌 정보 업데이트가 되지 않은 상태로, B도 똑같이 잔고가 10000원인 계좌에서 1000원을 출금하게 된다. 그 결과 A와 B의 인출을 모두 처리한 후, 계좌에는 8000원이 아닌 9000원이 남게 된다. 하지만 상호배제가 있다면 동시에 두 개의 인출이 처리될 수 없다. 따라서 A의 작업이 모두 완료된 후 B의 작업이 이루어지게 되고, 계좌에는 8000원이 남게 된다.
상호 배제(mutual exclusion)의 줄임말이 바로 뮤텍스이다. Philosophers의 경우 뮤텍스를 통해 철학자들이 동시에 한 포크를 집을 수 없도록한다.
2. 점유 상태로 대기(Hold and wait)
점유 상태로 대기란 자원 하나를 붙잡은 상태에서 또 다른 자원을 기다리는 것을 의미한다. 원형 테이블에 2명의 철학자가 있다고 생각해보자. 둘이 동시에 왼손으로 포크를 집는다면, 둘 중 한 명이 포크를 내려놓을 때까지 둘 다 식사를 하지 못한 채 대기해야 한다. 이러한 상황이 점유 상태로 대기(Hold and wait)이다.
3. 선점 불가(No preemption)
선점 불가(No preemption)은 다른 프로세스가 자원을 뺏어올 방법이 없음을 뜻한다. Philosopher의 경우 철학자 한 명당 하나의 쓰레드를 생성하고, 각각의 쓰레드는 포크라는 자원을 공유한다. Mutex를 사용하면 철학자가 포크에 걸린 lock을 unlock해줄 때 까지 다른 철학자가 포크를 사용할 수 없다. 그렇기 때문에 선점 불가 조건을 충족한다.
4. 순환성 대기(Circular wait)
순환성 대기란 모든 프로세스가 다른 프로세스들이 사용중인 자원을 기다리는 상황에서, 마지막 프로세스가 첫 프로세스가 사용 중인 자원을 쓰기 위해 대기중인 상황이다. 가령 모든 철학자들이 동시에 왼손으로 포크를 집는 상상을해보자. 철학자들은 식사를 하기 위해 자신의 오른쪽 철학자가 포크를 내려 놓기를 기다린다. 하지만 철학자들은 식사를 한 후에야 포크를 내려놓을 수 있기 때문에 모두가 왼손에 포크를 들은 채로 영원히 기다리게 된다.
사실 순환성 대기는 Deadlock조건의 핵심이라고 할 수 있다. 상호배제, 점유 상태로 대기, 선점불가가 주어진 조건이라면 순환성 대기는 코드를 어떻게 작성하느냐에 따라 달라진다. 위의 상황에서 순환성 대기가 발생하는 이유는 모든 철학자가 같은 순서로 포크를 집기 때문이다. 따라서 순환성 대기를 피하기 위한 핵심 아이디어는 적어도 한명의 철학자는 다른 순서로 포크를 집게 하는 것이다. 나는 홀수 번째 철학자와 짝수 번째 철학자가 포크를 집는 순서를 다르게 설정해서 순환성 대기를 막았다.
위에서 설명한 방법 외에도 순환성 대기를 피하는 방법은 여러가지가 있다. 대표적인 방법으로는 철학자가 간발의 차이로 다른 쪽 포크를 집는데 실패하면, 식사를 포기하고 집고 있는 포크를 반납하는 방법이 있다.
기억하고 싶은 내용
1. 컨텍스트 스위칭
컨텍스트 스위칭이란 CPU에서 실행중이던 Thread/Process가 다른 Thread/Process로 교체되는 것이다. 기본적으로 OS커널이 컨텍스트 스위칭을 해주지만 더 빠른 주기의 컨텍스트 스위칭이 필요한 경우가 있다. 철학자의 수가 200명으로 설정되면 Thread가 200개가 생성된다. 이렇게 Thread의 수가 많아지면 Thread들 간 공정한 자원 할당이 어려워진다. 그 결과 원래 죽지 않아야 할 철학자가 CPU자원을 할당받지 못해 포크를 못잡아 죽게 된다.
C언어에서는 usleep()함수를 사용하여 더 빠른 주기의 컨텍스트 스위칭을 할 수 있다. usleep()을 사용하면 현재 Thread가 대기 상태로 전환되어 다른 프로세스가 실행가능해 진다. 따라서 철학자의 행동 사이사이에 적절한 usleep()을 주어 철학자들이 더욱 공정하게 CPU자원을 할당받게 할 수 있다. 다만, 과도한 컨텍스트 스위칭은 CPU 오버헤드를 유발해 성능을 저하시킬 수 있음으로 주의해야 한다.
Philosophers에서는 usleep()에도 컨텍스트 스위칭을 적용했다. usleep()으로 대기 상태가 된 Thread가 정확한 시간에 다시 돌아오기 위해서는 운영 체제의 스케줄러가 정확한 시간에 프로세스를 다시 실행해야 한다. 하지만 스케줄러는 여러 프로세스와 스레드 간에 CPU 시간을 분배해야 하기 때문에, usleep이 끝난 후에도 바로 프로세스가 실행되지 않을 수 있다. 특히 Thread수가 많은 경우, usleep의 대기 시간이 더 길어질 수 있다. Philosophers에서는 usleep()을 쪼개는 방식으로 시간 측정의 정확도를 올렸다. 코드와 함께보자
long get_time(void)
{
struct timeval time;
long result;
gettimeofday(&time, NULL);
result = ((size_t)time.tv_sec * 1000);
result += ((size_t)time.tv_usec / 1000);
return (result);
}
void ft_usleep(long sleep_time)
{
long start;
start = get_time();
while (start + sleep_time > get_time())
{
usleep(100);
}
}새롭게 만든 ft_usleep() 함수는 입력받은 sleep_time을 1ms 단위로 나누어 측정한다. 이렇게 하면 컨텍스트 스위칭 빈도를 늘려 잦은 빈도로 sleep_time을 체크하기 때문에, Thread수가 많을 경우 보다 정확한 시간 측정이 가능하다.
2. Mutex 사용 방식
나는 포크 자체를 Mutex를 사용해 통제하는 방식을 사용했다. 이러한 방식에서는 현재 Thread에서 사용하고자 하는 포크에 lock이 걸려 있다면, 포크를 사용 중인 Thread가 unlock 해줄 때 까지 아무것도 못하고 대기만 해야 한다. Thread가 대기만 하고 있는 것은 비효율적이다. 따라서 포크 자체를 Mutex로 통제하는 것이 아니라, 포크의 상태 변수를 Mutex로 통제하는 방식이 더 효율적인 것 같다. Mutex lock을 걸고 포크 상태를 확인한 후, 아무도 사용하고 있지 않으면 포크를 집고 상태를 업데이트 한 후 Mutex unlock, 사용중이라면 그대로 둔 채로 Mutex unlock을 하는 것이다. 이렇게 하면 Thread가 대기하는 시간을 줄일 수 있다.
3. Thread와 Process의 차이
Thread와 Process의 차이는 표로 살펴보겠다.
Thread는 메모리 공유되는 대신 Data Race등의 문제가 발생할 수 있어, Mutex를 통해 Thread 간의 공유 자원 접근을 제한한다. Process는 메모리 공유가 되지 않기 때문에 Pipe를 사용하여 Process 간의 데이터를 주고 받는다.
마무리
과제를 해결하며 학습한 내용중 오랫동안 기억하고 싶은 부분들을 정리해 봤다. 확실히 나의 언어로 표현하는 과정을 거치니 머릿속에 더욱 잘 정리되는 것 같다. 앞으로 조금 더 열심히 기록해 보자. 그럼 20000 👋
흥미롭네요