[운영체제] 프로세스 동기화 (세마포)

June 19, 2020

현대에는 쓰레드를 기준으로 switching이 발생하기 때문에 프로세스 동기화(Process Synchronization)보단 쓰레드 동기화로 주로 불린다.

프로세스는 두 부류로 나눌 수 있는데 프로세스 사이에 아무런 관계가 없이 독립적으로 존재하는 Independent process와 서로 영향을 주고 받는 Cooperating process 가 있다. 현대 컴퓨터엔 일반적으로 Cooperating process가 더 많은데 예를 들어보면 프로세스간 통신하는 전자우편, 파일 전송이 있고 프로세스간 자원 공유하는 메모리 상의 자료들, 데이터베이스 등이 있다. 이 외에도 명절 기차표 예약, 대학 온라인 수강신청, 실시간 주식거래 모두 Cooperating process 이다.

만약 동기화가 잘 못 되면 기차표를 똑같은 시간 똑같은 좌석에 두 명이 예약한다든지, 수강신청 인원이 초과되어 받아들여지는 문제가 생길 수 있다. 따라서 Cooperating process 간에 질서 있는 실행(순서)을 통해 일관성이 유지되어야 한다.

은행 계좌 문제

프로세스 동기화를 현실 상황에 대입해보자. 부모와 자녀가 공유하는 은행 계좌가 있고 부모님(process)은 입금만 하고 자녀(process)는 출금만 한다. 각각의 입금(deposit)과 출금(withdraw) 은 독립적으로 일어난다. 이를 자바 코드로 구현해보자.

class Test {
  public static void main(String[] args)
  throws InterruptedException {
    BankAccount b = new BankAccount();
    Parent p = new Parent(b);
    Child c = new Child(b);
    p.start(); //부모 쓰레드 시작 요청
    c.start(); //자식 쓰레드 시작 요청
    p.join(); //부모 쓰레드가 종료되길 기다림
    c.join(); //자식 쓰레드가 종료되길 기다림
    System.out.println( "\nbalance = " + b.getBalance()); // balance = 0
  }
}

//은행 계좌
class BankAccount {
  int balance;
  void deposit(int amount) {
    balance = balance + amount;
  }
  void withdraw(int amount) {
    balance = balance - amount;
  }
  int getBalance() {
    return balance;
  }
}

//부모 입금 쓰레드
class Parent extends Thread {
  BankAccount b;
  Parent(BankAccount b) {
    this.b = b;
  }
  public void run() {
    for (int i=0; i<1000; i++)
      b.deposit(1000);
  }
}

//자녀 출금 쓰레드
class Child extends Thread {
  BankAccount b;
  Child(BankAccount b) {
    this.b = b;
  }
  public void run() {
    for (int i=0; i<1000; i++)
      b.withdraw(1000);
  }
}

결과

balance = 0

실제 입출금을 할 때는 시간 지연이 있다. 이에 맞추기 위해 temp와 System.out.print 추가하여 의도적으로 시간 지연을 발생시키고, 스레드 스위칭을 확인해보기 위해 입금에 + 출금에 - 가 찍히도록 코드를 수정해보자.

// 계좌
class BankAccount {
  int balance;
  void deposit(int amount) {
    int temp = balance + amount;
    System.out.print("+");
    balance = temp;
  }
  void withdraw(int amount) {
    int temp = balance - amount;
    System.out.print("-");
    balance = temp;
  }
  int getBalance() {
  return balance;
  }
}

결과

+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------------------------------------------------------------------------------------------------------------------+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
balance = -745000

balance = 0 이 출력되야할것 같은데 -745000라는 값이 나온다. 코드는 논리적으로 잘못된부분이 없는것 같은데 무엇이 문제인걸까? 시간지연을 주게되면서 low level에서는 잦은 switching이 발생하게 된다. 쓰레드들은 이런 잦은 switching을 통해 공통변수(balance)에 대해 동시에 상태를 변경하게되고 문제가 생기게된다.

위의 문제를 해결하기 위해 공통변수를 한번에 하나의 쓰레드만 업데이트할 수 있게 해야한다. 이를 원자적(atomic)으로 실행된다고 칭한다. 또 공통변수가 업데이트되는 영역을 임계구역 이라고 한다.

임계구역 문제

임계구역을 영어로 하면 Critical-Section 이라고 하는데, 이 구간에서 치명적인 문제가 발생할 수 있음을 뜻한다. 두개 이상의 쓰레드가 있을 때 쓰레드들이 공통으로 사용하는 데이터(변수, 데이터베이스, 파일)가 있다. 그 공통데이터를 업데이트 하는 구간을 임계구역이라고 한다.

위의 은행계좌문제에서의 임계구역은 다음과 같다.

void deposit(int amount) {
  balance = balance + amount;
}
void withdraw(int amount) {
  balance = balance - amount;
}

임계구역에서 일어나는 문제들을 해결하려면 다음과 같은 세가지조건을 만족해야한다

Mutual exclusion (상호배타): 임계구역에는 오직 한 쓰레드만 진입해야 한다.
Progress (진행): 어떤 쓰레드가 먼저 진입할지 결정은 유한 시간 내에 일어나야 한다.
Bounded waiting (유한대기): 임계구역에 진입하기 위해 대기중인 모든 쓰레드는 유한 시간 내에 임계구역이 진입할 수 있어야한다.

프로세스/쓰레드 동기화

원하는 값이 나오도록 임계구역 문제를 해결해야 한다(위에 언급한 세가지 조건)
프로세스 실행 순서를 원하는대로 제어할 수 있어야한다.

세마포

세마포는 프로세스의 동기화 문제를 해결하기 위한 대표적인 소프트웨어 도구로써 사전적으로는 철도의 신호기, 군대의 수신호라는 뜻을 갖고 있다. 세마포는 mutual exclusion(상호 배타) 목적으로 사용된다.

내부 구조는 정수형 변수 + 두 개의 동작 (P, V) 로 구성되어 있다.

P : Proberen (test / 정수값을 검사한다) -> acquire()
V : Verhogen (increment / 정수값을 증가시킨다) -> release()

세마포의 구조를 코드를 통해 살펴보자

class Semaphore {
  int value; // number of permits
  Semaphore(int value) {
    ...
  }
  void acquire() {
    ...
  }
  void release() {
    ...
  }
}

void acquire() {
  value--;
  if (value < 0) {
    add this process/thread to list;
    block;
  }
}
void release() {
  value++;
  if (value <= 0) {
    remove a process P from list;
    wakeup P;
  }
}

acquire를 호출하면 정수값이 1만큼 감소되고 감소된 값이 0보다 작으면 acquire를 호출했던 프로세스나 쓰레드를 리스트(세마포 내부의 큐)에 넣는다. 그리곤 나오지 못하게 block(가로막혀 멈춰있다)한다.
release를 호출하면 정수값을 1만큼 증가시키고 증가한 값이 0이하면 갇혀있는 프로세스를 리스트에서 빼내어 꺠워준다(Ready Queue로 보낸다)
value : 권한의 개수

세마포어의 동작과정

세마포어.value = 1;

// Parent
세마포어.acquire();
balance = balance + amount; //임계구역
세마포어.release();

// Child
세마포어.acquire();
balance = balance - amount; //임계구역
세마포어.release();

세마포어.value = 1 로 설정한다.
Parent가 먼저 실행된다.
세마포어.acquire() 호출
value값(1)이 하나 감소되어 0이 된다.
acquire의 내부 조건에 만족하지 않으므로 조건문을 통과한다.
입계구역에 들어가 balance 값을 업데이트 한다.
이 때 (업데이트 중에) context-switch가 일어난다.
Child가 실행된다.
세마포어.acquire() 호출
value값(0)이 하나 감소되어 -1이 되고 acquire의 조건문을 만족한다.
조건문에 따라 Child는 세마포어 큐에 갇히게된다.
context-switch가 일어난다.
Parent가 다시 실행된다.
임계구역에서 이전에 진행중이던 코드를 다 돌고 빠져나온다.
세마포어.release() 호출
value값(-1)에 1을 더해 0이 되고 조건문을 만족한다.
세마포어 큐에 들어있는 Child 프로세스를 빼내고 Ready Queue로 보낸다.
Child가 임계구역에 들어가고 코드를 다 돌고 빠져나온다.
세마포어.release()를 호출
value값(0)이 1이 되고 조건문을 만족하지 않는다(큐는 비어있는 상태)

Ordering

원하는 값이 나오게 했으면 프로세스 실행 순서를 원하는대로 제어할 수 있어야한다.

Parent가 먼저 실행되도록 순서를 정하고 싶다면

세마포어.value = 0;

Parent	Child
	세마포어.acquire();
S1	S2
세마포어.release();

이렇게 하면 Child가 먼저 돌아도 acquire로 인해 block당하고 Parent가 먼저 실행되게 할 수 있다. Parent가 돌게되면 실행이 끝나고 release하여 value값을 1로 올려주어 Child가 문제없이 실행될 수 있게 한다.

Parent와 Child가 교대로 실행되도록 하려면

세마포어를 두개를 사용한다.

출금세마포어.value = 0;
입금세마포어.value = 0;

Parent	Child
	출금세마포어.acquire();
S1	S2
	입금세마포어.release();
출금세마포어.release();
입금세마포어.acquire();

Park Answer

Find answer in the record

[운영체제] CPU 스케줄링 >