HyeJin Yoon

HyeJin Yoon

I’m an ordinary college student.

07 교착 상태

  • 대기 상태\(_{blocked\ /\ asleep state}\)
    • 프로세스가 특정 사건의 발생을 기다리는 상태 (추상적 설명)
    • 프로세스가 원하는 자원의 할당을 기다리는 상태 (구체적 설명)
    • 프로세스가 시스템 자원을 필요로 할 때: 시스템 호출 사용
      • 시스템 호출을 불러서 커널을 사용할 수 있게 함
        • 커널을 통해서 자원을 할당 받음

      • 프로세스 실행 모드: 커널모드로 변환
      • 커널은 프로세스가 요구한 자원의 가용 여부 검사
        • 가용: 자원 확보 및 활용
        • 불가용: 프로세스를 대기 상태로 전환
        • 이후 자원이 가용하면, 커널 → (signal 전송) → 대기 중인 프로세스: wakeup
          • signal 전송: I/O 컨트롤러에서 인터럽트와 관련된 이벤트가 발생하면 CPU에게 알리는 단계
        • 특정 사건 = 프로세스가 요청한 자원의 할당
  • 교착상태\(_{deadlock \ state}\)
    • 두 개 이상의 프로세스들이 (대기상태의 특정한 프로세스만이 발생시킬 수 있는) 이벤트를 무한 대기하는 것
    • 프로세스가 전혀 발생할 가능성이 없는 사건을 기다리는 경우 [대기 상태의 한 종류, wakeup 가능성이 없음]
    • 외부의 개입(OS 또는 시스템 운영자가 강제 종료)에 의해서만 대기상태를 벗어 날 수 있음
    • 교착 상태에 빠진 프로세스는 할당된 자원을 다른 프로세스가 사용하지 못함

  • 교착상태의 예

    • 무기한 연기 상태\(_{starvation}\)

      • 어떤 프로세스가 필요한 자원을 얻기 위해 무한정 기다리는 상태
      • 즉, 교착 상태에 빠진 프로세스는 무기한 연기 상태에 들어가게 된다.

    • 연기 상태에 빠진 프로세스의 자원을 뺏어서 타 프로세스에게 할당하면 해결됨

교착상태를 포함한 프로세스 상태 전이도

자원의 분류

  • 일반적인 자원의 분류
    • 하드웨어 자원
    • 소프트웨어 자원
    • 교착 상태를 설명하기 힘듦
  • 선점 가능성에 의한 분류
    • 선점 가능의 기준

    • 선점가능 자원\(_{preemptible \ resources}\)

      • 선점된 후 복귀시 아무런 문제점이 발생하지 않는 자원
      • 프로세서\(_{processor}\) , 메모리\(_{memory}\) 등

    • 선점불가능(비선점) 자원\(_{nonpreemptible \ resources}\)

      • 자원을 선점하였을 때 이를 선점 당한 프로세스에게 어떤 형태로든 영향을 미치게 되는 경우
      • 자기테이프 장치\(_{tape \ drive}\) , 광학 스캐너, 프린터, 플로피디스크 등
  • 할당 방식에 따른 분류
    • 전체 할당식\(_{total \ allocation}\) 자원
      • 프로세스에 할당될 때 항상 자원 전체를 할당하게 되는 경우
      • 프로세서, 자기테이프 장치 등
    • 분할 할당식\(_{partitioned \ allocation}\) 자원
      • 하나의 자원을 여러 조각들로 분할하고 이렇게 분할된 조각 단위로 프로세스에게 할당할 수 있는 자원
      • 메모리 등
  • 공유 형태에 따른 분류
    • 기준
      • 자원을 여러 프로세스가 할당 받아 [동시에 사용 가능] 여부
    • 배타적(비공유) 할당\(_{exclusive \ allocation}\) 자원
      • 여러 프로세스가 동시에 같이 사용할 수 없는 자원
      • 프로세서, 메모리, 자기테이프 장치, 버퍼, 터미널 등
    • 공유식 할당\(_{sharable \ allocation}\) 자원
      • 여러 프로세스가 동시에 같이 할당 받아 사용할 수 있는 자원
      • 대부분 공유 소프트웨어나 데이터 자원
      • 프로그램(시스템/유틸리티 프로그램 등), 공유 데이터 등
  • 자원의 속성에 따른 분류
    • 순차적 재사용\(_{SR : Serially \ Reusable \ Resources}\) 자원
      • 없어지지 않고 영구적으로 존재하는 자원
      • 한번에 한 프로세스만 안전하게 사용 가능한 자원
      • 프로세서, 메모리, 버퍼, 테이프 장치, 프로그램, 파일 등
    • 소비성\(_{CR : Consumable \ Resources}\) 자원
      • 한 프로세스가 사용한 후 그 자원이 사라지는 형태의 자원
      • 인터럽트, 신호\(_{signal}\) , 메시지 등
  • 교착상태 모델이 고려되는 자원의 일반적인 형태

    • 선점불가능(비선점) 자원\(_{nonpreemptible \ resources}\)

    • 배타적 할당 자원\(_{exclusive \ resources}\)

    • 순차적 재사용 자원\(_{serially \ reusable \ resources}\)

  • 소비성 자원\(_{consumable \ resources}\)을 대상으로 하는 교착상태 모델도 있음

교착상태 예시

  • 2개의 프로세스(P1, P2)
  • 2개의 자원(R1, R2)

그래프 모형(순환 대기)

  • 노드\(_{node}\)
    • 프로세스 노드(Pi), 자원 노드(Rj)
  • 엣지\(_{edge}\)
    • Rj → Pi : 해당 자원이 프로세스에게 할당됨
    • Pi → Rj : 프로세스가 해당 자원을 요청, 대기 중
  • 순환 형태가 된다. = 교착 상태가 된다.

시스템 상태 전이 모델

  • 시스템 상태 전이 모델
    • 프로세스들이 자원에 대해 요구, 할당, 반납이 수행되는 과정에 대한 시스템 상태의 변화 과정 모델 (교착상태 전이 과정 분석을 위해)
  • 가정
    • 2 개의 프로세스, 2 개의 단위 자원
    • 프로세스는 한번에 하나의 단위 자원만을 요청/반납 가능함

  • 각 프로세스의 상태

    • 자원형\(_{resource \ type}\)
      자기테이프 장치(2개)
    • 단위 자원\(_{resource \ unit}\)
      특정 자기테이프 장치

2x2 시스템

  • 프로세스: P1, P2
  • holds: 점유
  • needs: 요청
  • S33은 교착 상태에 빠짐
    • 각 프로세스에 자원이 1개씩 할당된 상태에서 추가로 자원을 1개씩 달라고 요청하기 때문

교착상태 발생원인

  • 4가지 필요조건
  • 다음 4가지 조건이 모두 만족되는 경우에 교착상태 발생됨

    • 상호배제\(_{Mutual \ exclusion}\)

      • 한 번에 한 프로세스만이 자원을 혼자만 사용
      • 자원에 대한 배타적 사용\(_{exclusive \ use}\)

    • 비선점\(_{No \ preemption}\)

      • 자원을 선점하지 못함
      • 선점불가능 자원\(_{nonpreemptible \ resources}\)

    • 점유와 대기\(_{Hold \ and \ wait}\)

      • 자원을 보유한 프로세스가 다른 프로세스에 할당된 자원을 추가로 얻으려고 대기
      • 프로세스에 대한 자원의 부분 할당\(_{partial \ allocation}\) → 추가로 필요한 자원 요청가능

    • 순환대기\(_{Circular \ wait}\)

      • 위 3가지 교착상태의 발생 원인 조건에 의하여 발생 가능
      • 두 프로세스 이상이 순환고리 형태(그래프 모형)
      • 각 프로세스는 고리 안에 있는 다음 프로세스가 점유하고 있는 자원을 대기
      • 환형대기 상태\(_{circular \ wait \ condition}\) 의 발생
  • 위 4가지 원인 중에서 한 가지 조건만이라도 배제 → 교착상태 발생X
    • 4개의 조건이 모두 독립적인 것은 아님 (순환대기는 점유와 대기 조건을 포함하는 개념)

교착상태 해결 기법(교재, 강의자료 참고)

  • 예방, 회피, 검출, 복구 기법

교착상태 예방 기법

  • 교착상태 발생 원인의 조건을 제거
  • 비현실적임
  • 자원에 대한 상호배제 조건 거부
    • 시스템 내의 모든 자원들을 공유 가능하게 하는 방법
      • 하드웨어 특성상 공유가 불가능한 자원 존재 (쓰기 동작의 경우)
    • 불가능
  • 원에 대한 비선점 조건 방지
    • 모든 자원이 선점 가능해야 함
      • 선점 불가능한 자원이 존재하기 때문에 불가능
  • 점유와 대기 조건 방지
    • 프로세스들로 하여금 필요한 모든 자원들을 실행 전에 미리 할당 받도록 하는 기법
      • 무기한 연기 상태 발생 가능
  • 순환대기 조건의 방지
    • 모든 프로세스들은 순서상의 한쪽 방향으로만 자원을 요구하고 할당 받을 수 있도록 하는 기법

교착상태 회피\(_{avoidance}\) 기법

  • 교착상태 예방 기법 보다 덜 엄격한 조건 → 자원의 효율적 이용 목적
  • 항상 시스템 상태를 감시
  • 자원의 할당 과정에서 시스템 상태가 교착상태로 전이될 가능성이 있다고 판단되면 자원 할당을 유보
  • 시스템을 항상 안전 상태로 유도

  • 안전 상태와 불안전 상태

    • 안전 상태의 의미
      • 시스템의 상태가 교착상태로 전이되지 않도록 보장할 수 있음
      • 유한 시간 내에 모든 프로세스를 정상 종료 가능
    • 불안전 상태의 의미
      • 교착상태로의 전이를 피하지 못할 가능성 존재
      • 반드시 교착상태가 발생한다는 의미 아님

Dijkstra의 은행원 알고리즘

  • 교착상태 회피를 위한 간단한 이론적 기법
  • 시스템 내에 자원형이 한 가지만 존재하는 경우
    • 1 resource type, multiple units
  • 시스템의 상태를 항상 안전상태로만 진행 시킴
  • 프로세스의 자원 할당/요청하는 자원의 종류(최대 수)에 대한 정보 필요
  • 은행원이 대출 업무를 수행하는 원리
    • 모든 고객은 계좌를 개설할 때 최대 대출 한도를 명시하여야 한다.
    • 어떠한 고객도 최대 대출 한도를 넘어서 대출할 수 없다.
    • 모든 고객이 대출한 금액의 총액은 은행의 총 대출금을 초과할 수 없다
  • 안전 상태의 예시
    • 한가지 종류의 자원 R, 단위 자원 10개, 프로세스 3개

    • Available resource units : 2
    • 실행 종료 순서 : P1 → P3 → P2
      • 안전 순서\(_{safe \ sequence}\)
    • 현재 상태에서 안전 순서가 하나 이상 존재하면 안전 상태임
  • 불안전 상태의 예시
    • 한가지 종류의 자원 R, 단위 자원 10개, 프로세스 3개

    • Available resource units : 2
    • 안전 순서 : 없음
    • 불안정 상태: 반드시 교착상태로 전이되는 것은 아님
    • 일부 자원을 반납하는 경우, 다시 안전상태로 진입 가능
  • 시스템의 상태를 항상 안전 상태로만 진행
  • 자원을 추가로 요구했을 때, 해당 자원을 할당한 뒤 안전상태인지 검사
    • 안전 상태: 자원할당 승인
    • 불안전 상태: 가용 자원이 남아 있어도 거절, 프로세스 대기, 추후 안전 상태로 전이될 수 있을 때 자원할당 승인

교착상태 검출(탐지) 기법

  • 교착상태 발생에 대비한 어떠한 예비 행동 (예방 또는 회피)도 취하지 않음
  • 교착상태가 발생할 수 있음
  • 주기적으로 또는 필요 시에 교착상태 프로세스 존재 유무 검사 (그래프모델 사용)
  • 실행 시 시스템 성능 감소
  • 검출을 통해 교착상태라고 판단되면 복구 기법을 사용

  • 자원할당 그래프 단순화

  • 실제론 잘 사용하지 않음

교착상태 복구 기법

  • 교착상태가 검출되면, 교착상태의 프로세스를 강제 종료 또는 자원 선점
  • 검출과 복구는 한 세트로 묶임

댓글남기기

참고