운영체제 관련 글 순서
- 프로세스란
- 쓰레드
- CPU 스케줄링
- 동기화 툴
- 동시성 제어 예제
- 데드락
- 주 메모리
- 페이징과 스와핑
- 가상 메모리와 디맨드 페이징
- 페이지 교체 알고리즘(FIFO, OPT, LRU), 쓰레싱, working set
데드락이란?
: 두개 이상의 프로세스(쓰레드)가 서로 상대방의 작업이 끝나기만을 기다리고 있어서 무한 대기에 빠지는 상황.
데드락 예시코드
데드락이 발생하는 조건
- 상호배제(Mutual Exclusion) : 자원은 한 프로세스만이 사용 가능
- 점유대기(Hold and Wait) : 한 개이상의 자원을 점유하고 있으면서 다른 프로세스가 점유하고 있는 자원을 점유하기 위해 대기
- 비선점(No preemption) : 다른 프로세스가 자원의 사용을 끝내기전까진 뺏을 수 없음
- 순환대기(Circular Wait) : 서로 순환하여 자원을 얻기 위해 대기
이 4가지가 다 만족해야 데드락이 발생한다.
Resource-Allocation Graph(RAG:자원할당 그래프)
- 데드락을 정확하고 쉽게 알아보기 위한 그래프
- 쓰레드의 집합을 T
- 자원의 집합을 R
- 여기선 순환대기 사이클이 없기 때문에 데드락 발생하지 않음.
- 순환대기 사이클이 존재하고 해당 그래프에선 데드락 발생
- 순환대기 사이클이 존재하지만 해당 그래프에선 데드락 발생하지않음.
- T2 또는 T4가 작업이 끝나고 자원의 인스턴스를 반환해주면 해결되기 때문.
데드락 해결 방법
- 데드락 발생여부를 신경쓰지 않고 프로그래밍
- 데드락을 방지하거나 데드락을 피할 수 있게 하는 방법.
- 데드락이 발생했을때, 알림을 통해 회복시켜주는 방법.
데드락을 예방하는 방법
- 위에서 말했던 4가지 조건 중에 한가지를 방지하는 방법
- 상호배제 방지
- 모든 리소스가 공유 가능하게 만들면 데드락이 발생하지 않음.
- 이건 말이 안되는게 뮤텍스로 동기화 시에 일어날 문제들을 막고, 뮤텍스는 공유가 가능하면 안된다.
- 점유대기 방지
- 쓰레드가 어떤 리소스를 획득하기위해선 다른 리소스를 내려 놓기.
- 선점
- 쓰레드가 어떤 리소스를 요청할때, 다른 쓰레드가 그 리소스를 사용중이다면 선점하기
- 순환대기 방지
- 자원이 순환 형태로 대기하지 않게 일정한 방향으로만 자원을 요구.
- 각 리소스에게 순서를 정해두고 점유하고 있는 리소스보다 높은 리소스만 요청.
- 상호배제 방지
- 이 방법들은 현실적으로 불가능하거나 시스템의 처리량 또는 효율성을 떨어트림.
데드락 회피방법
- 요청이 왔을때 받아주기 전에 데드락이 걸릴지 확인하고, 걸릴 것 같다면 기다리는 것.
- Safe State
- 프로세스들이 요청하는 모든 자원을 데드락이 발생시키지않게 모두에게 할당 가능한 상태
- 데드락이 발생하지 않는 순서를 안전순서(safe sequence) 라고 부름
- Unsafe State
- 데드락이 걸릴 수도 있는 상태
- 회피하는 방법은 Safe State에만 있어서, 데드락에 걸릴 상황자체를 가지 않는 것.
- 대표적인 알고리즘이 Banker's Algorithm
Banker's Algorithm
- 다익스트라 알고리즘을 개발하신 다익스트라씨가 개발한 알고리즘
- Safety Algorithm을 통해 요청을 받아들이거나 했을때 safe state 인지 미리 확인 하는 알고리즘.
Safety Algorithm
- 모든 자원들의 최대 할당량을 가지고 각 쓰레드의 요구량과 비교하여 safe sequence를 찾고 safe state인지 확인하는 알고리즘.
- 자료구조
- 쓰레드(T)의 개수가 N , 리소스(R)의 개수 M개일 때
- Available: 리소스 타입 별 현재 사용할 수 있는 개수
- Max: 각 스레드가 요청할 리소스의 최대개수
- Allocation: 쓰레드에 할당된 리소스
- Need: 각 스레드가 추가적으로 요청할 리소스
- 맥스값을 통해 각 쓰레드별 추가적으로 필요한 리소스(need)를 구할 수 있음.
- To 쓰레드 기준
- 현재 할당된 리소스(Allocation) A: 0, B: 1. C: 0
- 최종 요구하는 리소스 개수(Max) A: 7, B: 5, C: 3
- 할당된 리소스 제외 필요한 리소스 개수(need) A: 7, B: 4, C: 3
- 위와 같이 need가 구해짐
- 이때, 쓰레드별로 가능한지 확인하는 방법은 Need 각각의 숫자가 Availavle보다 작거나 같으면 가능.
-
각 쓰레드별로 가능한지 Boolean 배열 {false,false,false,false,false} T(o) Need = 7 4 3 Available = 3 3 2 불가 T(1) Need = 1 2 2 Availabe = 3 3 2 가능 가능할때 계산 시작 T(1)에 자원을 할당하여 끝냈다는 가정하에 T(1)에 할당되어있던 자원이 해제되고 Available에 합류됨 Available = Available + Allocation Available = 5 3 2 T(1)은 끝. {true,false,false,false,false} T(2) Need = 6 0 0 Available = 5 3 2 불가 T(3) Need = 0 1 1 Available = 5 3 2 가능 t(3)의 Allocation 2 1 1 Available = 7 4 3 {t,f,t,f,f} ... 계속 진행하면 전부 가능한지 파악 가능 {t,t,t,t,t} Safe sequence는 <T(1),T(3),T(4),T(2),T(0)> 또는 <T(1),T(3),T(4),T(0),T(2)>
Resource-Request Algorithm
- 새로운 요청이 들어왔을때 데드락이 발생하는지 확인하는 알고리즘
- 새로운 요청이 왔을때 요청 리소스의 수(Request)가 Available 보다 작거나 같을때 Need,Allocation,Available을 변경해준 뒤에 Safety Algorithm 적용
Banker's Algorithm 단점
- 프로세스 별 최대 자원 요구량을 알고 있어야함.
- 할당할 수 있는 자원 수가 일정해야함.
- 무조건 불완전 상태(Unsate State)를 방지해야해서 자원 이용도가 하락
데드락 감지 방법(Detection)
- 리소스 타입의 자원이 1개일때, wait for graph 구성
- 오른쪽이 wait-for graph. 여기서 상호대기가 일어날만한 사이클이 존재하는지 확인 가능.
- 리소스 타입의 자원이 여러개일땐, 뱅커스 알고리즘과 비슷한 구조로 확인.
- 기존엔 다 true여서 데드락이 없을때만 진행하지만, 몇개 false여도 데드락을 발견하고 진행한다.
- 단점
- 데드락 감지 방법도 호출 시 오버헤드가 있기때문에 빈도를 조절해야함
- 감지 방법을 사용할때 고려사항
- 교착 상태가 얼마나 자주 일어나는가?
- 교착 상태가 일어나면 몇개의 쓰레드가 데드락에 포함되는가?
- 예시와 같은 상황에 호출
- 자원 요청했는데 즉시 할당 실패했을때
- 일정시간마다
- CPU 이용률이 특정 값 이하로 떨어질때
데드락 회복 방법
- 데드락(교착 상태)가 발생 했을 때 복구방법
- 프로세스 종료(Termination)
- 방법1: 교착 상태의 프로세스 모두 중지
- 방법2: 교착 상태 제거될 때까지 한개씩 프로세스 중지
- 자원 선점(Resource Preemption)
- 최소한의 피해를 주는 프로세스를 선택(희생자 선정)
- 선정된 프로세스의 자원을 해제하고 safe state로 롤백 및 재시작
- 매번 선정되는 프로세스는 기아현상이 발생할 수 있으므로, 선점 될때마다 우선순위를 높여서 해결
참조
'CS > OS(운영체제)' 카테고리의 다른 글
| 페이징과 스와핑 (0) | 2022.01.07 |
|---|---|
| 주 메모리(Main Memory) (0) | 2022.01.07 |
| 동시성 제어 예제(Bounded-Buffer, Readers-Writers (0) | 2022.01.05 |
| 동기화 툴(프로세스 동기화) (0) | 2022.01.05 |
| CPU 스케줄링 (0) | 2022.01.05 |
댓글