지난시간

데드락을 방지하는 방법에 대해 배워보았다.

---

Deadlock avoidance

데드락을 미연에 방지하는 방법.

프로세스와 자원의 관계를 자원 할당 그래프로 나타내었을 때, 프로세스와 자원의 점유관계를 확인할 수 있었다.

자원 당 인스턴스가 하나뿐인 상황에서는 그래프를 이용해서 자원을 배분하고 데드락을 예측하여 Deadlock avoidance를 할 수 있다.

프로세스가 자신이 평생 사용할 최대 자원을 미리 알려준다. 그걸 바탕으로 요청하는 자원을 할당해주었을 때 남은 가용자원이 충분하여 데드락에서 안전한지를 판단한 뒤, 데드락이 발생하지 않는 상황일 때 자원을 할당한다.

사이클이 생기게 되는 상황을 미리 계산해보고, 사이클이 안생기는 상태에서만 자원을 할당한다. 사이클이 생길 상황이라면 자원을 할당하지않고, 대기하게한다.

불안정한 상태에 진입하는 것을 원천봉쇄하는 방식이다.

만약 자원 당 갯수가 여러개인 경우, Banker's Algorithm 을 활용하여 자원의 할당 여부를 결정한다.

Banker's Algorithm

프로세스 1, 2, 3, 4, 5 가 있고, 자원 A(10), B(5), C(7) 가 있다.

각 프로세스들이 평생 최대에 쓸 자원을 알고있다고 가정.

현재 시간 t에서 다섯 개의 프로세스에 할당된 자원을 제외하고, 남은 가용자원(available)이 몇개인지를 계산함.

평생 요청할 양에서 시간 t에서 사용한 자원양을 빼서 앞으로 필요할 갯수(need)를 구해보게됨.

자원이 여유있는 상황에서 프로세스들이 자원을 추가로 요청한다고 하더라도, 남은 자원을 모두 해당 프로세스에 할당하더라도 프로세스가 더 많은 자원을 필요로 한다면(available < need), 뱅커의 알고리즘에서는 자원을 할당해주지 않음.

가용자원(available)이 필요한 자원양(need)보다 여유가 있어야만 할당.

가용자원만 가지고 프로세스의 최대요청을 처리할 수 있는 요청만 받아들인다.
뱅커 알고리즘은 항상 safe한 상태를 유지함.

safe하다는 것은, 가용자원만을 가지고 프로세스를 하나씩 종료시킬 수 있는 시퀀스가 존재하면 safe.

안전한 친구들에게 자원을 몰아주고, 자원을 모두 사용한 프로세스는 종료되고, 사용이 완료된 자원을 리턴받아서 다시 필요한 프로세스에게 자원 할당.

이런식으로 프로세스를 하나 하나 종료시켜서 데드락이 일어나지 않게 프로세스에 자원할당하는 순서를 safe sequence 라고 한다.

뱅커스 알고리즘은 추가요청 자원과 가용자원을 비교하여 모두 줄 수 있다면 자원을 할당, 아니면 대기시키는 간단한 알고리즘이다.

항상 세이프한 상태를 유지하고, unsafe 해지지 않음.

• Safe sequence
  프로세스들의 최대 요청을 가용자원만으로 처리가 가능한지 확인.
  -> 처리가 완료되면 기존 가용자원 + 완료한 프로세스가 사용한 자원이 가용자원량이 됨.
  -> 가용자원으로 처리가 가능한 요청하는 프로세스에 자원 할당.

Deadlock Detection and recovery

데드락 발생은 허용하되 그에 대한 detection 루틴을 두어 데드락 발견 시 recovery함.

데드락이라는게 자주 생기는 상황이 아니다보니, 자원의 여유가 있는데도 주지 못하는 비효율적인 상황을 탈피하고자 나온 방식이다.

마찬가지로 자원할당 그래프를 통해 데드락 발생 여부를 확인해줄 수 있다.

자원 당 인스턴스가 여러개인 상황에서는 ?
데드락 디텍션을 어떻게 할까.

프로세스가 0,1,2,3,4 가 있고 A(7), B(2), C(6) 의 자원이 있다.

해당 방식에서는 요청한 자원에 대해 여유자원이 존재하면 무조건 주게 되어있다.

아무 자원도 요청하지 않은 프로세스가 작업을 완료하고 자원을 내어놓는다고 가정하고, 작업 완료시 생기는 자원들을 자원을 요청한 다른 프로세스들에게 전달하는 식으로 시퀀스를 만들 수 있다.

지금 자원을 요청안한 친구들은 자원을 내어놓을 것이다. -> 내어놓은 자원으로 다른 프로세스들의 요청을 만족할 수 있는지 확인.(자원을 현재 요청하지 않았다고 미래에도 요청하지 않는다고는 볼 수 없다. 굉장히 낙관적으로 프로세스 처리를 바라보는 방식이다.)

지금 당장의 데드락이 있는지 없는지를 판단한다.
시퀀스가 존재한다면 데드락이 없는 것으로 판단.

하지만 자원의 요청들을 가용자원으로 처리할 방법이 아예 없다면 -> 시퀀스 없음 -> 데드락!

데드락이 발생한 경우 recovery 진행.

데드락에 연루된 프로세스들을 termination 또는 Resource Preemption 진행.

1. Process termination
   abort all deadlocked processese
   Abort one process at a time until the deadlock cycle is eliminated

2. Resource Preemption
   비용을 최소화할 victim의 선정 .
   safe state로 rollback 하여 process를 restart.

2번 방식으로 recovery 진행 시 Starvation 문제의 가능성 존재.
동일한 프로세스가 계속하여 victim으로 선정되는 경우.
cost factor에 롤백 횟수도 같이 고려하여 하나의 프로세스만 계속 희생되는 것을 방지한다.

Deadlock Ignorance

데드락을 무시하는 방법.

매우 드물게 발생하는 일이기 때문에, 운영체제가 데드락에 대해 일하는 것 자체가 낭비라고 생각하는 방식.
아무것도 안함.

현대의 범용 운영체제들은 이 방식을 채택한다.
그럼 데드락 생기면 어떡해요?
-> 운영체제가 아무 동작 안해주니, 사람이 직접 처리해야함... 프로세스를 죽이든지 하는 방식으로,,,

데드락이 점점 운영체제에서 중요성이 줄어들고 있음.