/ #기타

프로세스 동기화

프로세스 동기화(Synchronization)란?

프로세스 동기화란 프로세스의 실행 순서를 제어하고 동시에 접근할 수 없는 자원에 하나의 프로세스만 접근하게 하여 데이터의 일관성을 유지하는 과정을 말합니다.

프로세스는 동시에 실행되면서 서로 영향을 주고 받는데, 이 과정에서 자원의 일관성이 보장되어야 합니다. 일관성이란 자원의 상태가 동일함을 의미합니다. 예를 들어 1번지에 저장되어 있는 데이터와 2번지에 저장되어 있는 데이터를 더한다고 할 때, 1번지와 2번지에 저장되어 있는 데이터는 연산이 종료될 때까지 값이 변하면 안됩니다.

여러 프로세스들이 동시에 자원에 접근하는 상황에서는 명려어 실행 순서에 따라 결과값이 달라질 수 있는데, 이 상황을 경쟁 상태(Race Condition)라고 합니다. 경쟁 상태가 발생하면 자원의 일관성이 깨질 수 있습니다.

예를 들어 생산자-소비자 문제(Producer Consumer Problem)가 있습니다.

생산자-소비자 문제(Producer Consumer Problem)
#include <stdio.h>
#include <pthread.h>

int sum = 0;

void *producer(void *arg) {
  for(int i = 0; i < 100000; i++) sum++;
  pthread_exit(NULL);
}

void *consumer(void *arg) {
  for(int i = 0; i < 100000; i++) sum--;
  pthread_exit(NULL);
}

int main() {
  pthread_t producer_tid, consumer_tid;

  pthread_create(&producer_tid, NULL, producer, NULL);
  pthread_create(&consumer_tid, NULL, consumer, NULL);

  pthread_join(producer_tid, NULL);
  pthread_join(consumer_tid, NULL);

  printf("sum: %d\n", sum);

  return 0;
}

자원을 공유하기 위해 프로세스 대신에 스레드를 생성했습니다. 스레드는 차후 설명하겠습니다.

producer 스레드는 10만번 더하고, consumer 스레드는 10만번 뺍니다. sum의 결과는 0이 예상되지만 동기화가 되지 않았기 때문에 일관성이 깨져 0이 출력되지 않는 것을 확인할 수 있습니다.

출력 결과

img132

각 스레드는 한줄의 코드 일지라도 sum의 값을 읽어 MBR에 저장하고 ALU에서 연산 후 sum에 연산값을 저장하는 등 여러 명령어로 구성되어 있습니다. producer가 공유 자원인 sum에 연산값을 저장하기도 전에 문맥 교환이 발생하여 consumer가 실행된다면 데이터의 일관성은 깨져버립니다. 이는 은행계좌 문제(Bank Account Problem)에서 명확히 확인할 수 있습니다.

은행계좌 문제(Bank Account Problem)
프로세스A 프로세스B 잔액
잔액 읽기   100만원
10만원 더하기   100만원
문맥교환   100만원
  잔액 읽기 100만원
  20만원 더하기 100만원
  문맥교환 100만원
잔액 저장   110만원
  잔액 저장 120만원

프로세스A는 10만원을 더하고 프로세스B는 20만원을 더하므로 최종 잔액은 130만원이 되어야 하지만, 프로세스A에서 10만원을 더한 값을 저장하기도 전에 프로세스B가 실행되어 잔액의 일관성이 깨져버렸습니다.

임계 구역(Critical Section)

이처럼 공유 자원에 접근하는 코드 중 동시에 실행되면 문제가 발생하는 코드 영역을 임계 구역(Critical Section)이라고 합니다. 프로세스가 임계구역에 동시에 접근하면 경쟁 상태가 되어 자원의 일관성은 깨져버립니다.

임계 구역 문제를 해결하기 위해 운영체제는 다음과 같은 조건을 만족해야 합니다.

  1. 상호 배제(Mutual Exclusion): 한 프로세스가 임계 구역에 진입했다면 다른 프로세스는 임계 구역에 들어올 수 없습니다.
  2. 유한 대기(Bounded Waiting): 어떠한 프로세스도 무한 대기해서는 안됩니다.
  3. 진행의 융통성(Progress): 임계 구역에 어떠한 프로세스도 진입하지 않았다면 진입하고자 하는 프로세스의 진행을 방해해서는 안됩니다.

동기화 방법

뮤텍스 락(Mutex Lock)

뮤텍스 락은 상호 배제를 위한 동기화 메커니즘 입니다. 공유 자원인 lock이 하나 존재하며, acquire 함수를 통해 임계구역을 잠그고 release 함수를 통해 임계 구역의 잠금을 해제할 수 있습니다.

뮤텍스 락
global bool lock = false;

acquire() {
  while (lock == true) ;
  lock = true;
}

release() {
  lock = false;
}

acquire();
// 임계 구역
release();

프로세스가 임계 구역에 진입하기 전에 acquire 함수가 호출합니다. 임계 구역이 잠겨 있다면(lock = true) 임계 구역이 열릴 때까지 임계 구역을 반복적으로 확인하는데, 이를 바쁜 대기(busy waiting) 이라고 합니다.

임계 구역이 열려 있다면 임계 구역을 잠근 후(lock = true) 임계 구역에 진입하고, 임계 구역의 작업이 끝난다면 release 함수를 호출하여 임계 구역의 잠금을 해제하고(lock = false) 임계 구역을 빠져나오게 합니다.

뮤텍스 락 예제
#include <stdio.h>
#include <pthread.h>
#include <stdbool.h>

volatile int sum = 0;
volatile bool lock = false;

void acquire() {
  while (lock == true) ;
  lock = true;
}

void release() {
  lock = false;
}

void *producer(void *arg) {
  acquire(); // 뮤텍스 락 잠금
  for(int i = 0; i < 100000; i++) sum++; // 임계 구역
  release(); // 뮤텍스 락 열림
  pthread_exit(NULL);
}

void *consumer(void *arg) {
  acquire(); // 뮤텍스 락 잠금
  for(int i = 0; i < 100000; i++) sum--; // 임계 구역
  release(); // 뮤텍스 락 열림
  pthread_exit(NULL);
}

int main() {
  pthread_t producer_tid, consumer_tid;

  pthread_create(&producer_tid, NULL, producer, NULL);
  pthread_create(&consumer_tid, NULL, consumer, NULL);

  pthread_join(producer_tid, NULL);
  pthread_join(consumer_tid, NULL);

  printf("sum: %d\n", sum);

  return 0;
}
출력 결과

img133

뮤텍스 락은 프로그래밍 언어에서 지원되는 경우가 많기 때문에 직접 구현할 일은 많지 않습니다.

C언어 뮤텍스락 예제
#include <stdio.h>
#include <pthread.h>

pthread_mutex_t lock = PTHREAD_MUTEX_INITIALIZER;

volatile int sum = 0;

void *producer(void *arg) {
  pthread_mutex_lock(&lock); // 뮤텍스 락 잠금
  for(int i = 0; i < 100000; i++) sum++; // 임계 구역
  pthread_mutex_unlock(&lock); // 뮤텍스 락 열림
  pthread_exit(NULL);
}

void *consumer(void *arg) {
  pthread_mutex_lock(&lock); // 뮤텍스 락 잠금
  for(int i = 0; i < 100000; i++) sum--; // 임계 구역
  pthread_mutex_unlock(&lock); // 뮤텍스 락 열림
  pthread_exit(NULL);
}

int main() {
  pthread_t producer_tid, consumer_tid;

  pthread_create(&producer_tid, NULL, producer, NULL);
  pthread_create(&consumer_tid, NULL, consumer, NULL);

  pthread_join(producer_tid, NULL);
  pthread_join(consumer_tid, NULL);

  printf("sum: %d\n", sum);

  return 0;
}

세마포어(Semaphore)

세마포어는 철도의 수신호를 의미하는 용어입니다. 철도의 수신호가 기차의 진행을 제어하듯이 세마포어도 프로세스의 임계구역 진입 여부를 제어합니다. 한번에 하나의 프로세스만 임계 구역에 들어갈 수 있는 뮤텍스 락과 달리 여러 프로세스가 임계구역에 들어가도록 할 수 있습니다.

세마포어는 임계 구역에 진입할 수 있는 프로세스의 개수를 나타내는 전역 변수 S와 임계 구역의 진입 가능 여부를 알려주는 wait 함수, 대기 상태인 프로세스에게 임계 구역에 진입 가능하다는 신호를 주는 signal 함수로 구현할 수 있습니다.

세마포어
global int S = false;

wait() {
  while (S <= 0) ;
  S--;
}

signal() {
  S++;
}

wait();
// 임계 구역
signal();

프로세스가 wait 함수를 호출할 때마다 임계구역에 진입할 수 있는 프로세스의 수인 S를 확인하고, S가 0이라면 S가 증가할 때까지 반복해서 확인합니다. S가 0보다 크다면 S를 1 감소시키고 임계구역에 진입합니다. 임계구역의 코드가 실행된 후 signal 함수를 호출하여 S를 1 증가시켜 줍니다.

wait 함수를 보면 뮤텍스 락과 같이 바쁜 대기 상태인데, 이는 CPU 성능을 저하시키는 요인이 될 수 있습니다. 이를 해결하기 위해서 wait 함수에서 임계 구역에 진입하지 못하면 프로세스를 대기 상태로 만들고, signal 함수가 호출될 때 대기 상태에 있는 프로세스를 준비 상태로 만들어주면 됩니다. 대기 상태에 있는 프로세스는 CPU 자원을 사용하지 않기 때문에 작업 사이클의 낭비를 막을 수 있습니다.

바쁜 대기 상태 해결
global int S = 2;

wait() {
  S--;
  if (S < 0) {
    // 현재 프로세스의 PCB를 대기 큐에 삽입
    sleep(); // 현재 프로세스를 대기 상태로 전환
  }
}

signal() {
  S++;
  if(S <= 0) {
    // 대기 큐에 있는 p 프로세스의 PCB 제거
    wakeup(p); // p 프로세스를 준비 상태로 전환
  }
}

wait();
// 임계 구역
signal();

세마포어 역시 뮤텍스 락과 마찬가지로 프로그래밍 언어에서 지원되는 경우가 많기 때문에 직접 구현할 일은 많지 않습니다.

모니터(Monitor)

세마포어는 임계구역 앞뒤로 wait와 signal 함수를 직접 호출해야 하므로 사용자가 사용하기에 조금 불편한 점이 있습니다. 가령 프로그램 규모가 커지면 실수로 함수를 호출하지 않거나 잘못된 순서로 함수를 호출하여 예기치 않은 결과가 발생할 수 있습니다.

모니터는 공유자원과 인터페이스를 하나로 묶어 관리함으로써 이러한 불편함을 해소한 동기화 도구 입니다. 뮤텍스 락이나 세마포어가 저수준 레벨의 언어에서 사용하기 적합한 도구라면 모니터는 고수준 레벨의 언어를 위한 도구입니다. 모니터를 사용하는 대표적인 언어는 자바가 있습니다.

공유자원에 접근하고자 하는 프로세스는 특정 인터페이스를 위한 큐에 쌓이며, 하나의 인터페이스를 통해서만 공유자원에 접근할 수 있게 함으로써 상호배제 동기화가 가능합니다.

img134

실행 순서를 제어하기 위해서는 모니터 내부의 조건 변수를 사용합니다. 모니터 내부에는 조건 변수에 대한 큐가 존재하며, 공유자원과 인터페이스, 조건 변수를 캡슐화하여 추상화된 데이터 형(Abstract Data Type, ADT)을 형성합니다.

모니터는 wait 함수를 통해 프로세스를 대기 상태로 전환하여 조건 변수 큐에 삽입합니다.

img135

조건 변수에서 대기 상태인 프로세스는 signal 함수를 통해 실행 상태로 전환되어 인터페이스를 통해 공유자원에 접근할 수 있습니다.

img136

자바에서는 모든 객체가 모니터를 가지고 있습니다. 임계구역은 synchronized 키워드를 통해 설정할 수 있으며, 모니터를 가지는 스레드는 해당 객체에 락을 걸어 다른 스레드가 해당 객체에 접근할 수 없게 됩니다.

예제 코드를 작성해보겠습니다.

BankAccount.java
public class BankAccount {

  int money = 0;

  public void deposit(int amount) {
    money += amount;
  }

  public void withdraw(int amount) {
    money -= amount;
  }
}
Consumer.java
public class Consumer implements Runnable {

  BankAccount bankAccount;
  int amount;

  public Consumer(BankAccount bankAccount, int amount) {
    this.bankAccount = bankAccount;
    this.amount = amount;
  }

  @Override
  public void run() {
    try {
      for (int i = 0; i < 1000; i++) {
        Thread.sleep(1);
        bankAccount.withdraw(amount);
        System.out.println("잔액: " + bankAccount.money);
      }
    }
    catch (InterruptedException e) {}
  }
}
Producer.java
public class Producer implements Runnable {

  BankAccount bankAccount;
  int amount;

  public Producer(BankAccount bankAccount, int amount) {
    this.bankAccount = bankAccount;
    this.amount = amount;
  }

  @Override
  public void run() {
    try {
      for (int i = 0; i < 1000; i++) {
        Thread.sleep(1);
        bankAccount.deposit(amount);
        System.out.println("잔액: " + bankAccount.money);
      }
    }
    catch (InterruptedException e) {}
  }
}
Example.java
public class Example {

  public static void main(String[] args) throws Exception {

    BankAccount bankAccount = new BankAccount();

    Producer producer = new Producer(bankAccount, 10000);
    Consumer consumer = new Consumer(bankAccount, 10000);

    Thread t1 = new Thread(producer);
    Thread t2 = new Thread(consumer);

    t1.start();
    t2.start();

    t1.join();
    t2.join();

    System.out.println("--------------");
    System.out.println("잔액: " + bankAccount.money);
  }
}

실행시켜보면 동기화가 되지 않아 최종 잔액이 0원이 아닙니다.

실행 결과

img137

다음과 같이 BankAccount에 syncronized 키워드를 통해 임계영역을 설정할 수 있습니다.

BankAccount.java
public class BankAccount {

  int money = 0;

  synchronized public void deposit(int amount) {
    money += amount;
  }

  synchronized public void withdraw(int amount) {
    money -= amount;
  }
}
실행 결과

img138

최종 잔액이 0원이 되었지만 중간과정에 잔액이 마이너스가 됩니다. 이때 실행 순서를 제어하기 위해 wait()와 notify()를 사용할 수 있습니다.

BankAccount.java
public class BankAccount {

  int money = 0;

  synchronized public void deposit(int amount) throws InterruptedException {
    money += amount;
    notifyAll();
  }

  synchronized public void withdraw(int amount) throws InterruptedException {
    if(money == 0) wait();
    money -= amount;
    notifyAll();
  }
}
실행 결과

img139