동현 유
척척석사
동현 유
전체 방문자
오늘
어제
  • 분류 전체보기 (181)
    • BlockChain (48)
      • [paper] Consensus (13)
      • [paper] Execution (19)
      • [paper] Storage (5)
      • [paper] ZKP (1)
      • [paper] Oracle (1)
      • Blockchains (9)
    • Java (19)
      • Java의 정석 (13)
      • Java 파헤치기 (5)
    • Python (20)
      • Python 뜯어보기 (6)
      • 데이터 분석 기초 (5)
      • Python 기초 강의 (6)
      • Python 기초 강의 부록 (3)
    • Golang (0)
    • MySQL (3)
      • programmers (2)
      • 기본 문법 (0)
    • 웹 프로젝트 (IBAS) (36)
      • Django 레거시 (14)
      • SpringBoot api 개편 (14)
      • Infra (3)
      • 서버 장애 기록 (4)
      • 신입팀원 교육 자료 (1)
    • CS (30)
      • Operating System (22)
      • Computer Security (3)
      • Network (4)
      • DBMS (1)
    • 책 (10)
      • 도메인 주도 설계 철저 입문 (9)
      • Real MySQL 8.0 (1)
    • BOJ 문제 풀이 (3)
    • 이러쿵저러쿵 (10)
    • 회고 (1)

인기 글

최근 댓글

최근 글

hELLO · Designed By 정상우.
동현 유

척척석사

[전공생이 설명하는 OS] 동기화 - (5) Deadlock
CS/Operating System

[전공생이 설명하는 OS] 동기화 - (5) Deadlock

2022. 5. 31. 08:20

Review

  • 쓰레드(Thread)와 동기화 문제
  • 동기화 - (1) 용어 및 개념정리
  • 동기화 - (2) 상호배제 전략(Mutex)
  • 동기화 - (3) 조건동기화 (pthread 예시)
  • 동기화 - (4) 생산자 소비자 문제

  지금까지 race condition 이 발생하는 이유와, 이를 해결하기 위해 다양한 동기화 기법이 필요하다는 점을 설명했다. 특히 이전 포스팅에서는 할당 가능한 자원의 개수를 (0~MAX)개로 제한하는 web server request buffer 를 살펴보면서 `생산자-소비자 문제`(bounded buffer problem) 를 해결해보았다. 

 이번에는 동기화로 인해 발생할 수 있는 심각한 문제인 교착상태(deadlock)을 알아보도록 한다.


1. Deadlock 이란?

프로세스 P1 과 P2 는 데드락 상태에 빠질 수 있다.

  다수의 스레드 또는 프로세스가 서로 깨워주기를 기다리면서, 모두 대기하고 있는 상태를 데드락이라고 한다. 데드락은 실제로 자주 발생하는 문제는 아니다. 하지만 한번 발생하면 서비스에 심각한 장애를 발생시키고, 또 그 원인을 제대로 파악하기가 매우 힘들다. (모든 자원 간의 의존관계를 파악해야한다.)


2. Resource

  여태까지 동기화에 대해 설명할 때에는 여러 실행 흐름을 제어하기 위한 관점에서 바라보았다면, 데드락에서는 자원의 분배 관점에서 바라보는 것이 더 유익할 듯하다. 데드락은 Non-preemptable 한 자원에 대해서 발생할 수 있다. 즉 한 프로세스가 어떤 자원을 점유하고 있을 때, 다른 프로세스가 그것을 강제로 빼앗을 수 없는 자원의 종류를 말한다. 크게 재사용 가능한 자원과 일회용 자원으로 나눌 수 있다. 두 자원 모두 non-preemptable 하기 때문에 데드락이 발생할 수 있다.

  • Reusable Resource 
    - 한 프로세스가 사용한다고 해서 사라지지 않는 자원. 한번에 한 프로세스만 사용가능한 경우가 많다.
    - 보통 request -> lock -> use -> unlock 의 과정을 거친다.
    - cpu, memory, file, database, etc.
  • Consumable Resource
    - 한번 사용하면 사라지는 일회성 자원.
    - interrupts, signals, messages, IO buffers, etc.

3. Resource Allocation Graph

  Resource Allocation Graph는 데드락이 발생할 수 있는 상황인지 파악할 수 있도록, 프로세스와 자원 사이의 관계를 도식화하는 방법이다. 프로세스는 원, 공유자원은 사각형으로 표현한다. 사각형 내부에 그려진 검은 점들은 자원의 개수를 의미할 수 있고 부분적으로 떼어줄 수 있다는 뜻이다.(생산자-소비자 문제에서의 버퍼, 할당가능한 메모리 크기 등). 화살표의 방향은 의존관계를 나타낸다. 

  이 그래프에서 순환 의존 관계가 발생하게 되면 데드락이 발생할 수 있다. 그림 (c)는 데드락이 발생한 상황이다. 그림 (d)는 데드락 상황은 아니지만, 추후에 얼마든지 데드락이 발생할 수 있다.

 


4. 데드락 발생의 4가지 필요조건

  위에서 설명한 것을 토대로 교착상태가 발생하는 4가지 조건을 정리하면 다음과 같다. 다음 중 하나라도 만족하지 않으면 교착상태는 발생하지 않는다.

  1. 공유자원이 non-preemptive 한다. 즉, 빼앗을 수 없다.
  2. 공유자원에 대해 상호배제가 이루어진다.
  3. 프로세스가 한 자원을 잡고 있으면서 다른 자원을 요청하는 Hold & Wait 상태가 발생한다.
  4. 순환 대기가 발생한다.

5. 교착상태를 해결하는 4가지 방법

  1. Deadlock Prevention
    - 4가지 조건을 모두 만족시키지 못하게 하는 방법.
    - resource 의 utilization 이 낮아지고, concurrency 가 저하된다.
  2. Deadlock Avoidence
    - 자원 요청이 있을 때, deadlock 이 발생가능하면 거절하고, 그렇지 않으면 할당하는 방법
    - 시스템의 모든 자원을 파악해야하고, 프로세스가 어떤 자원을 얼만큼 필요로하는지 미리 파악해야한다. 
  3. Deadlock Detection & Recovery
    - deadlock 이 발생했는지를 주기적으로 확인한다. 발생한 경우 자원을 회수하거나 프로세스를 종료하는 등의 조치를 취한다.
    - 교착상태는 매우 드물게 발생하기 때문에 overhead 가 크다.
  4. Ignore
    - 매우 드물게 발생한다 -> 무시하는게 오히려 효율성이 좋을수도 있다.

 

  다음 포스팅에서는 대표적인 데드락 상황인 식사하는 철학자 문제를 알아보고, 그에 따른 Prevention 과 Avoidence 방법을 실제 코드를 작성하면서 알아보도록 한다.

 

'CS > Operating System' 카테고리의 다른 글

[전공생이 설명하는 OS] 메모리 관리 - (1) Partition/Page/Segment  (0) 2022.06.02
[전공생이 설명하는 OS] 동기화 - (6) 식사하는 철학자 문제 (코드 포함)  (0) 2022.05.31
[전공생이 설명하는 OS] 동기화 - (4) 생산자 소비자 문제  (0) 2022.05.22
[전공생이 설명하는 OS] 동기화 - (3) 조건동기화 (pthread 예제 코드 포함)  (0) 2022.05.22
[전공생이 설명하는 OS] 동기화 - (2) 상호배제 전략 (Mutex)  (0) 2022.05.19
    동현 유
    동현 유
    Fault Tolerant System Researcher for more Trustful World and Better Lives. (LinkedIn: https://www.linkedin.com/in/donghyeon-ryu-526b8a276/)

    티스토리툴바