운영체제 기술면접 준비4: 임계구역, 교착상태

오늘은 임계 구역과 상호배제에 대하여 알아보자 

 

 

임계 구역(Critical Section) = 임계 지구(지역/영역) 

• 다중 프로그래밍 운영체제에서 한순간에 여러 개의 프로세스에 의하여 공유되는 데이터 및 자원 
• 동시 접근에 따른 문제를 방지하기 위하여 지정된 영역 
• 임계 구역은 서로 동시 접근과 독점할 수 없음 
• 임계 구역을 접근할 때에는 반드시 가용 상태를 확인해야 함

 

상호배제(Mutual Exclusion) 

• 다른 프로세스가 현재 사용중인 임계 구역(공유 자원)에 대하여 접근을 금지하는 행위 
• 공유 자원에 대하여 사용 중일 때 다른 프로세스들이 사용하지 못하도록 배제 

 

상호배제 관련 알고리즘

• 인터럽트 불능 처리

• 잠금(Lock / Unlock)

• 엄격한 교대(Dekker)

• TSL(Test and Set Lock)

• 세마포어(Semaphore)

• 모니터(Monitor) 등

 

위와 같은 알고리즘들이 있고 아래에서 좀더 자세하게 살펴보자 

 

---

Semaphore

 

• E.J. Dijkstra에 의해 고안된 프로세스간 상호배제 및 동기화 문제 해결 방법 
• 공유 자원에 대하여 동시 접근을 막음 
• P(S), V(S) 연산을 통해서 프로세스 사이의 동기를 유지하고 상호배제의 원리를 보장

                   • V(S) 연산: 대기중인 프로세스를 깨우는 신호를 보냄 => 가용 상태

                   • P(S) 연산: 프로세스들의 진입 여부를 결정 => 대기동작

 

 

Monitor 

• 공유 자원을 내부로 숨김 
• 외부 접속을 차단 
• 자료 추상화 및 정보 은폐의 개념을 기초적으로 사용 ex 객체지향 언어의 private 
• 인터페이스를 통해 공유 자원 갱신 및 데이터 추출 
• 모니터의 경계에서 상호 배제가 시행됨

 

 

---

 

교착상태 == Dead Lock 

• 2개 이상의 프로세스가 서로 다른 프로세스의 작업이 끝나기만 기다리며 작업을 더 이상 진행하지 못하는 상태 
• 병렬처리 기술과 자원 공유에 따라 발생된 부작용 중의 하나                                                                                                                    • 여러 프로세스가 작업을 진행하다 보니 자연 발생적으로 일어나는 문제 
• 아사(기아) 현상 : 특정 프로세스의 작업이 끊임없이 지연되 는 문제

 

교착상태 필요조건

상호 배제(mutual exclusion)

• 한 프로세스가 사용하는 자원은 다른 프로세스와 공유할 수 없는 배타적인 자원 

 

비선점(non-preemptive)

• 사용 중인 자원은 중간에 다른 프로세스가 빼앗을 수 없어야 함 

 

점유와 대기(hold and wait)

• 프로세스가 어떤 자원을 할당 받은 상태에서 다른 자원을 기다리는 상태 

 

순환(환형) 대기(circular wait)

• 점유와 대기를 하는 프로세스 간의 관계가 원을 이루어야야 함

 

 

 

---

이러한 교착상태를 해결하는 방안은 크게 3가지가 있다

 

교착상태 해결 방안 

• 예방(Prevention)
• 회피(Avoidance)
• 회복(Recovery)

 

 

예방(Prevention)

• 사전에 조치를 취하는 방안 => 성능 하락, 자원 낭비가 가장 큼

• 교착상태 발생의 네 가지 조건 중 하나를 제거

 

– 상호 배제 제거:

» 단일 프로그램 운영

» 자원을 독립적으로 사용하여 임계 구역을 없앰

 

– 비선점 제거 => 선점 인정

» 점유되어 있는 자원을 언제든 빼앗을 수 있도록 함

 

– 점유와 대기 제거 => 대기 제거

» 어떤 프로세스가 더 이상 요구가 수용되지 않는다면, 원래 갖고 있는 것을 반납

 

– 환형 대기 제거 => 선형 대기로 변환

» 각 자원 유형별로 할당 순서를 부여

 

 

 

 

회피(Avoidance)

• 시스템의 상태를 계속 감시

• 자원의 요청이 있는 프로세스에 대하여 Dead Lock 상태가 될 가능성이 있는 경우 요청을 보류

• 시스템을 항상 Safe State로 유지

 

• 상태:

– Safe State

» 모든 프로세스가 정상적으로 종료가 가능한 상태

 

– Unsafe State

» Dead Lock 상태가 될 가능성이 있음

» 꼭 발생한다는 의미는 아님

• 일례로: 은행원(Banker’s) 알고리즘이 있음

은행원 알고리즘(Dijkstra’s Algorithm) 

Dead Lock 회피(avoidance)를 위한 간단한 이론 적 기법 

Dijkstra가 제안한 알고리즘 

프로세스가 요구한 자원의 수가 현재 가용한(남은) 자원의 수보다 작을 때 할당



가정

• 한 종류(type)의 자원이 여러 개(unit) 

시스템을 항상 safe state로 유지

간단함 1.현재 자원을 모두 더함 10 + 50 + 20 = 80임 그리고 자원개수(100) 을 빼줌 

=> 20이 남음 요구자원 중에 20을 요구하는 p1이 있음 할당해줌 (할당순서1)

p1을 지움 그다음 현재자원 50 + 20 에서 100(자원 개수) 빼줌 30 요구하는 p3 있음

위 설명을 반복하면 위 사진 처럼 결과가 나옴

 

만약 하나라도 위 과정처럼 되지 않는다면 Unsafe State 상태임 

 

 

 

 

회복(Recovery)

• 프로세스 종료(Process Termination)

– Deadlock 상태에 있는 프로세스를 종료 시킴

– 강제 종료된 프로세스는 나중에 다시시작하여 처리

 

• 자원 선점(Resource Preemption)

– Deadlock 상태 해결을 위해 선점할 자원을 선택

– 프로세스에게 할당된 자원을 빼앗음

» 대상 프로세스는 오류발생으로 강제 종료되는 상황 발생