티스토리 뷰
목차
Deadlock
교착 상태(Deadlock)는 다중스레드 환경에서 설계 미스 등으로 발생하는 무한 대기 상태를 말한다.
조금 더 구체적으로는 두 개 이상의 스레드가 서로 상대방이 들고 있는 락의 해제를 기다리며
상황이 더 이상 진행되지 않는 상태를 말하는데, 이를 해결하는 일반적인 방법은 아직 없다고 한다.
때문에 현대의 OS는 언제나 교착 가능성을 염두에 두고 있으며,
Unix와 윈도우의 경우 드물게 발생하는 교착 상태를 무시하는 방법과 교착이 예측되는 구역에
자원을 더 할당하는 식으로 이를 회피하고 있다.
이어서 교착 상태의 발생 조건은 아래와 같으며,
- 상호 배제(Mutual Exclusion) - 임계 영역의 락은 한 스레드만 획득할 수 있음
- 점유 대기(Hold and Wait) - 자원을 점유한 채로 다른 스레드의 락이 풀리길 기다리는 것
- 선점 불가(Non Preemption) - 다른 스레드의 자원을 강제로 빼앗을 방법은 없다.
- 순환 대기Circle Wait) - 자원 할당 그래프가 순환구조를 가져야 한다.
- 자원 할당 그래프 - 교착 상태 관리를 목적으로 요청/할당의 두 가지 에지를 가지는 유향 그래프
위 조건 중 하나라도 만족하지 않으면 교착상태는 발생하지 않는다.
즉, 위 조건 중 하나라도 예방할 수 있다면 교착 상태를 사전에 예방할 수 있다는 뜻이 된다.
계속해서 교착 상태를 다루는 방법에 대해 알아보자. 크게 다음과 같은 네 가지 방법으로 나뉜다.
- 예방(Prevention)
- 회피(Avoidance)
- 탐지(Detection) 및 회복(Recovery)
- 무시(Ignoring)
Prevention
먼저 위에 언급했던, 각 조건에 대한 예방 가능성을 짧게 살펴보자.
- 상호 배제 예방 - 사실상 불가능
- 점유 대기 예방 - 자원을 점유한 스레드는 다른 자원을 기다리지 못하도록, atomic으로 처리
- 여기서 atomic이란 트랜잭션처럼 작업이 모두 실패하거나 모두 성공하는 것을 말한다.
- 하지만 보통 교착상태는 임계 영역, 즉 복수의 스레드가 접근할 때 문제가 생기는 영역에서 일어나므로 처리가 힘들다.
- 선점 불가 예방 - 다른 스레드의 자원을 강제로 빼앗을 수 있게 하면 생기는 문제가 한 둘이 아니다.
- 순환 대기 예방 - 자원과 스레드에게 우선순위를 부여해 순환구조를 끊는다.
- 언뜻 간단해 보이지만 교착 상태에 빠질 가능성이 있는 스레드 개수와 자원의 개수는 빠르게 늘어나기 때문에
예측하는 것은 힘들다.
- 언뜻 간단해 보이지만 교착 상태에 빠질 가능성이 있는 스레드 개수와 자원의 개수는 빠르게 늘어나기 때문에
위와 같은 예방 방법은 자원을 많이 소모하고 이외의 비용 역시 많이 드는 문제점이 있다.
Avoidance
위에도 잠시 언급했던 교착 상태 회피는 주로 자원 할당에 대한 알고리즘으로 이루어져 있으며,
그나마 회피하기 수월한 순환 대기를 예방하는 것을 목적으로 한다.
조금 더 구체적으로는 교착상태가 발생하기 전, 불안정 상태에 들어가는 것을 예방하려 하는데, 여기서
- 안정 상태란 교착 상태 발생 없이 자원을 할당하는 순서가 존재하는 경우를 가리킨다.
- 불안정 상태란 교착 상태의 발생 가능성이 존재하는 경우를 가리킨다.
계속해서 교착상태 회피에는 다음과 같은 가정이 들어간다.
- 스레드와 자원의 종류과 개수가 고정되어 있어야 한다.
- 스레드가 필요로 하는 자원과 할당 가능한 최대 자원의 수를 알아야 한다.
- 스레드는 작업이 끝나면 반드시 자원을 반납해야 한다.
대충 읽어도 현실적이지 않다. 스레드의 요청이 있을 때마다 위의 단계를 거쳤다간 자원을 크게 낭비하게 된다.
어쨌거나 계속해서 교착 상태를 회피하는 알고리즘에 대해 알아보자
- 자원 할당 그래프 알고리즘(Resource-Allocation Graph Algorithm)
- 위에 등장한 자원 할당 그래프를 조작하는 방식이며, 유형 별로 자원이 하나씩 존재할 때 사용된다.
- 기존의 요청/할당 에지에 더해 향후 요청할 가능성이 있는 자원을 가리키는 예약 에지를 추가한다.
- 스레드 시작 전 모든 예약 간선을 자원 할당 그래프에 표시한다.
- 스레드는 예약 간선이 가리키는 자원만 요청할 수 있으며, 순환구조가 형성되면 우선순위가 밀린다.
- 은행가 알고리즘(Banker's Algorithm)
- 유형마다 자원이 두 개 이상일 경우 사용되는 알고리즘이다.
- 스레드 생성시 자신이 필요로 하는 각 자원의 최대 개수를 선언한다.
- 요청 발생시 시스템이 안전한 상태로 유지되는 경우에만 자원을 할당한다.
- 불안정상태가 예상되면 우선순위가 밀린다.
Detection
탐지는 말 그대로 알고리즘을 사용해 교착 상태의 발생 여부를 판단한다.
교착 상태 판정 시 복구 기법을 통해 처리하며,
위에 언급했던 문제들과 같이 자원을 많이 차지하기 때문에 작동 주기를 적절히 설정하는 것이 중요하다.
- 대기 그래프(Wait-for Graph)
- 자원 할당 그래프 알고리즘과 마찬가지로 유형별 자원이 하나씩 존재할 때 사용된다.
- 자원 할당 그래프에서 자원을 제거하는 방식으로 그래프를 압축해 순환 여부를 판단한다.
- 은행원 알고리즘
- 역시 위의 은행원 알고리즘과 같은 상태에서 사용된다.
- 각 스레드의 최대 자원 요구량을 바탕으로 안전상태 여부를 판별한다.
- 불안정 상태일 경우 교착상태라고 판단한다.
추가로 위에 언급했던 탐지 알고리즘의 작동 주기 조절 방식은 대략 아래와 같은 종류가 있다.
- 스레드의 요청에 즉시 자원이 할당되지 못하는 경우 호출
- 일정 시간마다 주기적으로 호출
- CPU 점유율이 특정 값 아래로 내려가면, 즉 자원에 여유가 생기면 호출
Recovery
이렇게 탐지된 교착 상태는 가능하면 해결해야 한다. 복구 방식에는 크게 두 가지가 있다.
- 프로세스 종료
- 교착상태의 스레드를 모두 중지 - 모든 중간결과가 버려지기 때문에 비용이 발생한다.
- 해결될 때까지 하나씩 중지 - 하나씩 중지할 때마다 탐지 알고리즘을 호출해 오버헤드가 생긴다. 중지 기준은 아래와 같다.
- 우선순위가 낮은 순서대로 중지
- 누적 작업 시간이 적은 순서대로 중지
- 자원 할당량이 많은 순서대로 중지
- 자원 선점
- 교착 상태의 스레드의 자원을 우선순위가 높은 다른 프로세스에게 할당 후 해당 스레드 일시정지. 아래와 같은 고려사항이 있다.
- 희생자 선택 - 우선순위를 정하는 방법. 비용 최소화를 위해 각 스레드가 할당받은 자원의 수와
지금까지 작업한 시간 등을 바탕으로 선택한다. - 후퇴 - 자원을 선점당한 스레드의 상태 결정. 가장 확실한 방법은 종료 후 재시작(완전한 후퇴)이다.
교착 상태를 벗어날 정도로만 후퇴시키는 것이 이상적이지만 역시 비용이 많이 발생한다. - 기아 상태 - 특정 스레드가 기아 상태(무기한 대기 상태)에 빠지지 않도록 보장해야 한다.
한 번 우선순위가 낮에 평가된 스레드는 계속해서 희생자로 선택될 가능성이 있기 때문에
동일한 스레드는 일정 시간 이상 희생자로 선택되지 않도록 로직을 구성해야 한다.
- 스레드의 우선순위를 주기적으로 변경
- 오래 기다린 스레드일수록 높은 우선순위 배정
- 우선순위 큐가 아닌 일반 큐 사용
Ignoring
말 그대로 무시다. 못 본 체하는 거다.
그래도 되나 싶지만 위에서 봤듯이 교착 상태의 발견과 예방, 해결은 자원에 상당한 부하를 준다.
따라서 교착 상태의 비율이 현저하게 낮은 경우(발생 빈도가 연 단위)
교착상태가 발생하도록 두고 필요하다면 기기를 껐다 켜도록 유도하는 게 경제적일 수 있다.
'Development > Technical Interview' 카테고리의 다른 글
[면접 준비 - Java]서블릿(Servlet)에 대하여 (2) | 2022.12.26 |
---|---|
[면접 준비 - Network]HTTP Request 횟수에 대하여 (2) | 2022.12.26 |
[면접 준비 - CS]멀티 프로세스, 멀티 스레드, 싱글 스레드, 그리고 (4) | 2022.12.24 |
[면접 준비 - CS]프로세스, 스레드, 동기화, 그리고 (6) | 2022.12.22 |
[면접 준비 - CS]노드(Node)에 대하여 (2) | 2022.12.20 |
[면접 준비 - Network]부하 분산(SLB), AWS ELB에 관하여 (3) | 2022.12.19 |
- Total
- Today
- Yesterday
- spring
- 알고리즘
- a6000
- Python
- 동적계획법
- 유럽
- 세계여행
- 세계일주
- 중남미
- 스트림
- 지지
- 유럽여행
- 칼이사
- Backjoon
- 리스트
- 스프링
- 세모
- Algorithm
- RX100M5
- java
- 남미
- 백준
- BOJ
- 자바
- 야경
- 여행
- 파이썬
- 기술면접
- 맛집
- 면접 준비
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |