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동안 불가능하게 하는 방법이 존재
  • 문제점은 하나의 코어에서만 유효하고 탐욕스럽게 사용할 가능성이 존재하며 구현이 거의 불가하기 때문에 현실적으로 거의 사용되지 않음