Process Synchronization (1)

Synchronization (동기화)

• 여러 프로세스가 협업할 수 있도록 하는 수단
  • 공유되는 자원들을 적절하게 조정함으로써 협동할 수 있도록 한다       e.g. variables, files
• 정확성을 위해서 필요
  • 각각의 프로세스들은 얽혀 있지만 독립적으로 작동 (속도 예측 불가)
  • CPU 스케줄링은 OS 관할이라 프로그래머가 어떻게 동작할지 예상하지 않는다
  • 여러 프로세스들이 실행되는 환경에서 의도대로 동작시키기 위해
  • 프로세스뿐만 아니라 스레드도 해당

Synchronization problem

동기화를 시키지 않으면 많은 문제가 발생하지만 일단 대표적인 예를 들어보려 한다.

1. 현금 인출

두 개의 프로세스가 현금을 인출하는 상황이다.  balance가 100만 원이고 account가 10만 원이라 가정해보자. 100만 원에서 10만 원을 인출한 순간에 갑자기 context switch가 일어나서 다른 프로세스가 실행되었다. 프로세스 B는 이미 10만 원이 인출되었음에도 제대로 저장되지 않았으므로 원금을 100만 원으로 인식하고 다시 10만 원을 인출하여 잔액은 90만 원이 된다. 2개의 프로세스가 10만 원씩 인출하여 총 20만 원이 인출되었음에도 잔액은 90만 원이 되는 것이다.

 

2. Producer – Consumer

 

두 프로세스가 실행된다고 생각해보자. 여기서 공유되는 자원은 count이다. producer에서 증가시키고 consumer에서 감소시키니 count의 값은 결국 그대로일 것이라고 생각할 수 있다. 하지만 이것도 동기화를 시키지 않으면 어떤 값을 가지게 될 지 아무도 모른다.

 

 

위의 과정은 극히 많은 오답의 과정 중 하나에 불과하다. register1에서 5를 입력하여 1 증가시키면 6인데 다른 프로세스에서 register1에 6을 저장하기 전에 실행되면 register2는 5를 입력하여 1 감소시키니 4가 되는 것이다. 어느 순간에 interrupt가 일어날지 예측이 불가해서 벌어지는 문제이다.

 

3. 이유

• race condition
  • 프로세스들끼리 경쟁 관계라 누가 스케줄링될 지 모르는 상태
  • 결과가 타이밍에 따라 매번 다르기 때문에 예측할 수 없다
  • 여러 개의 프로세스가 공유 자원에 접근할 때 발생한다

 

Critical Sections (임계 영역)

• 공유되는 자원들이 처리되는 영역
• 동기화를 위해서는 critical section을 상호 배제시켜야 한다
  • critical section에서는 한 순간에 하나의 프로세스만 들어갈 수 있어야 한다
  • 다른 프로세스들은 모두 기다린다
  • critical section에 있던 프로세스가 나오면 다른 프로세스가 즉시 들어간다
  • 위의 조건이 아니라면 race condition이 유발된다
• 요구조건
  • Mutual Exclusion (상호 배제): critical section에는 오로지 하나의 프로세스만
  • Progress: critical section이 비어 있으면 들어가고 싶은 프로세스가 바로 진입 가능
  • Bounded waiting: 만약 어느 프로세스가 critical section에 들어가기를 기다린다면, 언젠가는 들어가야만 한다 (starvation 방지 위해)
  • Performance: critical section을 오갈 때의 overhead가 비교적 작아야 한다
• Mechanism 종류
  • Locks
    • 제일 일반적이고 단순하다   e.g. hardware lock, OS lock
  • Semaphores
    • lock 포함하지만 lock보다 풍성한 개념
    • OS 커널의 지원을 받아야 한다
  • Monitors
    • 프로그래밍 언어가 지원하는 기법으로 묵시적으로 작동한다   e.g. java’s synchronized
  • Messages
    • communication과 동기화의 간단한 모델로 데이터를 채널을 통해 주고받는다
    • 자연적으로 코드들의 순서가 정해진다 (send -> recv)

 

Locks

• lock은 하나의 object (변수 + operation)으로 2개의 operation이 존재한다
  • acquire(): lock이 free가 될 때까지 기다렸다가 free 하면 잡는다 (blocking)
  • release(): lock을 반납한다

int withdraw (int account, amount) {

    acquire(lock);

    balance = get_balance(account);

    balance = balance - amount;

    put_balance(account, balance);

    release(lock);

    return balance;
}

 

• 특징
  • Lock은 처음에 free 한 상태이다
  • critical section에 들어가기 전에는 acquire()을 호출하고 떠날 때는 release()를 호출한다
  • acquire()와 release() 사이에서 critical section에 있는 프로세스는 lock을 소유하고 있어야 한다
  • 어느 한 프로세스가 lock을 소유하고 있는 상태라면 다른 프로세스들은 acquire() 시 lock을 소유하고 있는 프로세스가 release 하기 전까지 기다려야 한다
  • 하나의 프로세스만이 한 순간에 lock을 소유할 수 있다
• Lock은 hardware가 제공하는 spinlock과 OS가 제공하는 mutex가 있다
  • spinlock: 낭비가 심하기 때문에 짧은 작업 처리 시에는 유용하지만 그렇지 않은 경우에는 되도록 사용하지 않는 것이 바람직하다
• Lock을 효율적으로 구현하기 위해 시도한 방법
  • Software-only algorithms: user 수준에서 동작하며 OS의 도움을 받지 않기 때문에 일반 명령어들로 만들어서 사용하지만 성능이 좋지 않다
    • Dekker’s algorithm (1962)
    • Peterson’s algorithm (1981)
    • Lamport’s bakery algorithm for more than two processes (1974)
  • Hardware atomic instructions
    • test-and-set, compare-and-swap, etc.
    • Disable/reenable interrupts
• Disabling Interrupts
  • lock을 구현하는 방법 중 하나로 interrupt를 critical section동안 불가능하게 하는 방법이 존재한다.
  • 문제점은 하나의 코어에서만 유효하고 탐욕스럽게 사용할 가능성이 존재하며 구현이 거의 불가하기 때문에 현실적으로 거의 사용되지 않는다