'상호배제'에 해당되는 글 2건

동기화, 임계 영역 등 더 많은 정보와 예제를 담은 리눅스 교재를 배포했습니다. 아래의 페이지에서 리눅스 교재를 받아가세요.

https://reakwon.tistory.com/233

교착상태(Deadlock)

deadlock... 이름도 뭣같이 무섭네요. 교착상태라고 하는 것은 다중 프로그래밍 시스템에서 프로세스 혹은 스레드가 결코 일어나지 않을 일을 무한정으로 기다리는 상태를 말합니다. 시스템에서 교착상태는 프로세스가 요구하는 자원이 엉켜서 더 이상 작업을 더 실행할 수 없는 상태를 의미합니다.

시스템이라고 생각하면 조금 어려울 수 있는데 인간 세계에서도 똑같아요. 예를 들어볼까요?

교착상태의 발생 조건

아래 설명에서는 프로세스만을 이야기하는데, 스레드도 같습니다. 편의상 프로세스만 예를 들어 이야기하도록 하겠습니다.

1. 상호배제 (Mutual Exclusion)

한 번에  한 프로세스만 자원을 사용할 수 있어야합니다. 사용중인 자원을 다른 프로세스가 사용하려면 요청한 자원이 다 사용되고 난 후 해제될때까지 기다려야합니다. 

2. 점유와 대기 (Hold And Wait)

프로세스는 자원을 점유한 동시에 대기해야합니다. 위의 예에서 볼 수 있듯이 A는 돈을 소유하고 있고 B가 노트북을 주기까지 대기하고 있습니다. 

3. 비선점 (Non Preemptive)

자원을 선점할 수 없는 조건으로 누군가가 자원을 가지고 있을때 뺏을 수 없습니다. 위의 예에서도 지극히 정상적인 상식에서 A와 B는 물건을 불법적으로 훔칠 수 없죠. 

4. 순환(환형) 대기 (Circle wait)

프로세스가 여러개 있을때 자원의 점유와 요청의 관계가 순환되는 조건을 말합니다. 프로세스 3개를 각각 p1, p2, p3라고 할때 p1이 p2의 자원을 요청하고, p2가 p3의 자원을 요청하고, p3가 p1의 자원을 요청하고 그 자원은 요청한 자원을 얻을 수 있을때까지 반환할 수 없습니다. 이 조건은 위의 세 조건이 만족이 되면 자연스레 만족됩니다.

아래의 그림은 순환 대기를 나타낸 것인데 R1, R2, R3는 각 P1, P2, P3가 점유한 자원을 의미하고 각 자원은 소유된 프로세스쪽으로 화살표가 나가고 있습니다. 프로세스들의 화살표는 요구하는 자원쪽으로 향하고 있지요. 여기서 이 화살표들의 방향대로 나가면 사이클을 그리며 무한정 순환하게 됩니다.

교착상태 발생 코드

아래의 코드는 교착상태를 스레드를 이용해서 발생한 예제입니다. 여기서는 간단히 메인 스레드와 메인 스레드에서 생성된 스레드를 고려합니다.

여기서 자원은 뮤텍스인 lock1과 lock2를 말하지요. 

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>


pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

void *function(void* arg){

        sleep(1);       //main thread가 먼저 실행할 여지를 줌
        printf("\t thread start\n");

        pthread_mutex_lock(&lock2);
        pthread_mutex_lock(&lock1);

        printf("\t critical section \n");

        pthread_mutex_unlock(&lock1);
        pthread_mutex_unlock(&lock2);

        printf("\t thread end\n");

}

int main(){
        pthread_t tid;

        printf("main thread start and create thread\n");
        pthread_create(&tid,NULL,function,NULL);

        pthread_mutex_lock(&lock1);
        sleep(5);               //thread가 lock2를 먼저 실행할 여유를 줌
        pthread_mutex_lock(&lock2);

        printf("critical section \n");

        pthread_mutex_unlock(&lock2);
        pthread_mutex_unlock(&lock1);

        pthread_join(tid,NULL);
        printf("main thread end\n");

}

(정확히 100% 아래처럼 동작한다고 말할 수는 없지만 위 코드는 대부분 제가 의도한 대로 동작합니다. 왜냐면 스레드 실행 순서의 흐름은 예측할 수 없으니까요.)

코드를 보면 각각 critical section을 pthread_mutex_lock을 통해 보호하고 있지요. 이 소스 코드에서 눈 여겨 봐야할 점은 메인 스레드가 우선 lock1을 점유하고, 이후 생성된 스레드는 lock2를 점유하고 있습니다. 

바로 메인 스레드는 lock2를 점유하여 임계 영역에 진입하여야하는데 이미 생성된 스레드가 가지고 있습니다. 그렇기 때문에 lock2가 해제될때까지 기다립니다.

한편 생성된 스레드는 lock2는 점유했고 lock1을 얻은 후에 임계 영역을 진입하려합니다. 하지만 lock1은 이미 메인 스레드에 의해 점유되었습니다. 따라서 lock1이 해제될때까지 기다려야합니다.

여기서 위의 네가지 조건이 보이시나요?

첫번째 조건으로 critical section으로 특정 한 스레드만 임계 영역에 진입할 수 있습니다. 여기서 임계 영역이 중첩되어 있네요. lock1을 이용해 잠근 임계영역과 lock2를 통한 임계영역이지요.

두번째 조건으로 점유와 대기를 이루고 있습니다. 메인 스레드는 lock1을 점유하고 lock2가 해제되기를 기다리고 있고 생성된 스레드는 lock2를 점유하고 메인 스레드에 의해 lock1이 해제될때까지 기다리고 있습니다.

세번째 조건은 비선점 조건인데 서로 강제로 lock1, lock2를 가져올 수 없습니다.

네번째 조건은 위의 그림처럼 그려보면 사이클을 이루게 되죠.

이 프로그램의 실행결과는 어떨까요? 무사히 수행이 될까요? 실행시켜 보도록 하겠습니다.

네, 사용자가 중지하지 않는 이상 이 프로그램은 영원히 끝나지 않습니다. 아래에서 교착상태를 해결하는 코드를 볼 수 있습니다.

교착상태 문제 해결

교착상태가 발생하면 어떻게 해결할 수 있을까요? 크게 세가지 방법이 있는데 간략히 알아보도록 합시다.

1) 교착 상태 예방

교착 상태가 발생하기 전에 조치를 취하는 방식으로 위의 4가지 조건 중 하나라도 발생시키지 않으면 됩니다. 

- 자원의 상호배제 조건 방지

- 점유와 대기 조건 방지

- 비선점 조건 방지

- 순환 대기 조건 방지

앞서 얘기했듯이 처음 세조건이 만족되면 순환 대기가 발생하므로 결국에는 순환대기를 발생시키지 않으면 됩니다.

교착 상태 예방은 시스템의 처리량을 떨어뜨립니다. 

2) 교착 상태 회피

예방처럼 교착 상태의 발생 가능성을 미리 제거하지 않고 교착상태가 일어난다고 보고 이것을 회피하는 것입니다. 예를 들어 몇 초동안 프로세스나 스레드가 임계 구역 전에 대기 중이라면 이 시간이 지난 후 다음 작업을 수행합니다. 위의 예제코드를 아래와 같이 수정할 수 있습니다.

#include <stdio.h>
#include <pthread.h>
#include <unistd.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>


pthread_mutex_t lock1 = PTHREAD_MUTEX_INITIALIZER;
pthread_mutex_t lock2 = PTHREAD_MUTEX_INITIALIZER;

void *function(void* arg){
        struct timespec tout;
        struct tm* t;
        int locked;

        sleep(1);       //main thread가 먼저 실행할 여지를 줌
        printf("\t thread start\n");


        clock_gettime(CLOCK_REALTIME,&tout);
        tout.tv_sec += 5;

        pthread_mutex_lock(&lock2);
        locked = pthread_mutex_timedlock(&lock1,&tout);  //5초간만 lock이 걸림

        printf("\t critical section \n");

        if(locked == 0){
                pthread_mutex_unlock(&lock1);
        }
        pthread_mutex_unlock(&lock2);

        printf("\t thread end\n");

}

int main(){
        pthread_t tid;

        printf("main thread start and create thread\n");
        pthread_create(&tid,NULL,function,NULL);

        pthread_mutex_lock(&lock1);
        sleep(5);               //thread가 lock2를 먼저 실행할 여유를 줌
        pthread_mutex_lock(&lock2);

        printf("critical section \n");

        pthread_mutex_unlock(&lock2);
        pthread_mutex_unlock(&lock1);

        pthread_join(tid,NULL);
        printf("main thread end\n");

}

pthread_mutex_timed_lock 함수는 특정 시간동안 lock을 얻을 수 없다면 뮤텍스를 잠그지 않고 ETIMEDOUT이라는 오류 부호를 돌려줍니다. 따라서 스레드가 무한정 차단되지 않게 만듭니다. 이 코드를 실행시켜보면 아래와 같이 끝나기는 합니다.

3) 교착 상태 회복 

교착 상태를 시스템에서 탐지하여 회복시키는 알고리즘으로 교착상태를 회복합니다.

동기화와 동기화를 이용한 더 많은 정보와 예제를 담은 리눅스 교재를 배포했습니다. 아래의 페이지에서 리눅스 교재를 받아가세요.

https://reakwon.tistory.com/233

임계 영역(Critical Section) 

mutex를 알아보기전에 우선 critical section(임계구역)부터 간단하게 알아보자면 critical section은 하나의 한 스레드만이 진입해야하는 특정 코드 구역을 말합니다. 다시 말해 공유자원의 변경이 일어날 수 있는 구간이 임계 영역입니다. 공유자원이라고 하면 여러가지가 있을 수 있는데 간단히 변수라고 생각하세요.

예를 들어볼까요? 자, 아래코드의 임계영역은 cnt=0으로 초기화하며 for루프를 실행하는 구역입니다. 여기에 공유자원은 cnt가 되지요. 스레드가 2개가 있고 차례대로 create하게 됩니다. 아래의 소스코드가 각각 스레드가 실행부가 됩니다. 이 코드의 실행 결과를 한번 예측해보세요. 

void *count(void *arg){
    int i;
    char* name = (char*)arg;

    //======== critical section =============
    cnt=0;
    for (i = 0; i <10; i++)
    {
        printf("%s cnt: %d\n", name,cnt);
        cnt++;
        usleep(1);
    }
    //========= critical section ============
}

우리의 예측은 이렇습니다. 

thread1이 count함수 실행 : cnt를 0으로 초기화하고 cnt를 10번 증가시킨 후 종료

thread2가 count함수 실행 : cnt를 0으로 초기화하고 cnt를 10번 증가시킨 후 종료

하지만 실제 결과는 다르지요. 아래와 같이 뒤죽박죽으로 나옵니다.

thread2 cnt: 0
thread1 cnt: 0
thread1 cnt: 1
thread1 cnt: 2
thread2 cnt: 3
thread1 cnt: 4
thread2 cnt: 5
thread1 cnt: 6
thread1 cnt: 7
thread2 cnt: 8
thread2 cnt: 9
thread1 cnt: 10
thread2 cnt: 11
thread1 cnt: 12
thread1 cnt: 13
thread2 cnt: 14
thread1 cnt: 15
thread2 cnt: 16
thread2 cnt: 17
thread2 cnt: 18

뮤텍스(MutEx)

Mutual Exclusion의 약자로 상호배제라고 합니다. 특정 쓰레드 단독으로 들어가야되는 코드 구역에서 동기화를 위해 사용되는 동기화 기법입니다.

우리는 리눅스에서 이 뮤텍스를 통한 동기화를 수행하여 위 코드의 문제점을 해결해볼겁니다. 

우선 원래의 문제가 되는 모든 코드는 아래와 같습니다.

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

int cnt=0;

void *count(void *arg){
    int i;
    char* name = (char*)arg;
    
    //======== critical section =============
    cnt=0;
    for (i = 0; i <10; i++)
    {
        printf("%s cnt: %d\n", name,cnt);
        cnt++;
        usleep(1);
    }
    //========= critical section ============
}

int main()
{
    pthread_t thread1,thread2;

    pthread_create(&thread1, NULL, count, (void *)"thread1");
    pthread_create(&thread2, NULL, count, (void *)"thread2");

    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);
}

문제해결을 위해서 우리가 생각해볼 수 있는 것은 cnt = 0 전에 먼저 실행되는 스레드가 어떤 잠금장치를 이용해 잠그고, 나올때 잠금을 해제하면 되겠다는 생각을 해볼 수 있겠네요. 이런 목적을 달성하기 위해 우리는 4개의 pthread mutex함수를 기억하면 됩니다. 이 함수들은 pthread.h내에 존재합니다.

pthread_mutex_init : mutex를 초기화하는데에는 두 가지 방법이 존재합니다.

1) 정적으로 할당된 뮤텍스를 초기화하려면 PTHREAD_MUTEX_INITIALIZER 상수를 이용해서 초기화합니다.

이런 형식으로 사용합니다. : pthread_mutex_t lock = PTHREAD_MUTX_INITIALIZER;

2) 동적으로 초기화하려면 pthread_mutex_init 함수를 사용하면 됩니다. mutex를 사용하기 전에 초기화를 시작해야합니다. 

int pthread_mutex_init(pthread_mutex_t *restrict mutex, const pthread_mutexattr_t *restrict attr);

첫번째 인자는 mutex, 두번째인자는 이 mutex의 속정을 주는데, 기본적으로 NULL을 사용합니다.

pthread_mutex_lock, pthread_mutex_unlock : 이 두 함수는 mutex를 이용하여 임계 구역을 진입할때 그 코드 구역을 잠그고 다시 임계 구역이 끝날때 다시 풀어 다음 스레드가 진입할 수 있도록 합니다.

한 가지 중요한 점은 pthread_mutex_lock이 어떤 스레드에서 호출되어 lock이 걸렸을때 다른 스레드가 임계구역에 진입하기 위해서 pthread_mutex_lock을 호출했다면 그 스레드는 이 전의 스레드가 임계 구역을 나올때까지, 즉, pthread_mutex_unlock을 할때까지 기다려야합니다. 

int pthread_mutex_lock(pthread_mutex_t *mutex);
int pthread_mutex_unlock(pthread_mutex_t *mutex);

pthread_mutex_destroy : 만약 뮤텍스를 동적으로 생성(pthread_mutex_init을 이용하여 초기화)했다면 이 함수를 사용하는 함수가 pthread_mutex_destroy입니다.

int pthread_mutex_destroy(pthread_mutex_t *mutex);

이제 문제를 해결하는 코드를 봐야겠네요.

문제를 해결한 코드는 아래와 같습니다. 

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

pthread_mutex_t mutex;
int cnt=0;

void *count(void *arg){
    int i;
    char* name = (char*)arg;

    pthread_mutex_lock(&mutex);

    //======== critical section =============
    cnt=0;
    for (i = 0; i <10; i++)
    {
        printf("%s cnt: %d\n", name,cnt);
        cnt++;
        usleep(1);
    }
    //========= critical section ============
    pthread_mutex_unlock(&mutex);
}

int main()
{
    pthread_t thread1,thread2;

    pthread_mutex_init(&mutex,NULL);

    pthread_create(&thread1, NULL, count, (void *)"thread1");
    pthread_create(&thread2, NULL, count, (void *)"thread2");

    pthread_join(thread1, NULL);
    pthread_join(thread2, NULL);

    pthread_mutex_destroy(&mutex);
}

critical section 전, 후에 lock, unlock을 하는 것과 프로그램 시작 직후, 종료 직전에 mutex를 초기화하고 제거하는 과정만 추가되었습니다. 

이제 컴파일하고 실행결과를 보도록 합시다.

#gcc pthread_mutex.c -lpthread
# ./a.out
thread2 cnt: 0
thread2 cnt: 1
thread2 cnt: 2
thread2 cnt: 3
thread2 cnt: 4
thread2 cnt: 5
thread2 cnt: 6
thread2 cnt: 7
thread2 cnt: 8
thread2 cnt: 9
thread1 cnt: 0
thread1 cnt: 1
thread1 cnt: 2
thread1 cnt: 3
thread1 cnt: 4
thread1 cnt: 5
thread1 cnt: 6
thread1 cnt: 7
thread1 cnt: 8
thread1 cnt: 9

차례대로 들어간 스레드부터 0~9까지 출력하는 것을 볼 수 있습니다.