[OS] 6. 프로세스 동기화 - Mutual Exclusion HW Solution

어떻게 하면 상호배제가 잘 작동하는 알고리즘을 만들 수 있을까? 

Mutual Exclusion Solutions

• SW solutions
  
  • Dekker’s algorithm (Peterson’s algorithm)
  • Dijkstra’s algorithm , Knuth’s algorithm, Eisenberg and McGuire’s algorithm, Lamport’s algorithm
• HW solution
  
  • TestAndSet (TAS) instruction
• OS supported SW solution
  
  • Spinlock
  • Semaphore
  • Eventcount /sequencer
• Language Level solution
  
  • Monitor

앞서 소프트웨어를 통한 ME 솔루션은 비효율적이고 구현이 복잡하다는 단점이 있다.

소프트웨어가 아닌 다른 방법으로 ME솔루션을 해결하는 방법을 제시한다.

 

HW solution: Synchronization Hardware

하드웨어에서 TestAndSet (TAS) instruction

• 기계적으로 한번에 수행이 되는 기계어 (Test 와 Set 을 한번에 수행하는 기계어)
• Machine instruction
  
  • Atomicity, Indivisible
  • 실행 중 interrupt 를 받지 않음 (preemption 되지 않음) => 실행이 보장됨
  • Busy waiting => Inefficient
• TestAndSet 명령어

// target을 검사하고, target값을 true로 설정
boolean TestAndSet (boolean *target){
  boolean temp = *target; //이전 값 기록
  *target = true;
  return temp;
}

TestAndSet은 일련의 과정들이 한번에 수행된다.

그렇다면 위의 연산이 어디에 어떻게 사용될까?

ME with TAS Instruction

해당 연산을 사용하면 ME 문제를 간단하게 해결할 수 있다.

1. lock 초기값 = false
2. lock이 TAS명령어에 넣으면 lock은 true가 되며, TAS(lock)의 return은 false가 된다.
3. while문을 빠져나와 CS에 진입하게 된다.
4. Pi가 작업을 수행하고 있을 때 Pj가 들어오려고 하면 TAS(lock)이 계속 True상태가 되기 때문에 Pj는 while문에서 대기하게됨.
5. Pi가 CS에서 작업을 마친순간 lock을 false로 바꿀 것이다. 
6. Pj는 while문에서 만족문을 만족하지 않으므로 CS에 진입하게 됨.

만약에

1. 1번 프로세스가 작업완료하고 2,3번이 CS에 들어가려고 대기한다면 누가 먼저 들어갈 것인지 모른다.
2. 만약 2번 프로세스가 3번보다 loop을 더 빨리 돌았다면 2번이 진입하고 3번이 대기하게 된다.
3. 4번이 와서 3번과 같이 대기를 한다면
4. 4번 loop를 도는 속도가 3번보다 빠르다면 3번은 대기하게 된다.
5. 이처럼 3번 프로세스가 계속 대기하게 되는 상황이 나올 수 있다.

ME문제가 해결하였지만 3개 이상의 프로세스인 경우 Bounded wating 조건을 위배한다. 

여기서 요점은 TAS라는 기계어를 이용해서 ME문제를 간단히 해결할 수 있다. 

N Process mutual exclusion

앞서 소개한 방법에서 N개의 프로세서의 Bounded wating 조건을 위배하는 것을 해결함.

HW Solution

장점: 구현이 간단하다.

단점: Busy waiting(비효율적) => 루프에서 오래 기다릴 수 있음

 

Busy wating문제를 OS상에서 해결할 수 있는 기법이 있다. => Semaphore

---

본 포스트는 KOREATECH의 HPC LAB. Duksu Kim 교수님 OS강의를 기반으로 정리한 내용입니다.

상업적 의도가 아닌 공부한 것을 정리해 놓은 목적으로 게시한 포스트입니다. 

아래의 출처에서 자세한 내용을 수강하실 수 있습니다.

https://www.youtube.com/playlist?list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN

---