WHY
이전에는 프로세스와 스레드. 멀티 프로세싱과 멀티 스레딩. CPU 스케줄링 기법들. 임계 영역과 상호 배제를 살펴보았다.
이번 질문은 위의 모든 과정을 이해해야 답변하기가 수월한 질문이다.
교착상태가 일어나기 위한 4가지 조건의 배경이 되기 때문!
해당 질문만으로 OS의 CPU 자원을 다루는 배경을 파악할 수 있어서 효율성이 높은 질문이다.
교착 상태의 원인, 조건, 해결방법 등을 살펴보면서 해당 질문에 깔끔한 답변을 할 수 있도록 준비해보자!
교착상태 (DeadLock)
프로세스는 자원을 사용하기 전에 "요청"을 하고 자원을 사용할 수 있는 경우에 자원을 "사용"한다.
해당 자원을 사용 완료했다면 다른 프로세스가 사용할 수 있도록 "방출"해야 한다.
요청, 사용, 방출의 단계를 통해 자원 경쟁을하는 프로세스들은
요청 시 해당 자원을 사용할 수 없으면 대기 상태로 머무른다.
이러한 프로세스들 중 특정 조건에 해당하는 프로세스들이 자원을 두고 경쟁하게 될 경우
서로 무한 대기에 빠지게 된다. 이를 교착상태라고 한다.
교착상태에 대한 깔끔한 정의는 아래와 같다.
"둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황"
교착 상태에 빠지기 위해서는 4가지 조건 모두에 해당되는 프로세스들이 충돌해야 한다.
상호 배제(Mutual Exclusion : Mutex)
한 번에 하나의 프로세스만 공유자원을 사용할 수 있다. [ lock을 소유한 프로세스만이 자원을 사용 ]
사용 중인 자원을 다른 프로세스가 사용하기 위해선 요청한 자원이 해제될 때까지 기다려야 한다.
비선점형 CPU 스케줄링(No Preemption)
다른 프로세스의 자원을 뺏을 수 없어야 한다. 해당 자원을 사용하기 위해서는 대기해야 한다.
점유와 대기(Hold and Wait)
자원을 점유하고 있는 상태에서 다른 자원을 기다리는 것이다.
원형 대기 (Circular Wait)
자원을 요구하는 방향이 서로 원을 이루어 양보하지 않는 경우이다.
자원 할당 그래프에서 순환 구조를 띄는 상태이다.
다시 교착 상태의 정의를 살펴보고 4가지 조건으로 길게 설명해보도록 하자.
"둘 이상의 프로세스가 다른 프로세스가 점유하고 있는 자원을 서로 기다릴 때 무한 대기에 빠지는 상황"
"비선점 CPU 스케줄링 정책으로 운영되는 두 개 이상의 프로세스가 각자 배타적인 자원을 점유하면서 다른 프로세스가 점유하고 있는 배타적인 자원을 대기하고 있을 때 두개 이상의 프로세스의 대기 구조가 원을 이루는 경우 무한 대기에 빠지는 상황이다."
교창상태는 시스템 자원, 공유 변수(뮤텍스), 응용 프로그램에
2개 이상의 프로세스가 사용하고자 접근할 때 자연스럽게 발생한다.
교착상태가 발생하면 프로세스가 진행되지 않을 것이며 해당 자원도 사용되지 않게 된다.
운영체제는 이 문제를 빠르게 해결하지 않으면
다른 프로세스들도 다같이 교착상태에 빠지게 되는 문제가 발생할 수 있다.
교착 상태에 대한 해결 접근법. 무엇이 있는지 살펴보자.
사회와 마찬가지로 문제를 해결하는 데에는 보편적인 3가지 접근법을 고려하게 된다.
1. 예방 : 문제를 일으키는 사전 조건을 차단하여 문제 발생을 막는 것이다.
[ 꽤나 무식한 방법이지만 강력한 효과가 있다. ]
2. 회피 : 문제의 발생 지점을 파악하고 문제를 회피할 수 있는 선에서 자유롭게 활동하는 것이다.
[ 예방보다는 나은 대안이지만 좀 더 복잡한 정책을 수용하게 된다. ]
3. 검출하고 회복하기 : 교착 상태의 발생을 받아들이고 발생할 경우 해결하고 회복하는 단계로 나아가는 것이다.
사회와 마찬가지로 3가지 접근법 중 가장 현실적인 방법은 "검출하고 회복하기"이다.
Deep Dive 해결방법
예방(Prevention)
4가지 조건에 모두 해당해야 교착상태가 발생하기 때문에 4가지 조건 중 하나를 무력화하는 것이다.
상호배제 예방
- 자원에 대한 공유를 막아버린다. 이것은 현실성이 매우 낮다.
비선점 예방
- CPU로 하여금 자원을 강제적으로 선점하게 만드는 것이다.
임계 영역을 보호할 수 없어 상호 배제를 보장할 수 없다.
점유와 대기 예방
- 자원을 점유한 프로세스가 다른 자원을 기다리지 못하게 하는 방식이다.
필요한 자원을 모두 사용하거나 아예 사용하지 않게 만든 것. 자원의 활용성을 상당히 떨어뜨린다.
원형 대기 예방
- 프로세스로 하여금 요청 구조에 대해서 "원형 구조"를 이루지 못하게 하는 것이다.
자원에 고유 번호를 할당하고 번호 순서대로 자원을 할당하여 처리하는 것.
현실에서도 그렇듯 예방은 아주 강력한 정책 중 하나이다.
원하는 목적을 이룰 수 있다고 하지만 운영체제가 가져야 할 정책과 비교해보면 효율성을 상당하게 잃는 방식이다.
자원의 비효율성으로 인해서 현실성이 상당히 낮고 미션 크리티컬한 운영체제가 아니라면 범용 운영체제에서는
고려하기 힘든 해결방법.
회피(Avoidance)
문제 발생 지점을 확인할 수 있다면 해당 지점 이전까지는 자유롭게 활동하는 것이다.
회피의 가장 큰 문제는 문제 발생 지점에 대한 일관성, 완전성을 보장하기가 현실적으로 어렵다는 것이다.
적은 공유자원, 적은 프로세스를 사용하는 운영체제라면 고려해볼 만한 해결 방법이지만 다수의 공유 자원, 다수의 프로세스를 사용하는 운영체제라면 공유 자원이 많을수록, 프로세스가 많을수록 기하급수적으로 복잡해지는 자원 할당 그래프를 분석하면서 안정상태에 적합한 자원의 수를 파악하는 것이란 상당히 어렵다.
다익스트라의 "은행원 알고리즘"이 대표적이다.
"안정 상태"의 조건 아래에서 자원 할당을 하는 것이다. 안정 상태를 넘기는 경우 자원을 할당하지 않는다.
4가지 조건을 유지하며 프로세스를 운영하기에 예방보다는 자원 활용성에서 유연하지만, 교착 상태 발생과의 연관성을 파악하는 것에 현실적인 어려움이 있다.
검출하고 회복하기(detection & recovery)
가장 현실적인 방법이다.
조건에 대한 제약도 없고, 안정상태를 유지하기 위한 제약도 없다.
다만 교착상태에 대해서 책임일 수 있는 절차가 필요하다.
운영체제가 "교착 상태"를 탐지했다고 판단한 경우 회복 단계를 진행시키는 것이다.
교착상태 검출 기준으로는 2가지 방법이 있다. [ 일정 시간, 자원 할당 그래프 사용 ]
보통은 일정 시간 동안 프로세스의 작업이 진행되지 않으면 해당 프로세스는 "교착 상태"에 빠진 것으로 간주한다.
교착 상태가 발생했다고 판단되는 두 개 이상의 프로세스를 종료시키는 것이다.
- 동시에 종료시키고 순차적으로 실행시키거나
- 우선순위가 낮은 프로세스를 종료시키고 나머지 프로세스들을 파악하는 것이다.
잘못 판단할 경우 멀쩡한 프로세스를 종료시킬 수 있다는 문제가 있다.
[네트워크를 사용하는 프로세스의 경우 오해가 발생할 수 있다. ]
타임아웃을 기준으로 교착상태를 파악하는 방법을 "가벼운 교착 상태 검출"이라 부르고
자원 할당 그래프를 이용하는 방법을 "무거운 교착 상태 검출"이라고 부른다.
참고 : 아사(Starvation) 현상과 데드락(DeadLock)은 완전히 다른 개념이다.
아사는 운영체제의 정책 중 "공평성"을 지키지 않는 스케줄링으로 인해서 특정 프로세스가 자원을 할당받지 못하는
상황을 의미한다.
데드락의 경우 프로세스가 작업을 진행하다가 4개의 조건을 만족하는 상황에서 두 개 이상의 프로세스가 작업을
진행하지 못하는 "무한 대기"상황에 빠지는 것을 의미한다.
아사의 경우 정책을 보완하면 충분하게 해결할 수 있지만, 데드락의 경우는 정책이나 알고리즘으로 해결하기가 어렵다.
보통은 교착 상태를 탐지하고 회복단계를 거치는 것이 현실적이다.
마무리
여기까지 CPU와 관련된 운영체제 면접 질문들을 살펴보았다.
[ OS 면접 질문 8번 글에서는 기타 CPU 관련 면접 질문들을 모아서 해결해보고자 한다. ]
PC를 구성하는 대표적인 자원은 CPU, 메모리, 하드이다. [ 최근에는 그래픽카드가 엄청 큰 자리를 차지하지만... ]
다음으로는 메모리와 관련된 면접 질문으로 접근해보고자 한다.
OS를 빨리 끝내고 네트워크를 마무리하고 싶다.
처음에는 몰랐는데.. 면접 질문을 공부하면서 다른 사람들의 글과 유명 사이트를 참고하면서 많은 정보들을 얻게 된다.
그간 책에만 빠져서 책으로만 공부했었는데 인터넷으로까지 확장해서 지식을 수집하고 정리하니 보는 시야가 달라지게 되는 것 같다.
그리고 훌륭한 블로그들 북마크하게 되면서 많은 지식인들을 발굴하기도 하고 있다.
면접을 통과하기 위한 지식으로만 남기보다는 체득되기를 바란다.
잘못된 정보가 있을 경우 말씀해주시면 수정하도록 하겠습니다.
참고자료
책
- 쉽게 배우는 운영체제
블로그
'면접질문[CS] > 알고리즘 & OS' 카테고리의 다른 글
| 운영체제 그리고 커널. [ 운영제체(OS) 면접질문 0 ] (0) | 2022.01.07 |
|---|---|
| 동기 비동기 블로킹과 논블로킹 2x2 매트릭스 [ 운영체제(OS) 면접질문8 ] (0) | 2022.01.06 |
| 임계구역을 보호하기 위한 기법 3가지[뮤텍스, 세마포어, 모니터] [ 운영체제(OS) 면접질문 6] (1) | 2021.12.24 |
| 동기화, 경쟁 조건(Race Condition), 임계 구역(Critical Section) [ 운영체제(OS) 면접질문 5] (0) | 2021.12.23 |
| CPU 스케줄링 알고리즘 [ 운영체제(OS) 면접 질문 4] (0) | 2021.12.22 |
