[운영체제] 프로세스 동기화 Process Synchronization

Process Synchronization 프로세스 동기화 = Concurrency control 병행 제어

데이터의 접근

Race Condition

경쟁 상태 Race condition: 하나의 데이터에 둘 이상 접근하게 되면 원하는 결과가 나오지 않을 수도 있음

OS 에서 race condition은 언제 발생하는가?

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

1. Interrupt handler v.s kernel

커널모드 running 중 interrupt가 발생하여 인터럽트 처리 루틴이 수행

→ 양쪽 다 커널 코드이므로 kernel address space 공유

이럴 경우에는 인터럽트가 들어와도 바로 처리하지 않고, 하던 일이 끝나면 그제서야 인터럽트를 처리함.

2. Preempt a process running in kernel?

• 두 프로세스의 address space 간에는 data sharing이 없음
• 그러나 system call을 하는 동안에는 kernel address space의 data를 access하게 됨 (share)
• 이 작업 중간에 CPU를 preempt 해가면 race condition 발생 

• 해결책
  • 커널 모드에서 수행 중일때는 CPU를 preempt 하지 않음
  • 커널 모드에서 사용자 모드로 돌아갈 때 preempt

3. Multiprocessor

• 어떤 CPU가 마지막으로 count를 store했는가? → race condition
• multiprocessor의 경우 interrupt enable/disable로 해결되지 않음
  • A CPU를 막는다고 B CPU에서 접근하는 것을 막을 수 없음
• 방법
  • 방법 1: 한번에 하나의 CPU만이 커널에 들어갈 수 있게 하는 방법
  • 방법 2: 커널 내부에 있는 각 공유 데이터에 접근할 때마다 그 데이터에 대한 lock / unlock을 하는 방법

Process Synchronization 문제

• 공유 데이터(shared data)의 동시 접근(concurrent access)은 데이터의 불일치 문제(inconsistency)를 발생시킬 수 있다.
• 일관성(consistency) 유지를 위해서는 협력 프로세스(cooperating process) 간의 실행 순서(orderly execution)를 정해주는 메커니즘 필요
• Race condition
  • 여러 프로세스들이 동시에 공유 데이터를 접근하는 상황
  • 데이터의 최종 연산 결과는 마지막에 그 데이터를 다룬 프로세스에 따라 달라짐
• race condition을 막기 위해서는 병행 프로세스(concurrent process)는 동기화(synchronize)되어야 한다.

임계 구역 문제 The Critical-Section Problem

• n개의 프로세스가 공유 데이터를 동시에 사용하기를 원하는 경우
• 각 프로세스의 codee segment에는 공유 데이터를 접근하는 코드인 critical section이 존재
• Problem
  • 하나의 프로세스가 critical section에 있을 때 다른 모든 프로세스는 critical section에 들어갈 수 없어야 한다.

Initial Attempts to Solve Problem

• 두 개의 프로세스가 있다고 가정 P0, P1
• 프로세스들의 일반적인 구조

do {
    entry section // critical section에 들어갈 때 lock을 걸음
    critical section
    exit section // critical section의 작업이 끝난 후 lock을 풀음
    remainder section
} while (1);

• 프로세스들은 수행의 동기화(synchronize)를 위해 몇몇 변수를 공유할 수 있다. → synchronization variable

프로그램적 해결법의 충족 조건

Mutual Exclusion (상호 배제)

• 프로세스 Pi가 critical section 부분을 수행 중이면 다른 모든 프로세스들은 그들의 critical section에 들어가면 안 된다.

Progress (진행)

• 아무도 critical section에 있지 않은 상태에서 critical section에 들어가고자 하는 프로세스가 있으면 critical section에 들어가게 해주어야 한다.
• 예를 들어 코드를 잘못 짜게 되면, 임계구역이 비어 있을 때 두 프로세스가 동시에 들어가려 하면 두 프로세스 모두 들어가지 못하는 경우가 발생할 수 있다.

Bounded Waiting (유한 대기)

• 프로세스가 critical section에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 critical section에 들어가는 횟수에 한계가 있어야 한다.
• 즉 임계 구역에 들어가지 못하고 기다릴 때 starvation이 발생하지 않아야 한다. 예를 들어 3개의 프로세스가 있을 때 2개의 프로세스가 번갈아가면서 실행하면 나머지 한 프로세스가 고립된다.

가정

• 모든 프로세스들의 수행 속도는 0보다 크다.
• 프로세스들 간의 상대적인 수행 속도는 가정하지 않는다.

Algorithm 1

• Synchronization variable
  
  • int turn;
  • initially turn = 0;  → Pi can enter its critical section if (turn == i)
• Process P0

do {
    while (turn != 0) ;	// My turn?
    critical section
    turn = 1;			// Now it's your turn
    remainder section
} while (1);

Satisfies mutual exclusion, but not progress

즉, 과잉보호: 반드시 한번씩 교대로 들어가야 함 (swap-turn)

그가 turn 을 내 값으로 바꿔줘야만 내가 들어갈 수 있음

특정 프로세스가 더 빈번히 critical section을 들어가야 한다면? 그래도 다른 프로세스가 들어갔다가 나와야 내가 실행될 수 있다 ! 즉 Progress를 만족하지 못한다.

Algorithm 2

• Synchronization variables
  • boolean flag[2]   → 프로세스 별로 flag 존재
    • initially flag[모두] = false; → no one is in CS
  • Pi ready to enter its critical section. if (flag[i] == true)
• Process Pi

do {
    flag[i] = true;	// Pretend I am in
    while (flag[i]);	// is he also in? then wait
    critical section
    flag[i] = false;	// I am out now
    remainder section
} while (1);

• Satisfies mutual exclusion, but not progress requirement.
• 둘 다 2행 까지 수행한 후 끊임 없이 양보하는 상황 발생 가능
  • 즉 이 알고리즘도 두 프로세스가 동시에 들어가는 상황은 발생하지 않지만, 아무도 안들어가는 상황 발생 가능

Algorithm 3

•  알고리즘1(turn)과 2(flag)의 변수를 통합한 버전
• Process Pi

do {
    flag[i] = true;			// 먼저 자신의 깃발을 들어서 임계 구역에 들어가겠다는 의사표현을 함
    turn = j;				// turn을 상대방 turn으로 바꿈
    while (flag[j] && turn == j);	// 상대방이 깃발을 들고 있고, 현재가 상대방 차례이면 기다림
    critical section
    flag[i] = false;
    remainder section
} while (1);

• 3가지 조건을 모두 만족시킨다.
• Busy Waiting (= spin lock) !!! (계속 CPU와 memory를 쓰면서 while문을 돌면서 기다린다)

Synchronization Hardware

• 하드웨어적으로 Test & modify를 atomic하게 수행할 수 있도록 지원하는 경우 앞의 문제는 간단히 해결
  • instruction 하나를 가지고 어떤 데이터를 읽는 작업과 쓰는 작업을 동시에 진행 할 수 있는 하드웨어 적인 것이 지원이 된다면 쉽게 락을 걸고 풀 수 있다.

• Mutual Exclusion with Test & Set
  • Synchronization variable:
    • boolean lock = false
  • Process Pi

do {
    while (Test_and_Set(lock));
    critical section
    lock = false;
    remainder section
}

이 Test_and_Set에서 락이 걸려있는지 확인하고, 안걸려 있으면 걸고 임계구역으로 넘어감

Semaphores

• 앞의 방식들을 추상화시킴

추상 자료형
- Object와 Operation을 구성됨
- Semaphore도 일종의 추상 자료형

• Semaphore S
  • integer variable - 정수형
  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능 -> P와 S
    • P연산: 공유 자원을 획득
    • V연산: 공유 자원을 반납

• 왜 Semaphore 사용?
  • 간단하게 lock을 걸고 풀고 할 수 있음
  • 어떤 공유 자원을 획득하고 반납하고를 할 수 있음

Critical Section of n Process

• Synchronization variable
  • semaphore mutex
    • initially 1: 1개가 CS에 들어갈 수 있다.

do {
    P(mutex);		// 만약 true이면 dec-&-enter, 아니면 기다림
    critical section
    V(mutex);		// semaphore를 증가시킴
    remainder section
} while (1);

• busy-wait 는 효율적이지 못함 (=spin lock)
• Block & Wakeup 방식의 구현 (=sleep lock)

Block / Wakeup Implementation

• Semaphore를 다음과 같이 정의

typedef struct
{
    int value;		// semaphore
    struct process *L;	// semaphore 때문에 잠들어있는 프로세스들의 queue
} semaphore;

• block과 wakeup을 다음과 같이 가정
  • block: 커널은 block을 호출한 프로세스를 suspend 시킴. 이 프로세스의 PCB를 semaphore에 대한 wait queue에 넣음
  • wakeup(P): block된 프로세스 P를 wakeup 시킴. 이 프로세스의 PCB를 ready queue로 옮김

Semaphore 연산

• P(S)

S.value--;		// 들어갈 준비를 함
if (S.value < 0) {	// 만약 0보다 작으면 if문 실행 X
    add this process to S.L;
    block();
}

• V(S)

S.value++;
// 그냥 ++만 시키는 것이 아니라 잠들어있는 프로세스를 깨우는 것까지 포함함
// 왜냐면 위에서 block 되었었기 때문에
if (S.value <= 0) {
    remove a process P from S.L;
    wakeup(P);
}

Busy-wait? v.s. Block/wakeup

• Block/wakeup overhead v.s. Critical section 길이
  • Critical section의 길이가 긴 경우 Block/Wakeup이 적당
  • Critical section의 길이가 매우 짧은 경우 Block/Wakeup의 오버헤드가 busy-wait 오버헤드보다 더 커질 수 있음
    • block/wakeup같은 경우에는 상태를 block()으로 바꿔주고 하는 등의 오버헤드가 있기 때문에
  • 일반적으로는 Block/wakeup방식이 더 좋음

Semaphore 타입 2개

• Counting semaphore
  • 도메인이 0 이상인 임의의 정수값
  • 주로 resource counting에 사용
• Binary semaphore (= mutex)
  • 0 또는 1 값만 가질 수 있는 semaphore
  • 주로 mutuial exclusion (lock/unlock)에 사용

Deadlock and Starvation

semaphore를 사용할 때는 원치하는 문제가 생길 수 있다. 그것이 바로 deadlock과 starvation이다.

• Deadlock
  • 둘 이상의 프로세스가 서로 상대방에 의해 충족될 수 있는 event를 무한히 기다리는 현상
• S와 Q가 1로 초기화된 semaphore라 하자

• Starvation
  • indefinite blocking. 프로세스가 suspend된 이유에 해당하는 세마포어 큐에서 빠져나갈 수 없는 현상