운영체제#4

LeeMir, 22 March 2021

2강 - Processes and Threads(이어서)

Race Conditions(경쟁 상황)
  • 두 개의 Process 또는 Thread가 같은 자원에 접근했을 때 발생하는 일
    • 컴퓨터 시스템에서는 Race Condition이 일어나면 안됨(덮어쓰기가 일어날 가능성이 있음)
  • Race Condition을 피해야하는 조건(시험에 나오기 좋음)
    • CPU의 속도나 개수와 상관이 없어야한다
    • Mutual Exclusion(상호 배제) : 어떤 두 Process도 공유 자원에 동시에 들어가면 안된다
    • Progress(진행) : 공유자원에 아무도 접근 안하고 있으면 들어가야한다
    • Bounded Waiting(순번) : 기다리면 무조건 들어갈 수 있어야한다(우선 순위는 해결책이 되지 않는다)
  • Critical Region : 임계 구역, 공유 자원
  • Busy Waiting을 이용한 상호 배제(Mutual Exclusion) 기법
    • Strict Alternation
      • turn 변수를 이용해서 while(turn!=i);식으로 대기하게 해 Process가 번갈아 실행되도록 함
      • 상대 Process가 다른 일을 하고 있으면 무한 대기가 발생, Progress를 만족하지 못함
    • Dekker’s Solution
      • Strict Alternation의 Progress 문제를 해결
      • flag 변수를 만들어서 자신이 임계 구역에 접근한다는 것을 다른 Process에게 알림
    • Peterson’s Solution
      • Dekker’s Solution과 같은 아이디어
        • 코드가 조금 더 간략함
        • 코드가 조금만 달라도 상호 배제가 안될 수 있음
    • Bakery Algorithm
      • 두 개의 Process => N개의 Process로 확장
      • 빵집에 들어가기 위해 번호표를 발급받겠다!
      • "(a,b) < (c,d)" => (a<c) or ((a==c)&&(b<d))
      • 다른 모든 Process보다 내 번호표가 가장 작을(빠를) 경우 내 차례
    • TSL Instruction
      • TSL : Test & Set Lock
      • LOCK이라는 변수에 Process의 접근 상태를 저장
        • CPU의 핀에는 Lock Signal 핀이 존재한다
      • LOCK 변수의 값을 레지스터에 저장해놓은 후 1로 세팅하고, 이전에 있던 LOCK 변수와 값을 비교
        • 만약 이전에 있던 LOCK 변수의 값이 1일 경우 다른 Process에서 접근하고 있는 중이라는 뜻이므로 대기해야 함
        • 만약 LOCK 변수의 값이 0일 경우 현재 Process가 실행되면 됨
      • Atomic Instruction으로 구현
      • 앞선 solution들은 enter_region 코드가 복잡함
Producer-Consumer Problem
  • 생산자-소비자 문제
    • 한정된 버퍼에서 데이터가 없는데 데이터를 읽으려는 Consumer나 꽉 차있는데 데이터를 추가하려는 Producer를 어떻게 제어할 수 있을까
    • 상호적으로 sleep과 wakeup을 반복함
  • Semaphore
    • Dijkstra가 고안
    • Mutual Exclusion과 Synchronization를 둘 다 만족할 수 있는 연산 방법
    • Up 연산과 Down 연산을 함
      • Producer : empty slot의 개수를 down하고 full(아이템 개수)을 Up
      • Consumer : empty slot의 개수를 up하고 full을 down
      • down(mutex), up(mutex)로 Mutual Exclusion 해결
Prioirty Inversion
  • 우선순위 역전
  • 우선순위가 높은 Process가 다른 Process로 인해 sleep되는 바람에 우선순위 낮은 Process가 실행됨
  • Prioirty Inheritance(우선순위 상속)
    • sleep시킨 Process에게 우선순위를 상속해 우선순위가 높은 Process가 제대로 끝나게 함
    • 우선순위 역전 문제 해결
Mutexes in Pthreads
  • mutex 변수를 통해 Mutual Exclusion 해결
  • 매개 역할을 하는 condition 변수를 통해 Synchronization 구현