교착 상태와 기아 상태

원래벌레·2022년 10월 24일
운영체제
1
post-custom-banner

🌞교착상태

  • 다중 프로그래밍에서 시스템에서 프로세스가 일어나지 않을 사건을 기다리는 상태

  • 시스템 운영자나 사용자가 작업 교체나 종료 등의 외부 간섭으로 해결해야 함
    -> 운영체제가 해결 하는 것이 바람직함

  • 두개 이상의 프로세스가 영향을 받는다.

프로세스의 자원 사용 순서
1. 자원 요청 : 다른 프로세스가 사용 중이면 대기한다.
2. 자원 사용
3. 자원 해제

🌻스풀링 시스템에서의 교착 상태

스풀링
입출력 연산을 위해서 하드디스크에 두는 데이터 버퍼이다.
입출력 장치는 느리고 CPU는 빠르기 때문에 버퍼가 필요하다.

CPU에서 버퍼(디스크)를 거쳐 프린터로 전달될 때 일정량(출력행)씩 전달된다.
즉, 버퍼에 일정량이 모아져야지만 프린터로 전달이 된다.

버퍼에 일정량이 모아지지 않은 상태에서 다른 프로세서로 인해 버퍼가 가득 차게되면, 교착 상태가 발생하게 된다.

🌱스풀링 시스템의 교착상태 예방법

  1. 스풀링 공간을 크게 한다 -> 비용이 증가한다.

  2. 스풀링 공간 사용량에 대한 포화 임계치를 설정한다. -> 시스템 처리량(thoroughput) 감소
    ex) 75% 정도가 차게되면 새 작업을 거부한다.

🌻네트워크에서 발생하는 교착상태🌼

네트워크 시스템에서 붐비거나 입출력(I/O) 버퍼 공간이 부족할 때 메시지 흐름을 제어하는 적절한 프로토콜 없으면, 교착 상태가 발생한다.

N1의 입출력 버퍼가 N6, N7에서 온것들로 꽉 차있고, N2로 나가고자 한다.

N2의 입출력 버퍼가 N3, N4에서 온것들로 꽉 차있고, N1으로 나가고자 한다.

나가려는 쪽의 입출력 버퍼가 서로 막혀 있어서 강제적으로 버퍼가 빌 때까지 대기를 하게 된다. 하지만 버퍼가 비기 위해서는 나가야 하는데, 나가는 방향이 서로이기 때문에 무한정 대기하게 되는 것이다.

🌻멀티스레드 어플리케이션에서 발생하는 교착상태

🌱 코드의 프로세스

  1. 두개의 뮤텍스 first, second를 생성한다.
  2. 두개의 뮤텍스를 각각 초기화한다.
  3. 두개의 함수를 정의한다. 각각은 first, second 뮤텍스를 점유한 이후에, 작업을 수행한다.
  4. 작업을 모두 완료한 이후에는 점유한 first, second 뮤텍스 자원을 해제한다.

🌱 이 코드의 문제점

두개의 스레드는 독립적으로 작업을 수행한다. 이 말은 즉 첫번째 스레드는 work_one을 두번째 스레드는 work_two를 실행하여 컴퓨터는 이 두개의 작업을 동시에 수행한다는 것이다.

이렇게 했을 때 생기는 문제점은 두개의 mutex를 차지해야지만 정상적인 수행이 가능한 이 두 프로세스가 충돌을 하게 된다는 점이다.

work_one 프로세스가 first_mutex 자원을 점유하고, work_two 프로세스가 second_mutex를 점유하게 되면 이 두개의 프로세스는 다른 한쪽의 프로세스가 점유하고 있는 mutex를 점유하지 못하여 무한정 대기를 하게 된다는 것이다.

🌞교착 상태의 발생 조건

🌱 교착 상태의 필요 조건

  1. 상호배제(mutual exclusion)
    -> 한 순간에 한 프로세스만 점유할 수 있는 자원이 있어야 한다.

  2. 점유와대기(hold and wait)
    -> 한 자원을 점유하고, 다른 프로세스가 점유한 자원을 얻으려는 프로세스가 있어야 한다.

  3. 비선점(non-preemption)
    -> 점유된 자원을 강제로 뺏을 수 없어야 한다.
    -> 자원을 점유하고 있는 프로세스가 스스로 점유한 자원을 해제해 주어야만 사용 가능하다.

  4. 순환대기(circular wait)

네가지의 조건이 모두 만족하여야만 교착상태이다.
하나라도 충족되지 않으면 교착상태가 아니다.

조건1~3은 정책이며, 조건4는 이러한 정책에 의해 발생한 결과이다.

교착상태를 회피하기 위해서는 발생조건 1~3의 발생 가능성을 허용하는 것이다.

정답확인 ( 클릭 )

Hold and Wait

순환대기(Circular Wait)

🌞교착 상태의 표현

🌻자원 할당 그래프

G = (V, E)

  1. 정점집합 V
    -> 프로세스 집합(P)과 자원집합(R)으로 구성됨

  2. 간선집합 E
    -> (P, R)나 (R,P)와 같은 연결선

자원 할당 그래프는 방향 그래프이다.
자원의 유형당 하나의 자원을 가지고 있을 때 사이클이 있다면 데드락 상태이다.
즉 위의 경우에는 사이클은 데드락의 필요충분조건이라고 할 수 있다.

🌱 자원의 유형이 다수개 일 때의 자원 할당 그래프

프로세스의 자원의 요청에 대해서는 사각형에 간선을 연결을 하고,
프로세스에 자원이 할당 된 것은 자원박스 안의 원에 간선을 연결을 한다.

정답확인 ( 클릭 )

왼쪽 : Yes, No
오른쪽 : Yes, No

자원 유형에 두개 이상의 자원이 있는 경우에는 사이클이 발생하더라도 교착상태가 발생하지 않을 수 있다.

그렇기 때문에 하나의 자원유형에 여러개의 자원이 있는 경우에는 사이클이 데드락의 필요조건이라고 할 수 있다. (없어서는 안되지만, 꼭 있다고해서 무조건적으로 데드락은 아니다.)

정답확인 ( 클릭 )
왼쪽 :
1. YES
2. 데드락 상태에 빠지게 된다.
3. P1이 수행되고, P2가 수행된다. 정상적으로 모든 프로세스를 완수한다.
4. 존재합니다. P1이 P2보다 먼저 자원을 할당해야 합니다.
5. NO / 자원할당 가능순서가 있다면 교착상태라고 하지 않는다.

오른쪽 :
1. YES
4. YES/ P2->P4->P3->P1, P4->P2->P3->P1
5. NO

정답확인 ( 클릭 )
왼쪽 :
1. NO
2. Pn->Pn-1->...->P2->P1

오른쪽 :
1. YES
2. NO

정답확인 ( 클릭 )
왼쪽 :
1. NO
2. YES/ P6->P1->P4->P5->P3

오른쪽 :
1. NO
2. YES

🌞교착 상태의 해결방법

  1. 무시
    -> 시스템의 제약 강화 보다는 편리성과 효율성을 추구한다.
    -> 발생 가능성이 희박한 데드락을 해결할 때 사용한다
  2. 예방
  3. 회피
  4. 탐지 후 회복

*예방법과 회피법은 절대 데드락 상태로 들어가지 않는다.

🌻예방(Prevention)

-> 교착 상태의 필요조건 중 하나라도 제거를 한다.
-> 자원 이용률이 낮다.
-> 예방 방법은 사이클을 확인한다거나 그런거 없이 교착 상태가 발생하지 못하게끔 만든다.

🌱상호배제 조건 제거

  • 많은 종류의 자원에 적용 불가하다. 상호배제가 꼭 필요 없는 공유 자원에만 적용 가능
    -> 파일(쓰기), 프린터는 불가능 / 파일(읽기)는 가능

🌱점유와 대기 조건 제거(hold and wait)

  • 각 프로세스는 필요한 자원을 모두 한꺼번에 요청, 점유, 해제
  • 자원을 점유하지 않은 상태에서만 자원을 요구한다. 이 경우 자원 이용률이 저하가 되고 기아가 발생할 가능성이 있다.
  • 대화식 시스템에서는 적용이 불가능하다.
    "자신이 사용하려는 모든 자원을 한꺼번에 점유하거나, 그렇지 못할 경우 자원을 모두 반납하는 방법의 단점"
 1.필요한 모든 자원을 미리 파악하기 어렵다.
 2.자원 사용 효율성이 떨어진다. / 나중에 필요한 자원까지 한 번에 점유해야 하기 때문이다.
 3.배치 시스템 처럼 동작하게 된다. / 필요한 자원을 모두 점유한 프로세스가 작업을 끝내야 그 다음 작업이 실행 될 수 있다.
 4.필요 자원이 많은 프로세스가 필요 자원이 적은 프로세스에 비해 불리하다. 이는 자원 사용의 공평성에 위배된다.

🌱비선점 조건 제거(preception)

  • 어떤 자원을 점유한 상태에서 우선순위가 낮으면 점유한 자원을 빼앗기게 된다.
  • 어떤 자원을 점유한 상태에서 다른 자원 요청 시 거부되면, 자원을 반납하고 대기한다.
  • 작업 상태가 쉽게 저장되거나 복귀 될 수 있는 경우에만 적용이 가능하다. 프로세서의 레지스터 같은경우
  • 일반적인 프린터, 카드판독기, 테이프 드라이버와 같은 입출력 장치 자원에는 적용하지 못하는 방법이다.

🌱순환(환형) 대기 조건 제거(circular wait)

  • 모든 자원에 일련번호를 부여 하고, 오름차순으로 자원을 요청하게끔 한다.
  • 자원 요청을 불필요하게 거부하고, 프로세스 R4를 먼저 할당해서 사용하고 R1을 할당받아 사용하려 할 때, R1부터 할당하고 R4를 사용한 후에 R1을 사용해야 하므로 역순으로 자원을 사용하는 경우 오래 전부터 미리 할당 받아 놓아야 한다. 이는 상당한 자원 낭비를 일으킨다.
  • 프로세스 속도가 저하된다.
  • 동일한 자원을 반복적으로 요청 후, 해제함에 따라 프로세스 무한 연기 가능
  • 점유된 자원을 선점하는 것은 일반적으로 롤백을 의미하며 오버 헤드가 매우 비싸다. 이미 실행한 작업의 상태를 잃을 수 있다.

정답

2번

🌞 회피

-> 교착상태 발생 가능성(3가지 필요조건)은 인정하되,
프로세스 시작이나 자원 할당 시에 교착상태를 회피

-> 2가지 회피방법
1. 프로세스 시작 거부
2. 자원 할당 거부

-> 순환 대기만 회피(Mutex, Hold-and-wait, no pre-emptyion) 허용

-> 장점
1. 예방보다 자원 사용률과 처리량 높음
2. 덜 엄격하고 병행성이 높다.

-> 예방과의 차이점
예방과 회피 모두 교착 상태가 발생하지 않지만, 예방의 경우에는 교착 상태를 발생하지 못하게끔 만든 것이고 회피는 이를 허용 하지만 프로세스 시작 전 검사를 통해서 교착상태를 회피한다.

🌻무엇을 통해 회피를 하는가?

🌱프로세스 시작 거부

  • 검사를 하여 교착상태 유발 우려시 프로세스를 시작을 거부한다.
  • 여기서 검사하는 사항은 각 프로세스의 최대 필요 자원 수를 미리 선언하고 검사한다.

프로세스 시작 거부 정책

R : 각 리소스의 유형의 전체 수
C : 프로세스에서 요청 할 리소스의 유형과 그 리소스의 수
A : 프로세스에 할당된 리소스의 유형과 그 리소스의 수
V : 각 리소스 유형의 이용 가능한 수



프로세스를 시작하기에 앞서 위에 요소들을 가지고 검사를 한다.

🌱 자원 할당 거부

  • 할당된 자원 양과 추후 필요량 등을 검사한 후 교착 상태 유발 우려 시 프로세스에 자원 할당 거부
  • 검사를 하여 안전상태와 불안전상태로 나누어 안전 상태이면 할당하고 아니면 거부한다. 이를 은행가 알고리즘이라고 한다.

자원 할당 그래프 알고리즘

  • 안전 상태
    -> 자원을 할당하는 순서가 한가지라도 존재하는 상태
  • 불안전 상태
    -> 안전 상태가 아닌상태 / 교착상태는 불안전 상태에 포함되는 개념

안전상태와 불안전상태의 그림을 보면 Claim 이란 것이 있다. 이는 아직 요청을 보낸 것이 아닌 요청을 보낼 것이라는 상황이다. 요청과는 다르다. 요청은 프로세스 실행이 되어 요청을 정말 보낸 상황으로 할당을 기대받는 상황이다. 이렇듯 자원할당 거부 회피는 프로세스 시작 전 할당된 것은 무엇인지 확인을 하고 요청을 한것은 무엇인지 본 이후에 클레임을 확인하여 클레임이 요청으로 변경되어도 문제가 없는지를 확인한다. 그 결과가 안전상태라면 할당을하고 불안전 상태라면 할당을 하지 않는다.

🌱은행가 알고리즘(자원 할당 거부)

  • 남은 자원량만 충분하면 자원을 할당하고, 할당 후에도 안전상태인지 검사한다.
  • 자원 요청 알고리즘과 안전 알고리즘으로 구성 자원 요청알고리즘을 먼저 진행 한 이후, 안전 알고리즘을 진행한다.

  • 안전상태 일때는 P2 - P0 - P1 - P3으로 자원을 할당을 하면 모든 프로세스의 요청을 처리 할 수 있다.

  • 반면에 불안전 상태의 경우를 보면 어떠한 상황에서도 모든 프로세스의 요청을 처리 할 수 없다.

정답

3번

정답

4 <= A <= 6

은행가 알고리즘을 위한 자료구조


i는 프로세스 번호, j는 자원 유형의 번호

🌱 은행가 알고리즘(자원 요청 알고리즘)

프로세스 Pi가 자원 요청 시 남은 자원량만 충분하면 할당한다.

🌱 은행가 알고리즘(안전 알고리즘)

자원 요청 알고리즘을 끝낸 후, 안전 알고리즘을 통해서 자원 할당 이후에도 안전한 상태인지를 확인한다.

  1. 초기화 : 이용가능한 자원의 수(벡터 형식)를 work 변수에 저장한다.
    Finish 변수는 프로세스가 최대자원을 할당 받고 종료 됐는지를 판별한다.
  2. index에 해당하는 프로세스가 종료 되지 않았고, 필요로하는 자원의 수가 남아있는 자원의 수를 넘지 않는지를 검사한다.
  3. 2번에 해당하는 것을 찾았다면, Work 값에 할당한 자원의 수를 더해주고 종료된 프로세스에 해당하는 index 값의 Finish를 true로 변경해준다.
  4. 모든 프로세스가 다 종료가 됐다면, 안전한 상태임을 return 한다.

정답

P2종료 후 : 1222+4003 = 5225
P0종료 후 : 5225+2011 = 7236
P1종료 후 : 7236+0121 = 7357
P3종료 후 : 7357+0210 = 7567
P4종료 후 : 7567+1030 = 8597

정답

P0의 Need 배열 (001)
P1의 Need 배열 (100)
P2의 Need 배열 (003)

100 -> 211 -> 512 -> P2에서 실패
불안전상태이다.

정답

P0의 Need 배열 (201)
P1의 Need 배열 (100)
P2의 Need 배열 (002)

100 -> 211 -> 502 -> 822
안전상태이다.

정답

P0의 Need 배열 (1012)
P1의 Need 배열 (1000)
P2의 Need 배열 (0031)
P3의 Need 배열 (0030)

1101 -> 2212 -> 2222 -> 불안전
P1 -> P0 -> 실패
불안전 상태이다.

정답

P0의 Need 배열 (1012)
P1의 Need 배열 (1000)
P2의 Need 배열 (0031)
P3의 Need 배열 (0033)

1101 -> 2222 -> 2232 -> 5937 -> 7 10 3 8
P1 -> P0 -> P2 -> P3 -> P4
안전 상태이다.

🌱은행가 알고리즘의 단점

  • 시스템 과부하 : 교착 상태로 안 갈 불안전 상태까지 피함

  • 자원 이용도 낮음 : 합리적인 응답 시간을 보장 못함

  • 실제 적용의 어려움 :
    자원 수의 수시 변동
    프로세스 수의 수시 변동
    프로세스의 최대 자원 필요량 미리 파악 곤란
    프로세스가 종료 될 때 비로서 점유자원들이 해제된다는 가정이 비현실적

정답

3번

🌞탐지 후 회복

  • 이미 교착 상태가 일어난 상황을 탐지하여 회복한다.

  • 예방이나 회피보다 덜 제약적이다.

  • 단점
    1) 교착 상태 탐지 알고리즘 수행 빈도 결정이 어렵다.
    -> 자주 실행하면 알고리즘 수행 비용으로 시스템의 성능이 떨어진다.
    -> 너무 가끔 실행하면 교착 상태로 인한 자원의 유휴 상태가 방치된다.
    2) 회복 비용
    -> 탐지 알고리즘을 위해 필요한 정보를 유지하고 탐지 알고리즘을 실행하는 비용
    -> 교착 상태 회복 자체가 비용이다.

  • 교착상태 탐지의 두가지 유형

-> 자원의 유형당 자원의 수가 하나 일때는 사이클을 탐지하고, 여러개인 경우에는 알고리즘을 이용한다.
-> 타임아웃을 통해서도 탐지를 할 수 있지만, 이는 다른 여러가지 오류에 의해서도 타임아웃이 발생 할 수 있으므로 교착상태만을 탐지하기 위해서 사용 할 수는 없다.

🌻교착 상태 탐지 알고리즘

자료구조

  1. 자원 유형별 할당 가능 수로 이루어진 벡터를 변수 work에 넣는다. 그리고 Finish 배열을 만드는데 자원할당이 하나도 안돼 있으면 데드락 상태를 탐지할 필요가 없기 때문에 Finish 값을 true로 초기화한다. 이 외에 값은 탐지 해야 하므로 false로 초기화한다.
  2. Finish의 값이 false이고 자원 요청량이 work값 안에 들어오는 경우의 index를 찾는다.
  3. 2번의 값에 해당하는 index를 찾았다면 해당 index에 해당하는 work값에 할당되어 있던 자원의 수를 더해주고 Finish는 true로 변경해준다.
  4. 모든 Finish가 true이면 데드락이 아니고, 하나라도 false가 있다면 데드락이다.

-> 은행가 알고리즘중 안전 알고리즘 과의 차이점은 안전 알고리즘은 2번에서 Work와 Need를 비교한다면, 탐지 알고리즘에서는 Work와 Request를 비교한다.
-> 그리고 1번 단계에서 Allocation==0일때에 대해서 finish 값을 true false로 나누는 부분이 다르다. 여기서 Need==0으로 못쓰는 이유는 Need==0은 프로세스가 안전상태 판별 과정에서 제외를 하겠다는 뜻이다. 그런데 이렇게 해주게 되면 다 쓴 자원을 work에 더해주는 작업을 못하게 된다.

정답

🌻교착 상태 회복 방법 2가지

🌱프로세스 강제종료

교착 상태 프로세스 모두 강제 종료

  • 순환 대기를 확실히 해결한다.

  • 자원 사용과 시간 면에서 비용이 크다.

    • 모두 다시 실행 해야됨, 프로세스의 오래 연산한 결과를 폐기할 가능성이 있음

  • 강제 종료가 힘든 경우

    • 프로세스가 파일 업데이트하다가 강제종료되면 해당 파일은 부적절한 상태
    • 프로세스가 인쇄하고 있을 때 강제종료되면 다음 인쇄 전에 프린터의 상태를 복구해야함

  • 보편적으로 많이 사용

교착 상태 프로세스 하나씩 강제 종료

  • 한 프로세스를 강제 종료 할때마다 교착 상태 탐지 알고리즘을 호출

  • 희생자 선택 : 되돌리기 쉬운 프로세스

    • 프로세스 우선순위가 낮은 것
    • 프로세스가 수행된 시간이 짧고 앞으로 수행할 시간이 많이 남은 것
    • 프로세스가 사용한 자원 수와 유형이 선점과 복원이 쉬운 것
    • 프로세스가 앞으로 필요한 자원 수가 큰 것
    • 함께 종료해야 하는 프로세스 수가 적은 것
    • 대화식/일괄식 -> 일괄식을 희생

정답

4번

🌱자원 선점

희생자 선택 : 비용이 적게 드는 자원을 먼저 선점

복귀

  • 자원을 빼앗긴 프로세스를 과거의 안전한 상태로 되돌림
  • 교착 상태에서 벗어날 정도까지만 복귀시키는 것이 이상적임
    • 모든 프로세스이 상태 정보를 유지해야 하는 부담
  • 완전히 복귀시키는 (프로세스 초기상태) 것이 가장 단순한 방법
    • 과거의 안전한 상태를 정확히 알기 어렵기 때문

기아

  • 동일한 프로세스가 항상 희생자가 되면 기아 상태

  • 비용에 복귀 횟수를 포함시키면 해결
    -> 복귀 횟수가 많은 프로세스가 자원을 빼앗기면 비용이 크게 되는 것으로 취급한다.

🌞기아상태

🌻식사하는 철학자 문제

  • 데드락을 설명하는 예제이다.

이 경우 최대 두명까지는 식사가 가능하다. 하지만 모든 철학자들이 왼쪽 포크를 다 집어버리고 대기하는 상태가 되면 데드락 상태가 된다.

정답

semaphore fork[5] = {1};
int i;

while(true) {
	if(P[i] == 4)
    {
    	wait(fork[i+1 % 5]);
        wait(fork[i]);
    }
    else
    {
    	wait(fork[i]);
        wait(fork[i+1%5]);
    }
    식사한다..
    signal(fork[i+1%5]);
    signal(fork[i]);
}
semaphore fork[5] = {1};
int i;

while(true) {
	if(P[i]%2 == 1)
    {
    	wait(fork[i]);
        wait(fork[i+1 %5]);
    }
    else 
    {
    	wait(fork[i+1 %5[);
        wait(fork[i]);
    }
    식사한다..
    signal(fork[i]);
    signal(fork[i+1%5]);
}
profile
원래벌레
학습한 내용을 담은 블로그 입니다.
이전 포스트

MySQL 내장함수

다음 포스트

인덱스

post-custom-banner

0개의 댓글