[OS #6] 프로세스 동기화

임계구역

데이터 정합성의 이슈

• 동시에 공유 데이터에 접근하고자 할 때 데이터의 불일치가 발생할 수 있음(입금과 출금에서 잔액)

• 데이터의 일관성을 유지하려면 협력 프로세스들을 순차적으로 실행하도록 보장해야 함

  -> Count값으로 조정

• 생산자 소비자 문제
  생산될 때마다 count++
  소비될 때마다 count--

• count ++/-- 하는 과정은 프로그램 상에서 세 단계로 표현
  

• 즉 세 단계가 내부적인 순서로 섞여서, 예측과 틀린 결과가 나올 수 있다

임계구역

• 각 프로세스에는 임계구역이라는 코드 세그먼트가 있다
• 각 임계구역에서는 다른 프로세스와 공유하는 데이터를 변경한다
• 한 프로세스가 임계구역에서 실행중일 때, 다른 프로세스는 해당 임계구역에 접근할 수 없다
• 일반적으로 프로세스는 진입/퇴출/나머지 구역으로 구성된다
• 임계구역 문제 해결을 위한 요구 조건

  1. 상호 배제 : 한 프로세스가 임계구역에서 실행될 때, 다른 어떤 프로세스도 임계 구역에 접근할 수 없음

  2. 진행 : 임계구역에서 실행중인 프로세스가 없고 임계 구역에 들어가고자 하는 프로세스가 존재한다면, 나머지 구역에서 실행 중이지 않은 프로세스들만 다음 임계 구역에 진입할 프로세스를 결정하는데 참여할 수 있음. 이 선택은 무한정 연기할 수 없음

     • 임계구역에 들어가고자 하는 프로세스가 있다면 >>?????

  3. 제한이 있는 대기시간
     프로세스가 자신의 임계 구여게 진입하려는 요청을 한 후부터 요청이 허용될 때까지, 다른 프로세스들이 자신의 임계구역에 진입하도록 허용되는 횟수에 한계가 있어야 함

임계구역 문제의 해결안

1. 피터슨의 해결안

• 두 개의 프로세스가 두 개의 데이터 항목을 공유하게 함
• int turn : 임계 구역에 진입할 순번
• Boolean flag[2] : 프로세스가 임계 구역에 진입할 준비가 되었는지
  

2. 뮤텍스 락

• 뮤텍스 락을 이용해 임계구역을 보호하고 경쟁을 방지함
• 프로세스는 임계영역에 진입하기 전 반드시 락을 획득해야함. 임계 영역 사용 종료 시
  잠금 해제
• 잠금 사용 가능 여부를 나타내는 Boolean 변수 사용
• 그러나, busy waiting이 존재함(spinlock)
  

3. 세마포어

• 정수 변수(S)

• wait() - P, signal() - V연산으로만 접근이 가능
  

• 카운트 세마포어 : 영역에 제한이 없고 유한한 개수를 가진 자원에 접근을 제어하는데 가용

• 이진 세마포어 : 0과 1 사이의 값만 가능, 뮤텍스 락과 유사

• 자원을 사용하려는 프로세스에 세마포어 wait 수행(S감소)

• 프로세스가 자원의 사용이 끝날 때 signal 수행(S증가)

세마포어도 busy waiting이 존재

• 대신 자신을 봉쇄하여 단점을 상쇄함
• Sleep: 프로세스를 해당 세마포어와 연결된 대기 큐에 위치
• Wakeup: 프로세스를 대기 상태에서 준비 상태로 변경

교착상태(DeadLock)와 기아상태(Starvation)

• 여러 프로세스가 같은 자원에 접근하고자 할 때 교착상태가 발생하는데, 교착상태를 해결하고자 계속해서 순서가 뒤로 밀리는 프로세스는 기아상태가 발생함

교착상태의 특징

다음 네 가지 조건이 동시에 성립하면 교착상태 발생.

1. 상호배제

   • 두 프로세스는 동시에 같은 자원에 접근할 수 없음
   • 다른 프로세스가 자원을 요청하면, 요청 프로세스는 자원이 해제될 때까지 대기한 후 사용 가능
     -> 공유 가능한 리소스를 설정한다(읽기 전용 파일), 동시에 접근 가능한

2. 점유하며 대기??

   • 프로세스는 최대한 하나의 자원을 점유한 채, 현재 다른 프로세스에 의해 점유된 자원을 추가로 얻기 위해 반드시 대기해야 함
     -> 프로세스가 작업을 시작하기 전에 필요한 자원을 미리 모두 획득
     -> 리소스를 획득하는데에 드는 시간은 줄지만, 이 작업을 하는 동안 자원은 다른 프로세스에 사용되지 않으니까 리소스 활용도 낮음 / 기아 발생

3. 비선점

   • 자원들을 선점할 수 없어야 함
   • 자원들이 강제로 해제될 수 없고, 점유하고 있는 프로세스가 태스크를 종료한 후에만 해제됨
     -> 이미 가진 자원에 대해 선점할 수 없어야 함. 강제로 다른 프로세스가 자원을 가져갈 수 있음
     -> 기존 프로세스가 작업 내용을 잃을 수 있음

4. 순환 대기

   • 자원들이 cyclic하게 점유한 자원들을 대기해야 함
     1 -> 2 -> 3 -> 1
     -> 리소스에 고유 번호를 할당해서 번호 순서대로 리소스를 요청하도록 함
     -> 작업에 필요한 자원은 오래 전부터 할당받고 있어야 하므로 자원 낭비 가능

교착상태 회피 - 은행가 알고리즘 / 뱅커스 알고리즘

• 상태를 안전상태(safe state) / 불안전상태(unsafe state)로 분류

• 안전상태를 유지할 수 있는 요청만을 수락, 불안전상태의 경우 추후 만족하는 상태로 바뀔
  때까지 계속 거절

• 파라미터

  1. 현재점유량 (Allocation) : 현재 프로세스 별 할당 자원의 수
  2. 최대요구자원 (Max) : 프로세스 별 최대 자원의 요구
  3. 현재여유자원 (Available) : 사용 가능한 자원의 수
  4. 필요량 (Need) : 프로세스 별 남아있는 자원의 수
     Need[i][j] = Max[i][j] – Allocation[i][j]

// 전혀 모르겟다