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

목차

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

---

상호 배제를 보장하기 위해 하드웨어에서 제공하는 방법에 대해서 알아보도록 하겠습니다.

 

TestAndSet (TAS) instruction

---

TestAndSet 명령어는 동시성을 제어 어하기 위한 동기화 명령어 중 하나로서, 하드웨어의 도움을 받아 수행됩니다.

 

이 명령어는 test 와 set을 한 번에 수행하는 기계어(machine instruction)입니다.

// target을 검사하고, target 값을 true로 변경
boolean TestAndSet (boolean *target) {     //<- 한번에 수행 (machine instruction)
  boolean temp = *target;  // 이전 값 기록
  *target = true;          // true로 설정
  return temp;             // 값 반환
}

기계어이기 때문에 원자성(atomicity)을 가지며 실행 중 interrupt를 받지 않아 명령어 수행 중에 선점(preemption)이 되지 않습니다.

TAS를 이용한 상호배제 구현

---

다음은 TAS를 활용하여 상호 배제를 구현한 예제입니다.

boolean lock = false;

do {
  while(TestAndSet(&lock));   // lock을 걸어줌, lock이 풀릴때 까지 다른 프로세스는 CS에 접근 못함.

  // Critical Section 

  lock = false;   // lock을 풀어줌
} while(ture);

설명

• 가장 먼저 TestAndSet을 실행하는 프로세스가 while(TestAndSet(&lock)); 루프에서 lock = ture로 바꾸고 false를 반환받아 while문을 빠져나오며 임계 구역에 진입합니다.
• 다른 프로세스는 lock = false가 될때까지 while루프를 빠져나오지 못하고 계속 대기하게 됩니다.
• 임계구역에 진입했던 프로세스는 임계구역을 빠져나오면서 lock=false를 수행하여 lock을 풀어주면 대기하던 다른 프로세스가 임계구역에 진입하게 됩니다.

이 알고리즘은 프로세스가 3개 이상인 경우 한 프로세스가 계속해서 임계구역에 진입하지 못하는 경우가 발생할 수 있습니다. 그렇기 때문에 bounded waiting 조건을 위배하게 됩니다.

728x90

N개의 프로세스에서 상호배제 구현

---

다음은 대기열(waiting)을 추가하여 bounded waiting 문제를 해결한 알고리즘입니다. 

boolean lock = flase;

do {                                 // 프로세스 Pi의 진입 영역
  waiting[i] = true;                 // 프로세스 i를 대기열에 넣음.
  key = true;                        
  while (waiting[i] && key)          // 대기가 풀리거나 lock이 풀릴 때까지 대기함. 
    key = TestAndSet(&lock);         // lock 값을 key에 반환. key와 lock은 같은 값으로 보면 됨.

  waiting[i] = false;                // CS에 접근할 수 있으므로 대기를 풀어줌. 이 코드가 없다면 무한 대기를 하게 됨.

  // Critical Section

  j = (i + 1) % n;
  while ((j != i) && !waiting[j])  // 대기 중인 프로세스를 찾음
    j = (j + 1) % n;
  
  if (j == i)                      // 대기 중인 프로세스가 없으면
    lock = false;                  // 다른 프로세스의 진입을 허용할 수 있게 lock을 풀어줌.
  else                             // 대기 프로세스가 있으면 다음 순서로 임계 영역에 진입하게 함. 
    waiting[j] = false;            // Pj가 임계 영역에 진입할 수 있도록 대기를 품.  

} while (true);

 

HW솔루션의 장단점

---

장점

• 하드웨어가 한번에 수행되는것을 보장해 주기 때문에 SW솔루션에 비해 구현이 간단합니다.

단점

• Busy waiting 문제가 있어 비효율적입니다.