[OS] Process Synchronization

Background

• Cooperating 프로세스들은 서로 영향을 주거나 받을 수 있다.
• Cooperating 프로세스들은 논리적 메모리 주소 공간을 공유하거나 데이터를 할당 받을 수 있다.

이 때, 공유 데이터에 동시 접근하면 데이터 일관성이 깨질 수 있다(데이터 무결성).

• 동시 실행(Concurrent execution)
  • 프로세스의 명령어 실행 흐름 중 인터럽트가 발생할 수 있다.
  • 할당된 코어는 다른 프로세스에 의해 선점될 수 있다.
• 병렬 실행(Parallel execution)
  • 두 개 이상의 명령어 흐름(instruction streams)
  • 서로 다른 코어에서 동시에 실행

따라서 Coopereating 프로세스 실행에서는 아래 내용이 확실하게 보장되어야 한다.

• 순차적 실행(Orderly execution)
• 공유하는 논리적 메모리 공간에서 데이터 일관성 유지

※ producer-consumer problem 상황에서는 어떤 일이 발생할까?

두 개의 프로세스가 데이터를 공유하고 비동기로 실행되는 상황을 가정해보자.

예시) 버퍼의 아이템 개수를 세기 위해, count 변수를 추가

• initialized to 0
• incremented every time we add a new item to the buffer
• decremented every time we remove one item from the buffer

/* producer */
while (true) {
  /* produce an item in next_produced */
  
  while (count == BUFFER_SIZE)
  ; /* do nothing */
  buffer[in] = next_produced;
  in = (in + 1) % BUFFER_SIZE;
  count++;
}

/* consumer */
while (true) {
  while (count == 0)
  ; /* do nothing */
  next_consumed = buffer[out];
  out = (out + 1) % BUFFER_SIZE;
  
  /* consume the item in next_consumed */
}

위의 예제는 잘 동작할 것 같지만 실제로는 문제가 존재한다.

❗Data inconsistency

두 개의 프로세스들이 각각 올바르게 실행되더라도, 동시에 실행되는 경우에는 올바르지 못 할 수 있다.

예를 들어, count 변수의 값이 5인 시점에서 producer와 consumer가 각각 count++; , count--; 문장을 실행하는 경우 count 변수의 값은 어떻게 될까? → 4, 5, 6 모두가 가능

❓ 그럼 왜 이런 현상이 발생할까?

count++; , count--; 두 문장을 자세히 분석해보면, 각각의 문장은 다음과 같은 기계어로 구현될 것이다.

/* increase instructions */
register1 = count
register2 = register1 + 1
count = register1

/* decreaese instructions */
register2 = count
register2 = register2 - 1
count = register2

💡 CPU가 덧셈 혹은 뺄셈 연산을 할 때에는 한 개의 레지스터에 원본 값을 저장하고, 다른 한 개의 레지스터에 연산 결과를 저장한 후, 원본 변수에 결과값을 저장하는 방식으로 동작한다.

위의 예제에서 각각의 명령어 집합들(increase, decrease)이 온전하게 실행되면 괜찮겠지만, 명령어 실행 중 Context Switch가 무작위로 발생하기 때문에 위와 같은 문제가 발생한다.

❗ Rade Condition

여러 개의 프로세스(혹은 쓰레드)가 공유 데이터에 동시에 접근하고, 조작하는 경우에는 특정 실행 순서에 따라 결과가 달라질 수 있다. 즉, 예측 불가능한 결과로 이어질 수 있다.

❓ 그럼 Race condition을 방지하기 위해서는 어떻게 해야할까?

특정 시점에 단 하나의 프로세스만 공유 데이터를 조작할 수 있도록 한다. (e.g. count 변수)

→ Process/Thread Synchronization: Rade condition을 방지하기 위한 방법으로, 프로세스들을 **동기화(synchroized)**시키는 방법

The Critical Section Problem

임계 영역 문제

Definition

• 가정) n 개의 프로세스로 구성된 시스템
  • 각 프로세스들은 공유 데이터를 접근(accessing), 수정(updating) 할 수 있는 **임계 영역(critical section)**이라고 불리는 하나의 segment of code를 갖는다.
  • 이 시스템에서 가장 중요한 기능은 하나의 프로세스가 임계 영역에서 실행 중인 경우, 다른 어떤 프로세스도 임계 영역 안에서도 실행될 수 없다는 것이다.

**임계 영역 문제(critical-section problem)**이란, 어떤 두 개의 프로세스 사이에서 임계 영역으로 지정되어야 할 영역이 임계 영역으로 지정되지 않았을 때 발생할 수 있는 문제를 뜻한다.

❗임계 영역 문제를 해결하기 위해서는 두 개의 프로세스가 서로의 활동(activity)을 동기화해서 데이터를 협력적으로 공유할 수 있도록 해야 한다.

Secions of codes

• entry-section: 임계 영역에 들어가기 위해 권한(permission)을 요청하는 영역
• critical-section: entry-section 다음의 영역(임계 영역; Context Switch가 발생하지 않도록)
• exit-section: critical-section 다음의 영역
• remainder-section: 남은 코드 영역

while (true) {
  1. entry section
    2. critical section
  3. exit section
  4. remainder section

Three requirements for the solution

• Mutual Exclusion
  • 어떤 프로세스가 임계 영역에서 실행 중이라면, 다른 프로세스들은 임계 영역에서 실행될 수 없다.
• Progress(deadlock 회피)
  • 어떤 프로세스도 임계 영역에서 실행 중이지 않은 경우에 몇 개의 프로세스들이 임계 영역에 접근하려 한다면, 어떤 프로세스가 접근할 것인지 결정해주어야 한다.
• Bounded Waiting(starvation 회피)
  • 임계 영역에 들어가는 경우, 한정된 시간만 허용된다.

위 세 가지 조건을 모두 충족해야만, 임계 영역 문제를 해결했다고 할 수 있다. 하지만 현실적으로는 적용이 어렵다고 한다.

Simple solution in a single-core enviroment

• 해결 방안: 공유 변수가 수정되는 경우에 인터럽트 발생 막는다.
• 조건: 1) 현재 실행되는 명령어 흐름이 선점되지 않으면서 순서대로 실행될 수 있어야 한다. 2) 예측 불가능한 공유 데이터 수정이 발생하지 않도록 다른 명령어들은 실행되지 않아야 한다.
• 문제점: 멀티코어 환경에서는 실현 불가능하다. 임계 영역이 큰 경우에 인터럽트가 발생하지 않게 된다면, 단일 흐름만 갖게 된다.

Non-preeptive kernel vs Preemptive kernal

• Non-preemptive kernel: 커널 모드의 프로세스가 커널 모드를 종료하거나, block되거나, 자발적으로 CPU 자원을 반납할 때까지 실행된다. 본질적으로 커널 자료 구조에서는 Race Condition으로부터 자유롭다.
• Preemptive kernel: 커널 모드에서 실행 중일 때도 선점될 수 있다. 설계하기 어렵지만, 더 유연하기 때문에 일반적으로 선호된다.