교착상태(Deadlock)

개념
Multi processing 환경에서 다수의 프로세스가 특정자원의 할당을 무한정 기다리고 있는 상태 교착상태에 있는 프로세스들은 결코 실행을 끝낼 수 없으며 시스템 자원이 묶여있어서 다른 작업을 시작하는 것도 불가능

I.  교착상태(Deadlock)의 개요
    가. 교착상태(Deadlock)의 정의

  • Multi processing 환경에서 다수의 프로세스가 특정자원의 할당을 무한정 기다리고 있는 상태
  • 교착상태에 있는 프로세스들은 결코 실행을 끝낼 수 없으며 시스템 자원이 묶여있어서 다른 작업을 시작하는 것도 불가능

 

    나. 교착상태와 무한대기의 비교

구분

Deadlock(교착상태)

Starvation(무한대기)

정의

다수의 프로세스가 아무 일도 못하고 특정사건 무한대기

특정 프로세스가 자원을 할당 받기 위한 무한정 대기 상태

발생원인

상호배제, 점유와 대기, 비선점, 환형대기

자원의 편중된 분배정책

해결방안

예방, 회피, 발견, 회복

Aging 기법

 
II. 교착상태의 개념도 및 발생 조건

    가. 교착상태의 개념도
 


    나. 교착상태의 발생원인
         - 교착상태는 한 시스템에서 다음 네 가지 조건이 동시 성립 시 발생

원인

상세 내역

상호배제

(Mutual Exclusion)

프로세스들이 자원을 배타적으로 점유하여 다른 프로세스가 그 자원을 사용하지 못함

점유와 대기

(Block & Wait)

프로세스가 어떤 자원을 할당 받아 점유하고 있으면서 다른 자원을 요구

비선점

(Non Preemption)

프로세스에 할당된 자원은 사용이 끝날 때까지 강제로 빼앗을 수 없으며, 점유하고 있는 프로세스 자신만이 해제 가능

환형 대기

(Circular wait)

프로세스간 자원 요구가 하나의 원형을 구성

 
III. 교착상태의 해결 방안
    가. 교착상태의 예방(Prevention)

  • 상호배제 예방 : 상호배제 사용하지 않음(동시액세스 허락)
  • 부분할당 예방: 프로세스가 필요로 하는 자원을 일시에 요구/할당
  • 비선점 예방 : 자원임시 할당해제 및 원상복구(다루기가 힘듦)
  • 환형대기 예방 : 모든 자원 고유번호 지정하여 환형대기 예방

 

    나. 회피(Avoidance)-Banker’s Algorithm(은행가 알고리즘)

  • 운영체제(OS)는 자원의 상태를 감시
  • 프로세스는 사전에 자기 작업에서 필요한 자원의 수를 제시
  • OS는 사용자 프로세스로부터 자원의 요청이 있으면 모든 프로세스가 일정기간 내에 성공적으로 종료될 수 있는 안전한 상태인지 면밀하게 분석
  • OS는 안전한 상태를 유지할 수 있는 요구만을 수락, 그 외의 요구는 만족될 때 까지 계속 거절

 

    다. 교착상태의 발견(Detection)

  • 시스템의 상태를 감시하는 알고리즘을 통하여 교착상태를 검사하는 알고리즘
  • 시스템의 자원할당 그래프로 교착상태검출(Graph reduction, cycle Detection, Knot detection)
  • 교착상태 발생 시 자원할당 소거

 


    라. 교착상태의 회복(Recovery)
        - Deadlock이 없어질 때까지 프로세스를 순차적으로 Kill하여 제거
        - 프로세스 종료비용 최소화 : 우선순위, 진행비용, 복귀비용 등
        - 자원의 우선순위 할당 : 희생자 선택, 복귀, 기아상태

 

IV. Wait-die와 Wound-wait 기법 비교

비고

Wait-die

Wound-wait

정의

오래된 트랜잭션 기다리고, 새로운 트랜잭션이 Rollback 되고 다시 계획

오래된 트랜잭션이 새로운 트랜잭션을 rollback 시키고 이를 다시 계획

트랜잭션 양

lock을 요청하는 단계 중에 abort되어 재시작되므로, abort되는 트랜잭션의 처리된 양이 적음

처리도중 높은 우선 순위

트랜잭션에 의해 abort되므로, 그 동안 처리된 일이 모두 무시되어 불필요한 작업 수행

공통점

- 두 방법 모두 우선 순위가 높은 트랜잭션이 낮은 트랜잭션을 abort 시킴

- 중지된 트랜잭션은 기존 타임스탬프를 가지고 재시작

- 결국 시스템에서 가장 높은 우선 순위를 갖게 되어 완료됨

- 구현이나 관리가 waits-for graph보다 쉬움

 

V. 교착상태 해결을 위한 전체 시스템 설계
    가. 내부 시스템 자원을 순서화

  • PCB, 버퍼, Semaphore 등의 자원 순서화

    나. 사용자 작업에 대한 주기억 장치 선점

  • 선점은 Paging, Segmentation, Swapping 시스템에서 가장 효율적인 접근법
  • 선점이 불가능 하면 주기억장치를 작업 자원의 부류에 포함시킴

    다. 작업이나 작업단계의 자원필요량 산정
    라. 교체 가능 공간 사전 할당

  • 요구된 기억장치를 사전에 할당

 

[ Livelock]

  • Lock : 잠금이 발생한 상황
  • Blocking : 잠금을 발생시킨 프로세스간 차단행위
  • Deadlock: 두 개 이상의 프로세스가 블록 된 채로 상대방이 보유한 자원을 해재하기를 기다리는 상태로 두 개 이상의 프로세스가 경계구역에 동시에 들어가지 못하게 하는 상호 배재 때문에 발생
  • Livelock: 데드락은 프로세스 집합 내의 프로세스들이 요구하는 자원을 할당 받지 못해서 블록된 상태로 계속 대기하는 반면 라이브 락은 자원을 할당 받기 위해 상태를 계속 바꾸지만 더 이상 진행되지 못한다.
  • 외나무 다리에서 서로 비키지 않고 대기하는 것이 데드락, 서로 비켰다가 다시 전진하는 것이 라이브 락.
  • 예를 들면 좁은 길을 걷고 있다가 대면한 보행자 2명이 서로 상대가 피하려고 한 방향으로 움직여 버려 피할 수 없는 경우가 있다. 다음에 반대의 방향으로 피할 려고 하지만 피할 수 없다. 이러한 상황이 계속 되어 몇 시간이 지나도 엇갈릴 수 없게 되는 상황에 해당한다.

 

 

  • 그림1 의 상황에서 서로 양보하려다 보니 그림 2의 상황이 되고, 또 서로 양보하려다 보니 그림 3이 되고 이것이 계속 반복 되어 A와B는 서로 지나가지 못하는 상태.
  • Sql Query 실행기에서의 Live Lock
  • Sql Query 실행기를 두 개 띄우고,  첫번째 Sql Query 실행기에서 특정 테이블에 대하여 Update문을 실행하고 Commit이나 RollBack은 실행하지 않는다.
  • 두번째 Sql Query 실행기에서 똑같은 update문을 실행하면 첫번째 Sql이 종료되지 않았으므로 두번째 Sql은 Livelock 상태.
  • 첫번째 Sql이 Commit이나 RollBack으로 명령이 종료되면 두번째 Sql은 Livelock상태가 종료되고 Update문이 실행.

댓글