동기화 원칙(임계영역, 뮤텍스, 세마포어)

동기화 원칙

• backgroud
• 공유된 데이터에 대한 동시 접근으로 인해 데이터 불일치 발생
• 일관된 데이터 관리를 위해서 협업 프로세스의 순서있는 실행을 보장하는 메커니즘이 필요하다
• critical section 문제
• 순수한 sw 솔루션
• hw에서 도움을 받을 수 있다.
• busy waiting 없는 동기화
• semaphore(세마포어)
• mutex lock
• condition variables

한정 버퍼(bounded buffer)
 = 생산자-소비자 문제(producer-consumer problem)

만약에 프로세스 2개가 shared data의 변수들을 공유한다고 했을때

위의 코드 중 atomic operation은 conter++; 과 conter--; 이다.

※ atomic operation : interruption 없이 전체적으로 완료되는 작업

atomic operation 부분을 실제 instruction sequence로 보면 아래 코드와 같은 문제가 있다.

// counter++
register1 = counter;
register1 = register1 + 1;
counter = register1;
 
// counter--
register2 = counter;
register2 = register2 - 1;
counter = register2;
 
// counter = 1;이라고 가정
// counter++;
// counter--;
// 우리가 원하는 모습(정상)
register1 = counter;
register1 = register1 + 1;
counter = register1;    // counter = 2
register2 = counter;
register2 = register2 - 1;
counter = register2;    // counter = 1
 
 
// 병렬처리할때 흔한 문제(에러)
register1 = counter;
register1 = register1 + 1;  // register1 = 2
register2 = counter;
register2 = register2 - 1;  // register2 = 0
counter = register1;    
counter = register2;    // counter = 0

이렇게 여러 개의 프로세스를 어떻게 동기화할 것인가에 대한 문제를 "한정 버퍼, 생산자-소비자 문제"라고 한다.

경쟁 상태(Race condition)

경쟁 상태 : 여러개의 프로세스가 공유된 데이터를 동시에 접근/처리하는 상황

공유 데이터의 최종 값과 참여 프로세스에 대한 영향은 프로세스 실행 순서에 달려있다.(비 결정론)

경쟁 상태의 예방을 위해서는 동시처리 프로세스는 동기화가 되야한다.

임계 영역 문제(Critical-section problem)

문제 상태

• n개의 프로세스 모두 공유된 데이터를 사용하기 위해서 경쟁해야한다.
• 각각의 프로세스는 임계 영역이라 부르는 code seqment를 가지고 있고 공유된 데이터에 접근 가능하다.

해결 조건

• 상호 배제(Mutual exclusion) : 하나의 프로세스가 임계 구역에 들어가 있다면 다른 프로세스는 들어갈 수 없어야 한다. 약자로 뮤텍스(mutex)로 사용한다.
• 진행(Progress) : 임계 구역에 들어간 프로세스가 없는 상태에서, 들어가려고 하는 프로세스가 여러 개 있다면 어느 것이 들어갈지를 적절히 결정해주어야 한다.
• 한정 대기(Bounded waiting) : 다른 프로세스의 기아(Starvation)를 방지하기 위해, 한 번 임계 구역에 들어간 프로세스는 다음 번 임계 구역에 들어갈 때 제한을 두어야 한다.

일반적인 프로세스 구조(임계 영역에 대한 프로세스)

do {
    wait(mutex);   //입장 구역
    임계 구역
    signal(mutex); //퇴장 구역
    나머지 구역
}

가정 : 명령어는 atomic하고 명령어의 순서를 바꾸지 않는다.

임계 영역 문제 해결을 위한 알고리즘

i와 j 2개의 프로세스가 있다고 가정함

알고리즘1

// shared variables
int turn = 0;
 
// i process
do {
    while (turn != i);
    // critical section
    turn = j;
    // remainder section
} while (1);

상호 배제는 만족하지만 progress가 아니다.

알고리즘2

// shared variables
boolean flag[2];
flag[0] = flag[1] = false;
 
// i process
do {
    flag[i] = true;
    while (flag[j]);
    // critical section
    flag[i] = false;
    // remainder section
} while (1);

상호 배제는 만족하지만 progress 요구사항을 충족하지 못함(누가 들어갈지 정해주지 못함)

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

// shared variables
int turn = 0;
boolean flag[2];
flag[0] = flag[1] = false;
 
// i process
do {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j);
    // critical section
    flag[i] = false;
    // remainder section
} while (1);

모든 조건을 만족하는 알고리즘

뮤텍스 락(mutex lock)

acquire() {
    while (!available); // busy wait
    abilable = false;
}
 
release() {
    abilable = true;    
}
 
do {
    acquire lock
    critical section
    release lock
    remainder section
} while(true);

busy waiting으로 임계 영역 문제 해결하기

busy waiting : 어떠한 특정 공유자원에 대하여 두 개 이상의 프로세스나 스레드가 그 이용 권한을 획득하고자 하는 동기화 상황에서 그 권한 획득을 위한 과정에서 일어나는 현상

대표적인 방법 : 뮤텍스, 세마포어

• 장점 : 공유 자원에 대한 권한 획득이 아주 빠른 시간 내에 이루어질 수 있다는 확신이 있는 상황 또는 뮤텍스나 세마포어 등의 동기화 객체등을 이용하기에는 그 오버헤드가 큰 상황에서 간단히 쓸 수 있다

• busy waiting 기반의 동기화 문제점
• cpu time 낭비
• 임계영역에서 프로세스가 cpu로 전환되는 경우
• 다른 프로세스는 cpu를 낭비한다.
• 엄격한 우선 순위 스케쥴링에서는 deadlock이 발생할 수 있다.

• 해결책
• 가능한 busy wait를 피한다.
• 피할 수 없으면 반드시 임계 영역에서 context switch를 방지해야된다.(커널에서 인터럽트를 비활성화)

세마포어

busy waiting을 요구하지 않는 동기화 방식

// or P(S)
wait(S) {
    wait until S>0;
    S--;
}
 
// or V(S)
signal(S) {
    S++;
}
 
// shared data
semaphore mutex = 1;
 
// process 
do {
    wait(mutex);
    // critical section
    signal(mutex);
    // remainder section
} while (true);

세마포어 vs 뮤텍스

뮤텍스 = binary 세마포어

2개의 상태인 locked/unlocked만 가진 세마포어가 뮤텍스

세마포어는 뮤텍스가 될 수 있지만

뮤텍스는 세마포어가 될 수 없다.

모니터

한번에 하나의 프로세스만 모니터에서 활동하도록 보장해주는 방식. 즉, 모니터에 들어간 프로세스만 공유된 데이터(임계 영역)에 접근할 수 있다.

세마포어와 다른 점은 condition variables를 counting하지 않는다. 즉, 세마포어는 동기화 함수의 제약 조건을 고려해야하지만 모니터는 프로시져를 호출하여 간단하게 해결한다.