💡 INTRO

  • 팀과 함께 나름 큰 프로젝트를 진행했다. 또한 추후에 있을 꽤 많은 사람들(약 100명 예상)이 참여하는 데모를 준비했다.
  • 실제 사람들에게 사용되려니 고려해야할 것이 굉장히 많았다.
  • 기능이 제대로 돌아가는 것도 중요하지만 많은 사용자에게 실제로 서비스 될 수 있는지까지 고려해야했다.
  • 따라서 어플리케이션이 실제로 구동되는 OS에 대한 지식이 없이는 어플리케이션의 안정성에 대한 판단력을 가지기 어렵다고 생각했다.
  • 따라서 운영체제 관련 책을 읽고 (추후 업로드 예정) 책에 빠진 부분을 보충하여 학습한다.

🌩 KEYWORDS

  • 교착상태 특징
    • 필요 조건들
    • 자원 할당 그래프 ..
  • 교착상태 처리 방법
    • 교착상태 예방
      • 상호 배제 Mutual Exclusion
      • 점유하여 대기 Hold and Wait
      • 비선점 No Preemption
      • 순환 대기 Circular Wait
    • 교착상태 회피
      • 안전 상태 Safe State
      • 자원 할당 그래프 알고리즘 Resource-Allocation Graph Algorithm
      • 은행원 알고리즘 Banker’s Algorithm
  • 교착상태 탐지 Deadlock Detection
  • 교착상태 회복
    • 프로세스 종료 Process Termination
    • 자원 선점 Resource Preemption

🌩 교착상태 Deadlock

  • 둘 이상의 프로세스 혹은 스레드가 다른 프로세스/스레드가 가지고 있는 자원을 기다리면서 무한대기 루프에 빠지는 것이다.
  • 자원은 I/O 디바이스, CPU cycle, 메모리, 세마포어 등등
  • 예를 들어 바이너리 세마포어 2개가 있는데 2개를 모두 획득해야 임계 영역에 들어갈 수 있다면 교착상태에 빠질 가능성이 생긴다.
    • P0 → P(A); P(B);
    • P1 → P(B); P(A);

발생조건 4가지

  • 상호 배제
    • 한번에 하나의 프로세스만 자원을 사용할 수 있다. 사용하고 싶은 다른 프로세스는 해제할 때까지 기다려야 한다.
  • 점유 대기
    • 자원을 하나 보유하고 다른 프로세스에 할당된 자원을 점유하기 위해 대기하는 프로세스가 존재한다.
  • 비선점
    • 다른 프로세스에게 할당된 자원을 강제로 빼앗을 수 없다.
  • 순환 대기
    • 대기 프로세스의 집합이 순환 형태로 자원을 대기하고 있어야 한다. 즉, 원하는 자원을 이어서 순환 사이클이 만들어진다.
  • 위 4가지를 모두 만족해야지 데드락이 발생한다.

자원 할당 그래프 Resource Allocation Graph

  • 프로세스의 자원 할당 상태를 표현해주는 그래프이다.
  • 각각 프로세스, 자원이 노드로 있으며 프로세스 → 자원 edge는 프로세스의 자원 요청, 자원 → 프로세스 edge는 해당 프로세스의 자원 소유를 뜻한다.
  • 자원 할당 그래프에 사이클이 없으면 데드락이 아니다.
  • 사이클이 있다면 맞을 수도 아닐 수도 있다.

    • 각 리소스 당 하나의 프로세스만 요청을 보내고 있다면 데드락이다.

    • 여러 인스턴스가 요청을 보내고 있다면 데드락 가능성이 있는 것이다.

    • 왼쪽은 데드락, 오른쪽은 데드락이 아니다.


🌩 교착상태 처리 방법

  • 교착상태 예방
    • 자원 할당을 하면서 데드락 발생조건 4가지 중 하나가 일어나지 않도록 하는 것이다.
    • 자원이 소모되고, 성능이 낮아지며, 기아 현상을 겪을 수 있다.
  • 교착상태 회피
    • 자원 요청의 부가적인 정보를 통해 데드락 가능성이 없는 경우에만 자원을 할당한다.
    • 보수적으로 자원을 할당하여 시스템에 비효율적이다.
  • 교착상태 탐지
    • 데드락 발생을 허용하고 탐지가 된다면 데드락을 회복시키는 방법이다.
    • 탐지하는데 오버헤드가 존재한다.
  • 교착상태 무시
    • 데드락을 시스템이 책임지지 않는다.
    • 자주 발생하는 상황이 아니므로 대부분은 os는 데드락 무시를 채택한다.

교착상태 예방

  • 상호 배제
    • 여러 프로세스가 자원을 공유할 수 있다면 데드락이 발생하지 않지만 공유할 수 없는 상황이므로 이 조건을 배제하기는 어렵다.
  • 점유하여 대기 Hold and Wait
    • 프로세스가 자원을 소유하면서 다른 자원을 요청할 수 없도록 한다. 애초에 필요한 모든 자원을 할당받거나 일부를 받지 못한 경우 보유 자원을 모두 반납하고 다시 자원을 요청하도록 한다.
  • 비선점 No Preemption
    • 만일 한 프로세스가 다른 자원을 기다리는 경우 보유된 자원은 선점되도록 한다.
    • 모든 자원을 다 얻을 수 있을 때 해당 프로세스가 시작된다.
    • 상태를 쉽게 저장하고 로딩할 수 있는 자원에서 주로 사용된다. (cpu, memory)
  • 순환대기 Circular Wait
    • 자원에 할당 순서를 정한다. 예를 들어 R1, R2 순서대로 자원을 할당 받도록 한다.

교착상태 회피

  • 안전 상태 Safe State
    • 프로세스가 시작될 때 사용할 자원의 최대 요구량을 알 수 있다.
    • 현재 가용 자원량을 판단하여 프로세스가 요구한 자원최대량 보다 많을 경우에만 프로세스에게 자원을 할당한다.
    • 시스템이 safe state에 있다면 데드락이 없고 unsafe state에 있다면 데드락 발생 가능성이 있는 것이다.
    • 따라서 시스템이 unsafe state에 들어가지 않도록 보장한다.
  • 자원 할당 그래프 알고리즘 Resource-Allocation Graph Algorithm
    • 자원 할당 그래프를 보고 사이클이 생기지 않는 경우에만 자원을 할당한다.
    • 사이클 생성 여부 조사시 O(n^2) 시간이 걸린다.
  • 은행원 알고리즘 Banker’s Algorithm

    • Allocation - 현재 프로세스에 할당된 자원량

    • Max - 프로세스가 요구할 수 있는 최대 자원량

    • Available - 자원당 가용 자원량

    • Need - 프로세스가 현재 추가로 요구할 수 있는 자원량 (Max - Allocation)

    • 아래 그림에서 P1의 Need는 현재 가용 자원으로 할당될 수 있으나, P1의 최대 자원량보다 현재 갸용 자원량이 적으므로 보수적으로 자원을 할당하지 않는다.

교착상태 탐지

  • 데드락이 발생했을 때 그것을 후속처리한다.
  • 탐지하는 방법
    • 만일 자원당 인스턴스가 하나인 경우 → 자원 할당 그래프의 사이클은 데드락이다.
      • wait-for graph 알고리즘 사용
        • 자원 할당 그래프와 비슷한 형태이지만 프로세스만 노드로 구성되어 있다.
        • P0 → P1은 P0이 P1의 자원을 기다리는 경우이다.
        • wait-for graph에 사이클이 존재하는지 주기적으로 조사한다. (O(n^2))
    • 자원당 여러 인스턴스 인 경우 → 은행원 알고리즘과 유사한 방법을 활용한다.
      • 자원을 요청하고 있지 않은 프로세스들이 보유한 자원은 반환된 자원이라고 가정한다.
      • 은행원 알고리즘으로 safe state를 찾아간다. 하지만 safe state를 찾을 수 없다면 데드락이다.
      • 이때 회복을 한다.

교착상태 회복

데드락 회복 2가지 방법

  • Process Termination 프로세스 죽이기
    • 데드락이 걸린 프로세스를 모두 죽인다.
    • 데드락이 풀릴 때까지 프로세스를 하나씩 죽인다.
  • Resource Preemption
    • 비용을 최소화 할 victim을 설정하여 해당 프로세스를 재시작한다.
    • 하지만 동일한 프로세스가 계속 victim으로 선정되면 기아현상이 발생할 수 있다.

교착상태 무시

  • 데드락은 잘 발생하지 않는다.
  • 만일 발생하면 시스템에 이상해지고 사용자가 알아서 프로세스를 죽이도록 한다.
  • 데드락을 예방하고 처리하는 것은 시스템 오버헤드가 존재한다.


[참고링크]