상호 배제 여러 가지 기법들 : SW solution

소프트웨어를 이용하여 상호 배제를 보장하는 알고리즘은 여러 가지가 있습니다.

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

데커의 알고리즘 (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;       // 진입을 취소하여 임계구역 사용완료를 알림.
}

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

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

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

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

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

// critical section

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

}

728x90

다익스트라 알고리즘 (Dijkstra algorithm)

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

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

flag [i] 변수 상태

idle : 프로세스가 임계 구역에 진입 시도를 하고 있지 않은 상태
want-in : 프로세스의 임계구역 진입 시도 1단계
in-CS : 프로세스의 임계구역 진입 시도 2 단계 및 임계구역 내에 있을 때

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;  // 임계구역 사용완료를 알림.
	
}

램퍼드의 베이커리 알고리즘 (Lamport's bakery algorithm)

프로세스 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;  // 임계구역 사용완료를 알림.
}

소프트웨어 솔루션의 문제점

속도가 느립니다.
구현이 복잡합니다.
busy waiting이 발생하여 비효율적입니다.
- Busy wating: 계속적으로 무한 루프를 돌면서 최대한 다른 스레드에게 CPU를 양보하지 않는 것
상호 배제 기본 기능 실행 중 선점(preemption) 될 수 있습니다.
- 공유 데이터 수정 중은 interrupt를 억제 함으로써 해결 가능하지만 overhead가 발생하게 됩니다.

728x90

저작자표시 비영리 변경금지