오퍼레이팅 시스템 [10] - Synchronization

in STUDY LOG / OS

‘Race condition을 예방하는 동기화기법’

Synchronization

  • Multi-Thread 환경에서의 Thread들을 조정하는것.
    • 공유자원에 접근 등
  • 동기화가 제대로 이루어지지 않았을경우 Race Condition이라고 불리는 상태가 발생해 부정확한 결과가 나온다.

Race Condition

Race condition의 발생원리

그림과 같이 Person A Person B 가 같은 계좌에 1원씩 입금하는 경우,

  1. 현재 잔액을 불러온다.
  2. 1원을 더한다.
  3. 더한 금액을 저장한다.

의 과정이 Atomic하게 한번에 이루어지지 않고, Person A, Person B가 동시에 잔액을 불러와 옳은 잔액인 19가 아닌, 18이 은행의 DB에 저장되었다.

  • Uniprocessor의 경우에는 Scheduler에 따라,

  • Multiprocessor의 경우에는 Excution순서에 따라 Race Condition이 발생할 수 있다.

  • 발생 원인
    • 공유 자원에 대한 Atomic한 접근이 이루어지기 힘들기 때문에.
    • Single Operator도 컴파일 과정에서 다수의 명령어로 나누어질 수 있다. → 더욱 Atomic 어려워짐
counter++ (Programming lv)

이랬던 단순한 코드가

mov 0x8049a1c, %eax  
add $0x1, %eax
mov &eax, 0x8049a1c
(Instruction lv)

와 같이 3개의 Instruction으로 나뉜다!

Critical Section

  • Critical Resource (임계자원)
    여러 Thread에게 공유되는 자원일때, 한번에 하나의 Thread만 접근가능한 자원이다.
  • Critical Section(임계영역)
    Critical Region이라고도 불리며, 임계자원에 접근하는 코드영역을 말한다.

앞에서 다룬 counter++의 경우에는

변수 counter = Critical Resource,

코드 counter++ (3개의 Instruction) = Critical Section 이다.

상호배제

  • Mutual Exclusion(상호배제)
    한번에 하나의 Thread만 Critical Section을 실행할 수 있도록 보장하는 방법.

즉, Synchronization은 Race Condition을 예방하기 위해서 Critical Section에 대한 Mutual Exclusion을 제공하는 매커니즘이다!

  • Critical Section에서의 문제해결 3단계
    1. Mutual Exclusion (상호배제)
      앞서 말한것과 같이 한번에 하나의 Thread만 Critical Section에 접근 가능하게 한다.
    2. Progress (진행)
      그저 상호배제만으로는 모자라다. 하나의 작업이 Critical Section을 빠져나가 종료되면 다음 Thread가 실행할 수 있게 해주는 단계
    3. Bounded Wating (한정대기)
      언젠가는 기다리는 Thread들은 Critical Section에 들어갈 수 있어야 한다. 대기시간을 한정시켜 Starvation문제를 예방한다.

상호배제 구현

① Disabling Interrupt

: Uniprocessor시스템의 경우, 상호배제를 보장하기 위해 프로세스가 Interrupt당해 Scheduling되는 것 자체를 차단시킨다.

  • 문제점 : 사용범위가 Uniprocessor에 국한되고, 아예 Interrupt를 꺼버리는것은 문제가 될 수 있다.(악용가능)

② Spin Locks

: CAS(compare and swap)을 이용하여 상호배제를 보장한다.

  • CAS : HW를 통해 Compare, Swap을 하나의 Instruction으로 구현한것.
    // file: "The-CAS-instruction"
// word값이 testval과 같을떄 newval로 바꾸고, 이전값 return
int compare_and_swap(int *word, int testval, int newval){
  int oldval;
  oldval = *word;
  if(oldval == testval) *word = newval;
  return oldval;
}
  • HW(CAS)의 도움으로 구현한 상호배제
    // file: "mutual_exclusion_using_CAS.cpp"
int bolt; //flag역할(1일때 lock, 0일때 unlock)
void P(int i){
  while(true){
while(compare_and_swap(bolt, 0, 1) == 1)//bolt == 1이라 swap되지 않았을때 대기하는 반복문
{
  //Do noting
}
//critical section
bolt = 0; //다른 CAS가 접근가능하도록 unlock
  }
}
void main(){
  bolt = 0;
  parbegin (P(1),P(2),P(3)...);//메인 프로그램을 중단하고 P()함수를 실행
}
  • 문제점
    1. 다른 Thread는 계속해서 bolt == 0 을 기다리며 Busy wating해야한다. = 의미없는 Instruction반복
    2. 공정하지 않다 : 동시에 0이 되었다면 우선순위를 임의로 결정할 수 밖에 없다. => starvation발생 가능

③ Semaphore

: 더욱 일반화된 동기화 방법이다.

  • Semaphore S : 정수를 하나 갖고있는 객체

  • semWait(), semSignal() : S를 수정하는 기본 operation (wait : 감소, signal : 증가)

  • 앞서다룬 CAS를 사용하는 방식과 달리 Busy waiting없이 상호배제를 구현할 수 있다.

  • 종류
    1. Binary Semaphore
    Semaphore 객체의 정수값이 0과 1로만 바뀔 수 있으므로 Lock, Unlock으로 사용된다.
// file: "binary semaphore"
struct binary_semaphore{
  enum {zero, one} value;
  queueType queue;
};
void semWait(binary_semaphore s){
  if (s.value == one)
    s.value = zero; //value가 1이면 lock하고 그대로 critical section진행
  else {
    //value가 0이면, 이 프로세스를 block하고, s.queue로 넣는다.
  }
}
void semSignal(binary_semaphore s){
  if (s.queue is empty())//queue에 기다리는 프로세스가 없으면
    s.value = one; //unlock한다.
  else {
    //대기중인 프로세스가 있으면 다음순서로 scheduling
  }
}

2. Counting Semaphore (범용 Semaphore) :
객체의 정수값이 정해진 범위가 없으며, 설정한대로 여러 조건을 추가할 수 있다.ex) 정수가 100보다 클때 등

// file: "counting semaphore"
struct semaphore{
  int count; //기다리는 프로세스의 수(1이면 queue에 아무프로세스도 없는 상태)
  queueType queue;
};
void semwait(semaphore s){
  s.count--; 
  //count변수가 1일때는 critical process진행
  if(s.count < 0){
    //1이 아닐때는 이 프로세스를 block하고 queue로 보냄
  }
}
void semSignal(semaphore s){
  s.count++;
  if(s.count <= 0){
    //count가 1이 아닐때, 기다리는 프로세스가 있으므로 다음순서로 Scheduling
  }
}
//프로세스를 실행(혹은 ready queue로)하며 -, 완료되면 +

counting semaphore를 통한 공유자원보호

Deadlock

  • Deadlock(교착상태) : Wait queue가 있는 Semaphore를 사용할때 발생할 수 있는 문제.
  • 현재 작업이 끝나기 위해서 필요한 자원을 여러 프로세스가 서로 갖고있는 경우
      (P0) : wait(S); - wait(Q); - ... - signal(S); signal(Q);
  (P1) : wait(Q); - wait(S); - ... - signal(Q); signal(S);

P0은 wait(Q)를 통해 P1에서 Q를 사용중이라 Block된다.

P1은 wait(S)를 통해 P0에서 S를 사용중이라 Block된다.

→ 교착상태

④ MUTEX

  • LOCK, UNLOCK을 지원하여 공유자원에 대한 접근을 막아 Thread가 단독으로 사용 할 수 있도록 하는 방법
//file: "Mutex example"
//pthread API는 Mutex기능을 제공한다.
#include <pthread.h>
pthread_mutex_t m; //Mutex 객체 생성

int pthread_mutex_init(&m, null);
int pthread_mutex_destroy(&m);

int pthread_mutex_lock(&m);
//사이에 critical section
int pthread_mutex_unlock(&m);

추가 참고문헌

CloudxLab blog “Race Condition and Deadlock”