운영체제 강의 7강

신승준·2022년 5월 29일

운영체제

목록 보기

7/12

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