ultra_dev
교착 상태 본문
교착 상태란?
대표적으로 식사하는 철학자 문제 예시 존재
철학자들이 원탁 테이블에 앉아있다.
- 계속 생각을 하다가 왼쪽 포크가 사용 가능하면 집어든다
- 계속 생각을 하다가 오른쪽 포크가 사용 가능하면 집어든다
- 왼쪽과 오른쪽 포크를 모두 집어들면 정해진 시간동안 식사를 한다
- 식사 시간이 끝나면 오른쪽 포크를 내려 놓는다
- 오른쪽 포크를 내려 놓은 뒤에 왼쪽 포크를 내려 놓는다
- 다시 1번부터 반복한다.
만약 이렇게 가정한다면 한 두명의 철학자만 식사할 때는 문제가 없지만
모든 철학자들이 동시에 이 순서로 식사를 하게 되면 누구도 식사를 할 수 없음
계속 생각만 하게 됨
왜냐하면
모든 철학자가 왼쪽 포크를 집어들면, 이후 오른쪽 포크를 들 수가 없음!! 오른쪽에 포크가 없으니!!
그래서 모든 철학자는 누군가 포크 내려놓을 때까지 기다리게 돼서 아무도 식사를 할 수 없게 됨
이렇게 일어나지 않을 사건을 기다리며 진행이 멈추는 현상을 교착상태라고 한다.
여기서 철학자를 프로세스나 스레드, 포크를 실행에 필요한 자원, 식사는 실행을 하는 것에 빗댈 수 있다.
예시)
게임과 웹브라우저가 동시에 실행 중인데
둘 다 자원 a,b가 필요한 상황에서
각자 a,b를 할당 받고 있고, 상대방이 가진 자원이 해제되는 것을 기다리는 것이 교착상태의 전형적인 예시
교착상태 해결을 위해서는
- 첫째, 교착 상태가 발생했을 때의 상황을 정확히 표현해보기
- 둘쨰, 교착 상태가 일어나는 근본적인 이유 이해하기
자원 할당 그래프
교착 상태 발생 조건 파악 가능
- 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능
- 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능
그리는 방법
- 프로세스는 원으로, 자원의 종류는 사각형으로 표현
- 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현
- 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시
- 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시
교착 상태가 일어난 자원 할당 그래프의 특징
자원 할당 그래프가 원의 형태를 띄고 있다.
교착 상태 발생 조건
- 상호 배제 : 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
- 점유와 대기 : 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
- 비선점 : 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
- 원형 대기 : 프로세스들이 원의 형태로 자원을 대기하는 상태
위 네가지 조건을 모두 만족하면 교착 상태가 발생할 수 있음
위 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않음
교착 상태 해결 방법
: 예방, 회피, 검출 후 회복
교착 상태 예방
- 애초에 교착 상태가 발생하지 않도록
교착 상태 발생 조건 (상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없애버리기
1. 상호배제를 없앤다면 ?
→ 모든 자원을 공유하게 만들게 되니까 말이 안됨
2. 점유와 대기를 없앤다면?
→ 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
- 자원의 활용도가 너무 떨어진다.
- 지금 당장 자원이 필요한데 활용되지 못하는 프로세스가 생기거나 할당 받지 못해서 오랫동안 대기해야하는 프로세스 생길 수도 있고, 프로세스한테 모든 자원을 할당 했더니 어떤 자원은 별로 사용 안해서 낭비가 될 수도 있음
3. 비선점 조건을 없앤다면?
→ 선점이 가능한 자원(cpu 등)에 한해 효과적
- 하지만 모든 자원이 선점 가능한 것은 아니다!
- 한 프로세스의 작업이 끝날 때까지 다른 프로세스는 이용할 수 없는 자원들도 많음
- 예를 들어 프린트는 한번에 하나의 프로세스만 이용 가능함
4. 원형 대기 조건을 없앤다면? (예방 방법 중 가장 현실적)
→ 자원엔 번호를 붙이고 오름차순으로 할당하면 원형 대기는 발생하지 않음
ex) 식사하는 철학자 문제에서 포크에 번호를 붙이고, 낮은 포크에서 높은 포크만 집을 수 있도록 함
그러면 1번 포크 들고, 2번 들 수있음. 3번들고 4번들 수 있음. 4번 들고 5번들 수 있음.
하지만 5번 들고 1번 들지 못함!!
즉 일렬로 식사하는 것과 같은 효과
단점 :
- 자원에 번호를 붙이는 것은 어려운 작업이다.
- 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다.
예를 들어, 어떤 자원은 많이 활용돼야 하는 자원인데 붙어 있는 번호가 낮아서 많이 활용되지 못할 수 있고
어떤 자원은 잘 안쓰이는 자원인데 번호가 높아서 많이 활용될 수 있음
결론 :
원형 대기 조건을 없애는 방식은 교착 상태를 예방하는 가장 현실적이고 실용적인 방식이지만 위와 같은 단점도 있다!!!
교착 상태 회피
- 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주
- 교착 상태가 발생하지 않을 만큼 조심 조심 할당하기
- 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원 배분
안전 순서열 : 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
ex) 프로세스 a,b,c 동시 실행 중인데 만약 자원을 a→b→c 할당 시 교착 상태 발생하지만, b→a→c 순서로 할당하니 교착 상태가 발생하지 않으면 b→a→c가 안전 순서열이 되는 것!!
안전 상태 : 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태
→ 안전 순서열이 있는 상태를 의미
불안전 상태 : 교착 상태가 발생할 수도 있는 상태
→ 안전 순서열이 없는 상태를 의미
예시)
- 컴퓨터 시스템에 총 12개의 자원이 존재
- 프로세스 P1, P2, P3가 각각 5개, 2개, 2개의 자원을 할당 받아 실행 중
- 운영체제가 배분할 수 있는 자원의 개수는? 3개겠지 (12 - 9)
- 프로세스 P1, P2, P3는 각각 최대 10개, 4개, 9개 자원을 요구할 수 있다고 가정
이 경우 안전 순서열이 존재 : P2 → P1 → P3
정리:
P1 ,10(요구량), 5(사용량)
P2, 4, 2
P3, 9, 2
할당 가능 자원 : 12
할당한 자원 : 9
남은 자원 :3
만약 P1, P2, P3가 모두 최대로 자원을 요구한 최악의 상황을 가정한다면
- P1, P2, P3가 각각 5개, 2개, 7개의 자원을 요구한 상황 가정!!
이때 P2 → P1 → P3 순서로 자원을 할당하면
1.
먼저 P2한테 할당 시,
P2, 4, 4
할당한 자원 : 11
남은 자원 : 1
이후 P2 종료하고 자원 반환
할당 가능 자원 : 12
할당한 자원 : 11 -4 = 7
남은 자원 : 1 + 4 = 5
2.
이제 P1한테 자원 할당 시,
P1, 10, 10
할당한 자원 : 7 + 5 = 12
남은 자원 : 5 - 5 = 0
이후 P3 종료하고 자원 반환
할당한 자원 : 12 - 10 = 2
남은 자원 : 0 + 10 = 10
이후 P3에게 자원 할당하면 됨
이렇게 P2 → P1 → P3 이라는 안전 순서열대로 할당하면 모든 프로세스 실행 가능
이번에는 다른 상황 가정
- 컴퓨터 시스템에 총 12개의 자원이 존재
- 프로세스 P1, P2, P3가 각각 5개, 2개, 3개의 자원을 할당 받아 실행 중
- 운영체제가 배분할 수 있는 자원의 개수는? 2개겠지 (12 - 10)
- 프로세스 P1, P2, P3는 각각 최대 10개, 4개, 9개 자원을 요구할 수 있다고 가정
정리:
P1 ,10(요구량), 5(사용량)
P2, 4, 2
P3, 9, 3
할당 가능 자원 : 12
할당한 자원 : 10
남은 자원 : 2
위 경우는 불완전 상태 → 교착 상태가 발생할 위험 존재
why?
프로세스 P1, P2, P3이 최대로 자원을 요구한 최악의 상황 가정
- P1, P2, P3이 각각 5개, 2개, 6개의 자원을 요구한 상황 가정!!
이 경우 P2에게 자원 2개를 할당하여 작업을 끝내도, 남은 자원으로는 P1의 요구도 P3의 요구도 들어줄 수 없다 (교착상태 발생 위험)
- 남은 자원이 2개니까 P1, P3 프로세스부터 할당 못하고
- 먼저 P2한테 할당 시,
P2, 4, 4
할당한 자원 : 10 + 2 = 12
남은 자원 : 2 - 2 = 0
이후 P2 종료하고 자원 반환
할당 가능 자원 : 12
할당한 자원 : 11 -4 = 7
남은 자원 : 0 + 4 = 4
-> 이제 남은 자원으로는 P1의 요구도, P3의 요구도 들어줄 수 없다 (교착상태 발생 위험)
교착 상태 회피 결론 : 항상 안전 상태를 유지하게끔 자원을 할당하는 방식
- 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식
- 항시 안전 상태를 유지하도록 자원을 할당하는 방식
- ex ) 은행원 알고리즘
교착 상태 검출 후 회복
- 교착 상태의 발생을 인정하고 사후에 조치하는 방식
- 프로세스가 자원을 요구하면 교착 상태 발생하든 말든, 일단 할당하고 이후 교착 상태가 검출되면 회복
- 교착 상태 회복하는 방법은 크게 2가지가 있는데
선점을 통한 회복, 프로세스 강제 종료를 통한 회복
선점을 통한 회복
: 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식
프로세스 강제 종료를 통한 회복
: 교착 상태에 놓인 프로세스 모두 강제 종료 (→ 작업 내역을 잃을 위험)
: 교착 상태가 해결될 때까지 한 프로세스씩 강제 종료 (→ 오버헤드, 교착 상태가 회복 됐나 안됐나 계속 확인해야 하니까..)
교착 상태 무시
: 교착 상태가 드물게 발생한다면, 드물게 발생하는 잠재적 문제는 그냥 무시하자는 것..
타조 알고리즘 (타조는 문제 생기면 땅에 머리묻는다는 유머에서 유래)