OS arrangement for test - Cooperating process and Synchronization (2)

It is just my opinion, so don't you attack me. please!

But if this posting has some incorrect informations, you comment about that

Please!!

Cooperating process and Synchronization

올바른 상호 배제 구현(Dekker's 알고리즘)

var turn;
var flags = new Array(2);

flags[0] = flags[1] = false;
turn = 0;                         // shared variable 0 or 1

flags[0] = true;                  // 1
while(flags[1]) {                 // 2
  if (turn === 1) {
    flags[0] = false;             // 3
    while (turn === 1);           // 4
  }
  flags[0] = true;
}
/*
임계 영역                           // 5
*/ 
turn = 1;
flags[0] = false;

flags[1] = true;
while(flags[0]) {
  if (turn === 0) {
    flags[1] = false;
    while(turn === 0);
    flags[1] = true;
  }
}
/*
임계 영역
*/ 
turn = 0;
flags[1] = false;

1번에서 p0는 자신이 들어간다고 선언
2번에서 p1이 C.S에 들어가 있지 않다면 바로 5번으로 감
그렇지 않으면 while문에 들어가서, 3에서 자신의 flag를 false로 바꾼다. 그 이후 무한 대기한다.
turn은 동시에 두 프로세스가 C.S에 들어가려는 것을 방지한다.

올바른 상호 배제 구현(test and set 명령어)

bool lock;

bool testAndSet(bool *target) {
  bool temp = *target;
  *target = true;
  return temp;
}

void main() {
  do {
    while (testAndSet(&lock));
    // 임계 영역
    lock = false;
  } while(true);
}

· testAndSet() 명령어는 기계명령어로서 원자적으로 실행 도중 끊김 없이 완료되는 연산입니다.

lock 의 초기값이 false이므로 최초 진입 프로세스가 testandset 을 실행하게 되면 target 값이 false 가 되어 temp 로 넘겨져, while 문은 false 가 되고 결과적으로 임계영역의 진입이 가능합니다.
임계영역을 실행중인 프로세스가 있다면 lock 의 값이 true 이므로 진입을 시도하는 다른 프로세스는 while 문에서 막혀 상호배제를 보장하게 됩니다.

· 장점
-구현이 단순합니다.
-다중임계 영역을 지원합니다.

· 단점
-busy waiting이라서 overhead가 발생합니다.
-기아상태가 발생할 수 있습니다.

올바른 상호 배제 구현(Bakery 알고리즘)

function bakery() {
  do {
    choosing[i] = true; //번호표를 받을 준비
    number[i] = max(number[0], ..., number[n - 1]) + 1; //현재 실행중인 프로세스 중 가장 큰 번호로 할당
    choosing[i] = false; //번호표 받기 완료
    for (j = 0; j < n; j++) { // 모든 프로세스에 대해서
      while (choosing[i]); // 비교할 프로세스가 받았는가?
      while ((number[j] != 0) && ((number[j], j) < (number[i], i))); 
      // j 프로세스가 받은 번호가 번호표를 받은 상태이고
      // j의 번호표가 i의 번호표보다 작고
      // j가 i보다 작으면 (먼저왔음)
      // 프로세스 j의 종료까지 대기
    }
    // C.S
    number[i] = 0; // 임계 영역 사용 완료
  }while(1);
}

· 번호표가 같은 값이면 먼저 기다리고 있던 프로세스가 C.S에 진입합니다.

지금까지 설명했던 상호배제의 경우는 모두 busy waiting한 방법입니다.
따라서 이것을 다익스트라가 해결했는데요? 바로 세마포어입니다.
다음 포스팅은 세마포어가 되겠습니다^^