[OS] Common Concurrency Problems

병행성 관련 버그

1. Deadlock이 아닌 버그

• 원자성 위반 버그
  • 쓰레드의 코드 행 간에 interrupt가 걸려서 불필요한 변화가 생기는 것
  • 해결
    • lock 사용하여 상호 배제
• 순서 위반 버그
  • 쓰레드들의 순서가 바뀌면 에러
  • 컨디션 변수 사용

2. Deadlock 관련 버그

• 발생 이유
  • 코드가 많아지면 구성 요소 간 복잡한 의존성 발생
  • 캡슐화
• Deadlock 조건
  1. 상호 배제(Mutual Exclusion): 쓰레드가 자신이 필요로 하는 자원에 대한 독자적인 제어권 주장
     • ex) lock 획득
  2. 점유 및 대기(Hold-and-wait): 쓰레드가 자신에게 할당된 자원을 점유한 채로 다른 자원을 대기
     • ex) 이미 lock을 얻었는데 다른 lock을 위해 대기
  3. 비 선점(No preemption): 자원을 점유하고 있는 쓰레드로부터 자원을 강제적으로 빼앗을 수 없음
     • ex) lock을 얻으면 일이 끝날 때까지 lock을 뺏기지 않음
  4. 환형 대기(Circular wait): 각 쓰레드는 다른 쓰레드가 요청한 하나 또는 그 이상의 자원을 갖고 있는 쓰레드들의 순환 고리가 있음
     • ex) cycle을 이룸
• Deadlock 예방
  • Deadlock 조건을 하나만 만족하지 않아도 예방
  • Circular wait
    • 전체 순서(total ordering)
      • lock을 얻는 순서를 하나로 정의
    • 부분 순서(partial ordering)
      • lock의 주소 값을 비교하여 큰 경우, 작은 경우 나눠서 정의
      • Dining Philosopher 예제 같은 경우, 마지막 사람만 순서를 변경
  • Hold-and-wait
    • atomic하게 만들어 상호 배제 되도록 하기 위해 전역 lock을 정의
  • No preemption
    • 상황에 따라 lock을 얻고 놓는 것을 반복
    • 무한 반복할 수 있는 문제 발생 가능
  • Mutual Exclusion
    • lock 사용 X
    • atomic하게 구 현(ex. LD, ADD, ST를 한번에)
• Deadlock 회피
  • 스케줄링
    • 병렬로 실행되면 Deadlock이 걸리는 쓰레드들은 같은 CPU를 쓰도록 배치
    • 하나의 CPU에 몰리게 되면 성능 저하