07. Deadlock

YeJi Kim·2023년 1월 26일
0

운영체제

목록 보기
7/7
post-thumbnail

교착 상태

  • 교착 상태: 일어나지 않을 사건을 기다리며 무한히 대기하는 현상
  • 식사하는 철학자 문제: 교착 상태의 발생을 보여주는 예시
  • 자원 할당 그래프: 교착 상태를 표현 가능
  • 교착 상태 발생 조건: 상호 배제, 점유와 대기, 비선점, 원형 대기

식사하는 철학자 문제

동그란 원탁에서 5명의 철학자가 두개의 포크가 필요한 식사를 할 때 모든 철학자가 동시에 포크를 집어 식사를 하면 어떤 철학자도 식사를 할 수 없다. 모든 철학자는 다른 철학자가 포크를 내려놓을 때까지 기다립니다. 이렇게 일어나지 않을 사건을 기다리며 진행이 멈춰 버리는 현상을 교착 상태(deadlock)이라고 한다.

  • 철학자 = 프로세스 혹은 스레드
  • 포크 = 자원, 한 번에 하나의 프로세스 혹은 스레드만 접근할 수 있으므로 임계 구역이다.
  • 포크를 기다리는 행위 = 자원을 기다리는 행위

교착 상태를 해결하기 위해서는

첫째, 교착 상태가 발생했을 때의 상황을 정확히 표현해 보고

둘째, 교착 상태가 일어나는 근본적인 이유에 대해 알아야 한다.

자원 할당 그래프

교착 상태는 자원 할당 그래프를 통해 단순하게 표현할 수 있다.

  1. 프로세스는 원으로 자원의 종류는 사각형으로 표현
  2. 사용할 수 있는 자원의 개수는 자원 사각형 내에 점으로 표현한다.
  3. 프로세스가 어떤 자원을 할당받아 사용 중이라면 자원에서 프로세스를 향해 화살표를 표시한다.
  4. 프로세스가 어떤 자원을 기다리고 있다면 프로세스에서 자원으로 화살표를 표시한다.

⇒ 교착 상태가 발생한 상황은 자원 할당 그래프가 원의 형태를 띄고 있다.

사진 출처: https://gamball.tistory.com/entry/%EC%9E%90%EC%9B%90-%ED%95%A0%EB%8B%B9-%EA%B7%B8%EB%9E%98%ED%94%84


교착 상태 발생 조건

교착 상태가 발생할 조건 상호 배제, 점유와 대기, 비선점, 원형 대기 이다.

4개의 조건이 모두 만족될 때 교착 상태가 발생할 가능성이 생긴다.

  • 상호 배제
    • 한 프로세스가 사용하는 자원을 다른 프로세스가 사용할 수 없을 때, 즉 상호배제 상황에서 교착 상태가 발생할 수 있다.
  • 점유와 대기
    • 자원을 할당받은 상태에서 다른 자원을 할당받기를 기다리는 상태를 점유와 대기라고 한다.
  • 비선점
    • 어떤 프로세스도 다른 프로세스의 자원을 강제로 빼앗지 못했기 때문에 교착 상태가 발생했다.
  • 원형 대기
    • 프로세스들이 원의 형태로 자원을 대기하는 것을 원형 대기라고 한다.
    • 프로세스들과 프로세스가 요청 및 할당받은 자원이 원의 형태를 이룬다.

교착 상태 해결 방법

  • 교착 상태 해결
    • 예방: 교착 상태가 일어나지 않도록 교착 상태 발생 조건에 부합하지 않게 자원을 분배하여 교착 상태를 예방
    • 회피: 교착 상태의 위험이 있다면 자원을 할당하지 않는 방식으로 교착 상태를 회피
    • 검출 후 회복: 자원을 제약 없이 할당하다가 교착 상태가 검출되면 교착 상태를 회복

교착 상태 예방

  • 교착 상태 발생 필요 조건 네 가지 중 하나를 충족하지 못하게 하는 방법과 같다.
  • 즉, 프로세스들에 자원을 할당할 때 상호 배제, 점유와 대기, 비선점, 원형 대기 중 하나의 조건이라도 만족시키지 않게 할당하면 교착 상태는 발생하지 않는다.

1. 상호 배제 없애기

  • 자원의 상호 배제를 없앤다는 말은 모든 자원을 공유 가능하게 만든다는 말과 동일하다. 현실적으로 모든 자원의 상호 배제를 없애기는 어렵기에 이 방식을 현실에서 사용하기에는 다소 무리가 있다.

2. 점유와 대기 없애기

  • 점유와 대기를 없애면 운영체제는 특정 프로세스에 자원을 모두 할당하거나, 아예 할당하지 않는 방식으로 배분한다.
  • 단점: 자원의 활용률이 낮아질 우려가 있다. 이 방식은 한 프로세스에 필요한 자원들을 몰아주고, 이로 인해 오랫동안 자원을 기다리는 프로세스와 오랫동안 자원을 사용하는 프로세스가 양산되기 때문에 자원의 활용률이 낮아진다.
    많은 자원을 필요로하는 프로세스가 무한정 기다리게 되는 기아 현상을 야기할 우려가 있다.

3. 비선점 조건 없애기

  • 자원을 이용 중인 프로세스로부터 해당 자원을 빼앗을 수 있다.
  • 선점하여 사용할 수 있는 일부 자원에 대해서는 효과적이다. ex. CPU
  • 하지만 모든 자원이 선점 가능하지 않다. 그렇기에 비선점 조건을 없애 모든 자원을 빼앗을 수 있도록 하여 교착 상태를 예방하는 방법은 다소 범용성이 떨어지는 방법이다.

4. 원형 대기 조건 없애기

  • 모든 자원에 번호를 붙이고, 오름차순으로 자원을 할당하면 원형 대기는 발생하지 않는다.
  • 앞의 세 방식에 비해 비교적 현실적이고 실용적인 방식이지만 단점 존재
  • 단점: 모든 컴퓨터 시스템 내에 존재하는 수많은 자원에 번호를 붙이는 일은 그리 간단한 작업이 아니며 각 자원에 어떤 번호를 붙이는지에따라 특정 자원의 활용률이 떨어질 수 있다.

교착 상태 회피

교착 상태가 발생하지 않을 정도록만 조심해서 자원을 할당하는 방식이다. 항상 안전 상태를 유지하도록 자원을 할당하는 방식이다.
프로세스들에 배분할 수 있는 자원의 양을 고려하여 교착 상태가 발생하지 않을 정도의 양만큼만 자원을 배분하는 방법이 교착 상태 회피 이다.

  • 안전 상태: 교착 상태가 발생하지 않고 모든 프로세스가 정상적으로 자원을 할당받고 종료될 수 있는 상태. 안전 순서열대로 프로세스들에 자원을 배분하여 교착 상태가 발생하지 않는 상태
  • 불안전 상태: 교착 상태가 발생할 수도 있는 상황. 안전 순서열이 없는 상황.
  • 안전 순서열: 교착 상태 없이 안전하게 프로세스들에 자원을 할당할 수 있는 순서

교착 상태 검출 후 회복

교착 상태 검출 후 회복은 교착 상태 발생을 인정하고 사후에 조치하는 방식이다.
검출 후 회복 방식에서 운영체제는 프로세스들이 자원을 요구할 때마다 그때그때 모두 할당되며, 교착 상태 발생 여부를 주기적으로 검사한다. 교착 상태가 검출되면 그때 비로소 회복한다.

  • 선점을 통한 회복

    • 선점을 통한 회복은 교착 상태가 해결될 때까지 한 프로세스씩 자원을 몰아주는 방식. 교착 상태가 해결될 때까지 다른 프로세스로부터 자원을 강제로 빼앗고 한 프로세스에 할당하는 방식.
  • 프로세스 강제 종료를 통한 회복

    • 운영체제는 교착 상태엔 놓인 프로세스를 모두 강제 종료할 수도 있고 교착 상태가 없어질 때까지 한 프렛스씩 강제 종료할 수도 있다.
  • 교착 상태를 아예 무시하는 방법(타조 알고리즘)

    • 타조가 문제에 처했을 때 머리를 땅에 묻고 모른 체하는 모습에서 따 온 이름이다.

[참고자료]
혼자 공부하는 컴퓨터구조+운영체제(저자: 강민철, 출판사: 한빛미디어)

profile
이전의 기록들 👉 https://blog.naver.com/reviewerkyj

0개의 댓글