데드락 설명
라이브니스 설명(우선순위 역전 설명 포함)
데드락 순환대기 부정 설명

라이브니스

임계구역 접근을 위해 동기화 도구를 사용할 때 문제

• 임계구역에 들어가려고 시도하는 프로세스가 무기한 대기할 가능성이 생김

※ 오버헤드
어떤 작업을 수행하기 위해 추가적으로 필요한 부가적인 비용이나 시간을 말함.

오버헤드는 일반적으로 시스템의 성능을 저하시키는 요인 중 하나이다.

[ 오버헤드가 발생하는 상황 ]

1. 시스템 호출 시 운영체제로부터 서비스를 받기 위해 프로세스가 시스템 호출(프로세스 간 커뮤니케이션, 파일 입출력, 메모리 관리)을 요청
   ※ 시스템 호출은 사용자 모드에서 커널 모드로의 전환과 관련해 비용이 큼

2. 새로운 프로세스나 스레드를 생성/종료 시 시스템은 메모리/자원/스케줄링 할당과 해제 작업

3. 컨텍스트 스위칭
   컨택스트 스위칭이란 멀티태스킹 환경에서 여러 프로세스나 스레드가 실행되는데, 실행 중인 작업을 일시 중지하고 다른 작업으로 전환하는 것으로 프로세스나 스레드 간 상태 정보를 저장하고 복구하는 과정을 포함하게 되는데 이 때 오버헤드가 발생한다.

4. 여러 프로세스나 스레드가 공유 자원에 접근하는 경우 이들 사이의 동기화를 위해 락(Lock) 을 사용하는데, 락을 획득하고 해제하는 과정에서 오버헤드 발생

5. 통신 프로토콜이나 암호화 알고리즘 등을 사용하는 경우, 추가적인 계산과 데이터 처리가 필요해서 오버헤드 발생 가능성 증가

라이브니스 실패

프로세스가 실행 수명주기 동안 진행되는 것을 보장해야 시스템이 충족되는데, 라이브니스 실패 시 무기한 대기하는 프로세스가 발생

종류

1. 무한루프
2. 바쁜 대기 루프
3. Mutex와 Semaphore 와 같은 동기화 도구 사용 시 실패 가능성 증가

교착 상태(DeadLock)

운영체제 또는 소프트웨어의 잘못된 자원 관리로 인해 둘 이상의 프로세스/스레드들이 아무것도 진행하지 않는 상태로 서로 영원히 대기하는 상황이다.

발생 조건 ( 4가지 모두 충족 시 교착 상태 발생 )

1. 상호 배제(Mutual Exclusion)
   자원은 한 번에 한 프로세스만 사용 가능
   줄여서 뮤텍스(Mutex)라고도 함
2. 점유상태로 대기(Hold and Wait)
   2개 이상의 자원을 동시에 사용할 때 순차적으로 할당 받을 경우 몇 개는 이미 할당이 끝났지만 남은 자원을 다른 프로세스가 붙잡고 놔주지 않아 무간지옥에 빠지는 경우.

   최소한 하나의 자원을 점유하고 있으면서 다른 프로세스에 할당되어 사용하고 있는 자원을 추가로 점유하기 위해 대기하는 프로세스가 존재해야 함

3. 비선점(No Preemption)
   다른 프로세스에 할당된 자원은 끝날 때까지 강제로 빼앗을 수 없음
4. 순환 대기(Circular Wait)
   모든 프로세스가 다름 프로세스가 사용중인 자원을 기다리는 상황에서, 마지막 프로세스가 첫 프로세스가 사용 중인 자원을 쓰려고 대기중인 상황.

위 그림에서 Process 1과 Process 2가 모두 Resource 1, Resource 2를 할당받아야 한다.

t1 시간에서 Process 1이 Resource 1 을 얻으며 Process 2는 Resource 2를 얻는다.
t2 시간에서 Process 1이 Resource 2의 할당을 기다리고, Process 2는 Resource 1의 할당을 기다리게 되면서 끝나지 않고 무한 대기상태가 된다.

즉, 현재 서로 원하는 자원이 각자 다른 프로세스에 할당되어 있어서 각각의 프로세스가 무한정 Wait 상태에 빠지게 되는 상태를 DeadLock이라고 한다.

DeadLock 처리 방법

1. 예방(Prevention)

   • 교착 상태 발생 조건 중 하나를 제거하여 DeadLock 해결(자원 낭비 심함)
     1. 상호배제 부정
        여러 프로세스가 공유자원 사용할 수 있음
     2. 점유대기 부정
        프로세스 실행전 모든 자원을 할당
     3. 비선점 부정
        자원 점유 중인 프로세스가 다른 자원을 요구할 때 가진 자원 반납
     4. 순환대기 부정
        자원에 고유번호 할당 후 순서대로 자원 요구

2. 회피(Avoidance)

   • 교착상태가 발생하기 전에 교착상태를 예상하여 Safe State에서만 자원 요청을 허용.

   • 자원을 신중하게 할당하면 교착상태를 회피할 수 있음

     1. 은행원 알고리즘(Banker's Algorithm)
     2. 자원 할당 그래프 알고리즘(Resource_Allocation Graph Algorithm)

3. 탐지(Detection)

4. 회복(Recorver)