Concurrency

Concurrency

Race Condition

공유 자원에 대해 여러 프로세스가 동시에 접근 할 경우 각 결과 값에 영향을 줄 수 있는 상태 (multi-thread 환경에서도 time-safety 한가?)

→ 동시 접근의 치명적인 문제점

어떻게 해결하지?

핵심은 동기화

• Race condition의 가능성이 있는 구역을 임계 구역(Critical Section)
• 그리고 그곳에 한 프로세스만 접근이 가능한 것을 상호 배제(Mutually exclusive)

이러한 방식에 있어서 아래와 같은 DeadLock이 발생한다…

---

DeadLock

두개 이상의 프로레스가 서로 무한히 다음 자원을 기다리게 되는 상태

언제 발생하는가?

• 멀티 프로그래밍 환경에서 서로 경쟁하는 상황
• 서로 wait 상태로 상대의 자원이 끝나기를 기다린다. → 교착 상태

DeadLock 발생 조건

• 상호 배제
  • 자원은 한번에 하나의 프로세스만 사용 가능
• 점유 대기
  • 최소한 하나의 자원을 점유하고 있으면서 대기하는 방식
• 비선점
  • 다른 프로세스에 할당 된 자원은 끝날떄 까지 강제로 뺏지 못한다.
• 순환 대기
  • 프로세스들이 서로 순환 형태로 자원을 대기하고 있어야한다.

위 4가지들이 모두 성립 해야 DeadLock 이라고 볼 수 있다.

DeadLock 처리

• 상호 배제 부정
  • 여러 프로세스가 여러개의 자원을 사용하게 한다.
• 점유 대기 부정
  • 프로세스는 실행전에 모든 자원을 할당하고 실행함
• 비 선점 부정
  • 자신의 자원을 반납 하고 다른 프로레스에 자원을 요청 할 수 있음
• 순환 대기 부정
  • 자원에 고유번호를 할당 하고 순서대로 요구

이 방식은 매우 자원 낭비가 심하다…

DeadLock 회피

• 은행원 알고리즘
  • 프로세스가 자원을 할당 할때 얘한테 할당 한 뒤에도 시스템이 안전 상태로 남아있는지 검사
• 자원 할당 그래프 알고리즘
  • 자원 - 프로세스를 요청 간선과 할당 간선으로 적용 하여 교착상태를 회피
  • 자원 요구시에 요청 간선을 할당 간선으로 변경해 사이클 파악

매우 큰 오버헤드를 가지고 있음…

교착 상태를 탐지 & 회복 & 무시

• 탐지
  • 자원 할당 그래프로 탐지 → 오버헤드 유발
    • 교착 상태의 프로세스를 모두 중지 하거나
    • 제거 될 때 까지 하나씩 중지
• 회복
  • 교착 상태를 일으킨 프로세스를 종료
  • 자원 선점방법
    • 교착 상태가 종료 될 때까지 점유한 자원을 선점해 다른 프로세스에게 할당
• 무시
  • 윈도우는 교착 상태 탐지 비용 > 교착상태 손해 비용 이라고 판단
  • 그냥 무시한다…

---

Semaphore & Mutex

• 임계영역에 접근을 막기 위해 허락된 프로세스만 들어갈 수 있게 만든 것

Mutex

• 임계영역에 프로세스나 스레드들이 하나만 접근하게 제어하는 기술
• lock : 임계 구역에 들어가 다른 프로세스/ 스레드의 접근을 막음
• unlock : 현재 임계 구역을 모두 사용했음 → 다른 얘들도 접근이 가능

Semaphore

• 하나 이상의 프로레스 / 스레드를 임계영역에 받아들임 (S)
• 세마 포어 (P, V) 연산
  • P: 임계 영역에 들어가기 전에 프로세스 진입 여부를 (S)를 통해 결정
  • V: 나올 때 반납하면서 수행
• 스레드간의 실행 순서를 정할 수 있음
  • S =1 일때 하나의 프로세스가 들어간다.
  • 해당 프로세스가 내부에서 S = 2로 증가시킨다.
  • 대기 큐에 있던 프로세스가 들어간다.
  • 정리 완료!
• 뮤텍스는 외부에서 unlock 할 수 없지만 세마포어는 외부에서도 S의 제어가 가능하다.