chap06.md

CHAP 06

• 교착상태(Deadlock): 컴퓨터 시스템에서 자원이 한정적인 상황에서 두 개 이상의 프로세스가 각자 먼저 확보한 자원을 가진 채 상대방의 자원을 필요로 할 경우, 외부로부터의 조치가 없는 한 이들은 아무 일도 못하고 계속 기다려야 함

교착 상태

• 교착상태가 발생하는 근본적인 원인: 시스템이 가지고 있는 한정적인 자원보다 사용하고자 하는 프로세스들의 요청이 더 많기 떄문
• 교착 상태: 둘 이상의 프로세스가 각자가 가지고 있던 자원을 보유한 채로 외부적 조치가 없는 한 영원히 그 상태에서 기다리고 있는 상황
  • 문제점
    1. 해당 프로세스들이 더 이상 실행되지 못하여 사용자들에게 응답해주지 못함
    2. 보유된 자원들이 교착 상태에서 벗어나기 전까지는 전혀 활용되지 못함
    • 이것들은 모두 시스템의 성능 저하로 이어지게 됨
  • 무한대기(indefinite postponement)와 차이점 : 무한 대기는 운영체제 상의 규칙이 한쪽으로 치우쳐(biased)있기 떄문에 발생. 오랜 시간 후에라도 무한 대기로부터 벗어나 (외부 조치가 없더라도) 서비스를 받을 수 있음

자원

• 자원: 교착 상태를 일으키는 원인 중 하나
• 자원의 종류 (소프트웨어의 관점에서)
  1. 하드웨어 자원: 눈으로 보고 만질 수 있는 모든 자원들
  2. 소프트웨어 자원: 데이터나 메시지
• 자원의 종류 (선점 가능성에 따라)
  1. 선점 가능 자원 (Preemptible): CPU나 메모리와 같은 자원처럼 한 프로세스에 의해 사용 도중 선점되어 다른 프로세스에게 할당해주었다가 이후 다시 원래의 프로세스에게 돌려주어도 되는 자원들
     • 사용하는 이유: 다중 프로그래밍의 성공을 위해서
  2. 선점 불가능 자원 (Nonpreemptible): 선점이 될 경우 자원을 뺏긴 프로세스는 정상적인 진행을 포기해야하는 불이익을 받게 되는 경우의 자원. 선점이 불가능한 자원.
     • 사용 도중 뻇을 수 없도록 하고 있음 (예시 책 참고)
     • 사용하는 이유: 시스템의 정상적인 진행을 위해서
• 자원의 종류 (자원이 사용되어지는 방식에 따라)
  • 한 프로세스에게 할당된 자원을 동시에 다른 프로세스가 할당받아 같이 사용할 수 있는가?
    1. 공유 가능 자원(Sharable): 공유 가능한 프로그램(시스템 프로그램 or 유틸리티 프로그램 등), 공유 데이터 -> 시스템의 모든 자원이 공유 가능 자원이라면 deadlock 발생 안함 (그러나 실제 시스템에서는 배타적 사용 자원이 필요한 경우가 많음)
    2. 배타적 사용 자원(Exclusive): CPU, 메모리, 테이프, 버퍼, 키보드, 모니터 등
• 자원의 종류 (자원의 속성에 따라)
  1. 순차적 재사용 가능(Serially Reusable): 먼저 할당된 자원이 사용 후 반납되었을 때 자원 자체는 계속 존재하여 또 다른 프로세스에게 할당이 가능할 떄의 자원
     • 시스템에서 프로세스들이 아무리 사용해도 없어지지 않고 영구히 존재함
     • CPU, 메모리, 테이프, 하드디스크, 버퍼, 프로그램 등
  2. 소모성 자원(Consumable): 사용 후 사라지는 자원
     • 시그널(일시적으로 생성되었다가 사용된 후 없어지는), 메시지 등

프로세스

실행 중인 프로세스가 자원에 대해 취할 수 있는 행동

1. 필요한 자원에 대한 요청(request)
   1. 요청된 자원이 사용가능(available)하다면 (시스템이 보유하고 있고, 현재 아무도 사용하고 있지 않은 상태의 자원): 이 자원을 할당받아 사용
   2. 이 자원이 다른 프로세스에 의해 사용중이라면: 반납되어질 때까지 대기 상태(blocked)로 기다려야함.
      • 대기 상태의 프로세스는 자력으로 그 상태에서 벗어날 수 없고 자원의 요청이나 반납과 같은 행동은 더 이상 할 수 없음
2. 사용이 끝난 자원의 반납
   • 자원의 요청과 반납은 실행 중인 프로세스가 시스템 서비스를 호출(system call)함으로써 운영체제에 의해 이루어짐
   • 반납된 자원으로 그 자원 때문에 대기 중인 프로세스를 깨우는 것도 운영체제

교착 상태의 원인

• 아래 4가지 중 하나라도 부정할 수 있다면 교착 상태는 절대로 발생하지 않음

1. 자원의 배타적인 사용 [M.E]: 시스템이 보유한 자원 중 배타적 사용이 요구되는 자원 때문에 교착 상태가 발생하는 원인이 됨 -> 상호배제 조건(mutual exclusion condition)
2. 자원의 부분 할당 (partial allocation) [H.W]: 어느 시점에 할당이 불가능한 자원 때문에 이미 확보한 자원들을 소유한 채 대기 상태가 되어버리는 과정을 겪으면서 교착 상태에 빠질 가능성을 높이는 것 -> 보유와 대기 (Hold & Wait) 조건
3. 자원의 선점 불가능성[No preemption]: 선점 가능한 자원이라면, 자신의 자원을 선점당한 프로세스들은 정상적인 실행을 포기해야함 (선점을 당한다 == 그 자원을 가지고 지금까지 해왔던 일들을 잃게 되는 것) 결국 자원의 선점 불가능성을 고수할 경우 교착 상태의 원인이 됨 -> 비선점(No Preemption) 조건
4. 자원에 대한 환형 대기 (circular-wait)[Circular w]: (책의 그림, 설명 참고)-> 그래프 이론에서 일컫는 사이클(Cycle)이 있음 -> 환형 대기(Circular wait)

교착 상태의 해결

1. 예방(prevention) 기법: 교착 상태를 아예 발생되지 않도록 하는 것
2. 회피(avoidance) 기법: 역시 프로세스들이 교착 상태를 피해가도록 하는 방법
3. 탐지+복구(detection+recovery) 기법 : 교착 상태가 발생되도록 놓아두었다가 발생 또는 발생 후에 교착 상태를 탐지하여 조치하는 방법. 복구 작업을 수반함

• 이전에는 교착 상태가 발생하는 경우가 적고 해결하기 위해 필요한 시간과 자원이 많아서 교착상태가 생기면 해당 프로세스를 죽이거나 시스템을 다시 재부팅하여 해결했었음.
• 이제는 분산 또는 병렬 처리가 일상이 되면서 시스템 내의 프로세스가 많아지고, 자원들은 그 비율만큼 늘어날 수 없으니 결국 한정적인 자원에 대한 프로세스들의 경쟁이 더 치열해짐 -> 교착 상태 발생 가능성이 증가
• 실시간 시스템의 경우 완료 시간을 맞춰야 하는 프로세스가 교착 상태에 빠지게 되면 안됨
• => 교착 상태 해결해야함!

1. 예방 기법 (Prevention)

• 발생 원인의 하나를 제거함으로써 교착 상태의 발생 자체를 막도록 한 방법

1. 자원의 배타적 사용 조건을 배제 : 모든 자원을 공유 가능 자원으로 하여 교착 상태의 발생을 차단 -> 시스템이 보유한 자원 중에는 배타적으로 사용할 수 밖에 없는 자원들이 있음(ex. 프린터, 테이프 장치 등) -> 이 조건을 배제하여 교착 상태를 예방하기는 불가능
2. 자원의 부분 할당을 배제: 모두 할당(Total allocation) -> 프로세스들은 각자 자신이 필요한 모든 자원을 미리 할당받아 실행을 시작하도록 하는 방법 (실행 도중 자원을 요구하는 일도 x, 대기 상태가 될 일도 x) "All or None" = "All at once"
   • 문제: 필요한 모든 자원이 확보되지 못한 프로세스는 대기 상태가 된다
     • 일이 시작될 떄 부터 모든 자원이 있어야할 경우란 거의 없음 -> 그 중 몇개만 실제로 사용되는 것이 일반적인 상황
     • 일부 자원만 확보되면 시작될 수 있음에도 불구하고 모든 것을 할당받을 때까지 기다려야 하고, 할당이 가능했던 일부 자원들은 사용되지 못해 낭비되는 현상이 발생
     • 모든 자원이 확보되어 실행을 시작할 경우에도 시작 시점에서 할당된 자원들이 실제로 사용되는 시점까지는 역시 낭비되는 것
   • 단점
     1. 위의 문제에 의해, 심각한 자원의 낭비가 초래되는 방법임
     2. 무한대기를 겪게 될 프로세스가 발생할 수 있음
        • 필요한 모든 자원 중 대부분이 할당 가능하지만 그 중 한 두개가 다른 프로세스가 사용 중이라서 대기하던 프로세스에게 시간이 흐른 후 대기의 원인이었던 그 한 두개가 사용 가능해졌다면 -> 그러나 이번에는 아까 할당이 가능했던 자원 중 몇 개가 그 동안 다른 프로세스에게 할당 되어버려 다시 대기를 해야하는 상황이 반복해서 발생한다면 -> 프로세스는 계속해서 실행을 늦출 수 밖에 없게 됨 (무한대기)
3. 자원의 선점 불가능성을 배제: 모든 자원이 선점 가능하도록 할 경우 교착 상태는 발생하지 않을 것 -> 그러나 문제 발생
   • 일부 자원을 가지고 실행하던 프로세스가 현재 할당이 불가능한 자원을 요청할 경우 자신이 보유하고 있던 자원을 내놓게 함으로써 (=선점 되어버린다) 비선점 조건을 없앰[장점]
     • 자원을 반납시킨 프로세스는 나중에 필요한 자원을 다시 한꺼번에 요청하여 일을 진행함
     • 단점 1: 그러나 이는 비정상적인 종료와 함꼐 심할 경우 다시 처음부터 시작해야하는 불이익을 받게 됨 -> 반납되어진 자원들을 사용하여 지금까지 해 왔던 일이 모두 무효가 됨으로써 결과적으로 그 동안 가동되었던 모든 자원들은 사실상 낭비된 결과가 되는 것
     • 단점 2: 이러한 비정상적인 종료가 자주 발생할 경우 -> 자원의 낭비 , 해당 프로세스는 정상적인 종료를 해보지도 못하고 계속해서 '처음부터 다시' 해야하는 무한 대기도 겪게 될 가능성 높음
4. 자원의 환형 대기 상황을 배제 : linear-ordering
   • 자원 R1과 R2를 일직선상에 순서를 정해 놓은 후 P1과 P2는 자원의 요청을 순서대로 한 방향으로만 가능
   • 모든 프로세스는 자신의 실행 동안 필요한 자원들을 실제로 사용할 시기와 상관없이 시스템에 정해놓은 순서에 따라 가져가도록 한 것
   • 자원들의 순서를 정하고 프로세스들은 이 순서를 지켜 요청하도록 함으로써, 모든 화살표가 한 방향으로만 생성하도록 하여 사이클이 발생될 소지를 없애 교착 상태를 없앤 방법
   • 단점 1: 순서를 지켜야하기 떄문에 당장에 필요 없는 자원을 먼저 할당받아야 함 -> 자원의 낭비
   • 단점 2: 실제로 필요한 자원을 확보하기 위해 지금 당장 필요 없는 순서상의 하위 자원들을 확보하느라 많은 시간을 보내야하는 프로세스 발생 -> 무한 대기 발생

• 위의 방법들 모두 자원의 심각한 낭비, 특정 프로세스의 무한 대기 가능성이 존재
• Realtime 시스템에서는 교착 상태 방지를 위해 이런 단점들을 수용해서라도 prevention 방법을 사용한다

2. 회피 기법

• 자원의 낭비는 예방 기법보다는 덜하는 여기서도 꽤 발생함
• 대표적인 알고리즘: Dijkstra의 은행가 알고리즘(Banker's Algorithm)
• 안전 상태 (safe state): 시스템에 있는 모든 프로세스가 유한 시간 내에 정상적으로 종료될 수 있는 상태, 교착 상태가 발생할 수 없는 상태
• 불안전(unsafe) 상태: 교착 상태로 갈 가능성이 있음 (꼭 교착 상태는 아니다)-> 방지책이 없음
• 회피 기법: 시스템의 상태가 안전 상태로만 가도록 지속적으로 제어해나가는 것
  • 각 프로세스의 자원에 대한 요청을 해당 자원이 사용 가능하다고 해서 할당하는 것이 아니라 할당의 결과 시스템이 계속 안전상태가 되느냐에 따라 결정함
• 은행가 알고리즘이 제대로 작동하기 위해 시스템에 대해 필요한 가정 4가지
  1. 시스템 내의 프로세스 수가 고정되어 있어야 한다
  2. 자원의 수도 고정되어 있어야 한다
  3. 각 프로세스가 요구할 자원의 최대 개수가 알려져야 한다
  4. 각 프로세스는 할당받은 자원을 사용 후 반드시 반납하여야 한다
  • 1번은 일반적인 시스템에서는 지켜지기가 어려움
  • 3번은 프로세스가 실제로 실행을 마쳐야 알 수 있는 것이므로 미래를 알아야하는 것이기 때문에 지키기 어려움
    • 따라서 은행가 알고리즘은 교착 상태를 말할 때 이론적인 접근의 방편으로 언급됨
    • 예방 기법과 비교했을 때 시작도 못하고 있던 프로세스를 실행시킬 수 있다는 점에서 자원의 낭비 감소 가능

Dijkstra의 은행가 알고리즘

• 시스템을 safe/unsafe state로 나누어서 어떤 process가 resource를 요구했을 떄 그 resource가 현재 사용가능하다 하더라도 그걸 그 process에 준 결과가 safe하면 주고, unsafe하면 주지 않음
  • 시스템을 계속 safe한 상태로 유도할 수 있도록 해서 deadlock을 피함
• 예시 책 참고할 것

3. 탐지 기법 detection & recovery

• 교착 상태의 발생을 허용 -> 교착 상태를 어떤 방법으로든 찾아내어 적절한 대응을 하겠다는 것
• 탐지를 위한 프로그램(운영체제의 프로그램) 실행
  • 그걸 위해 탐지 프로그램이 알 수 있는 적당한 형태로 시스템 내에 표현되어 있어야 함 "어떤 프로세스가 어떤 자원을 가지고 있는가?" "어떤 프로세스가 어떤 자원에 의해 대기 상태가 되어 있는가?"
    • 자원 할당 그래프(Resource Allocation Graph; RAG)
• 운영체제가 관리하는 모든 자원들은 그들에 대한 정보가 프로그램이 처리할 수 있는 형태로 저장 되어 있음 (Table, Array, Vector, Matrix, List 등..) => 이들에 대한 관리 작업이란 실제로는 저장된 자료에 대한 읽기/쓰기, 수정/추가, 삭제 등의 실행을 하는 것
• RAG
  1. RAG는 방향성(Directed) 이분(Bipartite) 그래프. 노드와 에지들로 이루어져 있음
     • 노드: 프로세스, 자원을 표현
     • 에지: 프로세스와 자원들 간의 할당과 대기 상황을 나타냄
     • 프로세스 -> 자원으로 향하는 에지가 의미하는 2가지
       1. 요청 중
       2. 대기 상태
          • 즉시 할당 상태(Expedient State): 2가지로 다르게 해석될 가능성이 있는 경우 RAG로 교착 상태를 탐지하는 작업이 훨씬 어려워지므로 요청 중이라는 상황이 생기지 않게 시스템이 바로 대처(할당 OR 대기로 바로 결정)
  2. RAG에서 자원 노드는 그 자원의 형(Type)을 나타냄
     • 안에 작은 동그라미: 자원의 개수
     • 한 자원 형에 여러 개의 자원이 있을 수 있음
  • 시스템에서 요청과 할당 그리고 대기와 같은 일이 발생할 때마다 운영체제는 이 사실들을 RAG에 반영.
    • 프로세스와 자원의 생성/소멸: 해당 노드의 추가와 삭제로 RAG를 수정
    • 자원에 대한 할당/반납,대기: 해당 에지의 추가와 삭제로 RAG를 수정

그래프 제거(Graph Reduction)법 으로 교착 상태를 탐지

• 싱크(Sink)(=unblocked process): 즉시 할당 상태를 가정하면 RAG에서 자원으로 향하는 에지가 없는 프로세스 -> 활동이 가능한 프로세스.
• RAG의 모든 싱크에 대해 자원들을 반납하는 작업을 계속하여 에지가 모두 제거되어 버리면 (Completely Reducible) -> 교착 상태가 없다고 판단
  • 만약 지워지지 않은 에지들이 있다면(Irreducible) 이 에지에 연결되어 있는 프로세스들이 교착 상태에 빠져 있는 걸로 결론이 남
• deadlock을 여러개 발견할 수도 있음! (0개~여러개)
• sink 순서는 신경 쓰지 않아도 됨
• 단점
  • 한번 deadlock을 detection할 때 system 전체를 따라가야하므로 시간이 걸림
  • 주기적으로 실행하므로 reduction 실행 직후에 발생한 deadlock은 다음 reduction을 할때야 발견이 가능함

그래프 탐색(Search) 기법으로 교착 상태를 탐지

• 자원의 할당과 반납은 교착상태와 거리가 멈
• 요청 후 대기 상태로 될떄가 교착 상태를 형성시킬 가능성이 있음

1. 탐색 도중 싱크가 발견되면 교착 상태는 없다고 판단
   • 대기 상태를 만든 요청은 단순한 대기일 뿐이고 교착 상태로까지 만들지는 않았다는 의미
2. 노드 자신으로 되돌아오는 사이클이 발견되면 교착 상태가 된 것
   • 사이클의 발견이 곧 교착 상태는 모든 자원 형이 한 개씩의 자원을 가졌을 떄의 이야기 -> 사이클 발견은 단지 교착 상태의 가능성을 높이는 필요 조건일 뿐
   • 한 자원 형에 다수 개의 자원이 있는 경우 노트(Knot)라는 자료구조의 발견이 곧 교착 상태의 발견이 됨

• 자주 실행하게 됨 (blocked이 발견될때마다)
• 장점: 횟수 적고, 걸리는 시간이 적음

복구 기법 (recovery)

• 교착 상태에서 벗어나기 위한 방법

1. 프로세스의 종료 (process termination) 방식
   • 교착 상태를 형성한 프로세스들 중 몇 개를 강제로 종료시켜 이들로부터 반납된 자원으로 복구를 하게됨
   • 문제: 어떤 프로세스를 종료시킬 것인가?
     1. 교착상태로부터 복구될 떄까지 종료 비용이 최소인 프로세스(Lowest-termination-cost Process First)
        • 종료 비용: 강제 종료되는 프로세스가 잃게 되는 일의 양으로부터 산출되는 비용
          • 우선순위나 종류, 실행된 시간의 크기, 남은 시간 등에 의해 산정됨
            • 우선순위 낮고, 실시간이 아니고, 실행된 시간이 적고, 남은 시간이 큰 것 -> 종료 비용이 싸다고 봄
        • 비교적 간단하나 프로세스를 종료시킬 때마다 교착 상태가 제거되었는지 알아봐야함
     2. 교착 상태에 있는 프로세스들의 집합에서 가능한 부분 집합을 만들어 이 집합들에 속하는 프로세스들을 종료시켰을 경우의 비용을 따져 최소의 비용이 드는 부분집합에 속하는 프로세스들을 한꺼번에 종료시키는 방식 취하는 것
        • 최소 비용의 프로세스를 고를 수 있으나 모든 부분 집합에 대해 비용을 계산하기가 어렵고 복잡할 수 있음
2. 자원의 선점에 의한 방식

• 필요한 자원을 가지고 있는 프로세스로부터 강제로 뺏어(선점하여) 교착 상태에 있는 프로세스들에게 줌으로써 해결
• 선점 시의 최소 비용 따져야 함
• heuristic
• 단점1: 프로세스의 강제 종료는 그 동안의 일을 없던 것으로 하고 처음부터 다시 해야하기 떄문에 복구 비용을 키우는 주요인이 됨 -> 시스템의 입장에서 낭비 요인
• 단점2: 특정 프로세스의 입장에서 종료 비용을 계산하는 근거에 계속적으로 해당될 경우 반복적인 종료를 겪을 수 있어 매우 불이익을 받게 될 것임
• 강제 종료 시의 낭비를 줄이는 방법 : 검사점 지정(Checkpointing), 재시작(Restart)
  • 검사점(Checkpoint): 프로세스들이 실행의 중간 중간에 그 시점까지의 실행 결과를 보존하고 표시해두는 것
    • 재시작 비용을 최소화
  • 재시작: 강제로 종료될 떄 아예 처음으로 돌아가는 것이 아니라 가장 최근의 검사점으로부터 차례로 하나씩 되돌리는 것
    • 잃게 되는 일의 양을 최소화

---

시험 대비 핵심 정리

• 교착 상태가 일으키는 문제 2가지
• 자원의 종류 (4가지 방법으로 분류 가능)
• 프로세스가 자원에 대해 할 수 있는 행동 2가지
• 교착상태 원인 4가지
• 교착 상태 해결 4가지 방법

1. 4가지 있음 + 각각 발생하는 문제점 2가지 (왜 발생?도 이해하기)
2. 안전상태 개념 (+가정 4가지), 은행가 알고리즘 이해
3. 그래프 이름? 탐색 방법 이해
4. 기법 2가지 -> 강제 종료시의 낭비 줄이는 방법?