[CS] 교착 상태

목차

• 교착 상태란?
• 자원 할당 그래프
• 교착 상태가 발생할 조건
• 교착 상태 해결

 

교착 상태란?

프로세스는 정상적으로 작동하려면 자원이 필요한데 두 개 이상의 프로세스가 각자 갖고 있는

각각의 자원들을 그저 기다리기만 한다면 그 어떤 프로세스도 실행되지 못하고 꽉 막힌 도심처럼 멈춰버리는 현상

 

식사하는 철학자 문제

교착 상태가 왜 발생하는지 교착 상태를 어떤 방식으로 해결할까?

 

• 동그란 식탁에 5명의 철학자가 앉아있다.
• 철학자들 사이사이에는 이 식사에 꼭 필요한 포크가 있다.
• 이 음식을 먹을려면 꼭 2개의 포크가 있어야 한다.

 

 

과연 모든 철학자들이 동시에 이 과정을 반복한다고 했을 때 철학자들은 무사히 이 식사를 마칠 수 있을까요?

• 한 두명의 철학자가 식사한다면 문제가 되지 않지만
• 모든 철학자들이 동시에 이러한 순서대로 식사를 하게 되면 모든 철학자는 평생 생각만 하다 끝난다.

철학자: 프로세스, 스레드

포크: 실행하기 위한 자원

식사: 자원을 이용하는 것(실행)

 

철학자 문제는 '서로가 점거하고 있는 자원을 서로가 기다리고 있을 경우에

그 어떠한 스레드나 프로세스도 실행될 수 없다' 라는 것을 시사하고 있습니다.

 

 

게임과 웹 브라우저라는 프로세스가 동시에 실행 중에 있는데 두 프로세스 모두 자원 A, B가 필요하다고 가정

 

게임은 자원 A를 할당받고 웹 브라우저가 갖고 있는 자원 B를 기다리고 있습니다.

웹 브라우저는 자원 B를 할당받고 게임이 갖고 있는 자원 A를 기다리고 있습니다.

 

=> 이럴 경우 서로가 갖고 있는 자원이 할당 해제될 때까지 무작정 기다릴 수 밖에 없을 것이다.

=> 실행 한번 못하는 상태(교착 상태)

 

교착 상태를 해결하기 위해서는 

• 첫 째, 교착 상태가 발생했을 때의 상황을 정확히 표현해보기
  • 자원 할당 그래프
• 둘 째, 교착 상태가 일어나는 근본적인 이유 이해하기
  • 교착 상태가 발생할 조건

 

자원 할당 그래프

 

교착 상태 발생 조건 파악 가능

• 어떤 프로세스가 어떤 자원을 할당 받아 사용 중인지 확인 가능
• 어떤 프로세스가 어떤 자원을 기다리고 있는지 확인 가능

 

그럼 어떻게 그래프를 그릴까?

 

첫 째, 프로세스는 원으로, 자원의 종류는 사각형을 표현

 

 

둘 째, 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현

 

 

셋 째, 프로세스가 어떤 자원을 할당 받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시

 

 

넷 째, 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표 표시

 

 

교착 상태가 일어난 그래프의 특징?

자원 할당 그래프가 원의 형태를 띄고 있다!

 

 

 

교착 상태가 발생할 조건

교착 상태가 발생할 조건

1. 상호 배제: 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없는 상태
2. 점유와 대기: 자원을 할당 받은 상태에서 다른 자원을 할당 받기를 기다리는 상태
3. 비선점: 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못하는 상태
4. 원형 대기: 프로세스들이 원의 형태로 자원을 대기하는 상태

위 네 가지 조건 중 하나라도 만족하지 않으면 교착 상태가 발생하지 않음

위 네 가지 조건을 모두 만족하면 교착 상태가 발생할 수 있음

 

 

 

교착 상태 해결

• 예방
• 회피
• 검출 후 회복

 

 

교착 상태 예방

• 애초에 교착 상태가 발생하지 않도록
• 교착 상태 발생 조건(상호 배제, 점유와 대기, 비선점, 원형 대기) 중 하나를 없애버리기
• 교착 상태가 발생하지 않음은 보장할 수 있으나 부작용이 따르는 방식

 

상호 배제를 없애면?

• 모든 자원을 공유 가능하게 만든다? => 현실적인 방법은 아님

 

점유와 대기를 없애면?

• 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분
• => 자원의 활용률을 낮출 수 있는 방식

 

비선점 조건을 없애면?

• 선점이 가능한 자원(CPU 같은)에 한해 효과적
• => 모든 자원이 선점 가능한 것은 아니다.

 

원형 대기 조건을 없애면?

• 자원에 번호를 붙이고 오름차순으로 할당하면 원행 대기는 발생하지 않음

 

 

한계

• 자원에 번호 붙이는 것은 어려운 작업
• 어떤 자원에 어떤 번호를 붙이느냐에 따라 활용률이 달라진다.

 

 

교착 상태 회피

• 교착 상태를 무분별한 자원 할당으로 인해 발생했다고 간주(자원은 한정)
• 교착 상태가 발생하지 않을 만큼 조심 조심 할당하기
• 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 만큼만 자원 배분

 

교착 상태 회피

• 안전 순서열: 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서
• 안정 상태: 교착 상태 없이 모든 프로세스가 자원을 할당 받고 종료될 수 있는 상태
  • 안전 순서열이 있는 상태
• 불안전 상태: 교착 상태가 발생할 수도 있는 상태
  • 안전 순서열이 없는 상태

 

예시

• 컴퓨터 시스템에 총 12개의 자원
• 동시에 실행되는 프로세스 P1, P2, P3가 각각 5개, 2개, 2개의 자원을 할당받아 실행 중
  • 운영체제가 배분할 수 있는 자원의 개수는 3개
• 프로세스 P1, P2, P3는 각각 최대 10개, 4개, 9개 자원을 요구할 수 있다고 가정

 

• 안전 순서열이 존재: P2 => P1 => P3
• 안전 순서열대로 할당하면 모든 프로세스 할당 가능

 

 

교착 상태 회피 정리

• 안전 상태에서 안전 상태로 움직이는 경우에만 자원을 할당하는 방식
• 항시 안전 상태를 유지하도록 자원을 할당하는 방식
• 은행원 알고리즘

 

 

교착 상태 검출 후 회복

• 교착 상태의 발생을 인정하고 사후에 조치하는 방식
• 프로세스가 자원을 요구하면 일단 할당, 교착 상태가 검출되면 회복
• 선점을 통한 회복
  • 교착 상태가 해결될 때 까지 한 프로세스씩 자원을 몰아주는 방식
• 프로세스 강제 종료를 통한 회복
  • 교착 상태에 놓인 프로세스 모두 강제 종료(=> 작업 내역을 잃을 위험)
  • 교착 상태가 해결될 때까지 한 프로세스씩 강제종료(=> 오버헤드)

 

 

해당 포스팅에 나온 글과 이미지들은 강민철 저자님의 혼자 공부하는 컴퓨터 구조 + 운영체제의 책과 강의를 참고하여 만들어졌습니다.

책에서 보다 깊게 나오는 내용이 있으므로 한번 구매하고 보셔도 좋을 것 같습니다.

[한빛미디어] 혼자 공부하는 컴퓨터 구조+운영체제