Synchronization Algorithm

Synchronization Algorithm

동기화를 위한 다음과 같은 알고리즘이 있다.

• flag 이용
• turn 이용
• peterson's algorithm : flag + turn 이용
• bakery algorithm by lamport : 번호표 이용

 

Mutual Exclusion 만족 1

Mutual Exclusion을 만족시키기 위해서 flag 변수를 사용한다.

• boolean flag[2];
  • 프로세스마다 flag를 배정한다.
  • 초기값은 false로 설정하고 critical section에 들어가기 전에 true로 설정한다.

 

critical section에 들어가기 전에 자신의 flag를 true로 바꾸고, (<pre>flag[i] = true;</pre>)

다른 프로세스가 critical section에 들어가있다면 나올 때 까지 기다린다. (<pre>while(flag[j]);</pre>

critical section에서 나오면 flag를 false로 바꿔준다. (<pre>flag[i] = false;</pre>)

do {
	// entry section
    flag[i] = true;
    while(flag[j]);	// 다른 process의 flag가 false가 될 때 까지 기다림

	// critical section
    ...
    
    // exit section
    flag[i] = false;
    ...
} while(1);

 

그러나 이는 progress를 만족시키지 못하는 문제가 있다.

2개의 프로세스가 deadlock에 빠져버릴 수 있다.

만약 Pi에서 flag를 ture로 하고 while에 들어가기 전에, Pj에서 flag를 true로 한다면 둘 다 while에 빠져버려서 deadlock이 발생해버린다.

 

Mutual Exclusion 만족 2

Mutual exclusion을 만족하는 다른 알고리즘이 있다.

turn이라는 변수를 이용한다.

• int turn
  • critical section에 들어갈 권한이 있는 프로세스를 의미한다.
  • 초기값은 0으로 설정한다.

 

들어가기 전에 자신에게 turn이 있는지 확인한다.

만약 없으면 자신에게 turn이 돌아올 때 까지 기다린다.

critical section에서 작업을 마친 후 turn을 상대 프로세스에게 넘겨준다.

do {
	// entry section
	while (turn != i);
    
    // critical section
    ...
    
    // exit section
    turn = j;
    ...
} while(1);

 

이 또한 mutual exclusion을 충족하지만, progress를 충족하지 않는다.

만약 P1이 turn을 가지고 critical section에 들어가려다가 중단되어 버리면 P0는 영원히 critical section에 들어가지 못한다.

 

그러나 앞서 flag를 이용해서 mutual exclusion을 해결하는 것 보다는 낫다.

flag를 이용하면 P0와 P1 모두 진행하지 못하지만, turn을 이용하면 하나만 진행하지 못하기 때문이다.

 

Peterson's Algorithm

Mutual exclusion, progress, bounded waiting을 충족할 수 있는 알고리즘이다.

앞의 flag와 turn을 모두 사용한다.

 

critical section에 들어가기 전에 turn을 상대방으로 넘겨줌으로써, 상대방이 flag와 turn을 모두 가지고 있다면 기다린다.

do {
	// entry section
    flag[i] = true;
    turn = j
    while (flag[j] && turn == j);
    
    // critical section
    ...
    
    // exit section
    flag[i] = false;
    ...
    
} while(1);

 

Bakery Alogrithm by Lamport

프로세스/스레드에게 번호표를 나눠주고 가장 작은 번호를 가진 순으로 입장시키는 방식이다.

 

번호표를 부여하는 행위도 atomic하게 일어나지 않기 때문에 동일한 번호가 생길 수 있다.

동일한 번호가 생기지 않도록 하면 알고리즘이 너무 복잡해지기 때문에 주로 동일한 번호부여를 허용하는 곳에서 사용한다.

 

Mutual exclusion & progress

그러나 이 알고리즘은 bounded waiting을 충족시키지 못한다.

번호표 작은 순서대로 critical section에 진입한다고 하면 upper bound waiting time은 n-1이 된다.

 

그런데 번호표를 발행하고 number에 반영하기 전에 스케줄링이 일어난다면 나보다 더 큰 번호를 가진 프로세스가 먼저 들어갈 수 있다.

이렇게 되면 n-1이라는 상한이 더이상 유효하지 않고, 대기할 수 있는 상한값을 정할 수 없게 된다.

do {
	// entry section
	number[i] = max(number[0], number[1], ..., number[n-1]) + 1; // 최대 번호 부여
	
    // 다른 프로세스와 비교
	for(j = 0 ; j < n ; j++) {
    	if (i == j) continue;
        
        // number == 0(초기값) => critical section에 들어가려는 의지가 없다.
        // 나보다 더 우선순위의 프로세스가 끝날 때 까지 기다린다.
        while((number[j] != 0) && (number[j] < number[i]));
        
        // 나와 동일한 우선순위이면 프로세스 번호가 더 작은 것을 먼저 실행한다.
        while((number[j] != 0) && (number[j] == number[i]) && (j < i));
    }
    
    // critical section
    ...
    
    // exit section
    number[i] = 0;
} while(1);

 

Bounded Waiting

번호표를 받고 있다는 것을 의미하기 위해서 choosing이라는 변수를 추가한다.

번호표를 받는 행위를 critical section으로 지정해서 synchronization을 하는 것으로 볼 수 있다.

do {
	// entry section
    choosing[i] = true; // 번호표 발행 중
	number[i] = max(number[0], number[1], ..., number[n-1]) + 1; // 최대 번호 부여
	choosing[i] = false; // 번호표 발행 끝
    
    // 다른 프로세스와 비교
	for(j = 0 ; j < n ; j++) {
    	if (i == j) continue;
        
        // 번호표를 받고 있다면 기다린다.
        while(choosing[i]);
        
        // number == 0(초기값) => critical section에 들어가려는 의지가 없다.
        // 나보다 더 우선순위의 프로세스가 끝날 때 까지 기다린다.
        while((number[j] != 0) && (number[j] < number[i]));
        
        // 나와 동일한 우선순위이면 프로세스 번호가 더 작은 것을 먼저 실행한다.
        while((number[j] != 0) && (number[j] == number[i]) && (j < i));
    }
    
    // critical section
    ...
    
    // exit section
    number[i] = 0;
} while(1);

 

---

Bounded Buffer

아래 producer-consumer problem에서 producer는 buffer가 full 일 때는 write 하지 않기 위해서 blocking을 한다.

그리고 consumer는 buffer empty 일 때 read 하지 않기 위해서 blocking을 한다.

그런데 buffer full과 empty를 정확하게 구분하다보니 buffer의 공간 하나가 낭비되는 문제가 있다.

 

이를 해결하기 위해서 새로운 variable <pre>counter</pre>를 사용해서 synchronization을 한다.

<pre>counter</pre>는 버퍼 안에 실제로 들어가 있는 데이터의 개수를 의미하고 초기값은 0이다.

#define BUFFER_SIZE 5
typedef struct {
	// 주고 받을 데이터의 형식
	...
} item;
 
item buffer[BUFFER_SIZE]; // 버퍼
int in = 0;		// producer가 정보를 넣을 때의 위치
int out = 0;	// consumer가 정보를 읽을 때의 위치
int count = 0;	// buffer에 들어가 있는 데이터의 개수

 

 

Atomic의 문제

위에서 <pre>count++</pre>와 <pre>count--</pre>에서 atomic이 보장되지 않는 문제가 발생한다.

count의 값을 증가시키고 감소시키는 코드는 여러 개의 machine code로 컴파일 된다.

 

따라서 이는 프로세스가 어떻게 스케줄링 되는지에 따라서 interleaving 될 수 있다.

서로 다른 thread들의 명령어들이 엇갈려서 수행되는 것을 말한다.

 

위의 어셈블리 코드가 수행될 때 한 스레드에서 count++을 하다가 중단되고 다른 스레드에서 count--를 하면, 정상적인 결과를 낳지 못한다.

count의 값이 5일 때 producer에서 ++ 하고 consumer에서 -- 하는 작업을 수행 중이라고 하자.

실행이 끝났을 때 count의 값은 여전히 5여야 하지만, 아래 처럼 interleaving 되면 count의 값은 6이 된다.

 

해결

 

병렬적 프로그래밍의 효율성을 위해서 critical section은 최소로 잡는 것이 좋다.