[운영체제] 5. Process Synchronization (2) - The Critical Section Problem

키워드

critical-sectioin, peterson's algorithm, synchronization hardware, semaphores

 

The Critical-Section Problem

프로그램적 해결법

 

충족 조건

• Mutual Exclusion(상호 배제)
  • 어떤 프로세스가 크리티컬 섹션에 들어가 있으면
    다른 모든 프로세스는 크리티컬 섹션에 들어가지 못하게 한다.
• Progress(진행)
  • 크리티컬 섹션에 아무도 들어가있지 않은 상황에서 내가 들어가고자 하면 들어가게 해줘야 한다.
  • 둘이 동시에 들어가려는 상황에서 둘 다 안들어가있음에도 둘 다 못들어가는 문제 고려
• Bounded Waiting(유한 대기)
  • 기다리는 시간이 유한해야함
  • 크리티컬 섹션에 들어가고자 하는 프로세스가 세 개 있을 때 둘이서만 번갈아가면서 들어가 
    나머지 하나는 못들어가고 마냥 기다리는 경우 고려

Algorithm 1

• 본인 차례가 아닌 동안 while 문을 돌며 기다리고 
  본인 차례가 되면 critical section에 들어가고, 나와서 turn을 상대방 차례로 만듦
• Mutual Exclusion 만족
• Progress 만족하지 않음
  -> P0, P1이 있을 때, P1이 한 번만 들어가고 영원히 안들어간다면 P0이 들어갈 기회가 다신 오지 않음
• 프로세스들이 critical section에 들어가는 빈도가 균일하지 않을 가능성 존재
• turn을 교대로만 바꿔줘서는 안되겠어서 나온 방법이 Algorithm 2

 

Algorithm 2

• flag라는 변수 사용 -> 본인이 critical section에 들어가고자 하는 의중을 표시
  1. critical section에 들어가기 위해선 본인의 flag를 true로 변경
  2. 상대방 flag 체크
     true인 flag가 없어야 들어갈 수 있음
  3. 들어갔다 나오며 flag -> false로 변경
• flag = true가 된 상황에서 CPU를 뺏긴 후 가져간 프로세스에서 flag = true를 하는 경우 문제 발생
  -> 둘 다 못들어감

 

Algorithm 3 (Peterson's Algorithm)

• turn, flag 모두 사용
• 충족 조건을 모두 만족
• Busy Waiting(=spin lock) 문제 존재
  -> 어떤 프로세스가 이미 critical section에 들어가 있는 상태에서 다른 프로세스가 CPU를 잡으면
  while문을 돌며 빠져나갈 수 없게됨
  -> 할당시간동안 계속 while문만 체크하다가 반납
  해결 방법이 존재

 

Synchronization Hardware

• 동시성 문제는 데이터를 읽는 것과 쓰는 것을
  하나의 인스트럭션으로 처리할 수 없기 때문에 발생해왔음
• 만약 하나의 인스트럭션으로 읽고 쓰는게 된다면 인스트럭션 하나가 실행되는 도중에
  CPU를 빼앗기진 않을 것임
  -> Test_and_set(a) 인스트럭션
• 이게 지원이 된다면 소프트웨어적으로 코드를 복잡하게 짤 이유 없이 
  critical section에 들어가기 전에 lock을 걸고 빠져나온 후 lock을 푸는 것으로 간단,간결하게 해결 가능

 

Semaphores

• 프로그래머가 매번 위의 소프트웨어적, 하드웨어적 작업을 하는건 효율적이지 않음
• 간소화를 위해 추상 자료형인 Semaphores를 정의 후 프로그래머는 연산만 해줌으로 lock을 걸 수 있게 됨