[운영체제] 교착상태

🍴식사하는 철학자란?

어떤 문제를 다루기 위한 문제

병렬처리(concurrent programming)에서의 동기화 이슈와 해결 방법을 설명하고자 낸 문제이다.

 

누가 처음 든 예이며, 이를 공식화한 사람은?

1965 년 Edsger Dijkstra에 의해 처음으로 문제화하였고, Communicating Sequential Processes, C. A. R. Hoare 1985년 Prentice Hall 출판사에서 출간한 논문에서 공식화 하였다.

 

제기된 문제의 내용과 해결 방법

문제가발생하는경우- 모두 거의 동시에 왼쪽 포크를 든 후 오른쪽포크 를 들려고 할 때, 모두 상대가 가진 포크를 기다리면서 먹을 수 없는 교착 상태 발생한다.

해결 방법 – 원형 상태로 요청이 생기지 않도록 한다.
5명 중 마지막 사람을 제외한 4명이 왼쪽 포크를 먼저 잡고 오른쪽 포크 를 잡는 순서로 진행하고, 마지막 사람은 오른쪽 포크를 잡고 왼쪽 포크 를 잡도록 한다.

---

🔐교착상태

교착상태를 정의

자원을 소유한 스레드들 사이에서, 각 스레드는 다른 스레드가 소유한 자원을 요청하여 무한정 대기하는 현상이다.

 

교착상태는 스레드 동기화 문제 ?

스레드 동기화 문제는 아니다. 스레드 동기화(상호 배제)가 되는 상황에서 발생하는 문제이다.

 

교착상태가 발생할 필요조건 4가지

상호 배제(MUTual EXclusion) : 최소한 하나의 자원이 비공유 모드로 점유되어야 한다. 비공유 모드에선 한 번에 한 스레드만이 그 자원을 사용할 수 있다. 다른 스레드가 그 자원을 요청하면, 요청 스레드는 자원이 방출될 때까지 지연되어야 한다.

점유 대기 : 스레드는 최소한 하나의 자원을 점유한 채, 현재 다른 스레드에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 한다.

비선점 : 자원들을 선점할 수 없어야 한다. 강제적으로 방출될 수 없고 사용하고 있는 스레드에 의해 자발적 방출만이 가능하다.

순환 대기 : 대기하고 있는 스레드의 집합에서 A는 B가 점유한 자원을 대기하고 B는 C가 점유한 자원을 대기하고 … Z는 A가 점유한 자원을 대기한다.

---

💎자원할당 그래프

무엇을 위해?

교착상태 예방, 회피, 감지를 위한 알고리즘 개발에 필요하다.

자원할당 그래프 사례

정점 - 스레드 : ○, 자원 □

간선 - 할당 간선 : 붉은색 화살표, 할당 받은 상태 표시 (□→○)

          요청 간선 : 푸른색 화살표, 요청 표시 (○→□)

교착 상태 판단 : 그래프간에 순환이 생기면 교착 상태 발생

---

⚒️교착상태를 다루는 방법 4가지

1. 교착상태 예방(prevention)
 교착상태에 빠지는 4가지 코프만 조건 중 하나 이상의 조건이 성립되지 못하도록 시스템 구성한다.

2. 교착상태 회피(avoidance)
 미래에 교착상태로 가지 않도록 회피한다.
 자원 할당 시마다 미래의 교착 상태 가능성을 검사하여 교착상태가 발생하지 않을 것이라고 확신 하는 경우에만 자원 할당한다.

3. 교착상태 감지 및 복구(detection and recovery)
 교착상태를 감지하는 프로그램을 백그라운드에서 구동, 발견 후 교착상태 해제한다.

 

4. 교착상태 무시
 교착상태는 없다고 단정, 아무런 대비책 없다.

교착상태 예방, 회피,감지 복구 등에는 많은 시간과 공간이 필요하며 시스템의 성능을 떨어뜨리기 때문에 리눅스, 윈도우 등 현재 대부분의 운영체제에서 사용하는 가장 일반적인 방법이다.

---

💉교착상태의 예방책의 문제점

코프만의 4가지 조건 중 최소 하나를 성립하지 못하게 함

1. 상호 배제(Mutual Exclusion) 조건 - 상호배제 없애기

상호 배제 없애기 n 동시에 2개 이상의 스레드가 자원을 활용할 수 있도록 함
컴퓨터 시스템에서 근본적으로 적용 불가능

2. 소유하면서 대기(Hold & Wait) 조건 - 기다리지 않게
방법 1 : 운영체제는 스레드 실행 전 필요한 모든 자원을 파악하고 실행 시 한 번에 할당
당장 사용하지 않는 자원을 스레드에게 묶어 두므로 자원 활용률 저하
다른 스레드는 필요한 자원을 할당 받지 못하고 실행 대기
방법 2 : 스레드가 새로운 자원을 요청하려면, 현재 할당 받은 모든 자원을 반환하고, 한 꺼번에 요청하여 할당
방법1과 방법2 모두 가능하지 않거나 매우 비효율적

3. 강제 자원 반환 불가(No Pre-emption) 조건 - 선점 허용
자원을 강제로 반환하게 된 스레드가 자원을 다시 사용하게 될 때 이전 상태로 되돌아갈 수 있도록 상태를 관리할 필요
간단치 않고 오버헤드 매우 큼

4. 환형 대기(Circular Wait) 조건 - 환형 대기 제거

모든 자원에 번호를 매기고, 번호순으로 자원 할당

---

📖교착 상태를 탐지하는 것의 단점과 해결책

🏦Banker ’s 알고리즘으로 해결

Edsger Dijkstra 에 의해 개발된 알고리즘.

자원 할당 전에 미래에 교착상태가 발생하지 않을 것인지 안전한지 판단하는 알고리즘

안전 : 현재 프로세스들을 어떤 순서로 실행 시켰을 때, 모든 프로세스들이 자신이 요청하는 자원을 가지고 실행할 수 있다면 안전한 상태

 

불안전 : 환형 대기에 빠질 수 있다면 불안전한 상태

 

알고리즘
각 프로세스가 실행 시작 전에 필요한 전체 자원의 수를 운영체제에게 알린다.
자원을 할당할 때마다, 자원을 할당해주었을 때 교착상태가 발생하지 않을 만큼 안전한 상태인 지판단하여 안전한 상태일 때만 자원을 할당한다.
각 프로세스가 필요한 자원의 개수, 현재 각 프로세스가 할당 받은 자원의 개수, 그리고 시스템 내 할당 가능한 자원의 개수를 토대로 현재 요청된 자원을 할당해도 안전한지 판단한다.

단점
각 프로세스가 실행 전에 필요한 자원의 개수를 아는 것은 불가능
프로세스의 개수도 동적으로 변하기 때문에, 미리 프로세스의 개수를 정적으로 고정시키는 것 불가능

---

교착상태 해결을 위해 범용 운영체제인 Unix, Linux, Windows의 기본 해결법

교착상태 예방, 회피,감지 복구 등에는 많은 시간과 공간이 필요하며 시스템의 성능을 떨어뜨리기 때문에 리눅스, 윈도우 등 현재 대부분의 운영체제에서 교착상태 무시를 한다.

---

교착상태가 발생하는 프로그램

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

int x = 0; // 공유 변수
int y = 0; // 공유 변수
pthread_mutex_t lock1;  // 뮤텍스 락 변수
pthread_mutex_t lock2;  // 뮤텍스 락 변수

void* worker1(void* arg) { // 스레드 코드
    pthread_mutex_lock(&lock1); // x를 독점 사용하기 위해 lock1 잠그기
    printf("%s lock1 잠금\n", (char*)arg);
        x++;
        sleep(2); // 2초 잠자기

        pthread_mutex_lock(&lock2); // y를 독점 사용하기 위해 lock2 잠그기
        printf("%s lock2 잠금\n", (char*)arg);
        y++;
        pthread_mutex_unlock(&lock2); // lock2 풀기
        printf("%s lock2 해제\n", (char*)arg);

    pthread_mutex_unlock(&lock1); // lock1 풀기
    printf("%s lock1 해제\n", (char*)arg);
}

void* worker2(void* arg) { // 스레드 코드
    pthread_mutex_lock(&lock2); // y를 독점 사용하기 위해 lock2 잠그기
    printf("%s lock2 잠금\n", (char*)arg);
        y++;
        sleep(2); // 2초 잠자기

        pthread_mutex_lock(&lock1); // x를 독점 사용하기 위해 lock1 잠그기
        printf("%s lock1 잠금\n", (char*)arg);
        x++;
        pthread_mutex_unlock(&lock1); // lock1 풀기
        printf("%s lock1 해제 \n", (char*)arg);

    pthread_mutex_unlock(&lock2); // lock2 풀기
    printf("%s lock2 해제\n", (char*)arg);
}
int main() {
    char *name[] = {"박정제", "루이지"};
    pthread_t tid[2];

    pthread_mutex_init(&lock1, NULL); // 뮤텍스 락 변수 lock1 초기화
    pthread_mutex_init(&lock2, NULL); // 뮤텍스 락 변수 lock2 초기화

    pthread_create(&tid[0], NULL, worker1, name[0]);  // worker1 스레드 생성
    pthread_create(&tid[1], NULL, worker2, name[1]); // worker2 스레드 생성

    pthread_join(tid[0], NULL);
    pthread_join(tid[1], NULL);

    pthread_mutex_destroy(&lock2);
    pthread_mutex_destroy(&lock1);

    printf("x = %d, y = %d\n", x, y);

    return 0;
}

---

생산자-소비자 문제

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

#define N_COUNTER 4 // 공유 버퍼에 저장할 정수 공간의 개수
#define MILLI 1000

void mywrite(int n);
int myread();

pthread_mutex_t critical_section;
sem_t semWrite, semRead; // POSIX 세마포
int queue[N_COUNTER]; // 공유 버퍼
int wptr; // queue[]에 저장할 다음 인덱스
int rptr; // queue[]에서 읽을 다음 인덱스

void* producer(void* arg) { // 생산자 스레드 함수
    for(int i=0; i<10; i++) {
        mywrite(rand()%20); // 0~19 사이의 랜덤한 정수를 공유 버퍼에 저장

        // m 밀리초 동안 잠을 잔다.
        int m = rand()%10; // 0~9 사이의 랜덤한 정수
        usleep(MILLI*m*10); // m*10 밀리초동안 잠자기
    }
    return NULL;
}

void* consumer(void* arg) { // 소비자 스레드 함수
    for(int i=0; i<10; i++) {
        int n = myread(); // 공유 버퍼의 맨 앞에 있는 정수 읽어 리턴
        for(int i=0; i<n; i++) {
            printf("*");
        }
        printf("\n");

        // m 밀리초 동안 잠을 잔다.
        int m = rand()%10; // 0~9 사이의 랜덤한 정수
        usleep(MILLI*m*10); // m*10 밀리초 동안 잠자기
    }
    return NULL;
}
void mywrite(int n) { // 정수 n을 queue[]에 삽입
        sem_wait(&semWrite); // queue[]에 쓸 수 있는지 요청

        pthread_mutex_lock(&critical_section); // 뮤텍스 락 잠그기
        queue[wptr] = n; // 버퍼에 정수 n을 삽입한다.
        wptr++;
        wptr %= N_COUNTER;
        pthread_mutex_unlock(&critical_section); // 뮤텍스 락 열기
       
        sem_post(&semRead); // consumer 스레드 깨우기
}

int myread() { // queue[]의 맨 앞에 있는 정수를 읽어 리턴
        sem_wait(&semRead); // queue[]에서 읽을 수 있는지 요청

        pthread_mutex_lock(&critical_section); // 뮤텍스 락 잠그기
        int n = queue[rptr]; // 버퍼에서 정수를 읽는다.
        rptr++;
        rptr %= N_COUNTER;
        pthread_mutex_unlock(&critical_section); // 뮤텍스 락 열기

        sem_post(&semWrite); // producer 스레드 깨우기
        return n;
}

int main() {
    pthread_t t[2]; // 스레드구조체

    srand(time(NULL)); // 난수 발생을 위한 seed 생성

    pthread_mutex_init(&critical_section, NULL); // 뮤텍스 락 초기화

   // 세마포 초기화 : N_COUNTER 개의 자원으로 초기화
    sem_init(&semWrite, 0, N_COUNTER); // 가용버퍼의 개수를 N_COUNTER로 초기화
    sem_init(&semRead, 0, 0); // 가용버퍼의 개수를 0으로 초기화

    // producer와 consumer 스레드 생성
    pthread_create(&t[0], NULL, producer, NULL); // 생산자 스레드 생성
    pthread_create(&t[1], NULL, consumer, NULL); // 소비자 스레드 생성

    for(int i=0; i<2; i++)
        pthread_join(t[i],NULL); // 모든 스레드가 소멸할 때까지 대기

    sem_destroy(&semRead); // 세마포 기능 소멸
    sem_destroy(&semWrite); // 세마포 기능 소멸
    pthread_mutex_destroy(&critical_section); // 뮤텍스락 소멸
    return 0;
}