운영체제 6장

1. 교착상태

교착상태: 2개 이상의 프로세스가 다른 프로세스의 작업 끝나기만 기다리며 작업을 진행하지 않는 상태

-> 여러 프로세스가 작업을 진행하다보니 자연 발생적으로 일어나는 문제

 

교착 상태가 발생하는 환경.

시스템 자원

• 교착 상태는 다른 프로세스와 공유할 수 없는 자원을 사용할 때 발생

공유 변수 

• 교착상태는 공유 변수를 사용할 때 발생 ( ex: 임계구역에서 공유하는 변수)

응용 프로그램 

• 데이터베이스 같은 응용 프로그램에서도 교착 상태 발생
• 데이터베이스는 데이터의 일관성을 유지하기 위해 "잠금"을 사용함 -> 잠금으로 인해 교착상태 발생 가능

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

-> 프로세스는 원으로, 자원은 사각형으로

 

다중 자원: 여러 프로세스가 하나의 자원을 동시에 사용하는 경우, 수용할 수 있는 프로세스 수를 사각형 안에 작은 동그라미로 표현

다중자원	식사하는 철학자 문제

2. 교착상태 필요 조건

• 상호배제: 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원이어야 함
• 비선점: 한 프로세스가 사용중인 자원은 중간에 다른 프로세스가 빼았을 수 없는 비선점 자원이어야 함
• 점유와 대기: 프로세스가 어떤 자원을 할당받은 상태(점유)에서 다른 자원을 기다려야 하는 상태(대기)이어야함
• 원형 대기: 점유와 대기를 하는 프로세스 간 관계가 원을 이루어야 함 <- 순환 구조

상호 배제, 비선점 조건: 자원이 어떤 특징을 가지는지 나타냄

점유와 대기, 원형 대기 조건: 프로세스가 어떤 행위를 하고 있는지를 나타냄

 

3. 교착상태 해결 방법(외우지 말고 이해해라)

• 교착상태 예방: 교착상태를 유발하는 네가지 조건이 발생하지 않도록 무력화하는 방식
• 교착상태 회피: 교착상태가 발생하지 않도록 자원 할당량을 조절하여 교착상태를 회피하는 방식
• 교착상태 검출과 회복: 교착상태 검출은 어떤 제약을 가하지 않고, 자원할당 그래프를 모니터링 하면서 교착상태가 발생하는지 살펴보는 방식 -> 교착상태가 발생하면 회복단계가 진행됨

1. 교착상태 예방(이 놈은 그냥 안돼. 다 안돼. 단점은 외우자)

- 상호배제 예방

• 시스템 내에 있는 상호 배타적인 모든 자원(독점적으로 사용할 수 있는 자원)을 없앰 -> 다중자원만 남긴다? 불가능
• 현실적으로 모든 자원을 공유하는 것은 불가능. -> 상호배제를 적용하여 보호해야 하는 자원이 있음
• 상호배제를 무력화하는 것은 사실상 불가능

- 비선점 예방

• 모든 자원을 뻬았을 수 있도록 만드는 방법
• 아사현상이 일어나 비선점 조건을 무력화하기에는 어려움

- 점유와 대기 예방

• 프로세스가 자원을 점유한 상태에서 다른 자원을 기다리지 못하게 하는 방법 -> 대기하지 않도록 함.
• '전부 할당하거나 아예 할당하지 않는' 방식
• 프로세스의 자원 사용 방식을 변화시켜 교착상태를 처리
• But, 프로세스가 자신이 사용하는 모든 자원을 자세히 알기 어렵고, 자원의 활용성이 떨어지고, 많은 자원을 사용하는 프로세스가 적은 자원을 사용하는 프로세스보다 불리함
• 결국, 일괄 작업 방식이랑 다른 게 없음 = 안돼!

- 원형 대기 예방

• 점유와 대기를 하는 프로세스들이 원형을 이루지 못하도록 막는 방법
• 모든 자원에 숫자를 부여하고 숫자가 큰 방향으로만 자원을 할당하는 것
• But, 프로세스 작업 진행에 있어서 유연성이 떨어지고, 자원의 번호를 어떻게 부여할 것인지가 문제.

 

2. 교착상태 회피

- 프로세스에 자원을 할당할 때 어느 수준 이상의 자원을 나누어주면(자원 할당량 조절) 교착상태가 발생하는지 파악하여 그 수준 이하로 나누어 주는 방법

- 교착 상태가 발생하지 않는 범위 내에서만 자원을 할당하고, 교착 상태가 발생하는 범위에 있으면 프로세스를 대기함

-> 할당되는 자원을 조절(자원 할당량 조절)하여 교착상태를 피함.(안정 상태, 불안정 상태)

• 안정 상태: 교착상태가 아닌 상태
• 불안정 상태: 불안정 상태가 크면 교착 상태임 (불안정 상태가 심해지면 교착 상태)

- 자원의 총 수(total)와 현재 할당된 자원의 수를 기준으로 시스템을 안정 상태와 불안정 상태로 나누고, 시스템이 안정 상태를 유지하도록 자원을 할당

- 할당된 자원이 적으면 안정 상태가 크고, 할당된 자원이 늘어날수록 불안정 상태가 커짐

- 교착 상태는 불안정 상태의 일부분이며, 불안정 상태가 커질수록 교착상태가 발생할 가능성이 높아짐

- 교착 상태 회피는 안정 상태를 유지할 수 있는 범위 내에서 자신을 할당 -> 교착상태 피함

할당된 자원의 수 ↓ = 안정 상태

할당된 자원의 수 ↑ = 불안정 상태

은행원 알고리즘 - 교착상태 회피를 구현하는 대표적인 알고리즘

• 전체 자원(Total): 시스템 내 전체 자원의 수
• 가용 자원(Available): 시스템 내 현재 사용할 수 있는 자원의 수 (Available = Total - 할당된 자원)
• 최대 자원(Max): 각 프로세스가 선언한 최대 자원의 수
• 할당 자원(Allocation): 각 프로세스에 현재 할당된 자원의 수
• 기대 자원(Expect): 각 프로세스가 앞으로 사용할 자원의 수 (Expect = Max - Allocation)

-> 각 프로세스의 기대 자원과 비교하여 가용 자원이 하나라도 크거나 같으면 자원을 할당

-> 가용 자원이 여러 기대 자원보다 크지 않으면 할당하지 않음

 

교착상태 회피의 단점

• 프로세스가 자신이 사용할 모든 자원을 미리 선언해야 함
• 시스템의 전체 자원 수가 고정적이어야 함
• 자원이 낭비됨

 

3. 교착상태 검출과 회복

교착상태 검출

• 운영체제가 프로세스의 작업을 관찰하면서 교착상태 발생 여부를 계속 주시하는 방식
• 교착상태가 발견(검출)되면 교착상태 회복 단계를 밟음

타임아웃을 이용한 교착상태 검출

• 일정 시간동안 작업이 진행되지 않은 프로세스를 교착상태가 발생한 것으로 간주하여 처리하는 방법
• 교착상태가 자주 발생하지 않을 것이라는 가정하에 사용, 특별한 알고리즘이 없어 쉽게 구현 가능
• 타임아웃이 되면 프로세스가 종료됨

데이터베이스에서 타임아웃의 문제

• 데이터베이스에서 타임아웃으로 프로세스가 종료되면 일부 데이터의 일관성이 깨질 수 있음
• 데이터의 일관성이 깨지는 문제를 해결하기 위해 체크포인트와 롤백 사용

체크 포인트: 작업을 하다가 문제가 발생하면 저장된 상태로 돌아가기 위한 표시

롤백: 작업을 하다가 문제가 발생하면 과거의 체크 포인트로 돌아가는 것

 

자원 할당 그래프를 이용한 교착 상태 검출

- 단일 자원을 사용하는 경우, 자원 할당 그래프에 사이클이 있으면 교착상태(실선: 할당, 점선: 대기)

교착상태 회복

• 교착상태가 검출된 후, 교착상태를 푸는 후속 작업을 하는 것
• 교착상태 회복 단계에서는 교착상태를 유발한 프로세스를 강제로 종료

강제 종료 방법

1. 교착상태를 일으킨 모든 프로세스 동시 종료
2. 교착상태를 일으킨 프로세스 중 하나를 골라 순서대로 종료

-> 1순위: 우선순위 낮은 경우, 2순위: 작업 시간이 짧은 경우, 3순위: 자원을 많이 사용하는 프로세스를 먼저 종료

 

4. [심화] 다중자원과 사이클

대기 그래프: 자원할당 그래프에서 프로세스와 프로세스 간 기다리는 관계(대기 관계)만 나타낸 그래프

그래프 감소 방법: 대기 그래프에서 끝날 가능성이 있는 프로세스의 화살표와 관련된 프로세스의 화살표를 연속적으로 지워내는 작업

 

다중 자원 사용 시 교착상태가 발생하지 않는 경우 = 대기 그래프에 그래프 감소 방법 적용 결과 모두 없어짐.

 

다중 자원 사용 시 교착상태가 발생하는 경우

- 그래프 감소를 해도 여전히 사이클이 남아있어 교착 상태가 발생 = 끝날 기미가 안보임