[운영체제] Process Synchronization

데이터의 접근

• 데이터를 읽어와 연산 후 결과를 다시 저장함
• 데이터를 읽기만 하면 문제 없음
• 근데 쓰면 누가 먼저 쓰냐가 중요해짐

Race Condition

• 스토리지의 값을 여러 프로세스가 읽어오고 수정 시 문제가 발생 가능
• 공유 자원을 여러 프로세스가 동시에 읽어오는 상황

Process Synchronization 문제

• 공유 데이터의 동시 접근 시 데이터 불일치 문제 발생 가능
• 일관성 유지를 위해서는 실행 순서를 정해줘야함
• 동기화가 되어야 한다.

Critical Section

• 공유 데이터를 접근하는 코드
• 하나의 프로세스가 critical section 에 있을 때 다른 프로세스는 들어갈 수 없어야 함

문제를 해결하기 위한 초기 접근

do {
    entry section
    critical section
    exit section
    reminder section
} while (1)

충족 조건

• Mutual Exclusion (상호 배제) : 프로세스가 critical section 부분을 수행중이면 다른 프로세스는 들어가면 안된다.
• Progress (진행) : 아무도 critical section 에 있지 않은 상태에서는 들어갈 수 있게 해줘야함
• Bounded Waiting (유한 대기) : 기다리는 시간이 유한해야 한다. → 지나치게 오래 기다려선 안된다.

알고리즘 1

• int turn = 0;
• turn의 숫자에 따라 몇번 프로세스인지 식별

do {
    while (turn != 0);
    critical section
    turn = 1;
    remainder section
} while (1);

• MX 만족
• Progress 불만족 - 무조건 상대방이 들어갔다 나와야 내 차례가 됨

알고리즘 2

• boolean flag[2] = false;
• true 인 경우 CS에 들어갈 준비가 되었다

do {
    flag[i] = true;
    while (flag[j]);
    CS
    flag[i] = false;
    rem
} while (1);

• No Progress
• 끊임없이 양보하는 상황 발생 가능

알고리즘 3 (피터슨 알고리즘)

do {
    flag[i] = true;
    turn = j; // 상대방에게 turn을 줌
    while (flag[j] && turn == j);
    CS
    flag[i] = false;
    rem
} while (1);

• turn, flag 둘다 사용
• 전부 만족
• 문제 : Busy Waiting (Spin lock) : 계속 CPU 와 메모리를 쓰면서 wait 하고 있음

하드웨어적 동기화 지원

• test and set : 하드웨어적으로 test & modify를 atomic 하게 동작하게 만드는 instruction
• a를 읽어와서 1로 바꿈 → 이를 한번에
• 이를 통해 소프트웨어적으로 복잡하게 해결하는 것이 아닌 하드웨어로 간단히 해결

boolean lock = false;

do {
    while (Test_and_set(lock));
    CS
    lock = false;
    rem
}

Semaphore

• 앞의 방식들을 추상화시킴
• Semaphore S
  • 정수 변수
  • 아래의 두 가지 atomic 연산에 의해서만 접근 가능
  • P(S) : while (S ≤ 0) do no-op; S—;
    • 만약 양수면, 감소하고 진입
    • 그렇지 않으면, 양수 될때까지 busy wait
  • V(S) : S++;

문제 해결

do {
    P(S)
    CS
    V(S)
    rem
} while(1);

• busy waiting은 효율적이지 못함 (spin lock)
• block & wake up 방식의 구현이 고안됨 (sleep lock)

Block / Wake Up 구현

• Semaphore를 다음과 같이 정의

typedef struct
{
        int value; // semaphore
        struct process* L; // process wait queue
} semaphore

• block : 커널은 block을 호출한 프로세스를 suspend시킴 → PCB를 semaphore wait queue에 넣음
• wakeup(P) : block된 프로세스 P를 깨움 → 이 프로세스의 PCB를 ready queue로 옮김
• P(S)

S.value--;
if (S.value < 0)
    add this process to S.L;
    block();
}

• V(S)

S.value++;
if (S.value <= 0)
    remove a process P from S.L;
    wakeup(P);

비교

• CS 길이가 긴 경우 Block/wakeup 이 좋음
• CS 길이가 매우 짧은 경우 busy-wait가 더 좋음 → BLock & wakeup 은 오버헤드가 있기 때문
• 일반적으로는 block & wakeup이 좋음

세마포어의 종류

• 카운팅 세마포어
  • 여러개 가능
• 이진 세마포어
  • 0 또는 1만 가질 수 있는 세마포어
  • 주로 mutual exclusion (lock, unlock)에 사용

데드락과 기아 현상

• 데드락 : 둘 이상의 프로세스가 서로의 자원을 기다리는 것
• 기아 현상 : 프로세스가 suspend 된 이후 해당 세마포어 큐에서 빠져나갈 수 없는 현상 (Indefinite Blocking)

고전 문제 (안함)

• Bounded Buffer 문제 (생산자-소비자 문제)
• Readers and Writers 문제
• Dining-Philosophers 문제

모니터 (Monitor)

• 세마포어의 문제점
  • 코딩 힘듦
  • 정확성 입증 어려움
  • 자발적 협력 필요
  • 한번 실수하면 모든 시스템 영향
• 하이레벨 동기화 구조
• 모니터 내부 프로시저(함수)로만 공유 데이터에 접근 가능
• 좋은점
  • P,V 등 락을 프로그래머가 걸 필요가 없음
• 모니터 내에서는 한번에 하나의 프로세스만이 활동 가능
• 조건 변수는 값을 가지지 않고 자신의 큐에 프로세스를 매달아서 sleep 시키거나 큐에서 프로세스를 깨우는 역할만 함
• 조건 변수 메소드
  • wait() : signal을 기다림
  • signal : 다른 프로세스(wait 하고 있음)를 깨워줌 - 하나만