7. 훑어보는 프로세스 동기화

프로세스 동기화

현대 운영체제는 모두 다수의 프로세스를 적재하여 처리하는 다중 프로그래밍 환경이다. 다중 프로그래밍 환경에서 프로세스들은 기본적으로 엄격하게 분리되어 상호 간섭이 불가능하여 비동기적으로 진행되지만, 프로세스들이 메모리를 공유하거나(공유 메모리) 다중 스레드를 지원하는 경우, 여러 개의 프로세스(스레드 포함)들이 변수 등 같은 자원에 대한 접근을 경쟁하는 상황이 일어날 수 있어 동기화가 필요하다.

접근 경쟁 상황은 병행 처리와 병렬 처리 두 가지 처리 형태에서 나타난다.

1. 병행 처리와 경쟁 상황

병행 처리(Concurrent Processing): 하나의 CPU가 여러 개의 프로세스를 조금씩 빠른 속도로 번갈아 처리함으로써 거시적 관점에서 여러 개의 프로세스를 한꺼번에 처리하는 효과가 있다.

즉, 병행 처리에서는 어느 순간에 살펴보면 오직 한 프로세스만 실행된다.

공유 변수 A = 5

CPU: P0 -> P1

P0: b = 3, c = 4, d = 2
A = A + b * c - d;   (A = 15)

P1: x = 2, y = 3, z = 2
A = A - x * y + z; (A = 11)

위에서 공유 변수 A를 참조하는 두 프로세스 P0과 P1에 의해 변수 A의 최종값은 11이어야 한다. 그런데, 아래 시나리오같이 CPU 스케줄링이 이루어지면 A의 최종값이 잘못 계산된다.

1. P0이 A의 현재 값 5를 사용하여 A + b * c 의 계산을 마치자마자(중간값: 17) CPU 스케줄링으로 인해 CPU가 P1에 할당된다.
2. P1은 아직 변하지 않은 A 값 5를 참조하여 계산을 마치고 A 값을 1로 변경한다.
3. 나중에 P0이 다시 할당되면, 이전에 중단되었던 수식 계산을 계속하여 이전의 중간값 17 - d를 계산하여 나온 15를 A에 저장함으로써 결국 A는 원하는 값 11이 아닌 15가 남게 된다.

이런 병행 처리 경쟁 상황(Race Condition)은 공유 변수가 포함된 수식 계산을 완전히 마치지 못한 상태에서 CPU 스케줄링이 일어날 때 발생한다.

2. 병렬 처리와 경쟁 상황

병렬 처리(Parallel Processing): 두 개 이상의 CPU가 여러 프로세스를 분담하여 독립적으로 동시에 처리하는 형태를 말하는데, 어느 순간에 CPU 개수만큼의 프로세스들이 CPU를 할당받아 실행되고 있다.

이 같은 병렬 처리 환경에 공유 변수를 참조하는 프로세스들이 존재한다면 병행 처리 환경에서와 유사한 경쟁 상황이 발생한다.

예를 들어, P0과 P1이 각각 CPU0과 CPU1에 각각 할당되어 병렬 처리 중이고, 양쪽 모두 두 수식 부분을 계산 중이라면, 병행 처리와 같은 문제가 발생한다. 또한. P0과 P1의 수식이 끝나는 순서에 따라 공유 변수 A의 최종값이 달라진다.

즉, 병렬 처리 경쟁상황은 병렬 처리 환경에서 공유 변수를 참조하는 프로세스들이 처리될 때 발생한다.

3. 임계 영역과 상호 배제

경쟁 상황이 발생할 수 있는 부분은 어느 쪽이든 먼저 도착한 프로세스가 계산을 모두 마치고 공유 변수값을 최종 변경할 때까지 다른 프로세스는 수식에 대한 계산 시작을 연기하고 기다려야만 올바른 계산 결과가 보장된다.

이처럼 경쟁 상황이 발생할 수 있는 부분들을 합쳐서 임계 영역(Critical Section)이라 부르고, 임계 영역은 어떤 경우에도 오직 하나의 프로세스만이 실행할 수 있도록 제한하는 개념을 상호 배제(Mutual Exclusion)라 한다. 상호 배제에 기반을 둔 프로세스 진행을 프로세스 동기화(Process Synchronization)라 한다.

상호배제는 크게 소프트웨어 방법과 하드웨어 방법으로 구현할 수 있다.

4. 소프트웨어 상호 배제 방법

- Dekker's Algorithm

- Perterson's Algorithm

- Lamport's Bakery Algorithm

5. 상호 배제를 위한 하드웨어 지원

상호 배제를 위한 소프트웨어 기법들이 복잡하고 어려운 이유는 컴퓨터 하드웨어 구조상, 메모리에 존재하는 특정 변수에 대하여 CPU가 "메모리 읽기 - 판단 - 메모리 저장" 과정을 거치는 동안에 다른 프로세스가 중간에 끼어들어 해당 변수를 참조할 수 있기 때문이다.

즉, 일반적인 기계 명령어는 메모리에서 값을 읽자마자 메모리 버스를 놓아주므로 다른 프로세스의 메모리 접근이 가능한 것이다. 따라서 중간에 끼어들기를 허용하지 않는 "메모리 읽기 ~ 저장" 기계 명령어가 제공된다면 상호 배제는 아주 쉽게 이루어질 수 있다.

이런 기계 명령어는 "읽기 ~ 저장"하는 단계 동안 메모리 버스를 놓지 않을 뿐만 아니라, 하나의 기계 명령어이므로 이 사이에 인터럽트 당할 염려도 없다.

- TAS(Test & Set)

- SWAP

6. 세마포어(Semaphores)

앞에서 제안된 상호 배제 기법들은 모두 바쁜 대기(Busy Waiting)를 기반으로 임계 영역을 보호한다. 이러한 잠금장치를 스핀 록(Spin Lock)이라 부르는데, 임계 영역이 길면 스핀 록에 의한 CPU 사용 낭비가 심하고, 임계 영역에 진입한 프로세스가 CPU 스케줄링에 의해 스위칭 되거나 비정상적으로 종료하면 이에 따른 파급효과가 크다는 단점이 있다. 이를 개선할 수 있는 보다 보편적 개념의 잠금장치 세마포어가 출현했다.

세마포어는 추상적 잠금장치로 잠금 연산 P()와 해제 연산 V()에 의해 접근 가능한 정수 변수 S를 일컫는다.

P(S) // 잠금
{
  if(S > 0)
    S = S - 1;
  else
    V() 연산에서 깨울 때까지 세마포어 큐에서 대기;

  return;
}

V(S) // 해제
{
  if(세마포어 큐가 비어있으면)
    S = S + 1;
  else
    세마포어 큐의 한 프로세스를 깨워줌(대기->준비);

  return;
}

S = 1(세마포어 정수 변수), A = 5(공유 변수);

Process 0:
b = 1, c = 2, d = 3;
...
P(S);
A = A - b * c - d;
V(S);
...


Process 1:
e = 2, f = 3;
...
P(S);
a = a + e - f;
V(S)
...

세마포어 S에 대한 연산 P()와 V() 각각의 처리 절차 전체는 하나의 임계 영역으로 이루어져 원자적으로 처리된다. 즉, P()와 V() 연산을 합쳐서 이들은 어느 한 프로세스만이 진입하여 실행할 수 있다.

세마포어에서 변수 S는 공통 깃발을 역할을 하고, 연산 P(S)는 잠겼다는 의미로 깃발 S를 내리려는 행위(Probern)이며, 연산 V(S)는 열렸다는 의미로 깃발 S를 올리려는 행위다.

만약 두 프로세스가 거의 동시에 P(S) 연산을 시도했다면, 이들 중 하나는 깃발을 내려놓고 진행을 계속하지만, 다른 한쪽은 내릴 깃발이 없으므로 세마포어 큐에서 대기한다. 이 프로세스 다음에 P(S)를 시도하는 모든 프로세스도 마찬가지로 세마포어 큐에서 대기한다.

P(S) 연산에서 성공하여 임계 영역을 마친 프로세스는 깃발을 다시 올려놓기 위해 V(S) 연산을 해주어야 하는데, 이때 V(S) 연산은 세마포어에서 대기하는 프로세스가 있다면 깃발은 그대로 두고 하나의 프로세스를 선택하여 준비 상태로 만들어 줌으로써 P(S) 연산을 성공하고 임계 영역에 진입하도록 한다.

세마포어는 임계 영역 집일을 위해 대기하는 동안 바쁜 대기를 하지 않으므로 CPU 사용 낭비를 줄일 수 있으나, P(S) 연산에서의 대기 상태 전환으로 인한 CPU 스케줄링이 요구되므로 문맥 교환(Context Switch) 부담이 따른다. 따라서 스핀 록과 세마 포어 사이의 선택은 임계 영역 크기와 성격에 따라 신중하게 이루어져야 한다.

---