CS/운영체제

[4주차] 프로세스 동기화, 교착 상태

mint* 2024. 9. 5. 23:17
728x90

프로세스 동기화

병행성(동시성)에 대해 설명해주세요.

  • 작업이 동시에 실행되는 것처럼 보인다.
    • 싱글 코어 : 시분할 기법(time-slicing)을 사용하여 cpu 시간을 나누어 사용한다.
    • 멀티 코어: 물리적으로 병렬로 동작할 수 있다. (실제 병렬 처리 가능)

 

병행 프로세스

  • 프로세스 여러개가 실제로 동시에 실행되는 것
  • 각 프로세스는 독립적으로 작업을 수행하거나 다른 프로세스와 협력하면서 특정 기능을 수행한다.
    • 병행 프로세스는 제한된 자원을 공유하기 위해 자주 상호작용한다.
    • 상호작용하는 프로세스들은 순서에 맞게 실행되도록 동기화시켜야한다.
  • 영역
    • 진입 영역 : 해당 자원의 임계영역에 들어갈 수 있는지 요청
    • 임계 영역 : 공유 자원 접근 순서에 따라 실행 결과가 달라지는 부분
    • 출구 영역: 임계영역에서 수행을 마치고 나갈 프로세스를 선택하는 부분
    • 잔류 영역: 임계영역을 마치고 나와 수행

 

병렬성에 대해 설명해주세요.

  • 실제로 여러 작업이 동시에 처리되는 것
  • 멀티 코어 프로세서나 분산 시스템에서 구현된다.
병행성은 작업을 동시에 다루는 것에 관한 것이고, 병렬성은 작업을 동시에 실행하는 것에 관한 것이다.

 

 

Race Condition(경쟁 조건)이 무엇인가요?

    • 2개 이상의 프로세스가 공유 자원을 병행해서 읽거나 쓸 때, 자원에 대한 접근 순서에 따라 실행 결과가 달라지는 상황
      • 공유 자원에 최종적으로 남는 데이터의 결과를 보장할 수 없다.

 

Race Condition(경쟁 조건)을 어떻게 해결할 수 있나요?

  • 경쟁 조건(상태)를 방지하려면 병행 프로세스들이 동기화되어 실행되어야한다.
  • 뮤텍스, 세마포어, 락 등을 통해 해결할 수 있다.
    • 뮤텍스 : 공유 자원에 접근할 때 뮤텍스를 이용해 한 번에 하나의 스레드만 접근하도록 한다.
    • 세마 포어: 여러 스레드가 동시에 접근할 수 있는 자원의 수를 제한한다.
    • 락 : 특정 코드 블록을 실행할 때 락을 획득하고 실행 후 해제하는 방식으로 동기화한다.

 

프로세스 동기화에 대해 설명해 주세요.

  • 프로세스들 사이의 수행 시기를 맞추는 것
      1. 실행 순서 제어: 프로세스를 올바른 순서대로 실행하기
      1. 상호 배제: 동시에 접근해서는 안되는 자원에 하나의 프로세스만 접근하게 하기
         -  공유 자원을 동시에 사용하지 못하게 실행을 제어하는 기법
        - 임계 구역을 설정하여 상호 배제한다.

 

Critical Section(임계 구역)에 대해 설명해주세요.

  • 공유 자원에 접근하는 코드 중 동시에 실행하면 문제(경쟁 조건)가 발생하는 코드 영역
    • 프로그램에서 임계자원을 이용하는 부분
      • 임계 자원 : 둘 이상의 프로세스가 공유할 수 없는 자원
    • 공유 자원 접근 순서에 따라 실행 결과가 달라지는 프로그램의 영역
      • 위 그림에서 각 프로세스가 전역 변수를 사용하는 부분(예금 확인->입금->저장)이 임계구역이다.
  • 임계 구역에서는 프로세스들이 동시에 작업하면 안된다.
    • 한 번에 하나의 프로세스만 임계 구역에 진입할 수 있어야 한다.

 

임계구역 문제 : 생산자-소비자 문제

    • 임계구역에 관련된 전통적인 문제이다.
    • 생산자는 물건을 계속 생산해서 버퍼에 넣고, 소비자는 버퍼에서 물건을 계속 가져온다. (공유변수 sum)
    • 생산자와 소비자 코드가 동시에 수행되면 전역 변수 값을 덮어쓰게 되어 실행 순서에 따른 결과 차이(경쟁 조건) 가 발생한다.
      • 임계 구역은 버퍼이다.

 

public class ProducerConsumerProblem {
    private static final int BUFFER_SIZE = 5;
    private static int[] buffer = new int[BUFFER_SIZE];
    private static int in = 0, out = 0;
    private static int counter = 0;

    static class Producer implements Runnable {
        public void run() {
            int nextp = 0;
            while (true) {
                if ((in + 1) % BUFFER_SIZE != out) {  // 버퍼가 꽉 차지 않았는지 확인
                    buffer[in] = nextp;
                    in = (in + 1) % BUFFER_SIZE;
                    counter++;
                    System.out.println("생산: " + nextp + ", Counter: " + counter);
                    nextp++;
                }
            }
        }
    }

    static class Consumer implements Runnable {
        public void run() {
            int nextc;
            while (true) {
                if (in != out) {  // 버퍼가 비어있지 않은지 확인
                    nextc = buffer[out];
                    out = (out + 1) % BUFFER_SIZE;
                    counter--;
                    System.out.println("소비: " + nextc + ", Counter: " + counter);
                }
            }
        }
    }

    public static void main(String[] args) {
        Thread producerThread = new Thread(new Producer());
        Thread consumerThread = new Thread(new Consumer());

        producerThread.start();
        consumerThread.start();
    }
}
생산자-소비자 문제 해결 방법: 상호배제와 동기화가 필요하며 세마포어를 이용해 구현할 수 있다.
  •  

임계 구역 문제 해결 조건

  • 상호 배제 : 한 프로세스가 임계 구역에 들어가면 다른 프로세스는 임계 구역에 들어갈 수 없어야 한다.
  • 한정 대기: 어떠한 프로세스도 임계 구역에 들어가지 못해 무한 대기하지 않아야 한다.
  • 진행의 융통성: 한 프로세스가 다른 프로세스의 진행을 방해해서는 안된다.

 

Mutual Exclusion(상호배제)에 대해 설명해주세요.

  • 한 프로세스가 임계 구역에 들어가면 다른 프로세스는 임계 구역에 들어갈 수 없어야 한다.
    • 임계 구역에 들어가기를 원하는 프로세스는 진입 상호배제를 수행해야한다.
      • 진입 상호배제 : 프로세스 하나가 임계 구역에 있으면 다른 프로세스가 임계영역에 들어가지 못하게 하는 것
      • 출구 상호배제: 임계 구역을 떠나는 프로세스가 다른 프로세스의 진입을 허용하는 것
    • 목적 : 특정 공유 자원을 한 순간에 한 개의 프로세스만 사용할 수 있도록 한다.
      • 프로세스들이 충돌 없는 연산(데이터 읽기 연산)을 수행하는 경우에는 공유 데이터를 동시에 접근할 수 있다.
      • 여러 프로세스가 사용하는 공통 변수나 파일은 각 프로세스가 하나씩 차례대로 읽거나 쓰도록 해야한다.
상호 배제를 수행하면 교착상태와 기아상태가 발생한다.
  •  

Mutual Exclusion(상호배제)를 구현하는 방법은?

  • 검사와 지정, 피터슨, 데커 알고리즘이 있다.
  • 뮤텍스, 세마포어, 모니터 등을 사용할 수 있다.

 

임계 구역 문제를 고려한 코드 설계

상호 배제 조건을 충족하지 않는 경우

  • 새롭게 임계구역을 진입하는 프로세스는 잠금을 걸고 작업을 하며, 작업을 마치면 다른 프로세스가 사용할 수 있도록 잠금을 해제한다.

  • lock=true로 설정 직전, 문맥교환이 발생하면 둘 다 임계구역에 진입하게 된다.

 

한정 대기를 충족하지 않는 경우

  • 임계 구역에 진입하기 직전에 잠금을 설정하고, 다른 프로세스가 잠금을 설정하지 않았다면 임계구역에 진입한다.

  • lock=true 후 문맥 교환이 발생하면 둘 다 임계구역에 진입하지 못하고 무한 대기하는 상황이 발생한다.
  • 교착 상태(프로세스가 살아있으나 작업이 진행되지 못하는 상태)가 발생한다.

 

진행의 융통성 문제

  • 공유 변수 lock을 통해 다른 프로세스가 임계구역에 없으면 진입한다.
  • 문제: 서로 번갈아가면서 실행된다.
    • 프로세스의 우선순위에 상관없이 번갈아 진행하기때문에 한 프로세스가 다른 프로세스의 진행을 방해한다.

 

하드웨어로 해결하는 방법: 검사와 지정 (test-and-set)

  • 임계 영역에 진입하기 전에 플래그를 검사하고 설정하는 방식이다.
  • 하드웨어 지원을 받아 while(lock==true) : 잠금 검사 와 lock=true: 검사 후 잠금 설정 문을 한꺼번에 실행한다.
    • 명령어 실행 중간에 타임아웃이 걸려 임계구역을 보호하지 못하는 문제가 발생하지 않는다.
  • 임계 구역 문제를 해결할 수 있다.
  • 편리하지만 바쁜 대기를 사용하여 검사하므로 자원 낭비가 발생한다.

 

피터슨 알고리즘

  • 두 프로세스 간의 상호 배제를 보장하는 알고리즘
  • lock1, lock2와 turn 공유 변수를 사용한다.
    • 임계구역에 진입하기 전에 잠금을 걸고 turn을 설정한다.
    • turn은 두 프로세스가 동시에 잠금을 걸고 임계구역에 못들어가는 상황에 대비하기 위한 장치다.
  • 임계 구역 문제의 3가지 조건을 모두 만족하지만 2개의 프로세스만 사용가능하다는 한계가 있다.

 

데커 알고리즘

  • 잠금을 걸고 다른 프로세스도 동시에 잠금을 걸었다면 차례(turn)을 확인한다.
  • 임계 구역 문제의 3가지 조건을 모두 만족하지만 프로세스가 늘어나면 변수도 늘어나고 전체 알고리즘도 복잡해진다.

 

피터슨 vs 데커 

  • 피터슨 알고리즘 : 조건 검사 전 turn 값을 상대방에게 먼저 넘겨준다.
  • 데커 알고리즘 : 임계 영역 실행 후 turn 값을 상대방에게 넘겨준다.
  • 공통점 : 소프트웨어적으로 상호 배제를 구현한 알고리즘

 

피터슨과 데커 알고리즘은 구조가 복잡하여 현재 잘 사용되지는 않는다.

 

 

뮤텍스(Mutex)에 대해 설명해주세요.

  • 하나의 공유 자원에 접근하는 프로세스들을 위한 동기화 도구
  • 임계 구역을 잠금으로써 프로세스 간의 상호 배제를 이룬다.
    • lock : 자물쇠 역할, 프로세스들이 공유하는 전역 변수
    • acquire : 임계 구역이 잠겨있는지 확인하고 열려 있다면 잠그는 역할
    • release : 임계 구역의 잠금을 해제하는 역할
  • 임계 구역이 잠겨 있는지를 반복적으로 확인하는 바쁜 대기를 수행한다.

 

세마포어에 대해 설명해주세요.

기존 임계구역 문제 해결 알고리즘의 문제점

  • 앞서 살펴본 임계구역 문제 해결 알고리즘은 바쁜 대기를 사용하여 자원을 낭비하거나, 알고리즘이 너무 복잡하다.
    • 세마포어는 간단하고 사용하기 쉽다.

 

뮤텍스 vs 세마 포어

  • 뮤텍스 : 하나의 공유 자원에 접근하는 프로세스를 상정한 동기화 도구
  • 세마 포어: 공유 자원이 여러 개 있을 경우에도 적용이 가능한 동기화 도구

 

세마포어란?

    • 공유 자원이 여러 개 있는 임계 구역 문제도 해결할 수 있는 동기화 도구

 

    • 프로세스가 임계구역에 진입하기 전에 사용중이라고 표시하고(P()) 임계구역에 들어간다.
    • 프로세스가 작업을 마치고 임계구역을 나올때 비었다고 표시한다. (V())
      • 세마포어는 다음 프로세스에 임계구역을 사용하라는 동기화 신호를 보낸다.
임계 구역 문제를 해결하는 간단하고 사용하기 쉬운 알고리즘이다.
  •  

작동 과정

    • Semaphore(n) : 현재 사용 가능한 자원의 수(n)가 저장된다.
    • P() 연산 (또는 wait()) : 잠금을 수행하는 코드로, RS가 0보다 크면 1만큼 감소시키고 임계구역에 진입하며 0보다 작으면 대기한다(block()).
      • wake_up() 신호를 보낼때까지 대기한다.
    • V() 연산 (또는 signal()) : 잠금 해제와 동기화를 수행하는 코드로, RS 값을 1 증가시키고 세마포어에서 기다리는 프로세스에 임계구역에 진입해도 좋다는 wake_up() 신호를 보낸다.
      • 대기하는 프로세스는 세마포어 큐에 저장되어 있다가 wake_up() 신호를 받으면 큐에서 나와 임계구역에 진입한다.
P()와 V()의 내부 코드는 검사와 지정을 사용하여 완전히 실행되도록 구현한다.
  •  

 

상호 배제를 위한 큐와 조건 변수에 대한 큐는 다르다.

  • 상호 배제를 위한 큐 : 모니터에 진입하기 위해 삽입된다.
  • 조건 변수에 대한 큐 : 실행이 중단된(대기하는) 프로세스들이 삽입된다.

 

세마포어를 이용해 임계 구역 보호하기

 

세마포어는 공유 자원이 여러개일때도 사용할 수 있다.

  • 2개의 공유자원에 대해 3개의 프로세스가 작업하는 상황

 

뮤텍스(Mutex)와 이진 세마포어의 차이에 대해 설명해주세요.

  • 뮤텍스는 소유권 개념이 있고, 이진 세마포어는 소유권 개념이 없다.
    • 뮤텍스 : 락을 획득한 스레드만이 락을 해제할 수 있다.
    • 이진 세마포어: 어떤 스레드라도 락을 해제할 수 있다.

 

모니터에 대해 설명해주세요.

세마포어의 문제점

  • 세마포어는 잘못 사용할 경우 임계구역을 보호하지 못하는 문제가 있다.
    • 프로그래머가 실수로 P()나 V() 연산을 누락하거나 잘못된 순서로 사용할 경우 심각한 동기화 문제가 발생할 수 있다.

 

모니터

  • 공유 자원을 사용할 때 임계구역 보호와 동기화를 자동으로 처리하는 고수준의 동기화 도구
  • 공유 자원을 내부적으로 숨기고 공유 자원에 접근하기 위한 인터페이스만 제공한다.
    • 세마포어의 P()와 V()를 직접 사용할 필요가 없다.
    • 임계구역의 보호와 프로세스의 동기화가 모니터 내부에서 처리되므로 사용자는 인터페이스의 메서드만 호출하면 된다.
  • 세마포어에 비해 사용자가 사용하기 편리한 동기화 도구
    • 조건 변수를 사용한다.
모니터는 세마포어의 단점을 보완하고 더 안전하고 편리한 동기화 메커니즘을 제공한다.

 

작동 과정

  • 임계 구역에 접근하고자 하는 프로세스는 직접 P()나 V()를 사용하지 않고 모니터에 작업 요청을 한다.
  • 모니터는 요청받은 작업을 모니터 큐에 저장한 후 순서대로 처리하고 그 결과만 해당 프로세스에 알려준다.

 

모니터 내부 코드 예시

public class SharedBalanceMonitor {
    private int balance = 10;  
    private boolean busy = false;

    public synchronized void increase(int amount) {
        while (busy) {
            try {
                wait();  // 큐에서 기다림
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }

        busy = true;
        balance = balance + amount;
        busy = false;
        notify();  // 다음 프로세스 깨움
    }

    public synchronized void decrease(int amount) {
        while (busy) {
            try {
                wait();  // 큐에서 기다림
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }

        busy = true;
        balance = balance - amount;
        busy = false;
        notify(); // 다음 프로세스 깨움
    }

    public synchronized int getBalance() {
        return balance;
    }

    public static void main(String[] args) {
        SharedBalanceMonitor monitor = new SharedBalanceMonitor();

        Thread increaseThread = new Thread(() -> {
            for (int i = 0; i < 5; i++) {
                monitor.increase(10);
                System.out.println("New balance: " + monitor.getBalance());
            }
        });

        Thread decreaseThread = new Thread(() -> {
            for (int i = 0; i < 5; i++) {
                monitor.decrease(5);
                System.out.println("New balance: " + monitor.getBalance());
            }
        });

        increaseThread.start();
        decreaseThread.start();
    }
}

 

교착 상태

데드락(교착 상태)이 무엇인가요?

  • 2개 이상의 작업이 동시에 이루어지는 경우, 다른 작업이 끝나기만 기다리며 작업을 더이상 진행하지 못하는 상태
  • 시스템 자원을 사용하거나 잠금을 사용할 때 발생한다.
    • 시스템 자원 사용 : 공유할 수 없는 자원을 할당받은 후 양보하지 않은 경우
    • 잠금 : 한 변수를 할당받은 상태에서 다른 변수를 기다리면 교착 상태가 발생한다.

 

아사현상(기아현상) vs 데드락

  • 아사현상 : 잘못된 정책으로 특정 프로세스의 작업이 지연되는 문제
  • 데드락: 여러 프로세스가 작업을 진행하다보니 발생하는 자연적인 현상
    • 교착 상태가 발생하면 강압적으로 해결해야한다.

 

자원 할당 그래프

  • 어떤 프로세스가 어떤 자원을 사용하고 있고, 어떤 자원을 기다리고 있는지 표현하는 그래프
  • 규칙
    • 프로세스는 원으로, 자원의 종류는 사각형으로 표현한다.
    • 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현한다.
    • 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다.
    • 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.
  • 교착 상태는 자원 할당 그래프를 통해 표현할 수 있다.

 

데드락(교착 상태) 발생 조건 4가지를 설명해 주세요.

  • 상호 배제, 비선점, 점유와 대기, 원형 대기의 네가지 조건을 동시에 만족해야만 교착 상태가 발생한다.

 

상호 배제(교착 상태)

  • 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야한다.
    • 임계 구역으로 보호되므로 다른 프로세스가 동시에 사용할 수 없다.

점유와 대기

  • 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야한다.

비선점

  • 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야한다.

순환(원형) 대기

  • 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야한다.

 

데드락(교착 상태)을 막는 방법에 대해 설명해주세요.

  • 교착 상태를 해결하는 방법은 예방, 회피, 검출 이며 자원을 회복 하는 방법도 있다.

 

교착 상태 예방

  • 교착 상태를 유발하는 4가지 조건을 무력화한다.
  • 실효성이 적어 잘 사용되지 않는다.

상호 배제 예방

  • 시스템 내의 모든 자원을 공유하도록 하면 된다.
  • 하지만 현실적으로 모든 자원을 공유할 수 없으며 상호 배제를 적용하여 보호하는 자원이 있다.
    • 시스템 내에는 공유할 수 없는 자원이 있다.
  • 상호 배제를 무력화하는 것은 사실상 어렵다.

 

비선점 예방

  • 모든 자원을 빼앗을 수 있게 만드는 방법이다.
  • 임계 구역을 보호하기 위해 잠금을 사용하면 자원을 빼앗을 수 없을 뿐만 아니라 상호 배제도 보장할 수 없다.
  • 선점은 아사 현상을 일으킨다.
  • 비선점을 무력화하는 것은 사실상 어렵다.

 

점유와 대기 예방

  • 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법이다.
    • 전부 할당하거나 아예 할당하지 않는 방식을 적용한다. (all-or-nothing)
  • 프로세스는 시작 초기에 자신이 사용하려는 모든 자원을 한꺼번에 점유하거나, 그렇지 못할 경우 자원을 모두 반납해야한다.
  • 단점
    • 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵다.
    • 자원의 활용성이 떨어진다.
    • 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리하다.
    • 결국 일괄 작업 방식으로 동작한다.

 

원형 대기 예방

  • 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법이다.
    • 자원을 한 방향으로만 사용하도록 설정함으로써 원형 대기를 예방할 수 있다.
  • 단점
    • 프로세스 작업 진행에 유연성이 떨어진다.
    • 자원을 한 방향(숫자가 큰 방향으로만)으로 할당하므로 자원 사용에 제약이 따른다.

 

교착 상태 예방 정리

    • 자원을 보호하기 위해 상호 배제와 비선점을 예방하기 어렵다.
    • 점유와 대기, 원형 대기는 프로세스 작업 방식을 제한하고 자원을 낭비하기 때문에 사용할 수 없다.
교착 상태 예방은 실제로 구현하기 어렵다.

 

교착 상태 회피

  • 교착 상태가 발생하지 않는 수준으로 자원을 할당한다.
    • 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면 자원 할당을 중단하고 지켜본다.
  • 자원을 얼마만큼 할당해야 교착 상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 적다.

 

안정 상태와 불안정 상태

  • 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나눈다.
    • 할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어날수록 불안정 상태가 커진다.
    • 불안정 상태가 커질 수록 교착 상태가 발생할 가능성이 높아진다.
  • 안정 상태를 유지할 수 있는 범위 내에서 자원을 할당함으로써 교착 상태를 피한다.

 

은행원 알고리즘

  • 자원의 총수와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고, 시스템이 안정 상태를 유지하도록 자원을 할당한다.
  • 은행이 대출을 하는 방식과 유사하기 때문에 은행원 알고리즘이라 불린다.
    • 은행은 대출 금액이 대출 가능한 범위 내(안정 상태)이면 대출하고, 그렇지 않으면 거부한다.
  • 용어
    • 가용 자원: 시스템 내 현재 사용할 수 있는 자원의 수 (전체 자원-전체 프로세스 할당 자원)
    • 최대 자원: 각 프로세스가 선언한 최대 자원의 수
    • 할당 자원: 프로세스에 현재 할당된 자원의 수
    • 기대 자원: 각 프로세스가 앞으로 사용할 자원의 수 (최대 자원-할당 자원)
  • 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당한다.
  • 안정 상태 : 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한번 이상인 경우

  • 불안정 상태 : 현재 남은 자원으로는 어떤 프로세스도 끝낼 수 없다.

 

교착 상태 문제

    • 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
    • 시스템의 전체 자원 수가 고정적이어야 한다.
      • 실제로는 새로운 자원이 추가되거나 일시적인 고장이 빈번하므로 시스템의 자원 수가 유동적이다.
    • 자원이 낭비된다.
      • 모든 불안정 상태가 교착 상태가 되는 것은 아님에도 불구하고 자원을 할당하지 않는 것은 낭비이다.
교착 상태 회피는 구현할 수는 있지만 자원을 낭비하는 문제가 있다.
  •  

교착 상태 검출과 회복

  • 교착 상태 검출 : 자원 할당 그래프를 사용하여 교착 상태를 발견한다.
    • 교착 상태가 발생하면 교착 상태 회복 단계가 실행된다.
  • 교착 상태 회복 : 교착 상태를 검출한 후 해결한다.

 

교착 상태 검출

  • 타임아웃 이용
    • 일정 시간동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리한다.
    • 문제
      • 교착 상태가 아닌 다른 이유로 작업이 진행되지 않은 엉뚱한 프로세스가 강제 종료될 수 있다.
      • 모든 시스템에 적용할 수 없다.
        • 분산 데이터베이스라면 네트워크 문제로 작업이 진행되지 않을 수도 있다.
    • 작업이 간단하여 대부분의 데이터베이스나 운영체제에서 선호한다. (가벼운 교착상태 검출)
  • 자원 할당 그래프 이용
    • 사이클이 존재하면 운영체제는 교착 상태가 발생한 것으로 판단한다.
    • 자원 할당 그래프를 유지하고 갱신하고 사이클을 검사하는 추가 작업으로 인해 오버헤드가 발생한다. (무거운 교착상태 검출)

 

교착 상태 회복

  • 선점을 통한 회복: 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식이다.
  • 프로세스 강제 종료를 통한 회복: 교착 상태를 유발한 프로세스를 강제로 종료한다.
      1. 교착 상태를 일으킨 모든 프로세스를 동시에 종료
      1. 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

 

+ 교착 상태 무시 (타조 알고리즘)

  • 교착 상태를 아예 무시하는 방법

 

728x90