[시스템 프로그래밍] Miscellaneous Thread Topics

Dining-Philosophers Problem

 

Philosophers who spend their lives thinking and eating

• When a philosopher thinks, he/she does not interact with his/her colleagues
• When a philosopher get hungry, he/she tries to pick up the two chopsticks that are closest to him/her
  • Chopsticks that are between him/her left and right neighbors
  • He/she cannot pick up a chopstick that is already in the hand of a neighbor
• When he/she is finished eating, he/she puts down both of his/her chopsticks and starts thinking again

철학자들은 생각하거나 먹으면서 인생을 보냅니다. 이들이 생각할때는 주변의 동료들과 소통하지 않고, 만약 배고파진다면, 그들은 그들 옆에 있는 젓가락을 들어 밥을 먹습니다.

그들이 밥 먹는것이 끝나면 젓가락을 다시 원래 자리로 돌려놓습니다.

 

즉, 젓가락이 공유자원이 됩니다.

 

Dining-Philosophers Problem psudocode

while(1){
    think for a random number of seconds
    pickup(p); // Critical Section!!
    eat for a random number of seconds
    putdown(p);
}

 

A Mutex for Each Chopstick

typedef struct{
    int id;            /* The phil's id: 0 to 4 */
    long t0;           /* The time when the program started */
    long ms;           /* The maximum time that phil sleeps/eats */
    void *v;           /* The void * that you define: Sticks */
    int *blocktime     /* Total time that a phil is blocked */
    int phil_count     /* 5 */
    pthread_mutex_t *blockmon; /* monitor for blocktime */
} Phil_struct;

typedef struct sticks{
    pthread_mutex_t *lock[MAXTHREADS]; /* MAXTHREADS is the number of phil */
    int phil_count;
} Sticks;

void pickup(Phil_struct *ps)
{
    Sticks *pp;
    int phil_count;
    
    pp = (Sticks *) ps->v;
    phil_count = pp->phil_count;
    /* lock up left stick */
    pthread_mutex_lock(pp->lock[ps->id]);
    /* lock up right stick */
    pthread_mutex_lock(pp->lock[(ps->id+1)%phil_count]);
}

void putdown(Phil_struct *ps)
{
    Sticks *pp;
    int phil_count;
    
    pp = (Sticks *) ps->v;
    phil_count = pp->phil_count;
    /* unlock right stick */
    pthread_mutex_unlock(pp->lock[(ps->id+1)%phil_count]);
    /* unlock left stick */
    pthread_mutex_unlock(pp->lock[ps->id]);
}

 

Deadlock

 

Although this solution guarantees that no two neighbors are eating simultaneously, it could create a deadlock

만약 5명의 철학자가 동시에 오른쪽에 있는 젓가락을 집으면, 모든 철학자는 왼쪽에 있는 젓가락이 unlock이 될때까지 기다리게 되므로, 이는 교착상태가 될 수 있습니다.

 

Deadlock-Free Solution

 

Possible solutions

• Allow at most n-1 philosophers to be sitting simultaneously at the table → 철학자의 수를 n-1명으로 줄이거나, 반대로 젓가락의 수를 n+1개로 늘리면 해결할 수 있다.
• Allow a philosopher to pick up his/her chopsticks only if both chopsticks are available → 두 젓가락이 동시에 사용가능한지를 확인한 후에 젓가락을 집게 하면 해결할 수 있다. 하지만 이렇게 한다면 병렬성이 떨어진다는 문제가 있다.
  • Must pick them up in a critical section
• Asymmetric solution
  • Odd philosophers start left-hand first, and even philosophers start right-hand first

void pickup(Phil_struct *ps)
{
    ...
    if (ps->id % 2 == 1) { /* Odd */
        /* lock up left stick */
        pthread_mutex_lock(pp->lock[ps->id]);
        /* lock up right stick */
        pthread_mutex_lock(pp->lock[(ps->id+1)%phil_count]);
    } else { /* Even */
        /* lock up right stick */
        pthread_mutex_lock(pp->lock[(ps->id+1)%phil_count]);
        /* lock up left stick */
        pthread_mutex_lock(pp->lock[ps->id]);
    }
}

asymmetric solution

 

Fairness and Starvation

 

Philosophers are not equally weighted, and even starve

• Depending on how the thread system is implemented
  • Suppose philosopher A is waiting for a chopstick
  • The owner of the chopstick (philosopher B) will eat and put the chopstick down, but there's no guarantee that philosopher A will get it if philosopher B wants to eat again before philosopher A's thread is rescheduled

위에 방법은 공평성의 문제가 있을 수 있습니다.

 

Possible solution

• Using condition variables
  • Will be coverd in the Operation System class

 

Sending SIGTERM to a Multi-threaded Process

 

Which thread will be terminated?

void* thread1(void *data)
{
    while(1){
        printf("thread 1\n");
        sleep(2);
    }
}

void* thread2(void *data)
{
    while(1){
        printf("thread 2\n");
        sleep(2);
    }
}

void* thread3(void *data)
{
    while(1){
        printf("thread 3\n");
        sleep(2);
    }
}

main(void)
{
    ...
    thr_ret = pthread_create(&tid[0], NULL, thread1, NULL);
    thr_ret = pthread_create(&tid[1], NULL, thread2, NULL);
    thr_ret = pthread_create(&tid[2], NULL, thread3, NULL);
    sleep(3);

    kill(getpid(), SIGTERM);

    printf("Main return\n");
    return 0;
}

 

result

 

+ main을 포함하는 모든 thread가 종료됩니다.

 

+ SIGTERM은 process 자체를 종료시키는 것이기 때문에 해당 process안에 있는 모든 thread들은 종료됩니다. 이때 종료되는 시점은 어떤 thread에게 Program Counter가 향해있는지에 따라 다릅니다.

 

Sending SIGALRM to a Multi-threaded Process

 

Which thread will be preempted?

main(void)
{
    ...
    thr_ret = pthread_create(&tid[0], NULL, thread1, NULL);
    thr_ret = pthread_create(&tid[1], NULL, thread2, NULL);
    thr_ret = pthread_create(&tid[2], NULL, thread3, NULL);
    sleep(3);

    kill(getpid(), SIGALRM);

    printf("Main return\n");
    return 0;
}

 

+ 현재 실행중인 thread에서 signal을 처리합니다.

 

+ 해당 thread의 context안에서 signal_handler가 실행됩니다. 즉 지금 실행중인 thread의 stack을 빌리는 것입니다.

 

Sending a Signal to a Thread

void sig_handler(int signum){
    for(int i=0; i<5; i++){
        printf("this is signal handler\n");
        sleep(2);
    }
}

int main(int argc, void* argv[]){
    ...
    signal(SIGUSR1, sighandler);
    
    thr_ret = pthread_create(&tid[0], NULL, thread1, NULL);
    thr_ret = pthread_create(&tid[1], NULL, thread2, NULL);
    thr_ret = pthread_create(&tid[2], NULL, thread3, NULL);
    sleep(3);

    pthread_kill(tid[select-1], SIGTERM);

	sleep(10);
    printf("Main return\n");
    return 0;
}

 

+ 여전히 SIGKILL/SIGTERM은 모든 thread를 종료합니다

 

result

 

+ 왼쪽 결과의 경우, thread 2번만 signal_handler가 불리고, 1,3번은 정상적으로 계속 돌아감을 알 수 있습니다.

 

+ signal을 받는 즉시 handler가 불리는 것이 아니라 그 thread에 CPU가 할당되었을때, handler가 불리는 것입니다.

 

+ signal mask의 경우는 process단위입니다.