[OS] 10. Process Synchronization and Mutual Exclusion 3

이번엔 하드웨어 쪽에서의 해결책을 살펴보자. 

 

Synchronization Hardware

• TestAndSet(TAS) instruction
  • test와 set을 한 번에 수행하는 기계어이다. 
  • Machine instruction (한 번에 수행됨)
    • 실행 중에 interrupt를 받지 않는다 (preemption 안됨!)

TAS를 이용한 ME 구현

여기서 TAS는 값을 반환하고, 값을 바꿔준다. 

swift로는 약간 이런 느낌..?

func TAS(_ target: inout Bool) -> Bool {
    var temp = target // 이전 값 기록
    target = true // 값 변경
    return temp // 값 반환
}

즉 초기에는 lock이 false여서 while문을 패스하는데, 이 때 TAS(lock)이 false를 뱉음과 동시에 값이 true로 바뀌게 되는 것이다. 

P0이 먼저 들어갔다고 하면 위 과정을 거치고 CS 영역에 들어가게 되며, 이 때 P1이 접근하려고 하면 lock이 true이기 때문에 while문 아안에서 돌게된다. P0이 작업을 마치고 lock을 false로 바꿔주면 그 때 P1이 while 문을 벗어나 CS 영역으로 진입할 수 있게 된다.

 

하지만 프로세스가 3개 이상일 경우는 bounded waiting 위반하는 경우가 발생한다. 

 

예를 들어, P0이 먼저 진입해서 작업을 하고 있을 때 P1, P2가 도착했다고 가정해보자. 그러면 P0이 일을 마친 후, P2가 들어갈 수 있다. 그런데 P2가 들어간 이후에 P3이 도착하여 대기자가 P1, P3이 되는 경우가 발생할 수 있다. 이 때 P1이 아니라 P3이 들어가게 되면 P1은 계속 대기하게 된다. 이러한 상황이 반복되는 경우 프로세스가 유한 시간 내에 진입이 허용되지 않기에 bounded waiting을 위반하는 경우라고 생각하면 된다. 

 

프로세스가 N개 이상일의 경우는 어떻게 처리해줘야 할까?

 

프로세스가 N개 이상일 때 ME

 

Swift 코드로 바꿔서 봐보자. 

(대략 이 정도 될 것 같다..!)

 

// 전역변수
var waiting = [Bool]()
var lock = false
var j = 0 // 0..<n
var key: Bool

repeat {
    waiting[i] = true
    key = true
    
    while waiting[i] && key {
        key = TAS(&lock) // lock을 true로 변경하고, 변경 이전값 반환
    }
    
    waiting[i] = false
    // 임계 영역
    // ...
    // 탈출 영역
    
    j = (j+1) % n
    while j != i && !waiting[j] { // 대기 중인 프로세스 찾기
        j = (j+1) % n
    }
    
    if j == i { // 대기 중인 프로세스가 없다면
        lock = false // 다른 프로세스 진입 허용
    } else { // 대기 중인 프로세스가 있다면 다음 순서로 임계 영역에 진입
        waiting[j] = false // Pj가 임계 영역에 진입할 수 있도록 해준다. 
    }
    
} while true

waiting이라는 새로운 변수가 생긴 것을 볼 수 있다. waiting이라는 것은 내가 들어가길 기다릴지(true) 아니면 기다리지 말지(false)를 정해주는 역할을 한다. 

 

위 코드를 천천히 살펴보자. 

 

 

우선 Pi가 먼저 들어오는 경우라고 가정해보자. waiting[i] = true라는 것은 "Pi가 임계 영역에 들어가려고 대기하겠다"라고 말하는 것과 같다. key의 초깃값 또한 true로 첫 while문에 들어가서 key를 false로 두고 lock은 true로 만들어주고 탈출한다. 

 

그 이후 이제 Pi는 임계 영역에 들어가기 전에, 이제 더 이상 기다리는 게 아니라 작업을 수행하면 되기에 waiting[i]를 false로 바꿔준다. 

그러면 정상적으로 임계 영역에 들어가서 작업을 하게 되며, 탈출할 때 다음에 대기하고 있는 프로세스가 있는지 탐색해봐야 한다. 

 

이 탐색은 (j+1) % n을 통해 수행된다. 이 때 j가 자기 자신(i)이거나, waiting[j]가 true이면 while문을 탈출할 수 있다.  

 

그래서 아래 If-else문으로 한 번 더 걸러준다. 만약 j가 자기 자신(i)이라면 lock을 false로 만들어서 다른 프로세스들이 진입할 수 있도록 도와준다. 반면에 j가 i와 다를 경우 즉, waiting[j]가 true였던 경우 j는 진입을 기다리고 있었기에, 이제 Pj가 들어갈 수 있도록 세팅한다. 

(waiting[j] = false)

 

 

HW Solution의 장단점

• 장점 
  • 구현이 간단하다.
• 단점 
  • busy waiting이 여전히 발생한다. 
  • 여전히 비효율적, 많이 기다려야함 
  • 이제 이를 해결하기 위해 OS가 나서서 상호배제 기법을 제시하는데, 대표적인게 바로 Semaphore이다.

 

세마포어는 다음에 더 자세하게 알아보자!

---

Ref: https://www.youtube.com/watch?v=Zps0ckSvKys&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=14