Chapter 6 - 7 (Synchronization Tools and Examples)

여러 process들은 동시에 실행될 경우 서로의 공유 데이터에 접근할 수 있으므로, 

동기화가 꼭 필요합니다.

 

Possibility of Interleaving

process 끼리 동기화를 제대로 안해주면 interleaving 현상이 발생합니다.

예를 들어 counter 변수를 늘리는 producer와 줄이는 consumer process가 있다고 가정하면

counter ++ 와 counter -- 는 위에 보듯이 다음과 같은 기계어로 실행됩니다.

이를 동시에 실행하면 interleaving 이 발생할 수 있습니다.

interleaving 현상은 producer와 consumer가 누가 먼저 실행되는가에 달렸습니다.

 

예를 들어 counter = 5라고 가정

먼저 producer에서 counter을 +1 해줬으므로 counter = 6이 되었지만, 

동기화가 일어나지 않아 consumer가 counter를 볼때에는 처음에 5입니다.

여기서 consumer는 counter을 -1을 해주므로 4가 됩니다.

따라서 producer는 counter를 6으로 보고, consumer는 counter를 4로 봅니다.

원래 제대로 동기화가 일어나면 counter은 5가 되어야 합니다.

 

Race Condition

위와 같은 상황을 race 라고 합니다. 즉, 동시에 실행되는 process들이 같은 공유 데이터에

접근하는 경우입니다.

이와 같은 경우, thread의 실행 순서를 잘 조절하지 않으면, 위와 같은 문제들이 발생합니다.

특히, 이런 경우 디버깅시에 문제가 전혀 보이지 않기 때문에 개발자 입장에서 잘 고려해야 합니다.

결국, 우리는 synchronization(동기화)를 잘해야 합니다.

위에서 봤던 

counter ++;
counter --;

은 atomically 해야 합니다.

atomic은 interrupt없이 완전히 작업을 끝 마치는 것을 의미합니다.

 

Critical Section (CS)

예를 들어 n개의 process가 있다면 각 process는 공유 데이터에 접근하는

critical section 이라고 부르는 code가 있습니다.

그곳에서 다른 process들과 공유하는 데이터를 변경하는 등의 작업을 합니다.

중요한점은 어느 한 process가 자신의 critical section에서 작업을 하게 되면 다른 process들은 

그들의 critical section에 절대 들어갈 수 없습니다.

 

CS구현에 대한 접근 방식이 있습니다.

1. Software-based 접근

2. Synchronization instruction

3. Semaphore

4. High-leveel synchronization (ex monitor)

 

Properties of a CS Implementation

CS 문제에 대한 해결책은 다음과 같은 3가지 요구조건을 충족 시켜야 합니다.

Mutual Exclusion

process P가 자신의 critical section에서 실행된다면, 다른 process들은 그들 자신의 

critical section에 실행될 수 없습니다.

즉, 이미 한 process가 critical section에서 작업중일 때 , 다른 process는 critical section에 

진입해서는 안됩니다.

 

Progress

자신의 critical section에서 실행되는 process가 없는 상황에서 그들 자신의 critical section으로

진입하려는 process들이 있다면, 다음에 누가 해당 critical section으로 진입할 수 있는지를 결정하는 데

참여할 수 있으며, 이 선택은 무한으로 연기될 수 있습니다.

즉, critical section에서 작업중인 process가 없다면, 다른 process가 critical section에 진입할 수 

있어야 합니다.

 

Bounded Waiting

process가 자신의 critical section에 진입하려는 요청을 한 후 부터 그 요청이 허용될 때가지

다른 process들이 그들 자신의 critical section에 진입하도록 허용되는 횟수에 제한이 있어야 합니다.

여기서 각 process는 0이 아닌 속도로 실행한다.

또한 n개의 process들의 상대적인 속도는 고려하지 않습니다.

즉, critical section에 진입하려는 process가 무한하게 대기해서는 안됩니다.

모든 process가 CS에 들어가기 위한 기회를 가질 수 있게 하기 위한 것입니다.

 

Software-based Approach

오직 2개의 process P0과 P1이 있다고 하자.

각 process는 자신의 critical section으로 진입하기 위해 허가를 요청해야 하는데, 이러한 요청을

구현하는 코드 부분을 entry section 이라고 하며, critical section 뒤에는 exit section이

있을 수 있습니다.

나머지 코드들은 remainder section 이라고 합니다.

process들은 동기화 하기 위해 몇몇 공통 변수들을 공유할 수 있습니다.

 

(Algorithm 1)

int turn = 0 입니다. 만약 turn이  i 가 되면 Pi는 자신의 critical section에 들어갈 수 있습니다.

위의 알고리즘은 mutual exclusion은 만족하지만, progress는 만족하지 못합니다.

만약 turn이 0이고 P1은 critical section에 들어갈 준비가 됬다면, P1은 들어가지 못합니다.

비록 P0이 remainder section에 있음에도 불구하고

turn이 0이기 때문입니다.

 

(Algorithm 2)

bool flag[2]; 처음에 flag[0] = flag[1] = flase 입니다.

만약 flag[i]가 true 이면, Pi는 ciritical section에 들어갈 준비가 됩니다.

위에 알고리즘은 mutual exclusion은 만족하지만, progress는 만족하지 못합니다.

P0이 flag[0] = true 로 셋팅 하고, P1이 flag[1] = true로 셋팅하면???

 

(Peterson's Algorithm)

process i, j 가 있다고 가정합니다.

flag 변수는 critical section에서 process가 작업중인지 저장합니다.

turn 변수는 critical section에 진입하고자하는 process를 가리키는 변수입니다.

flag[i] = true;

먼저 Pi 가 critical section에 들어가고 싶다고 신호를 보내줍니다.

turn = j;

Pj 차례로 돌려줍니다.

즉, Pi가 내가 critical section으로 들어가기 전에 미리 critical section에 들어가고 싶은 

다른 process가 있는지 확인하는 것입니다.

Pj 입장에서는 flag[j] = true; turn = i; 까지 진행한 상태에서 Pi가 flag[i] = true; turn = j; 를 

실행한 상태입니다.

그럼 이제 Pj에게 turn이 넘겨줬으므로 Pj는 while문으로 들어갑니다.

while (flag[j] && turn == j); //busy waits

지금 현재 Pj의 thread에서 작업을 수행하는 중입니다. 

따라서 무한 loop 처럼 보일 수 있습니다.

그럼 어떻게 이 무한 loop를 빠져나오냐면 Pj가 critical section을 다 끝낸후 flag[j] = false; 를 하는 순간

loop를 빠져나오게 됩니다.

critical section

flag[i] = false;

remainter section

이제 critical section에 들어가게 되고 작업이 다 끝나면 flag[i] = false 로 바꿔줘 다른 process가 

사용하게 끔 해줍니다.

 

Synchronization Instruction

사실 위에서 설명한 software based approach는 현대에는 잘 사용하지 않습니다.

여기서는 Hardware에서 부터 Software 기반 API를 사용해 critical section 문제를 

해결하는 방법을 알아봅니다.

먼저 critical section을 해결하는 방법으로는 모두 lock 방법을 기반을 둡니다.

 

single processor 환경에서는 간단히 interrupt를 비활성화 시킬 수 있어 critical section에 

들어가기 전에 interrupt가 발생할 수 있는 가능성을 완전히 배재할 수 있습니다.

 

하지만 현대의 multiprocessor 환경에서는 그러지 못합니다.

따라서 많은 현대 컴퓨터들은 interrupt 되지 않는 하나의 단위로서, 특별한 Hardware 명령어를

제공합니다. 해당 명령어는 atomic 합니다. 즉, 중간에 interrupt를 할 수 없습니다.

예를 들어 TestAndSet() 과 Swap() 이 있습니다.

TestAndSet()은 메모리 word를 테스트하고 값을 설정합니다.

Swap()은 두개의 메모리 word를 swap 해 내용을 바꿉니다.

bool TestAndSet(bool *target){
    bool rv = *target;
    *target = true;
    return rv;
}
bool lock = false;
int main(){

      do{
	   while(TestAndSet(&lock);
        	critical section
           lock = false;
        	remainder section
       }while(true);
       
     return 0;
}

test and set의 원형입니다. 

lock은 전역변수로 모든 thread가 접근해 값을 변경할 수 있습니다.

만약 현재 다른 process가 critical section을 사용하고 있으면 lock은 true이기 때문에 

while(TestAndSet(&lock))은 무한 루프를 돌며 자기 차례를 기다리고 있습니다.

 

void Swap(bool *a, bool *b){
    bool temp = *a;
    *a = *b;
    *b = temp;
}
bool lock = false;
int main(){
	do{
        key = true;
        while(key == true) Swap(&lock, &key);
        	critical section
        lock = false;
        	remainder section
        }while(true)
}

마찬가지로 위의 test and set과 같은 논리 입니다.

여기서는 변수 key를 추가해 lock의 value와 swap 합니다.

결국 다른 process가 critical section을 사용하고 있으면 key는 계속 true이므로

무한루프를 계속 돌게 됩니다.

 

하지만 위의 두 코드들은 critical section의 문제점 해결 원칙중 

3번째인 bound waiting을 만족하지 못합니다.

이제 test and set을 사용하면서 3번째 조건도 만족시키는 코드를 살펴보겠습니다.

do{
    waiting[i] = true; //i번째 process가 현재 critical section에 들어가고 싶음
    key = true; // lock과 같은 역할을 하는 변수 key가 true이면 계속 무한 루프
    
    while(waiting[i] && key) key = TestAndSet(&lock);
    
    waiting[i] = false;
    //while 무한 루프를 빠져나왔으니, 이제 대기라인에서 빼주는 것입니다.
    
    critical section
    
    j = (i + 1) % n;
    while((j != i) && !waiting[j]) j = (j + 1) % n;
    //3번의 bounded waiting을 위해 위 코드 추가
    //현재 i번째 process가 critical section을 사용하였으므로, 그 다음에 사용할 process 찾기
    //i번째 부터 +1 씩하면서 j번째 process가 critical section을 사용할지 말지 확인하는 작업
    //만약 j가 사용하기 싫다면 j+1을 해 쓰고 싶은 다음 process 찾음, j가 나올때까지 진행
    
    if(j == i) lock = false;
    //j가 i가 됬다는 것은 모든 process를 한바퀴 다 돌았다는 의미
    //넘겨줄 process가 없으니 그냥 lock을 false로 해 풀어줍니다.
    else waiting[j] = false;
    //j번째 process에게 넘겨줄 것이므로 waiting[j]를 false로 바꿈
    //현재 j번째 process는 5번째 줄에서 무한 루프 돌고 있기 때문
    remainder section
}while(true);

코드에 자세한 설명을 해놓았습니다.

 

Semaphores

세마 포어는 여러개의 process나 thread가 critical section에 진입할 수 있는 lockng 매커니즘 입니다.

semaphore는 카운터를 이용해 동시에 resource에 접근할 수 있는 process를 제한합니다.

물론 한 process가 값을 변경할 때 다른 process가 동시에 값을 변경하지는 못합니다.

semaphore는 P와 V라는 명령으로 접근할 수 있습니다.

semaphore S는 integer 변수 처럼 표현됩니다. 물론 (atomic한)P와 V에 의해서만 접근가능합니다.

wait(또는 P라고 불림) 는 semaphore을 -1해주고

signal(또는 V라고 불림)는 semaphore을 +1 해줍니다.

 

semaphore에는 2가지 형태가 있습니다.

Counting semaphore : semaphore가 -1, 0, 1, 2, 3,.... 제한 없이 변할 수 있습니다.

Binary semephore : semaphore가 0 또는 1로 제한됩니다. mutex lock이라고도 불립니다.

 

일반적으로 busy waiting(=spinlock)은 다른 prcess에 생산적으로 사용할 수 있는 CPU cycle을 낭비합니다.

따라서 정말 어쩔 수 없는 경우를 제외하고는 사용하지 말아야 합니다.

Spinlock은 lock을 기다리는 동안 무한루프 처럼 계속 돌아가는 것입니다.

이러한 spinlock은 context switch가 필요없다는 장점이 있습니다. 

또한 lock이 짧은 시간 동안 묶여 있다고 예상되면 spinlock이 유용할 수 있습니다.

multiprocessor 시스템에 자주 사용됩니다.

 

semaphore의 전체적인 구조는 들어갈 때, wait, 나갈 때는 signal입니다.

semaphore값이 0이 되면, 모든 자원이 사용 중임을 나타냅니다.

이후 자원을 사용하려는 process는 semaphore 값이 0보다 커질 떄 까지 blocking 됩니다.

당연히 처음에 mutex는 1로 설정합니다. mutex 단순히 그냥 변수 이름입니다. 

 

Deadlock and Starvation

Deadlock

위의 두개의 process들은 deadlock에 빠져있다.

P0와 P1이 모두 wait() 를 실행하게 되면 P0은 P1이 signal()을 실행할 때가지 기다리며, P1은 P0이 signal()을

실행할 때 까지 기다리게 됩니다. 이에 P0와 P1은 deadlock 상태가 됩니다.

즉, process가 process를 무한정 기다리는 상태를 말합니다.

 

Starvation

무한 blocking 되는 것입니다.

process가 일시 중단된 semaphore queue에서 제거되지 않을 수 있습니다.

 

Monitors

동시 process 간에 추상 데이터 유형을 안전하게 공유할 수 있는 고급 동기화 구성입니다.

java에서 자주 사용됩니다.

semaphore 는 잘못사용하면 발견하기 어려운 타이밍 오류를 불러올 수 있습니다. 

모니터는 semaphore 개념과 매우 유사하면서 이러한 문제점을 방지할 수 있습니다.

위와 같이 공유 데이터에 접근하기 위해서는 모니터 내부에 공유 데이터를 선언 하고 내부의 procedure를

통해서만 내부의 공유 데이터에 접근할 수 있게 합니다.

또한 내부의 procedure가 동시에 접근이 되지 않도록 만들어 lock을 걸 필요가 없습니다.

모니터 내에서는 한번에 하나의 process만이 활동가능합니다.

 

process가 모니터 내에서 기다릴 수 있도록, 조건 변수 x, y를 선언합니다.

조건 변수는 wait() 과 signal() 연산에 의해서만 접근이 가능합니다.

x.wait()

x.wait() 연산은 다른 process가 x.signal()을 호출할 때까지

x.wait()을 호출하는 process가 중단됨을 의미합니다.

x.signal()

x. signal()은 정확히 하나의 일시 중단된 process를 재개합니다.
일시 중단된 process가 없으면 아무 일도 일어나지 않습니다.

semaphore에서도 자원을 카운트 해서 자원이 있을 때만 process가 접근이 가능하게 했는데

모니터에서도 마찬가지 입니다. 조건 변수가 대체하는 것입니다.

process P에 의해 x.signal() 연산이 호출될 때,

조건 x(이미 모니터에 있음)와 연관된 일시 중단된 process Q가 있다고 가정합니다.

 

Signal and Wait

P는 Q가 모니터에서 나갈 때까지 기다리거나 다른 조건을 기다립니다.
조건은 신호가 발생하는 특정 순간에 참입니다.

 

Signal and Continue

Q는 P가 모니터에서 나갈 때까지 기다리거나 다른 조건을 기다립니다.

일반적으로 context switch가 별로 안일어납니다.

보통 이러한 형태를 자주 씁니다. 

Classical Problem of Synchronization

지금 까지 본 동기화에서 고전적인 문제들이 발생합니다.

1) Bounded-Buffer Problem