운영체제 강의 7강

7-1강, Deadlock 1

Deadlock, 교착 상태

• 일련의 프로세스들이, 서로가 가진 자원을 기다리며 Block되어 있는 상태
  • 자원
    • 그 자원은 하드웨어일 수도 있고 소프트웨어일 수도 있다.
    • ex. I/O device, CPU, Memory space, semaphore
  • 프로세스가 자원을 사용하는 절차
    • request, 자원 요청
    • allocate, 자원 획득
    • use, 자원 사용
    • release, 자원 반납
  • Deadlock Example
    
• Deadlock 발생의 4가지 조건
  
  • Mutual Exclusion
    • 자원을 독점적으로 사용하고 있다. 남들은 못 쓰고
  • No preemption
    • 이 자원을 빼앗기지 않는다.
  • Hold and wait
    • 가진 자원은 내놓지 않고 보유하면서, 추가적인 자원을 기다리는 경우이다.
  • Circular wait
    • 서로가 다른 프로세스의 자원을 기다리는, 꼬리에 꼬리를 물게 되어 싸이클을 형성하는 경우이다.

Resource-Allocation Graph(자원할당그래프)

• 자원할당그래프를 통해, 데드락이 발생했는지 안했는지 알 수 있게 된다.
  • 위 상황은 데드락이 아니다.
• 원은 프로세스, 사각형은 자원
• 화살표
  • 자원에서 프로세스
    • 이 자원이 이 프로세스에 있다.
  • 프로세스에서 자원
    • 이 프로세스가 이 자원을 요청한 것(획득이 아니라 그저 request만 한 상태)
• 점은 자원의 갯수(인스턴스 수)
  • R2는 2개의 인스턴스가 있고, R4는 3개의 인스턴스가 있다.
  • 필요하면, 그리고 존재한다면 아무거나 가져다 써도 상관없다.
    
• 위에서 왼쪽은 싸이클이 2개 존재한다. 오른쪽은 1개 존재한다.
• 그래프에 싸이클이 존재하지 않으면 데드락이 아니다.
• 그래프에 싸이클이 존재하면
  • 이때 인스턴스가 1개라면 데드락이다.
  • 하지만 인스턴스가 2개 이상이라면 데드락일 수도 있고 아닐 수도 있다.

Deadlock의 처리 방법

• 데드락을 미연에 방지(강력하게 방지)
  • Deadlock Prevention(가장 강력)
  • Deadlock Avoidance
• 데드락이 생기도록 놔둔다.
  • Deadlock Detection and recovery
    - 데드락을 감지하고 회복
  • Deadlock Ignorance
    - 데드락에 대해 아무 일도 하지 않는다. 생기든 말든 관여하지 않는다. 현대 방법
    • 사람이 알아서 데드락이 걸리면 프로세스를 죽이든가 한다.

Deadlock Prevention

• 데드락이 발생하는 4 조건 중 1가지를 차단하도록 한다.
  • Mutual Exclusion
    • 막을 수 있는 조건이 아니다.
    • 애초에 다 같이 사용할 수 있는 자원이라면 데드락 문제 자체가 안 나올 것이다.
    • 한 번에 하나의 프로세스가 접근할 수 있는 자원이라면 어쩔 수 없이 Mutual Exclusion이 성립된다.
  • Hold and wait
    • 자원을 기다리는 상황에서는 자원을 보유하고 있지 않으면 된다.
    • 방법 1. 프로세스가 시작될 때, 프로세스가 필요로 하는 모든 자원을 할당받게 하는 방법
      • 중간에 추가로 필요한 자원이 없을 것이다.
      • wait할 필요가 없다.
      • 매 시점마다 그 자원이 필요한 것도 아닌데 미리 보유하고 있으면, 자원에 대한 비효율성이 생길 수 밖에 없다.
    • 방법 2. 다른 자원을 기다려야 하는 상황이 된다면, 이미 홀드한 자원을 다 뱉어낸 다음 기다리게 한다.
      • 지금 당장 필요한 것을 다 얻거나, 뱉어낸다.
  • No Preemption
    • 다른 프로세스가 가진 자원을 뺏어올 수 없기 때문에 생긴 문제(프로세스가 한 번 가지고 가면 내놓지 않을 때)
    • 자원을 Preemption할 수 있게 바꾸어야 한다.
      • CPU 같은 자원은 Preemptive 스케줄링을 주로 사용했다.(Timer Interrupt 등)
        • 영원히 반납 안하는 자원을 가지고 있을 수도 있었기 때문이다.
    • 자원 중 CPU나 memory는 빼앗아 올 수 있다.
      • 이러한 자원들은 자원들의 현재 사용 상태를 save하고 restore(회복)할 수 있기 때문이다.
        • 프로세스가 CPU를 빼앗기고, 나중에 다시 얻었을 때 그 다음 직후 시점부터 실행하는 것이 가능했다.
  • Circular Wait
    • 자원에게 번호를 부여한다. 낮은 번호부터 얻어야 다음 번호의 자원을 얻을 수 있다.
      • ex. 1, 3, 5 자원이 있다고 가정하면, 3번 자원을 가지려면 1번 자원을 획득하고 3번을 가지려고 해야 한다.
      • 즉 3번을 가지고 1번을 가지려는 상황이 생기지 않는다.
      • 3인 자원을 가지고 있는 프로세스가 1인 자원을 얻으려고 한다면 3인 자원을 먼저 내놓아야 한다.
• 생기지도 않을 데드락에 대한 제약조건을 다는 셈이 될 수도 있기 때문에 다음과 같은 부작용이 생긴다.
  • Utilization 저하, 자원에 대한 이용률이 떨어진다.
  • throughput 감소, 시스템의 처리량이 떨어진다.
  • starvation 문제

Deadlock Avoidence

• Deadlock Avoidance
  • 프로세스가 시작될 때, 프로세스가 사용할 자원의 최대량을 알고 있다고 가정하고 데드락을 피해가는 것이다.
  • 자원 요청에 대한 부가정보를 이용하여, 자원 할당이 데드락으로부터 안전한지를 동적으로 조사해 안전한 경우에만 할당한다.
  • 가장 단순하고 일반적인 모델은, 프로세스들이 필요로 하는, 각 자원별 최대 사용량을 미리 선언하도록 하는 방법
    

궁금한 점

• Deadlock, 프로세스, 자원의 관계가 애매하게 이해됨.
  

팀 스터디에서 얻은 지식

데드락 동영상

https://www.youtube.com/watch?v=ESXCSNGFVto