[OS] 9. 데드락 - (3)

[이화여자대학교 반효경 교수님의 강의를 듣고 정리한 글입니다.]

운영체제

운영체제 운영체제는 컴퓨터 하드웨어 바로 위에 설치되는 소프트웨어 계층으로서 모든 컴퓨터 시스템의 필수적인 부분이다. 본 강좌에서는 이와 같은 운영체제의 개념과 역할, 운영체제를 구성하는 각 www.kocw.net

운영체제

---

[그림과 함께 편하게 보려면 여기로]

https://adorable-aspen-d23.notion.site/OS-9-3-8cb5bff3e4eb458b9d8c1133224e1aa5

[OS] 9. 데드락 - (3)

1. DeadLock(교착상태)

: 프로세스들이 각자 일부 자원을 가지고 있으면서, 상대방이 가진 자원을 요구하는 상태

• 자원
  • 하드웨어, 소프트웨어 등을 포함하는 개념
  ex) I/O device, CPU cycle, memory space, semaphore 등

1. Deadlock 발생의 4가지 조건

1. Mutual Exclusion (상호배제)

• 상호 배제적으로 사용되는 자원을 사용할 때 발생한다.
  • 프로세스들이 동시에 한 자원을 사용할 수 있다면 해당 자원에 대해서는 데드락 발생X

2. No Preemption (비선점)

• 프로세스는 자원을 스스로 내어놓을 뿐 빼앗기지 않는다. (강제로 빼앗기지 않는다)
  • 양보 따윈 없다

3. Hold and wait (보유대기)

• 자원을 가진 프로세스가 다른 자원을 기다릴 때 보유 자원을 놓지 않고 계속 가지고 있음 (스스로 내놓지 않는다)
• 프로세스는 일을 하기 위해 가지고 있는 자원은 절대로 내어놓지 않고 다른 자원이 오기까지 기다린다.

4. Circular wait (순환대기)

• 자원을 기다리는 프로세스들 간에 Cycle이 형성된다.

2. 자원그래프

• Cycle 없음
  • 데드락이 아니다.
• Cycle 존재
  • 자원의 인스턴스의 갯수 == 싸이클의 갯수 이면 데드락이 아니다.
  • 이외의 경우는 데드락이다.

2. 교착상태 해결

1. Prevention(예방)

: 데드락의 네 가지 조건 중 하나를 무산시킨다.

• Mutual Exclusion
  • 이것은 데드락 방지를 위해 무산시킬 수는 없다.
  • 공유될 자원이면 애초에 데드락이 발생하지도 않음
• No Preemption
  • 외부에서 강제로 빼앗아 버린다. (선점)
  • 프로세스가 어떤 자원을 기다려야 하는 경우, 대기상태로 들어가면서 현재 할당 받은 자원을 강제로 반환한다. (선점)
    • 이후 자원을 선점 당한 프로세스가 재시작시, 반환한 자원 + 요청한 자원 모두 할당받아야 한다.
  • 그래서 CPU, memory는 데드락이 발생하지 않는다.
    • 왜? → 선점당할 수 있게 설계되어 있기 때문이다. 얘네는 context swtiching으로 문맥 보존도 가능하다.
    • 입출력장치, mutex, semaphore 는 context를 저장할 수 없기 때문에 선점이 불가능하다.
• Hold and Wait
  • 어떤 작업을 하기 위해 필요로 하는 자원을 획득하려고 할 때, 다른 어떤 자원도 가지고 있지 않아야 한다.
    • 1. 프로세스 시작 시 모든 필요한 자원을 할당받게 하는 방법 (대기없음)
      • But, 지금 바로 안쓰는 작업 쥐고 있으면 효율성 떨어짐
    • 1. 자원이 필요할 경우 보유 자원을 모두 놓고 다시 요청 (점유없음, 자진반납)
      • But, 기아상태 가능
        • 자주 쓰이는 작업은 이미 다른 곳에 할당되어 있기 때문에
• Circular Wait
  • 모든 자원 유형에 할당 순서를 정하여 정해진 순서대로만 자원을 할당한다. (일렬번호 부여)
  • 번호가 증가하는 순으로만 자원 요청 가능
    • 1,3을 획득해야 하는 프로세스는 반드시 1,3 순으로 획득해야 한다.

⇒ But, 예방 방법은 너무 비효율적이다. (생기지도 않을 데드락을 막는다니?)

Utilization 저하, throughput 감소, Starvation 문제 발생 가능

2. Avoidance (회피)

: 프로세스가 시작될 때 평생 쓸 자원의 최대량을 알고 있다고 가정한다.

• 자원 요청 시 최대를 Allocation 했을 경우를 가정해서 안정 상태가 유지되는지를 확인한다.
  • 데드락이 일어날 것 같으면 자원의 여분이 있어도 아예 자원을 안줌
• 안정 순열
  • 시스템이 어떤 순서로든 프로세스들의 최대 요구 수에도 교착 상태를 야기하지 않는다.
• 안정 상태
  • n!개의 순열 중 안정순열이 하나라도 존재하면 안정상태이다.
  • 자원을 할당해줘도 안정상태가 유지되는가?
• Single Resource
  • 점선 : 프로세스가 평생에 요구할 수 있는 자원
    • 점선을 연결해서 사이클이 형성되면 데드락이 발생할 수 있다고 가정하고 자원 안줌
  
• Multiple Resource
  • Banker’s Algorithm (Safety Algorithm)
    • Allocation : 현재 할당중인 자원의 양
    • Max : 프로세스가 평생 쓸 자원의 양
    • Work : (전체에서) 현재 사용 가능한 자원의 양
    • Need : 프로세스가 앞으로 더 요구할 자원의 양 (Max - Allocation)
    ⇒ 현재의 Work로 Need를 만족시킬 수 있다면 안정상태이다.
    • Safety Algorithm
    • 
  • 모든 프로세스를 순서대로 돌면서 만족시키는 순열이 있는지를 확인한다.
  

⇒ 근데 얘도 비효율적이다.

3. Detection (탐지)

: 현 상태를 대상으로 하여 request와 교착상태를 체크한다.

• 현 상태에서 request가 존재하는 자원내에 사용이 불가능하면 할당하지 않는다.
• 알고리즘
• 

4. Recovery (복구)

• 종료(Abort)
  • 교착상태에 있는 모든 프로세스를 종료시킨다.
    • But, 처음부터 계산해야해서 비용이 크다.
  • 교착상태 탐지 알고리즘을 수행시키면서 한 프로세스씩 중지시킨다.
    • But, 탐지 알고리즘 수행에 오버헤드가 발생한다.
• 선점(Resource Preemption)
  • Rollback(후퇴) 필요
    • 안정상태가 확인될 때까지 자원을 이동시키며 rollback시키고, 거기서 다시 시작한다.
      • But, 안정상태 결정이 힘드며, 프로세스 상태 정보 관리가 필요하다.
      • ⇒ total rollback (abort & restart)
      • But, 기아상태가 발생할 수 있다.
        • 비용에 근거하여 프로세스 선점 시 특정 프로세스만 계속 선점될 수 있다.
        ⇒ 유한 횟수로만 희생자 선정, 비용에 희생 횟수를 반영

5. Ignorance (무시)

• 아무것도 안함
• 데드락은 잘 발생하지 않는 애기때문에 얘를 막으려고 쇼하는게 비용이 더 많이 든다. (낭비)
• 그러니까 발생해서 프로그램 느려지면 → 사용자가 눈치챙겨서 → 알아서 종료시키기