[운영체제] 여러 프로세스가 공유 데이터에 동시에 접근하면 어떻게 되나?

여러 프로세스가 공유 데이터에 동시에 접근하면 어떻게 되나?

어떤 데이터를 바꾸는 과정은 크게 두 개의 과정으로 나뉘어집니다. 첫 째는 해당 값을 읽어오는 것이고 둘 째는 새로운 값을 할당하는 것입니다. 만약 0이 할당된 D라는 공유 데이터의 값을 1 증가시키는 A프로세스를 실행하는 도중에, CPU를 뺏겨 같은 D의 값을 1 감소시키는 B프로세스에게 넘어가면 어떻게 될까요? B가 D를 읽는 시점에는 0일 것이고, 0에서 1을 뺀 -1을 다시 D에 저장할 것입니다. 이후 A에게 차례가 돌아와 A의 문맥에서는 여전히 D를 0으로 알고 있고, 1을 더한 1을 D에 저장할 것입니다. 이 경우 B는 완전 무시당하게 됩니다.

Race Condition

이렇게 여러 프로세스가 동시에 프로세스에 접근하는 상황을 Race Condition이라고 합니다. 이 문제는 다음의 상황에서 발생할 수 있습니다.

1. kernel 수행 중 인터럽트 발생 시
2. Process가 system call을 하여 kernel로 수행 중에 Context Switch가 일어나는 경우
3. Multiprocessor에서 shared memory 내의 Kernel data에 접근하는 경우

해결 방법

공유 메모리리에 접근하는 중에는 인터럽트를 disable시키는 방법이 있습니다. 하지만 Multiprocessor에서는 이 방법으로는 부족합니다. 각 CPU는 독립적이기 때문입니다. 따라서, 1) 한번에 하나의 CPU만 커널에 들어가게 하거나 2) 공유 데이터 자체에 lock/unlock을 거는 방법이 있습니다.

Critical-Section

공유데이터에 접근하는 코드를 Critical-Section이라고 합니다. 위의 해결방법의 2번, 공유 데이터 자체에 lock/unlcok을 거는 방법을 Critical Section에 적용할 수 있습니다.

• Synchronazation: 기본적으로 동기화를 위한 변수를 프로세스들이 공유하여, 이를 통해 lock을 걸 수 있습니다. 예를 들어, Critical Section에 들어가기 전에 해당 변수를 확인해서 다른 프로세스가 사용중이라면 기다리고, Critical Section이 지난 후에는 이 공유 변수를 바꿔 공유 변수를 사용하고 있지 않다고 표시하는 것입니다.

공유 변수를 통해 Lock을 거는 방법의 충족 요건

1. Mutual Exclusion
   한 프로세스가 Critical Section을 수행 중이면, 다른 모든 프로세스는 이 Section에 접근할 수 없다.
2. Progress
   아무도 Critical Section에 없으면, 들어가 수 있다.
3. Bounded Waiting
   프로세스가 Critical Section에 들어가려고 요청한 후부터 요청이 허용될 때까지, 다른 프로세스들이 Critical Section에 들어가는 횟수에 한계가 있어야한다.

Peterson's Algorithm

/** 
 * flag과 turn은 Synchronization varable (공유 변수)
 * flag[i]: 프로세스i가 Critical Section에 들어가고 싶다고 깃발을 드는 것.
 * turn: 이 변수의 값이 i라면, 프로세스i의 차례라는 뜻.
 * 프로세스 i의 코드
 */
do {
  flag[i] = true
  turn = j;
  while (flag[j] && turn == j);
  critical section
  flag[i] = false;
  remain section
} while(1);

• 프로세스j가 깃발을 들고, j의 턴일 땐 기다립니다.
• 둘 중의 하나라도 false이면 critical section에 들어갑니다.
• 상대방이 깃발을 들지 않고 나만 깃발을 든 경우: 언제든 들어갈 수 있습니다.
• 상대방과 내가 동시에 깃발을 든 경우: 번갈아가면서 실행됩니다.
• 만약 flag 변수가 없다면, 반드시 상대방이 나의 턴으로 바꿔줘야 내가 CS에 들어갈 수 있습니다. 이런 경우 한 프로세스가 더 빈번히 CS에 들어가야한다면, 비효율이 발생합니다.
• 만약 turn 변수 없이 flag만 있다면 두 프로세스가 깃발을 든 직후에 CPU가 뺏기는 경우, 서로 양보하느라 아무도 Critical Section에 접근하지 못하는 문제가 생깁니다. 위의 충족 요건 중 2번을 만족시키지 못하죠.
• 따라서 두 변수를 함께 사용함으로써 위의 세 가지 요건을 모두 충족시킬 수 있습니다. 프로세스 i가 깃발도 들고 turn을 j로 바꾸고 CPU가 프로세스 j로 넘어간 후, j도 깃발을 들고 turn을 i로 바꾼다면, while을 돌다가 다시 프로세스i에게 cpu가 넘어가게 됩니다. 이때, turn이 i로 바뀌어있음으로 critical section에 들어가게됩니다.
• 하지만 두 프로세스가 기다리는 동안에는 계속 while문을 돌면서 쓸데 없이 CPU를 낭비하는 문제가 있습니다.

Synchronization Hardward

하드웨어적으로 Test & Modify를 atomic하게 수행하는 것을 지원한다면, 위의 문제를 해결할 수 있습니다. Atomic하게 수행한다는 것은은 읽고 쓰는 행위를 하나의 인스트럭션으로 수행함으로써 중간에 CPU를 뺏기는 가능성을 차단한 것입니다.

/**
 * 공유 변수: boolean lock = false;
 * Test_and_Set(boolean lock) -> lock 변수를 읽어서 그 값을 반환한 후, lock 변수를 true로 바꾼다. 이 두 작업을 Atomic하게 한다.
 */
Process Pi
  do {
    while (Test_and_Set(lock));
    critical section
    lock = false;
    나머지 코드
  } while (1);

위의 코드에서 lock이 true인 경우는 다른 누군가가 critical section에 있다는 뜻입니다. 이때는 while문을 계속 돌게 됩니다. 반면 lock이 false인 경우에는 아무도 없다는 뜻임으로 critical section을 수행한 후 lock을 false로 바꿉니다. 그럼 while문을 돌 던 process가 critical section에 들어갈 수 있습니다.

Semaphores

Semaphore S 변수는 위의 연산들을 추상화 시킨 것입니다. 이 변수는 아래의 두 연산에 의해서만 접근이 가능합니다.

1. P(S):

    while (S <= 0) do no-op;
    S--;

2. V(S):

    S++;

위의 S 변수가 뜻하는 것은 남은 공유 자원의 개수입니다. S가 양수라면 남은 공유 자원이 있음으로 사용할 수 있다는 것입니다. P연산은 공유자원을 획득하는 것이고, V 연산은 반납하는 것입니다.

/**
 * 공유 변수: Semaphore mutex;
 */
Process Pi
  do {
    P(mutex);
    critical section
    V(mutex);
    나머지 코드
  } while (1);

Semaphore의 종류

1. Counting
   정수 값으로 사용합니다. 자원의 남은 개수를 가리킵니다.
2. Binary semaphore(boolean)
   주로 Critical Section에 들어갈 수 있는 상태의 여부(lock / unlock)을 나타냅니다.

Block & Wakeup

하지만 위의 방식은 여전히 Busy Wait 문제(기다리는 동안에 쓸데없이 CPU를 낭비하는 것)가 있습니다. 이 문제를 기다리는 동안에는 프로세스를 잠재우고 (상태를 wait로 바꿈), Critical Section으로 들어가기 직전에 깨우는(Ready) 방법으로 해결할 수 있습니다.

Semaphore 구조체 정의

typedef struct {
  int value;
  struct process *L; /* critical section에 들어가기위해 기다리는 프로세스들의 큐 */
}

P와 V연산 정의

1. P(S):

    S.value--;
    if (S.value < 0) {
      add this process to S.L; /* 큐에 삽입 */
      block;/* 재우기 */
    }

2. V(S):

    S.value++;
    if (S.value <= 0) {
        remove a process P form S.L;
        wakeup(P);
    }

무엇이 더 좋은가? (Busy-Wait v.s. Block & Wakeup)

Critical Section이 긴 경우, Block & Wakeup 방식이 더 좋고, 그렇지 않을 경우 Busy-Wait가 더 좋습니다. 그러나 대게의 경우 Block&Wakeup방식이 더 좋습니다.