이론 4) - 2 임계구역 문제 / SW, HW 해결법

1. 임계구역 또는 임계영역

: 한 순간에 한 프로세스만 사용할 수 있는 영역이다.

 

 

 

2. 진입 상호 배제 및 출구 상호 배제

: 프로세스 하나가 임계 영역에 있으면 다른 모든 프로세스는 임계영역으로의 진입을 금지한다.

 

 

 

 

3. 임계영역을 해결하기 위한 세 가지 만족 요건

1) 상호 배제

2) 진행 : 임계영역에 프로세스가 없을 때, 다음에 임계구역으로 진입하려는 프로세스의 진입을 미루면 안된다.

3) 한계 대기 : 한 프로세스가 임계영역 진입 요청을 한 후 수락되기까지 다른 프로세스가 임계영역에 진입할 수 있는 횟수를 제한해야 한다.

( 새치기 금지 )

 

 

 

 

4. 임계구역 SW 해결법 : 2개의 프로세스를 위한 임계구역 SW해결법

 

1) 알고리즘 1

critical section = counter ++ 하는 부분

-> 상호 배제는 충족하나, 진행을 만족하지 못해 실패한 알고리즘이다.

 

 

 

2) 알고리즘 2

 

 

-> 이 알고리즘 또한 상호 배제는 충족하나, 진행을 만족하지 못해 실패한 알고리즘이다.

 

 

 

 

 

3) 알고리즘 3 (피터슨의 해결안)

: 알고리즘 1, 2의 변수들을 결합한 아이디어

-> 모든 세 요건들을 충족한다.

-> 다만, 2개의 프로세스가 있을 경우만 해결할 수 있다.

 

 

 

 

 

 

 

5. 임계구역 SW 해결법 : N개의 프로세스를 위한 임계구역 SW해결법

 

- 램포트(Lamport)가 제안한 베이커리 알고리즘

 

 

-> 너무 복잡하여 배보다 배꼽이 큰 상황이 되었다.

 

결론) HW해결법은 실제로는 거의 사용되고 있지 않다.

 

 

 

 

 

 

 

 

 

6. 임계구역 HW 해결법

: 하드웨어 명령어를 이용한 임계영역 문제 해결

 

- TestAndSet() : 원소적으로 단어의 내용을 테스트하고 수정하는 명령

- Swap() : 원소적으로 두 변수를 바꾸는 명령

 

-> 한 원소가 다 끝날 때까지는 변경하지 않도록 한다.

-> 이 명령어에 대해서는 하드웨어가 다르게 작동하도록 한다.

 

 

 

 

 

알고리즘 해석 )

문이 잠겨있을 때, (lock = true)

lock이 true이면 반환값도 true이므로 

lock이 false가 될 때까지 while문을 반복한다.

 

문이 잠겨있지 않을 때, (lock = false)

lock이 false이면 while문을 돌지하지않고

빠져나간다. 이 때, lock은 false -> true가 된다.

그 후에 critical section을 실행하고 

false로 다시 변환된다.

 

 

 

 

 

-> 위의 TestAndSet 알고리즘과 동일한 원리이다.

차이점은 lock과 key를 바꾸는 것인데

 

문이 잠겨있지 않을 때 (lock = false)

lock이 false이면,

lock과 key가 바뀌면서

lock은 true, key는 false가 

되어 while문을 빠져나간다. -> critical section 실행하고(하는 동안은 lock이 true이므로 다른 프로세스가 진입하지 못한다)

끝난 뒤에 lock = false로 바꿔주어 다른 프로세스가 진입할 수 있도록 해준다.

 

 

 

 

 

 

- 임계구역에서는 인터럽트는 금지하여야 한다.

: 임계구역 내에서는 다른 일을 최소화하고 빠르게 출구 코드로 복귀해야 한다.

 

-임계구역으로 들어갈 때 바쁜 대기(Busy waiting)를 유발한다.

: 프로세스를 블록시키고 CPU를 다른 프로세스에 배정한다.

 

-> SW, HW 해결법은 바쁜 대기 문제를 해결하지 못했다.