# 05. 병행프로세스 동기화

 

0. 병행 프로세스(Concurrent Processes)란?

 

병행 프로세스란 프로세스 여러 개가 동시에 실행되는 것을 의미한다.

 

하지만 이러한 병행프로세스들은 문제점이 있는데 바로 프로세스 여러개를 동시에 실행하다보면 공유 데이터에 접근을 할 때 충돌이 발생할 수 있다는 것이다.

 

A프로세스는 SUM에서 1을 빼는 작업을 하고, B프로세스는 SUM에서 1을 더하는 작업을 한다고 하자. SUM=10이라고 할때 먼저 A가 실행되어 9로 값을 바꾸고 이 값을 SUM에 저장하려고 하는 중에~~~ B프로세스로 사용권이 넘어갔다면 최종 SUM의 값은 11이 된다. 반면 B가 먼저 실행하려는 중에 A에게 뺏겨 버리면 최종값은 9가 된다.  

 

 

 

1. 경쟁 상태(Race Condition)란?

 

프로세스들이 공유 데이터에 대해 서로 접근을 시도하며 싸우는 상황을 Race Condition이라고 한다.

여러 프로세스들이 동시에 데이터에 접근하는 상황에서 어떤 순서로 데이터에 접근하느냐에 따라 결과값이 달라질 수 있는 상황을 말한다. 

 

프로세스들이 서로 경쟁하는 Race Condition에서는 3가지의 문제가 발생한다.

상호배제
교착상태(데드락)
기아

하지만 우리는 이번에 상호배제에 대해서만 알아 볼 것이다.  그 전에 임계구역이 무엇인지 스르륵 보고 가자. 

 

 

 

* 임계구역(Critical Section)이란?

 

임계 구역이란 코드 상에서 Race condition(싸움)이 발생할 수 있는 특정 부분을 말한다. 즉 공유 데이터를 접근하는 코드 부분을 말한다. 

 

 

 

2. 상호배제(Mutual Exclusion)이란?

 

위에서 임계영역에 대해서 알고 왔다면 상호배제를 이해하기가 더 쉽다. 

상호배제란 한번에 하나의 프로세스만이 임계영역에 들어가야 함을 의미한다. 

 

상호배제를 위해서는 몇 가지 알고리즘이 있는데 대표적인 것만 알아보자. 

데커의 알고리즘 (Dekker's algorithm) -프로세스 두 개
피터슨의 알고리즘 (Peterson's algorithm) - 프로세스 두개
다익스트라 알고리즘 (Dijkstra algorithm) - 프로세스 n개
램포트의 베어커리 알고리즘 (Lamport's bakery algorithm) - 프로세스 n개

 

 

 

2.1 데커의 알고리즘 (Dekker's algorithm)

 

프로세스 두 개일때 상호 배제를 보장하는 최초의 알고리즘.

flag는 누가 CS(Critical Section)에 진입할 것인지 알리는 변수이고, turn은 누가 CS에 들어갈 차례인지 알리는 변수.

while(1) {               // 프로세스i의 진입 영역

  flag[i] = ture;        // 프로세스i가 임계구역에 진입하기 위해 진입을 알림

  while(flag[j]) {       // 프로세스j가 임계구역에 진입하려고 하는지 확인
    if (turn == j) {     // 프로세스j가 임계구역에 있다면
      flag[i] = flase;   // 프로세스i가 진입을 취소하고
      
      while (turn == j); // 프로세스i의 차례가 올 때까지 대기 함.
      
      flag[i] =ture;     // 차례가 넘어왔다면 진입을 알림.
    }
  }

// Critical Section

  turn = j;              // 임계구역의 사용이 끝났다면 차례를 프로세스j에게 넘김.
  flag[i] = false;       // 진입을 취소하여 임계구역 사용완료를 알림.
}

 

 

2.2 피터슨의 알고리즘 (Peterson's algorithm)

 

프로세스 두 개 일 때 상호 배제를 보장하는 알고리즘.

데커의 알고리즘과 유사하지만 상대방에게 진입 기회를 양보한다는 차이가 있고 보다 더 간단하게 구현되었다.

 

while(1) {                        // 프로세스i의 진입 영역

  flag[i] = ture;                 // 프로세스i가 임계구역에 진입하기 위해 진입을 알림.
  turn = j;                       // 프로세스j에게 진입을 양보함.
                                  //  (두 프로세스중 먼저 양보한쪽이 먼저 임계구역에 들어가게 됨.)
  while (flag[j] && turn = j);    // 프로세스i의 차례가 될 때까지 대기를 함.

// critical section

  flag[i] = false                 // 임계구역 사용완료를 알림.

}

 

 

2.3 다익스트라 알고리즘

 

프로세스 n개의 상호배제 문제를 해결한 최초의 알고리즘.

CS에 진입하기 위해 단계를 2단계로 나누어 단계마다 진입할 수 있는 프로세스를 걸러내어 최종적으로 하나의 프로세스만 CS에 접근할 수 있게 구현되었음.

 

while(1) {                                // 프로세스i의 진입 영역

	do {
	// 임계구역 진입시도 1단계
	  flag[i] = want-in                     // 1단계 진입시도를 한다고 알림
	  while (turn != i ) {                  // 자신의 차례가 될 때까지 대기를 함.
	    if (flag[turn] == idle) {           // 임계구역에 프로세스가 없다면,
	      turn = i;                         // 자신의 차례로 변경함.
	    }
	  }
	
	// 임계구역 진입시도 2단계
	  flag[i] = in-CS                      // 임계구역에 진입하겠다고 알림.
	  j = 0;
	  while ((j < n) && (j == i|| flag[j] != in-CS ){ // 자신을 제외한 in-CS 상태의 프로세스가 있는지 검사 함.
	    j = j + 1;
	  }
	} while(j < n)   // 자신 외에 2단계 진입을 시도하는 프로세스가 있다면 다시 1단계로 돌아감.
	
	// critical section   // in-CS 상태의 프로세스가 자신밖에 없다면 임계영역에 진입함.
	
	flag[i] = idle;  // 임계구역 사용완료를 알림.
	
}

 

 

2.4 렘퍼드의 베이커리 알고리즘

 

프로세스 n개의 상호 배제 문제를 해결한 알고리즘.

bakery 알고리즘은 프로세스에게 고유한 번호를 부여하고, 번호를 기준으로 우선순위를 정하여 우선순위가 높은 프로세스가 먼저 임계 구역에 진입하도록 구현되었음.

• 번호가 낮을수록 우선순위가 높음.

while(1) {              // 프로세스i의 진입 영역

  choosing[i] = ture;   // 번호표 받을 준비
  number[i] = max(number[0], number[1], ..., number[n-1]) + 1;  // 번호표 부여 
                                                                // (번호표 부여중 선점이 되어 같은 번호를 부여 받는 프로세스가 발생할 수 있음)
  chossing[i] = false;  // 번호표를 받음

  for (j = 0; j < n; j++) { // 모드 프로세스와 번호표를 비교함.
    while (choosing[j]);    // 프로세스j가 번호표를 받을 때까지 대기

    while ((number[j] != 0) &&    
            ((number[j] < number[i])               // 프로세스 j가 프로세스 i보다 번호표가 작거나(우선순위가 높고)
            || (number[j] == number[i] && j < i)); // 또는 번호표가 같을 경우 j 가 i 보다 작다면 
                                                   // 프로세스 j가 임계구역에서 나올 때까지 대기.     
  }


// Critical Section

  number[i] = 0;  // 임계구역 사용완료를 알림.
}

 

---

출처

https://yoongrammer.tistory.com/61

https://rebro.kr/172?category=504670