운영체제 - 병행제어(9)

2020-10-10

OS를 공부하면서 정리를 한 내용들 입니다.

데드락의 처리방법 네 가지중 데드락 어보이던스에 대해 알아봅니다.

Deadlock Avoidance

  • 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로 부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당.

  • 가장 단순하고 일반적인 모델은 프로세스들이 필요로 하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법

Safe state

  • 시스템 내의 프로세스들에 대한 safe sequence가 존재하는 상태

Safe sequence

  • 프로세스의 sequence<P1,P2,…,Pn>이 safe하려면 Pi(1 <= i <= n)의 자원 요청이

    “가용자원 + 모든 Pj(j<i)의 보유 자원”에 의해 충족 되어야 함.

  • 조건을 만족하면 다음 방법으로 모든 프로세스의 수행을 보장.

  1. Pi의 자원 요청이 즉시 충족될 수 없으면 모든Pj(j<i)가 종료될 때까지 기다린다.
  2. Pi-1이 종료된다면 Pi의 자원요청을 만족시켜 수행한다.

2가지 경우의 avoidance 알고리즘

  1. Single instacne per resource type
  • Resource Allocation Graph Algoritum 사용

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

데드록의 개념을 알기 위해서 자원 할당의 과정이 어떤식인지 그림으로 간략히 표현한 그림 입니다.

출처 : basic it topic

프로세스(P)와 자원(R)이 각각 n, m개가 있고

간선 프로세스에서 자원으로 가는 선은 request, 자원에서 프로세스로 가는 선은 assignment입니다.

점은 자원에 있는 instance의 갯수입니다.

  1. Multiple instances per resource types
  • Banker’s Algorithm사용

Banker’s Algorithm

  1. 가정
    • 모든 프로세스는 자원의 최대 사용량을 미리 명시한다.
    • 프로세스가 요청 자원을 모두 할당받은 경우 유한 시간 안에 이들 자원을 다시 반납한다.
  2. 방법
    • 기본개념: 자원요청시 safe 상태를 유지할 경우에만 할당
    • 총 요청 자원의 수가 가용 자원의 수보다 적은 프로세스를 선택(그런 프로세스가 없으면 unsafe 상태)
    • 그런 프로세스가 있으면 그 프로세스에게 자원을 할당)
    • 할당받은 프로세스가 종료되면 모든 자원을 반납
    • 모든 프로세스가 종료될 때까지 이러한 과정 반복

출처 : sSlideServe

-참고 KOCW 이화여자 대학교 반효경 교수님 : 운영체제 강의