[운영체제] 교착상태 처리

교착상태 처리 방법

• 교착상태가 발생하지 않도록 하는 방법과 교착상태를 방치하고 이를 탐지하여 복구하는 방법이 있다.
• 이에 따라 예방, 회피 / 탐지, 복구로 나뉘어 진다.

교착상태 예방

• 교착상태 발생의 4가지 필요충분조건 중 한가지만 일어나지 않아도 예방이 된다.
• "상호 배제" 조건 부정 : 상호배제 조건을 부정하는 것은 사실상 불가능하다. 자원자체가 상호배제를 요구하는 것을 전제로 했기 때문이다.
• "점유 대기" 조건 부정 : 모든 자원을 실행 전에 미리 확보하도록 한다. 이렇게 되면 대기 자체가 필요없어져 교착상태를 예방할 수 있다. 하지만 자원을 바로 사용하지 않고도 장시간 점유를 해야하기 때문에 다른 프로세스에 악영향을 줄 수 있다. 또한 하나의 프로세스가 자원들을 독점하여 자원의 활용도가 낮아진다. / 자원을 가지고 있지 않은 상태에서 요청하도록 하는 방법도 있다. 임의의 프로세스가 자원을 추가로 얻고자 하면, 가지고 있던 자원을 일단 해제 후 추가 자원을 포함해 재요청을 하도록 한다. 이 경우 점유가 사라져 교착상태를 예방할 수 있게 된다. 단, 자원 여러개를 필요로 하는 프로세스의 경우 그 중 하나는 이미 할당되어 무한정 대기하게 되는 기아 상태가 발생할 수 있다.
• "비선점" 조건 부정 : 하나 이상의 자원을 보유중인 임의 프로세스가 현재 할당할 수 없는 자원을 요청할 경우 대기상태로 들어가면서 보유중이던 자원을 강제로 반환토록 한다. 해당 프로세스가 다시 재시작되려면 반환했던 자원과 요청자원을 모두 할당받아야 한다. CPU 레지스터나 메모리를 대상으로는 유용한 기법이지만, 입출력장치나 mutex, 세마포어 등에는 적용이 어렵다.
• "환형 대기" 조건 부정 : 특정 함수 F로 각 자원 유형에 번호표를 부여한다. 그리고 어떤 프로세스든 자원을 요청할 때는 번호가 증가하는 순서대로만 자원을 요청하도록 강제한다. 현재 할당중인 자원 유형의 번호보다 작은 번호를 가진 자원 유형을 요청할 때는, 현재 할당 중인 더 큰 번호의 자원 유형을 모두 반납해야 한다. 환형 대기라는 것은 결국 마지막 프로세스가 첫번째 프로세스의 자원을 요청하게 되는 형태이다. 이렇게 되면 첫번째 프로세스의 자원 유형이 마지막 프로세스의 자원 유형보다 번호가 작을 것이므로, 마지막 프로세스가 보유중이던 자원을 반납하게 되면서 환형대기가 역순으로 풀릴 수 있게된다. 단, 마지막 프로세스는 다른 모든 프로세스가 역순으로 자원을 반납할 때까지 기다려야 첫번째 프로세스의 자원을 받을 수 있으므로 이를 '비대칭 해결안'이라고 부른다. 환형 대기 조건을 부정하는 방법은 상황에 따라 해당 방법 말고도 다양하다.

Dining Philosophers Problem

philosopher (int i){
    while(1) {
        think();
        P(fork[i]);
        P(fork[(i+1) mod 5]);
        eat();
        V(fork[(i+1) mod 5]);
        V(fork[i]);
    }
}
semaphore fork[5];
fork[0] = fork[1] = fork[2] = fork[3] = fork[4] = 1
create_thread(philosopher, 0);
create_thread(philosopher, 1);
create_thread(philosopher, 2);
create_thread(philosopher, 3);
create_thread(philosopher, 4);

• philosopher 함수는 5개의 포크 중 자신에게 할당된 포크 자원과 다음 포크 자원을 가져가서 식사한다.
• 이를 반복한다. 이러다 다섯쓰레드 모두 자원을 할당받는 P함수가 겹치게 될 경우, 교착상태가 발생한다.

philosopher (int i){
    while(1) {
        think();
        int j = i % 2;
        P(fork[i+j] mod 5]);
        P(fork[(i+1-j) mod 5]);
        eat();
        V(fork[(i+1-j) mod 5]);
        V(fork[i+j]);
    }
}
semaphore fork[5];
fork[0] = fork[1] = fork[2] = fork[3] = fork[4] = 1
create_thread(philosopher, 0);
create_thread(philosopher, 1);
create_thread(philosopher, 2);
create_thread(philosopher, 3);
create_thread(philosopher, 4);

• 홀수 철학자는 오른편의 포크를 먼저 집고, 짝수의 철학자는 왼편의 포크를 먼저 집도록 한다.
• 이 경우 "환형 대기" 조건이 부정되어 교착상태가 발생하지 않는다.

P_sim(semaphore S, int N){
    L1: if((S[0] >=1) && … && (S[N-1]>=1)) {
        for(i=0; i<N; i++) S[i]--;
    } else {
        Enqueue the calling thread in the queue for the first S[i] where S[i] < 1;
        The calling thread is blocked while it is in the queue;
        Goto L1; // When the thread is removed from the queue
}}

V_sim(semaphore S, int N) {
    for(i=0; i<N; i++){
        if( S[i]++ <= 0){
            Dequeue all threads in the queue for S[i];
            All such threads are now ready to run(but may be blocked again int P_sim);
}}}

• 세마포어 오퍼레이션 자체를 수정하여 해결할 수도 있다.
• 필요한 모든 세마포어의 자원을 하나씩 순차적으로 P 오퍼레이션을 하는 것이 아니라, 한번의 P 오퍼레이션 내에서 한꺼번에 모두 차지하였을 경우에만 리턴이 되는 P연산을 만들어 준다.
• S연산도 그에 맞도록 수정한다.

philosopher (int i){
    while(1) {
        think();
        P_sim(fork[i], fork[(i+1) mod 5]);
        eat();
        V_sim(fork[i], fork[(i+1) mod 5]);
    }
}
semaphore fork[5];
fork[0] = fork[1] = fork[2] = fork[3] = fork[4] = 1
create_thread(philosopher, 0);
create_thread(philosopher, 1);
create_thread(philosopher, 2);
create_thread(philosopher, 3);
create_thread(philosopher, 4);

• 위의 수정된 세마포어를 활용하면 이와 같은 코드를 작성할 수 있다.
• 즉, fork[i]와 fork[i+1] 모두가 가능할 때만 자원을 할당받는 것이라고 할 수 있다.

교착상태 회피

• 교착상태 예방 방법은 교착상태 발생 조건 성립 자체를 부정하는 방법을 마련해, 이를 강제한다. 그에 따라 자원의 활용도가 낮아지거나 시스템의 처리량을 감소시키고, 기아상태를 발생시킬 위험이 있다.
• 교착상태 회피 방법은 프로세스가 요청할 자원에 대해 더 많은 정보를 미리 제공받고, 이러한 정보를 기반으로 전체적 상황을 고려하여 각 자원을 할당해줄지 아니면 기다리도록 할지 결정하는 방법이다. 즉, 현재 요구가 만족가능한지, 미래의 가능한 교착상태 회피를 위해 대기해야 하는지 결정할 수 있다.
• 이러한 교착상태 회피에 적용되는 알고리즘은 다양하다. 그 중 가장 대표적인 것이 Banker's 알고리즘이다. 해당 알고리즘은 각 자원에 대한 최대 요구량을 선언토록 요구한다.

안정 순열과 안정상태

• 뱅커스 알고리즘 이해를 위해서는 안정순열과 안정상태에 대한 정의를 알아야한다.
• 시스템의 상태가 '안정'하다는 말은 시스템이 어떤 순서로든 프로세스들이 요청하는 모든 자원을 교착상태 야기없이 모두 할당 가능한 상태를 의미한다. 이러한 안정상태를 유지할 수 있도록 하는 프로세스의 순열이 '안정순열'이다.
• 안정순열 : 프로세스의 임의의 순열 <P1, P2, ..., Pn>이 있다고 하자. 이 때 각 프로세스가 앞으로 요청할 최대의 자원량이 현재 남은 자원의 개수와 순열상에서 앞서있는 프로세스가 가진 자원을 합친 것보다 적거나 같으면 이를 안정 순열이라고 한다.
• 여기서 '앞으로 요청할 수 있는 최대의 자원량'은 프로세스가 일생동안 요청할 최대 요구량과 현재 할당받아 보유하고 있는 양과의 차이값을 의미한다. 해당 값을 시스템에 현재 남아있는 자원과 앞에서 수행을 마칠 모든 프로세스 Pj들이 반납하는 자원들로 만족시켜 줄 수 있는지를 모든 프로세스에 대하여 체크해 본다는 의미이다.
• 프로세스가 n개 있다면 가능한 순열의 개수는 n!개이다. 해당 순열 중 앞서 언급한 '안정 순열'이 하나라도 존재한다면 시스템은 안정상태이다.
• 단, 시스템이 안정상태가 아니라고해서 반드시 교착상태로 이어지는 것은 아니다. 교착상태에 빠지게 될 가능성이 생기는 것 뿐이다. 하지만 시스템을 안정상태로 머물도록 한다면 교착상태를 회피할 수 있을 것이다.
• 자원 할당 전에 해당 자원을 할당해주어도 안정상태가 유지될지를 파악한 뒤 그렇지 않다면 자원의 할당을 연기한다.
• 현재 남는 자원이 존재해도 충분하지 않다면 기다려야 하므로 시스템 이용도는 낮아진다.

Banker's 알고리즘의 자료구조

• 뱅커스 알고리즘은 5개의 행렬과 벡터를 정의한다. (행렬은 2차원 배열 / 벡터는 Array라고 생각하자.)
• Available 벡터 : 각 자원별 사용 가능 개수를 기록한다. Available[j]=k 라면 현재 자원 Rj 가 k개 사용가능한 상태임을 나타낸다.
• Max 행렬 : 임의의 프로세스가 각 자원을 최대 몇 개까지 요청하여 사용하기로 되어있는지를 의미한다. Max[i,j]=k 라면 프로세스 Pi 가 자원 Rj 를 최대 k 개까지 요청할 수 있음을 의미한다.
• Allocation 행렬 : 임의의 프로세스가 각 자원을 현재 몇 개 할당받아 사용중인지를 의미한다. Allocation[i,j]=k 라면 프로세스 Pi 가 자원 Rj 를 현재 k 개 할당 받고 있음을 뜻한다.
• Need 행렬 : 임의 프로세스의 최대 요청가능 개수를 의미한다. 즉, Max - Allocation 값과 동일하다.
• Request 행렬 : 임의 프로세스가 자원을 요청한 개수를 의미한다. Request[i,j]=k 라면 프로세스 Pi 가 자원 Rj 를 현재 k 개 요청했다는 뜻이다.

Banker's 알고리즘

• 위의 자료구조를 기반으로 몇가지 비교를 진행한다.
• 행렬 i는 해당 행렬의 i번째 행을 의미한다. 즉, Allocation i는 프로세스 i에 할당된 자원들을 의미한다.
• 1. 임의의 프로세스 i의 Request가 프로세스 i의 Need 보다 작거나 같은지 확인한다. 아닐 경우 잘못된 요청으로 처리한다.
• 2. 임의의 프로세스 i의 Request가 Available보다 작거나 같은지 확인한다. 아닐 경우 바로 자원 할당을 받지 못하고 대기한다.
• 3. Available에서 Request i에 해당하는 값들을 차감한다. Allocation에는 해당 Request 만큼 더해준다. Need에는 Request만큼 차감해준다. (Pi에게 자원을 할당해준 것처럼 나타낸 것이다.)
• 이 후엔 'Safety 알고리즘'을 수행하여 시스템이 안정상태인지를 확인한다. 불안정상태로 판정되면 수정한 값을 복구하고 프로세스 i를 대기시킨다.

Safety 알고리즘

Work = Available;
Finish[i] = false; // 모든 finish를 false로
for(j=0; j<n; j++){
    for(i=0; i<n; i++){
        if (Finish[i]==false && Need[i] <= Work)
            break;
    }
    Work = Work + Allocation[i];
    Finish[i]=true;
}

// 모든 i에 대하여 Finish[i]=true면 안정 상태;

• Safety 알고리즘은 안정순열이 존재하는지 판별하는 알고리즘이다.
• Work 변수에 현재 남은 자원을 저장해놓고, 프로세스를 돌면서 요구량이 Work 값보다 작은 프로세스 i를 찾는다.
• Work 변수에는 그렇게 찾은 프로세스 i의 할당량을 더해준다. 그리고 i는 Finish값을 true로 처리하여 완료된(혹은 완료될) 프로세스임을 표기한다.
• 반복문을 모두 돌았을 때 모든 i에 대해 Finish가 true라면 안정 순열이 존재하는 것이다.

교착상태 탐지

Work = Available;
Finish[i] = (Allocation[i] != 0) ? False : true;
for(j=0; j<n; j++){
    for(i=0; i<n; i++){
        if (Finish[i]==false && Request[i] <= Work)
        break;
    }
    Work = Work + Allocation[i];
    Finish[i]=true;
}

• Safety 알고리즘과 상당히 유사하다. 하지만 Safety 알고리즘은 자원 요청이 들어오면 해당 요청에 따라 Allocation 했을 경우를 가정한 상태에서 검사하는 것이고, 교착상태 탐지는 그러한 검토 없이 일단 자원 할당을 해주고 교착상태가 발생했는지만 주기적으로 검사하는 방법이다.
• Safety 알고리즘은 일단 모든 프로세스가 아직 마무리되지 않았다고 가정하고 시작하는 것에 반해, 교착상태 탐지 알고리즘은 현재 할당된 자원이 없다면 Finish값을 True로 처리해놓는다. 자원을 갖고 있지 않은 프로세스는 교착상태에 연루되지 않을 것이므로 탐지의 대상에서 제외하는 것이다.
• 또한 Safety 알고리즘은 Need (현재필요량)을 기준으로 Work보다 작거나 같은지 여부를 확인했지만, 탐지 알고리즘은 Request (요구량) 대해서 계산을 수행한다.
• 반복문을 모두 돌았을 때 모든 i에 대해 Finish가 true가 아니라면 시스템에 교착상태가 존재함을 탐지한 것이다.

교착상태 복구

• 교착상태가 탐지되면 교착상태 복구를 통해 복구한다.
• 교착상태를 복구하는 방법은 두가지가 있다.
• 하나는 순환대기를 깨트리기 위하여 단순히 한 개 혹은 그 이상의 프로세스를 중지시키는 방법이다. 교착상태의 모든 프로세스를 중지시키는 것이 가장 확실하지만, 해당 자료들을 전부 잃게되므로 비용이 커진다. 따라서 교착상태 탐지 알고리즘을 통해 한 프로세스씩 중지시키는 방법을 차용할 수 있는데, 약간의 오버헤드는 감수해야 한다. 이 때 어떤 프로세스를 중지시킬 것인지가 중요한 이슈가 된다. 이를 결정하기 위한 고려사항에는 프로세스 우선순위, 얼마나 오랫동안 프로세스를 수행했고, 얼마나 더 오래 수행될 것인지, 프로세스가 사용한 자원타입과 수 (자원을 선점하기 얼마나 수월한지), 작업을 끝내기 위해 얼마나 더 많은 자원을 필요로 하는지, 복귀하는데 얼마나 많은 프로세스가 포함되어 있는지 (자식 프로세스가 많다면 문제 발생), 프로세스가 대화형인지 일괄처리 인지 등이 포함된다.
• 다른 한가지는 교착상태에 있는 하나 이상의 프로세스들로부터 자원을 'preemption' 즉 선점해 오는 방법이 있다. 선점이 가능해지려면 rollback이 이루어져야 한다. 안정상태가 확인될 때까지 자원을 이동시키면서 rollback 시키고, 그 상태에서 다시 시작하는 것이다. 하지만 이러한 rollback은 안정상태를 결정하기 어렵고 프로세스들의 상태 정보를 더 많이 관리해야 하기 때문에 처리가 어렵다. 따라서 가장 단순한 방법은 앞서 설명한 '중지'이다. 또한 선점방식은 특정 프로세스의 자원만 계속 선점하여 기아상태를 유발시킬 수 있다. 프로세스의 선점횟수를 유한하게 제한하거나 선점당한 횟수를 비용 요소에 반영하는 방식으로 이를 방지할 수 있다.