운영체제 스터디 도중 쉽게 배우는 운영체제를 읽고 요약한 내용입니다. 자세한 내용은 책을 구매하여 확인 부탁드립니다.

6. 교착상태

교착 상태의 개요

교착 상태의 정의

프로세스가 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태
두명의 요리사와 두개의 조리 기구가 있고, 각 요리사가 각 조리 기구 하나씩 독점 중에, 서로의 조리기구를 탐하고만 있는 경우에 해당
아사상태 : 운영체제가 잘못된 정책을 사용하여 특정 프로세스의 작업이 지연되는 문제
교착상태 : 여러 프로세스가 작업을 진행하다 보니 자연적으로 일어나는 문제

교착 상태의 발생

시스템 자원, 공유 변수, 응용 프로그램들을 사용 할 때 발생 할 수 있음
시스템 자원
- 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생
- 임계 구역으로 보호되는 프린터, 스캐너, CD 레코더 등 동시에 같이 사용 할 수 없는 시스템 자원을 할당 받은 후 양보하지 않는 경우에 해당
공유 변수
- 한 변수를 할당 받은 상태에서, 다른 변수를 무한정 기다리기만 할 때 교착 상태가 발생
응용 프로그램
- 여러 프로세스가 하나의 데이터베이스에 저장된 데이터를 사용 할 때엔 일관성을 유지하기 위해 잠금을 사용 → 이때 잠금 때문에 교착 상태 발생 가능

자원 할당 그래프

프로세스가 어떤 자원을 사용 중이고, 어떤 자원을 기다리고 있는지를 방향성이 있는 그래프로 표현 한 것
어떤 프로세스에 어떤 자원이 할당되어 있는지 한눈에 파악 가능

출처 : https://wannabe-gosu.tistory.com/26

자원을 사용하고 있는 경우는 자원으로 부터 프로세스로 향하는 화살표 ( 할당된 경우 )
프로세스가 자원을 기다리고 있는 경우는 프로세스로 부터 자원으로 향하는 화살표로 표기 ( 대기하는 경우 )
다중자원
- 여러 프로세스가 하나의 자원을 동시에 사용하면 다중 자원이라고 명
- 다중 자원은 수용 할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표현
- 위에서 R3가 이에 해당하며, 2개의 프로세스를 수용 할 수 있다.
철학자의 식사 문제
- 철학자 네명이 둥그런 식탁에 둘러앉아 식사를 하는 경우를 가정
- 철학자 옆에는, 포크가 하나씩 있고, 철학자는 양 옆의 포크를 모두 쥐어야만 (왼쪽 포크 잡고, 오른쪽 포크 잡아야 )식사 가능
- 이때 모두 왼쪽 포크를 잡고, 오른쪽 포크를 잡으려 할때 모든 포크가 사용중이므로 아무도 식사를 하지 못하는 상황 발생
교착 상태가 발생하는 조건 4가지
- 철학자들은 포크를 공유 할 수 없다
  - 자원을 공유하지 못하면 교착상태가 발생한다.
  - 상호 배제의 조건
- 각 철학자는 다른 철학자의 포크를 뺏을 수 없다
  - 자원을 못뺐으면 자원을 놓을 때 까지 기다려야 하므로 교착 상태 발생
  - 비선점의 조건
  - 빼앗을 수 있으면, 자원이 공유 되므로 교착상태 발생 x
  - 임계 구역에 진입하기 전의 상태와 연관성 있음
- 각 철학자는 왼쪽 포크를 잡은 채 오른쪽 포크를 기다림
  - 자원 하나를 잡은 상태에서 다른 자원을 기다리면 교착 상태 발생
  - 점유와 대기 조건
  - 한 철학자가 두 포크를 모두 점유하거나, 두 자원을 다 기다리는 형태라면 교착 상태에 진입하지 않음
  - 작업을 진행하는 쪽과, 기다리는 쪽의 선 후 관계를 만드는 의미
- 자원 할당 그래프가 원형
  - 자원을 요구하는 방향이 원을 이루면 양보를 하지 않기 때문에 교착상태 발생
  - 원형 대기의 조건
  - 만약 사각형 식탁에서 한줄로 식사를 하면, 교착 상태가 발생하지 않음

교착 상태 필요 조건

상호 배제
- 한 프로세스가 사용하는 자원은 다른 프로세스와 공유 할 수 없는 배타작언 자원이어야 함
- 배타적인 자원은 임계구역으로 보호 되어야 하기 때문에, 다른 프로세스가 동시에 사용 할 수 없다.
비선점
- 한 프로세스가 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없는 비선점 자원이어야 함
- 빼앗을 수 있다면, 자원을 공유 할 수 있게 되므로 교착상태에 들어가지 않는다.
점유와 대기
- 자원을 할당받은 상태에서 다른 자원을 기다리는 상태여야 한다.
- 다른 프로세스가 필요로 하는 자원을 점유하고 있으면서, 또 다른 자원을 기다리는 상태가 되어야 함
원형 대기
- 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야 함
- 원을 이루면, 서로 양보하지 않기 때문에 교착상태에 돌입 가능 - 위의 네가지 조건을 모두 충족해야 교착 상태에 돌입 가능

교착 상태 해결 방법

교착 상태 예방
- 교착 상태를 유발하는 네가지 조건이 발생하지 않도록 무력화 하는 방식
- 위 네가지 조건 중 한가지라도 막는다면 교착상태에 진입하지 않기 때문
- 실효성이 떨어지는 방식
- 상호 배제 예방
  - 독접적으로 사용 할 수 있는 자원을 없애버리는 방법
  - 모든 자원을 공유 할 수 있다면 교착상태에 들어가지 않기 때문
  - 하지만, 현실적으로 상호 배제를 활용하여 보호해야 하는 자원들이 있기 때문에 적용 불가능
- 비선점 예방
  - 모든 자원을 빼앗을 수 있도록 만드는 방법
  - 식사하는 철학자 문제에서, 포크를 빼앗을 수 있도록 하는 방식
  - 상호 배제도 보장할 수 없어지기 때문에 현실적으로 적용 불가능
  - 어떤 기준으로 뺏을지, 얼마나 사용 할 지 등의 설정이 어려울 뿐더러, 설정 하더라도 아사 현상을 일으킬 수 있음
  - 아사현상을 위해 에이징을 사용하면, 교착 상태에 들어갈 수 있는 문제점이 생김
- 점유와 대기 예방
  - 자원을 전부 할당하거나, 아예 할당하지 않는 방식을 적용 하는 것
  - 식사하는 철학자 문제에서, 왼쪽 포크를 잡은 상태에서 오른쪽 포크를 잡을 수 없다면, 포크를 내려 놓도록 명령하면, 교착 상태가 해결 되는 것과 같은 원리
  - 프로세스의 자원 사용 방식을 변화시켜 교착 상태를 처리
  - 단점
    - 실행 후 자원이 추가적으로 필요 할 수도 있기 때문에, 프로세스가 자신이 사용하는 모든 자원을 자세히 알 수 없음
    - 프로세스가 앞으로 사용할 자원까지 모두 선점해 버리기 때문에, 그 자원을 필요로 하는 다른 작업이 진행되지 않음 → 낭비 심함
    - 많은 자원을 사용하는 프로세스는 아사 상태에 빠질 가능성이 있음
    - 하나의 자원을 공유하고 있는 프로세스가 여러개라면, 해당 작업들은 일괄 작업 방식으로 진행 되기 때문에 작업 진행이 매우 비효율적
- 원형 대기 예방
  - 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
  - 식사하는 철학자 문제에서, 원형 테이블이 아닌 사각형 테이블에 직선으로 앉아서 식사하는 방식이라면 교착상태가 일어나지 않는 것과 같은 원리
  - 모든 자원에 숫자를 부여하고, 숫자가 큰 방향으로만 자원을 할당 하는 방식
  - 숫자가 작은 자원을 잡은 상태에서, 큰 숫자를 잡는것은 허용하지만, 큰 숫자의 자원을 잡은 상태에서 작은 숫자의 자원을 잡는것은 허용 하지 않는 방식
  - 단점
    - 프로세스 작업 진행의 유연성이 매우 떨어짐
    - 자원의 번호를 어떻게 부여 할 것인지에 대한 문제 발생
교착 상태 회피
- 자원 할당량을 조절하여 교착상태 해결하는 방식
- 자원을 할당하다가 교착 상태를 유발할 가능성이 있다고 판단되면, 자원 할당을 중단 하는 방식 즉, 어느 수준 이상의 자원을 나누어 주면, 교착 상태가 발생하는지 파악하여 그 수준 이하로 자원을 나누어 주는 방법
- 시스템에 총 20개의 자원이 있을 때, 자원을 하나만 할당 해주면 교착 상태가 발생 할 확률이 낮으나, 자원 20개를 할당 해 주면 교착 상태에 빠질 확률이 높아짐
- 따라서 안정 상태를 유지 할 수 있는 범위 내에서 자원을 할당하므로써 교착 상태를 피함
- 은행원 알고리즘
  - 음식점에 스파게티 10인분, 우동 20인분의 재료가 준비 되어 있을때, 예약 인원을 10명 초과로 받을시 예약 인원 모두가 스파게티를 시키는 경우 문제가 될 수 있음
  - 따라서 10명 이하로만 예약 인원을 잡는다면, 어떤 경우에서도 문제가 생기지 않음
  - 그래서 은행원 알고리즘 에서는, 최악의 경우를 기준으로 잡기 때문에 문제 상황을 철저히 피함
  - 따라서 모든 프로세스는, 자신이 사용할 자원의 최대 수를 운영체제에 알려줘야만 함
  ### [정리]
- 각 프로세스의 기대자원과 비교하여, 가용 자원이 하나라도 크거나 같으면 ( 해당 프로세스를 끝낼 수 있으면 ) 자원을 할당
- 가용 자원이 어떤 기대 자원보다 크지 않으면 ( 가용 자원을 사용하여 마칠 수 있는 프로세스는 존재하지 않기 때문 ) 할당하지 않음
- 안정 상태 → 각 프로세스의 기대 자원과 비교하여 가용 자원이 크거나 같은 경우가 한번 이상인 경우
### [Total = 14 / Available = 2 ]

→ 위의 경우엔, P2가 가용 자원을 사용하여 작업을 마무리 할 수 있으므로, 안정 상태에 해당

### [Total = 14 / Available = 1]

→ 위의 경우엔, 어떤 프로세스도 가용 자원을 사용하여 작업을 마무리 할 수 없으므로, 불안정 상태에 해당
- 문제점
  - 자원을 얼마만큼 할당해야 교착상태가 발생하지 않는다는 보장이 없기 때문에 실효성이 낮음
  - 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 하는데 이는 거의 불가능함
  - 시스템의 전체 자원 수가 고정적 이어야 하는데, 이는 지속적으로 변동 되기 때문에 현실적으로 맞지 않음
  - 실제로 교착 상태가 발생하지 않는데도 발생 할 것이라고 예상 함으로써 프로세스에 자원을 할당하는데 제약을 두기 때문에 자원이 낭비 됨
교착 상태 검출과 회복
- 자원 할당 그래프를 모니터링 하면서, 교착 상태가 발생하는지 살펴보는 방식
- 가장 현실적인 접근 방식
- 타임아웃을 이용한 교착 상태 검출
  - 일정 시간 동안 작업이 진행되지 않은 프로세스를 교착 상태가 발생한 것으로 간주하여 처리하는 방법
  - 대부분의 운영체제에서 이를 채택 ( 가벼운 교착 상태 검출 )
  - DB의 경우엔, 타임아웃으로 데이터의 일관성이 깨질 수 있기 때문에 스냅샷 / 롤백을 통해 일관성을 유지
  - 윈도우 OS의 경우, 시스템 복원을 통해 스냅샷 / 롤백 사용 가능
  - 문제점
    - 타임아웃 시간동안 작업이 진행 되지 않은 모든 프로세스가 교착 상태에 빠진 것은 아니기 때문에, 엉뚱한 프로세스가 강제 종료 될 수 있음
    - 분산형 DB의 경우엔, 하나의 OS에서 모든 프로세스가 진행되는 것이 아니기 때문에, 타임아웃이 발생 했을 때 교착상태 때문인지, 네트워크 오류 때문인지 명확하게 알 수 없음
- 자원 할당 그래프를 이용한 교착 상태 검출
  - 첫번째 그래프
    - 위에서 첫번째 그래프는, P1이 P2가 R2를 다 사용하고 반환하기를 기다리고, P4는 P1을, P3은 P4를 기다리고 있는 상태
    - 사이클이 존재하지 않음 ( 원형 대기 )
    - 따라서 교착 상태가 발생하지 않음
  - 두번째 그래프
    - P2가 R3를 추가로 요구하면, P1 → P2 → P4 → P1로 이어지는 사이클이 존재하기 때문에 교착 상태가 발생 할 수 있다고 판단 → 운영체제는 교착 상태가 발생 했다고 판단
  - 교착 상태를 정확하게 파악 할 수 있다는 것이 장점
  - 자원 할당 그래프를 유지하고, 갱신하고, 사이클을 검사하는 추가적인 작업이 오버헤드 유발 가능
  - 일정 시간마다 검사를 진행하는 방법도 가능
- 교착 상태 회복
  - 교착 상태를 유발한 프로세스를 강제로 종료
    - 교착 상태를 일으킨 프로세스를 모두 동시에 종료
      - 종료된 프로세스들이 동시에 시작된면 다시 교착상태에 빠질 수 있음
      - 다시 실행 할때는 순차적으로 실행 해야 함 ( 그렇지 않으면 교착상태에 다시 빠질 수 있기 때문 )
      - 어떤 프로세스를 먼저 실행 할 것인지에 대한 기준 필요
    - 교착 상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
      - 프로세스 중 하나를 골라 순서대로 종료하면서 나머지 프로세스의 상태를 파악하는 방법
      - 프로세스를 종료 할 때 어떤 프로세스부터 종료 할 것인지 기준 필요
        
        우선순위가 낮은 프로세스 부터 종료
        
        우선순위가 같은 경우 작업 시간이 짧은 프로세스부터 종료
        
        위 두 조건이 같은 경우 자원을 많이 사용하는 프로세스 부터 먼저 종료
- 다중 자원에서의 교착 상태 검출
  - 하나의 자원을 여러 개의 프로세스가 동시에 사용 할 수 있는 경우에는 교착 상태 검출이 복잡
  - 다중 자원의 경우, 사이클이 있다고 해서 모두 교착상태가 되는 것은 아님
  - 이 경우 대기 그래프와 그래프 감소 방법을 이용하여 사이클을 찾음
  - 대기 그래프 → 자원 할당 그래프에서 프로세스와 프로세스간 기다리는 관계만 나타낸 그래프
  - 그래프 감소 → 대기 그래프에서 작업이 끝날 가능성이 있는 프로세스의 화살표와, 관련 프로세스의 화살표를 지워 나가는 작업
  - 위의 경우, R2가 다중 자원에 해당
    1. P2는 기다리는 자원이 없는 프로세스 이므로 P1과 P2가 이어진 화살표를 지움
    2. P2가 끝날 수 있는 프로세스 이므로 P1이 끝날 수 있는 프로세스가 되어 P4와 P1가 이어진 화살표를 지움
    3. P1이 끝날 수 있는 프로세스 이므로 P4가 끝날 수 있는 프로세스가 되어 P4와 P3이 이어진 화살표를 지움
    4. P4가 끝날 수 있는 프로세스 이므로 P3이 끝날 수 있는 프로세스가 되어 P3과 P1이 이어진 화살표를 지움
  → 모든 선분이 지워 졌으므로, 사이클이 존재하지 않는다고 판단하여 교착상태는 일어나지 않는다고 판단
  - 하지만, 위 상태에서 P2가 R3을 기다리고 있는 경우를 추가한다면, P2와 P4가 화살표로 연결되고, 이는 그래프 감소를 할 수 없기 때문에 교착 상태가 발생한다고 판단
  - 즉, 단일 자원만 있는 자원 할당 그래프에서는 사이클 만으로 교착 상태 검출이 가능 하지만, 다중 자원을 사용 할 때에는 그래프 감소를 한 후 사이클이 남아 있는지 확인하여 교착 상태를 검출

"Operation System" 카테고리의 최근 포스팅

카테고리 모든 글 보기

운영체제 스터디 (13) - 네트워크와 분산 시스템	2021. 03. 14
운영체제 스터디 (12) - 파일 시스템	2021. 03. 14
운영체제 스터디 (11) - 입출력 시스템과 저장 장치	2021. 03. 11
운영체제 스터디 (10) - 가상 메모리 관리	2021. 03. 10
운영체제 스터디 (9) - 가상 메모리의 기초	2021. 03. 08
운영체제 스터디 (8) - 물리 메모리 관리	2021. 03. 07
운영체제 스터디 (7) - 교착상태	2020. 12. 04
운영체제 스터디 (6) - 프로세스 동기화	2020. 11. 10
운영체제 스터디 (5) - interrupt	2020. 10. 20
운영체제 스터디 (4) - CPU 스케줄링	2020. 10. 19