1. 교착 상태의 정의
1) 교착상태란
- 2개 이상의 프로세스가 다른 프로세스의 작덥이 끝기만을 기다리는 것을 말한다.
- 시스템이 작동하다가 자연스럽게 발생하므로 운영체제가 강제로 해결해 주어야 한다.
2) 교착상태의 발생
- 시스템 자원
- 공유자원
- 응용프로그램
⇒ 위 3가지를 사용할 때 발생한다.
- 시스템 자원
- 교착상태는 공유할 수 없는 자원을 사용할 때 발생한다.
- 이는 동시에 같이 사용할 수 없는 시스템 자원을 할당받은 후 양보하지 않는 경우를 의미한다.
ex) 스캐너, 프린터, CD레코드
- 공유 변수
- 임계구역에서 교착상태가 발생하기도 한다.
- 응용 프로그램
- 데이터 베이스같은 응용프로그램에서도 교착상태가 발생하곤 한다.
3) 자원 할당 그래프
-
프로세스가 어떤 자원을 사용 중이고, 어떤 자원을 "기다리는지" 방향성 있는 그래프로 표시한 것을 자원 할당 그래프이다.
-
프로세스는 원, 자원을 사각형 으로 표시한다.
- 다중자원
: 여러 프로세스가 하나의 자원을 동시에 사용하는 것
- 식사하는 철학자 문제
1) 왼쪽 포크가 사용가능할 때까지 대기, 가능해지면 집어듦
2) 오른쪽 포크가 사용가능할 때까지 대기, 가능해지면 집어듦
3) 양쪽 포크를 잡으면 식사
4) 식사를 마치면 오른쪽 포크를 내려놓음
5) 왼쪽 포크를 내려놓음
· 모두 똑같이 왼쪽 포크를 잡으면, 모든 사람이 오른쪽 포크가 사용가능해질 때까지 대기해야 함
· 식사하는 철학자 문제에서 교착 상태가 발생하는 조건
철학자들은 서로 포크를 공유할 수 없음
각 철학자는 다른 철학자의 포크를 빼앗을 수 없음
철학자는 왼쪽의 포크를 잡은 채 오른쪽 포크를 기다림
자원 할당 그래프가 원형· 한정된 자원을 여러 개의 프로세스가 이용할 때, 어떤 문제가 생길 수 있고 그 문제를 어떻게 풀어야 하는가
· 한정된 cpu의 계산 능력으로 인해 가능한 최소의 메모리로 효율적인 사용을 위한 문제
2. 교착상태의 필요조건
1) 교착상태의 필요조건
- 상호 배제
: 프로세스가 사용하는 자원은 공유할 수 없는 배타적인 자원이어야 한다.
- 비선점
: 프로세스가 사용중인 자원은 중간에 다른 프로세스가 빼았을 수 없는 비선점 자원 이어야 한다.
- 점유와 대기
: 프로세스가 어떤 자원을 할당받은 상태에서 다른 자원을 기다리는 형태이어야 한다.
- 원형 대기
: 프로세스간의 관꼐가 원을 이루어야 한다.
⇨ 교착상태는, 위 4가지 조건이 동시에 모두 충족할때 발생한다.
ex) 식사하는 철학자
3. 교착 상태 해결 방법
1) 교착 상태 해결 방법
-
예방
: 네 가지 조건이 발생하지 않게 최초에 예방한다. -
회피
: 유발 가능성이 있다면 자원 할당을 중지한다. -
검출 및 회복
: 검출 후 회복하는 단계를 가진다.(가장 현실적)
3.1 교착 상태 예방
2) 교착 상태 예방
-
상호 배제 예방
: 모든 자원을 공유할 수 있다면 교착상태가 발생하지 않는다. -
비선점 예방
: 모든 자원을 빼앗을 수 있다면 교착상태를 예방할 수 있다.
⇨ 아사현상이 발생
⇨ 에이징기법을 사용하여도 그 끝에는 비선점 프로세스가 되어 다시 교착상태에 빠질 가능성이 존재
⇨ 1번, 2번 모두 현실적으로 구현하기 어렵다.
3) 점유와 대기 예방
- 전부 할당하거나, 아예 할당하지 않는것을 말한다.
⇨ 프로세스가 시작 초기에 자신이 사용하려는 모든 자원을 한번에 점유하거나, 그렇지 못했다면 모두 반납한다.
⇨ 결과적으로 속도가 빠른 프로세스가 먼저 점유하므로, 먼저 실행된다.
- 문제점
-
프로세스가 자신이 사용하는 모든 자원을 자세히 보기 어렵다.
-
자원의 활용성이 떨어진다.
: 당장 사용하지 않더라도 자원을 미리 선점해 놓기 때문이다. -
많은 자원을 사용하는 프로세스가 불리하다.
⇨ 따라서 아사현상이 발생 할 수 있다. -
결국 일괄작업으로 실행됨
: 자원을 획득한 프로세스가 작업을 끝내야 다른 프로세스가 작업 할 수 있다.
4) 원형 대기 예방
- 프로세스들이 원형을 이루지 못하게 예방하는 것이다.
- 자원을 한 방향으로만 설정한다.
⇨ 모든 자원에 숫자를 부여하여, 숫자가 큰 방향으로만 자원을 할당한다.
- 문제점
-
프로세스 작원의 유연성이 떨어진다.
⇨한방향이기 때문에 순서대로, 혹은 마우스< x < 프린터 사용 후 마우스를 다시 사용할 수 없다. -
자원의 번호를 신중하게 매겨야한다.
3.2 교착상태 회피
-
교착상태가 발생하지 않는 범위 내에서만 자원을 할당하는 방법이다.
-
교착상태가 발생하는 범위에 있으면 프로세스를 대기시킨다.
⇨교착 상태 회피는 할당되는 자원의 수를 조절하여 교착 상태를 회피한다.
(안정/ 불안정 상태)
-
교착상태란 자원을 할당할 때 어느 수준 이상의 자원을 할당하면 교착 상태가 발생하는지 파악해 그 이하로 할당하는 방법
-
시스템의 운영방식에 변경을 가하지 않기 때문에 교착 상태 예방보다 좀 더 유연
-
자원의 총 수와 할당된 자원의 수를 기준으로 안정, 불안정 상태로 나누고 시스템이 안정 상태를 유지하도록 할당한다.
ex) 은행원 알고리즘
: 대출 금액이 대출 가능한 범위 내면 허용되지만 그렇지 않으면 거부되는 것과 유사해 이렇게 불리게 된다.
|은행원 알고리즘의 변수|
-
전체 자원 : 시스템 내 전체 자원의 수
-
가용 자원 : 시스템 내 현재 사용할 수 있는 자원의 수
-
최대 자원 : 각 프로세스가 선언한 최대 자원의 수
-
할당 자원 : 현재 할당된 자원의 수
-
기대 자원 : 앞으로 사용할 자원의 수 (최대자원 - 할당자원 = 기대 자원)
- 안정상태
: 각 프로세스의 기대 자원과 비교하여 가용자원이 크거나 같은 경우가 한번 이상인 경우를 말한다.
<문제점>
-
프로세스가 자신이 사용할 모든 자원을 미리 선언해야 한다.
-
시스템의 전체 자원의 수가 고정적이어야 한다.
-
자원이 낭비된다.
3.3 교착 상태 검출
1) 교착상태 검출이란
-
교착 상태 해결 방법 중 가장 현실적인 방법
-
운영체제가 프로세스의 작업을 관찰하면서 교착 상태 발생 여부를 계속 주시
-
교착 상태가 발견되면 교착 상태 회복 단계를 밞음
2) 타임아웃을 이용한 교착상태 검출
- 타임아웃
: 일정시간 동안 작업이 진행되지 않은 프로세스를 교착상태가 발생한 것으로 간주하는 방법
<문제점>
-
엉뚱한 프로세스가 강제 종료될 수 있다.
-
모든 시스템에 적용할 수 없다.
(DB → X, 네트워크 문제일 수도 있기 때문이다.)
⇨ 따라서 타임아웃을 이용한 방법을, "가벼운 교착 상태 검출" 이라 부른다.
-
데이터베이스의 교착 상태 처리
· 타임아웃으로 데이터의 일관성이 깨지는 문제를 해결하기 위해 체크포인트와 롤백을 사용
· 체크포인트: 작업 시 문제가 발생하면 저장된 상태로 되돌아오기 위한 표시
· 스냅숏: 체크포인트를 설정했을 때 현재의 시스템 상태가 하드디스크에 저장된 데이터
· 롤백: 작업을 하다 문제가 발생해 체크포인트로 되돌아가는 것
3) 자원할당 그래프를 이용한 교착 상태 검출
- 무거운 교착상태 검출 이라 한다.
-
OS는 자원을 요청하거나 할당할 때마다, 자원 할당 그래프를 갱신한다.
-
이 자원 할당 그래프가 원, 즉 "싸이클" 을 이룰때 마다 교착상태가 발생한다.
가. 교착 상태가 없는 자원 할당 그래프
- (a)그래프에 사이클이 존재하지 않기 때문에 프로세스의 작업이 계속 진행되어 교착 상태가 발생하지 않음
나. 교착 상태가 있는 자원 할당 그래프
-
운영체제는 그래프에 사이클이 발생하면 교착 상태가 검출된 것으로 판단함
-
단일 자원을 사용하는 경우 자원 할당 그래프에 사이클이 있으면 교착 상태
-
다중 자원을 사용하는 경우 사이클이 있다고 해서 모두 교착 상태라고 판단할 수 없음
-
자원 할당 그래프를 유지, 갱신, 검사 작업으로 인해 오버헤드가 발생하는 단점
- 교착상태이 회복 (2가지 방법)
- 교착상태를 일으킨 모든 프로세스를 동시에 종료한다.
⇨ 희생이 너무크고, 실행 시 순차적으로 다시 실행하여야 한다.
-
교착상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료
|고르는 기준|
1) 우선순위가 낮은 프로세스
2) 작업시간이 짧은 것
3) 자원을 많이 사용하는 것
⇨ 대화식(회원가입 같은)은 입력할게 많으므로 나중에 종료한다.
- 강제 종료된 프로세스가 실행되기 전에 시스템을 복구해야 한다.
- 명령어가 실행될 때마다 체크포인트를 만들어 가장 최근의 검사 시점을 돌아가는 방식
