-
💻 [OS 오퍼레이팅시스템] #13 | Deadlocks | 데드락, 뱅커스 알고리즘, 교착상태CS/OS 2022. 6. 13. 11:02
💻 데드락 (교착상태)
- 데드락
- 시스템 자원을 두고 경쟁하거나 서로 통신하는 프로세스의 집합의 영구적 차단- 집합의 각 프로세스가 다른 block된 프로세스에 의해서만 발생될 수 있는 이벤트를 대기하면서 block되면 프로세스 집합은 데드락
- 더이상 이벤트들이 발생할 수 없는 상태여서 두 개 이상의 프로세스가 더이상 진행될 수 없는 상황
두 개 이상의 프로세스에 의한 자원 요구의 충돌을 수반한다.
- Resources (자원)
[ 비선점 자원(non preemtable) ]- 빼앗을 수 없는 자원
- 보통 데드락이 비선점자원을 수반한다.
- 비선점 자원 종류 2가지 : reusable and consumable
[ 1) 재사용 자원(reusable) ]
- 사용해서 사라지지 않고, 한번에 한 프로세스만 사용될 수 있다.
- 자원 이용 과정 : 1)요청 -> 2)Lock(할당) -> 3)사용-> 4)Unlock(release)
- e.g. 프로세서, 메모리, 디바이스, 프린터, 파일, 세마포어 등
[ 2) 소비되는 자원(consumable) ]
- 생성되고 사라진다.
- e.g. interrupts, signals, messages, I/O 버퍼의 information 등
- Resource Allocation Graphs
유향그래프.
Vertices : P는 프로세스(동그라미로 표시), R은 리소스(사각형으로 표시)
Edges : 프로세스에서 리소스로 향하는 edge는 요청한다는 의미, 리소스에서 자원으로 향하는 edge는 점유한다는 의미
cycle 없으면 데드락 X
cycle 있는데 one instance면 데드락 0, multi instances면 데드락 있을 수도 없을 수도(보통 없다)
💻 식사하는 철학자 문제 (동기화 문제)
- 식사하는 철학자
다익스트라에 의해 소개된 개념. 보통 5명의 철학자(프로세스)와 5개의 음식(자원)각 철학자는 먹기위해 2개의 포크가 필요하다. 동시에 포크 사용 불가하며 자신의 왼쪽 포크와 오른쪽 포크를 사용한다.목표 : 데드락(굶어죽음)을 예방하고 포크는 상호배제 해준다.getforks() -> eat() -> putforks() -> think() 반복하는게 기본 틀이다.
더보기<구현 코드>
💻 데드락 발생 조건
- 상호 배제 Mutual Exclusion
(필요조건) 한번에 한 프로세스만 자원 사용 보장
- 비선점 No preemption
(필요조건) 프로세스가 작업 완료한 뒤, 리소스는 프로세스에 의해서만 자발적으로 풀어질 수 있다.
- 점유한 상태에서 대기 Hold and Wait
(필요조건) 하나 이상의 리소스를 점유한 프로세스가 다른 프로세스에 의해 점유된 다른 리소스를 획득하기 위해 대기 중인 상태
- 순환 대기 Circular Wait
(필요충분조건) 프로세스0이 프로세스1에 의해 점유된 자원을 기다리고, 프로세스1이 프로세스2에 의해 점유된 자원을 기다리고 ... 프로세스n이 프로세스0에 의해 점유된 자원을 기다리는 서로가 다른 서로의 자원을 기다리는 cycle
💻 식사하는 철학자 해결법
- 1) 4명만 식사할 수 있게 하자
room이라는 세마포어 변수 추가(공유자원이므로 상호배제 필요)
단졈 : concurrency 손해
- 2) 점유대기 제약
- 3) 순환대기 제약
💻 데드락 예방 (조건 방지)
- 데드락 예방
데드락 발생 조건 4가지 중 하나에 제약을 걸자.상호 배제와 비선점은 상대적으로 제약 걸기 어렵다.
- 점유 대기 제약 : 프로세스가 모든 요청된 자원을 한번에 요청하고, 모든 요청이 동시에 승인될 수 있을 때까지 프로세스를 블로킹한다.점유 대기 제약 단점 : 비효율적, 프로세스 속도 저하 및 불필요하게 리소스 접근 거부. 점유 상태에서 대기 불가
- 순환 대기 제약 : 리소스에 번호매김으로써 순서화(linear ordering) 각 프로세스는 오름차순으로 자원 요청. 순환 대기 제약 단점 : 편리하지 않고 복잡하고 자원 요청 오름차순으로밖에 못하는 제약
💻 데드락 회피 (승인/거절)
- 데드락 회피
단점 : low device utilization, less concurrency, difficulty of resource use
- Resource-Allocation-Graph 알고리즘
- (Banker's) 뱅커스 알고리즘
💻 데드락 핸들링
- 핸들링 종류
1) 데드락 예방 : 데드락 발생 조건 4가지 안가지도록 제약, concurrency, utilization이 희생 될 가능성 존재
2) 데드락 회피 : 데드락 발생 가능성 있으면 자원 사용을 회피 (추가적인 미래 정보가 필요)
3) 데드락 탐지와 회복 : 데드락 가정하고 주기적으로 데드락을 체크, 프로세스 종료 또는 자원 회수로 회복시킨다.
4) 그냥 무시 : 위의 3가지 방법 cost 커서 아무것도 안하는게 성능 좋을 수도. 데드락은 어차피 잘 안일어나는 일이니 그냥 무시하는 방법
'CS > OS' 카테고리의 다른 글