Race condition

• 여러 프로세스들이 동시에 공유 데이터에 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
  • race condition을 막기 위해서는 concurrent process는 동기화되어야 함
• Race Condition이 발생할 수 있는 상황
  1. kernel 수행 중 인터럽트 발생 : 중요한 루틴을 처리하고 있을 때는 인터럽트가 들어와도 인터럽트 처리를 미룬 뒤 작업을 마친 후에 인터럽트 처리
  2. 프로세스가 system call을 해 kernel 모드로 수행 중인데, Context switch 발생 : 프로세스가 커널 모드로 수행 중일 때는 CPU를 preempt하지 않게 하고 커널모드에서 사용자모드로 복귀할 때 다시 preempt함
  3. Multiprocessor에서 Shared memory내의 kernel data에 접근할 경우 : 하나의 프로세서가 공유 메모리에 접근할 때 데이터에 대해 lock을 걸어주고 메모리에서의 작업이 끝나면 unlock을 해줌
• 하지만, 무조건 접근을 제한하면 비효율적이므로 Critical Section에 어떠한 방법을 적용해야 함
  1. Mutual Exclusion (상호배제) : critical section에 동시에 도달하면 안됨
  2. Progress : 아무도 공유 데이터에 접근하고 있지 않을 때 접근하고자 하는 프로세스가 있다면 접근을 허용해야 함
  3. Bounded waiting : 프로세스가 접근하기 위해 요청한 후부터 요청이 허용될 때까지의 waiting time이 유한해야 함

  ⇒ 위 세 가지 조건을 모두 충족시키며 lock과 unlock을 분배할 알고리즘 필요

Semaphore

• 멀티프로그래밍 환경에서 공유 자원에 접근을 제한하기 위해 고안된 두 개의 원자적 함수로 조작되는 정수 변수
• 세마포어 변수는 정수값을 가지고, 이는 자원의 개수를 의미
• ✅ 락을 걸고 푸는 작업, 공유 자원 획득/반납을 간결하게 해줌
  • P(S) : 공유 데이터를 획득하는 함수, 변수가 하나인 경우 락을 거는 것

    while (S <= 0) do no-op; //wait
    S--;
  

  • V(S) : 공유 데이터를 반납하는 함수, 변수가 하나인 경우 락을 푸는 것

    S++;
  

• ❌ 구현과 정확성 입증이 어렵고, 한 번의 실수로 모든 시스템에 치명적 영향을 줄 수 있음

1. Counting semaphore : resource counting에 사용
2. Binary semaphore : 0 또는 1만 가질 수 있고 주로 mutual exclusion(lock/unlock)에 사용

Deadlock

• 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태
• Deadlock 발생조건
  1. Mutual exclusion (상호 배제) : 자원을 일단 얻었으면 독점적으로 사용, 즉 다른 프로세스가 동일한 자원을 동시에 사용할 수 없음
  2. No preemption (비선점) : 자원을 가지고 있으면 강제로 빼앗길 수 없음
  3. Hold and wait (보유 대기) : 이미 어떤 자원을 가지고 있으면서 다른 추가적인 자원을 기다릴 때 발생, 이 때 가지고 있는 자원은 반납하지 않음
  4. Circular wait (순환 대기) : 자원을 기다리는 프로세스 간 사이클이 형성되는 경우
• Deadlock 해결방법

1. Deadlock Prevention
   • 데드락이 생기지 않게 미리 방지하는 방법, 가장 강력한 방법
   • 데드락이 발생하는 4가지 조건 중 하나를 차단하는
   1. Hold & Wait
      • 어떤 프로세스가 시작될 때 이 프로세스가 필요한 모든 자원을 할당 받게 하는 방법 (중간에 추가로 필요한 자원이 없도록 함 ⇒ 비효율적)
      • 자원이 필요한 시점에 할당받게 하지만, 프로세스가 어떤 자원을 가지고 있는 상태에서 다른 자원을 기다려야 한다면, 이미 가지고 있는 자원도 모두 반납한 후에 기다리게 하는 방법
   2. No preemption
      • 자원을 강제로 빼앗길 수 있게 함, 자원의 현재 상태를 쉽게 save & restore 할 수 있는 상태일 때 사용하는 방법
   3. Circular Wait
      • 자원마다 번호를 매겨 낮은 번호의 자원부터 획득해야 높은 번호의 자원을 획득할 수 있도록 함 (싸이클 방지) ⇒ 자원에 대한 이용률⬇ 시스템 성능⬇ starvation 등의 문제 발생가
2. Deadlock Avoidance
   • 데드락이 생기지 않게 미리 방지하는 방법
   • 자원 요청에 대한 부가 정보를 활용해서 deadlock 가능성이 없는 경우만 자원을 할당해주는 방법
   • 자원의 instance가 하나씩인 경우 : Resource Allocation Graph Algorithm 사용
   • 자원의 instance가 여러 개인 경우 : Banker’s Algorithm 사용
3. Deadlock Detection and recovery
   • 시스템에 문제가 있을 때 데드락이 있는지 확인하고 고쳐주는 방법
   • 자원의 instance가 하나씩인 경우 : Resource Allocation Graph Algorithm 사용
   • 자원의 instance가 여러 개인 경우 : 표를 그려 확인
4. Deadlock Ignorance
   • 데드락에 대해 아무 일도 하지 않는 방법 (현대 운영체제가 대부분 이 방법 사용)
   • 사용자가 알아서 처리하도록 함

---

참고링크

• 참고링크1
• 참고링크2
• 참고링크3
• 참고링크4