2024 운영체제 정리 - 5. Synchronization & Deadlock

 

2024 운영체제 정리 - 5. Synchronization & Deadlock

 

 

 

 

• 1. 운영체제란
• 2. Process & Thread
• 3. IPC
• 4. CPU Scheduling  
• 5. Synchronization & Deadlock
• 6. 메모리 관리와 Virtual Memory 

---

 

 

Race Condition 문제 

 

 

• 동시다발적으로 수행되는 쓰레드/프로세스에서, 서로 다른 쓰레드/프로세스가 같은 메모리 영역을 공유하기 때문에 여러 쓰레드/프로세스가 동일한 자원에 동시에 접근할 때 발생하는 문제 발생
  • 이를 해결하기 위한 방법 - Synchronization! 
• 이때, 동시에 접근하게 되는 공동의 자원을 공유자원, shared resource라고 한다
  • 이 공유 자원은 전역 변수, 파일, 입출력 장치, 보조기억 장치 등이 될 수 있다 
• 이때, 둘 이상의 thread/process가 동시에 동일한 자원에 접근하도록 하는 프로그램의 코드 부분을 critical section, 임계 구역이라고 한다 
  • 공유 자원에 접근하는 코드 중 동시에 실행하면 문제가 발생하는 코드 영역 
• 여러 프로세스가 임계 구역에 있는 코드를 동시에 실행하여 발생하는 문제는 Race Condition이라고 한다 

 

 

Race Condition 해결 방법 

 

 

• 1. 상호 배제 
  • 한 번에 하나의 쓰레드/프로세스만 임계구역에 접근할 수 있다 
• 2. 유한 대기
  • 한 프로세스가 임계구역에 들어가고 싶다면 언젠간 꼭 임계 구역에 들어가야 한다 
• 3. 진행 
  •  임계 구역에 어떠한 프로세스도 진입하지 않았다면 임계구역에 진입하고자 하는 프로세스는 들어갈 수 있어야 한다 

 

 

 

 

Synchronization 기법 

 

 

• 동시다발적으로 수행되는 쓰레드/프로세스에서, 서로 다른 쓰레드/프로세스가 같은 메모리 영역을 공유하기 때문에 여러 쓰레드/프로세스가 동일한 자원에 동시에 접근할 때 발생하는 문제 발생
  • 이를 해결하기 위한 방법 - Synchronization! 위의 세 가지 조건을 고려한다 
• 종류 
  • Mutex
  • Semaphore 
  • Monitor

 

 

 

• 1. Mutex (Mutual Exclusion)
  • lock과 unlock으로 공유자원에 접근할 수 있는 process/thread의 수를 1개로 제한하는 기법 
    • 임계 구역을 보호하기 위해서 한 프로세스가 임계구역에 진입할 때는 lock을 걸고, 나오게 된다면 unlock을 수행 -> 대기 중인 프로세스가 임계 구역에 접근할 수 있게 된다 
• 2. Semaphore 
  • 공유 자원에 접근할 수 있는 process/thread의 개수가 2개 이상이 될 수 있는 기법 
  • Semaphore 변수 S에 동시에 접근할 수 있는 process/thread의 개수를 지정 
    • S가 0보다 크면 임계 구역에 접근할 수 있고, 접근하면 S 값 1 감소 
    • S가 0이 되면 임계 구역에 접근할 수 없고, 나오게 된다면 S값 다시 1증가 시킴
• 3. Monitor 
  • 매번 Lock/Unlock하기 불편하기 때문에 큐에 넣어서 하나씩 조건 변수(Coditional Variable) 사용해서 조건에 따라 중단/실행 수행 

 

 

 

 

Deadlock (교착상태)

• 두 개의 프로세스가 임계 구역에 들어가기 위해 Ready Queue에서 무한정 기다리고 있는 상황 
• 발생 조건 
  • 1. 상호배제 
    • 동시에 한 thread만 자원을 점유할 수 있는 상황
    • 다른 thread가 자원을 사용하려면 자원이 방출될 때까지 기다려야 함
  • 2. 점유와 대기 
    • thread가 자원을 보유한 상태에서 다른 thread가 보유한 자원을 추가로 기다리는 상황
  • 3. 비선점
    • 다른 thread가 사용 중인 자원을 강제로 선점할 수 없는 상황
  • 4, 원형대기 (순환대기)
    • 대기 중인 thread들이 순환 형태로 자원을 대기하고 있는 상황
• 위 4가지 조건이 모두 발생할 때 Deadlock이 발생하게 된다

 

 

• 해결 방안 
  • 무시 
    • deadlock 발생 확률이 낮은 시스템에서 아무런 조치도 취하지 않고 deadlock을 무시하는 방법
    • 현대 시스템에서는 deadlock이 잘 발생하지 않고, 해결 비용이 크기 때문에 무시 방법이 많이 사용
  • 회피 
    • thread가 앞으로 자원을 어떻게 요청할지에 대한 정보를 통해 순환 대기 상태가 발생하지 않도록 자원을 할당하는 방법 - 시스템은 안전한 시퀀스를 유지할 수 있는 경우에만 자원 요청을 승인
    • 자원 할당 그래프 알고리즘, 은행원 알고리즘 등을 사용하여 자원을 할당하여 deadlock을 회피합니다.
  • 예방 
    • 교착 상태의 4가지 발생 조건중 하나가 성립하지 않게 하는 방법
    • 순환 대기 조건이 성립하지 않도록 하는 것이 현실적으로 가능한 예방 기법 - 하지만 자원 사용의 효율성이 떨어지고 비용이 큼 
      • 또는 점유 및 대기 조건을 제거하기 위해 프로세스가 실행을 시작하기 전에 필요한 모든 자원을 한 번에 요청하도록 함 
  • 탐지 & 회복
    • 시스템 검사를 통해 deadlock 발생을 탐지하고, 이를 회복시키는 방법
    • 자원 사용의 효율성이 떨어지고 비용이 큽니다.

 

 

 

Q1. 왜 현대 시스템에서는 Deadlock이 잘 발생하지 않나요? 많은 시스템이 여유 자원을 많이 보유하고 있어서, 자원 간의 경쟁이 적어짐 현대의 운영 시스템들은 더욱 진보된 자원 관리와 스케줄링 알고리즘을 사용하여 프로세스와 스레드들이 자원을 효율적으로 사용할 수 있도록 설계되어 있음 Q2. Deadlock 해결 방법 중 회피 방법에 해당하는 자원 할당 그래프 알고리즘, 은행원 알고리즘이 뭐야 ? 자원 할당 그래프 알고리즘(Resource Allocation Graph Algorithm): 이 알고리즘은 시스템 내의 자원과 프로세스 간의 요구와 할당을 그래프로 표현합니다. 노드는 자원과 프로세스를 나타내고, 엣지는 요구 또는 할당을 나타냅니다. 데드락을 탐지하는 주요 방법 중 하나로, 순환을 형성하는지 여부를 검사하여 데드락의 존재를 확인합니다. 은행원 알고리즘(Banker's Algorithm): 이 알고리즘은 '은행원'이 고객에게 자금을 안전하게 대출할 수 있는지 결정하는 과정에 비유됩니다. 시스템이 각 프로세스의 최대 자원 요구량을 알고 있고, 프로세스가 자원을 요구할 때마다 시스템은 안전 상태를 유지할 수 있는지 계산합니다. 안전 상태란, 현재 자원의 할당 상태에서 모든 프로세스가 자원을 안전하게 모두 할당받고 완료될 수 있는 상태를 말합니다. 이 알고리즘은 데드락을 회피하기 위해 사용됩니다. Q3. Deadlock 해결 방법에서 자원 사용의 효율성이 떨어지고 비용이 크다는 것은 구체적으로 어떤 걸 말하는 거야? 알고리즘들이 자원을 보수적으로 관리하도록 요구하기 때문입니다. 예를 들어, 은행원 알고리즘을 사용할 경우, 시스템은 항상 안전 상태를 유지하기 위해 필요 이상의 자원을 여유롭게 확보하고 있어야 하며, 이는 사용 가능한 자원의 총량 대비 실제 활용도가 낮아지게 합니다. 또한, 데드락을 탐지하고 해결하는 과정에서 발생하는 시스템 검사와 프로세스 중지 및 재시작과 같은 복구 작업은 추가적인 시스템 리소스를 요구하며, 이는 운영 비용 측면에서도 부담을 가중시킵니다

 

 

 

 

 

• +) 좀 더 자세한 해결 방안 (공룡책) 
  •  
• 1. 예방 
  • 4가지 교착상태 발생 조건들 중에 적어도 하나가 성립하지 않도록 하여 교착상태를 예방
  • 1) 상호 배제(Mutual Exclusion)
    • 공유 가능한 resource에 대해서는 교착상태(Deadlock)이 일어나지 않는다 
  • 2) 비선점 
    • 할당된 resource이 선점되지 않아야 한다
    • 방법. 어떤 resource을 점유하고 있는 프로세스가 즉시 할당할 수 없는 다른 resource을 요청하면, 현재 점유하고 있는 모든 resource들이 선점되게 하기 
  • 3) 점유와 대기 
    • 프로세스가 resource를 요청할 때, 다른 resource들을 점유하지 않도록 하기 
      • 단점 
        • 많은 resource들이 할당된 후 오랫동안 사용되지 않기 때문에, resource의 이용도가 낮을 수 있다.
        • 기아(Starvation) 문제가 발생할 수 있다. (특정 프로세스는 무한정 대기하는 상황이 나올 수 있다.)
    • 방법 1. 프로세스가 전혀 resource를 갖고 있지 않을 때만, resource을 요청하도록 허용
      •  다른 추가 resource를 요청하려면, 현재 자신에게 할당된 resource를 모두 방출
    • 방법 2. 프로세스가 초기에는 DVD drive와 Disk file만 요청하도록 허용하는 방법
  • 4) 순환 대기
    • 방법. 이 조건을 성립하지 않게 하기 위해, 모든 resource type에 대해 전체적인 순서를 부여하여, 각 프로세스가 열거된 순서대로, 오름차순으로 resource을 요청하도록 요구

 

• 2. 회피
  • resource가 어떻게 될지 추가 정보를 통해 Deadlock이 발생하지 않는 경우에만 자원 할당 
  • 방법 1. 자원 할당 그래프 알고리즘 
    • 자원 할당 그래프를 그려보면서 cycle이 안 생기게 하여 교착상태(Deadlock)을 회피할 수 있다.
      • 그래프에서 cycle이 없다면, resource를 할당해도 시스템은 안전 상태가 된다.
      • cycle이 발생하게 되면, 시스템은 불안전한 상태가 되므로 교착상태를 회피할 수 없게 된다.
  • 방법 2. 은행원 알고리즘
    • 자원 할당 그래프 알고리즘은 종류마다 자원이 여러 개씩 있게 되면 사용할 수 없다.
    • 은행원 알고리즘(Banker's Algorithm)에서는 자원이 여러 개씩 있더라도 사용할 수 있다.

 

 

 

• 3. 탐지 & 회복 
  • 탐지 알고리즘 : 탐지 알고리즘(Detection-Algorithm)은 언제 돌려야 하는지에 대해서는 두 가지를 살펴봐야 한다
    
    •  1) 교착상태(Deadlock)가 얼마나 자주 일어나는가?
    • 2) 교착상태(Deadlock)이 일어나면, 통상 몇 개의 프로세스가 거기에 연루되는가?
  • 회복하기 위해선 1) 프로세스를 종료시키는 것과 2) 자원을 선점하는 것 두 가지 종류가 있을 수 있다.
    • 1) 프로세스 종료
      • (1) 교착상태(Deadlock) 프로세스를 모두 중지 
      • (2) 교착상태(Deadlock)가 제거될 때까지 한 프로세스씩 중지
        • 어떤 프로세스를 먼저 중지시켜야 하는가는 아래와 같은 기준들이 있을 수 있다.
          • (1) 프로세스의 우선순위가 어떠한지
          • (2) 지금까지 프로세스가 수행된 시간과 종료하는 데까지 더 필요한 시간
          • (3) 프로세스가 종료하기 위해 필요한 추가 resource의 수
          • (4) 프로세스가 사용한 resource type과 수
    • 2) 자원 선점 
      • 교착상태(Deadlock)을 해결하기 위해 선점이 필요하다면, 다음의 세 가지 사항을 고려해야 한다.
        • (1) 희생자 선택(Selection of a victim) : 어느 resource와 process가 선점될 것인가?
        • (2) 후퇴(Rollback) : 프로세스로부터 자원을 선점하려면, 그 프로세스를 어떻게 해야 하는가?
        • (3) 기아 상태(Starvation) : 기아(Starvation) 상태가 발생하지 않는다는 것을 어떻게 보장해야 하는가?

 

 

 

---

 

Reference

 

https://will-behappy.tistory.com/23

공룡책으로 정리하는 운영체제 - CHAPTER 7. 교착상태(Deadlocks)