운영체제 - 5(++ 병행프로세스/상호배제 해결법)

비동기 병행프로세스(상호배제)

 

1. 임계 영역(Critical Section)

- 프로세스가 공뮤메모리를 사용하는 코드를 임계영역이라 한다

- 임계영역의 사용을 통제해주어야 한다

 

 

2. 상호 배제

- 한 프로세스가 임계영역에 들어가면 다른 프로세스는 그 임계영역에 못들어가도록 운영체제가 통제한다.

- 이러한 임계영역의 문제를 해결하기 위해 상호배제가 필요하다.

* 임계영역을 제외한 영역을 잔류영역이라고 한다

---

 

상호배제 해결법

 

1. Algorithm 1

- 교대로 임계영역에 들어갈 수 있다.

While문에 의하여 Process 2가 실행중이라면, 계속 작업을 반복하고(do ;)

그렇지 않다면, p1이 임계영역에 진입하는 알고리즘

프로세스 2 역시 마찬가가지로, P1이 실행중이라면 그 작업을 반복하고

그렇지 않다면 P2가 임계영역에 진입하게 한다.

이 모든 작업은 무한루프로 반복된다.

 

이렇게 Algorithm1은 교대로 임계영역에 들어가 상호배제를 해결한다.

 

문제점) 두 프로세스 중 하나가 비정상적으로 중지되면 다른 프로세스는 진행불가능

(비정상적인 중지시 While을 빠져나오지 못하므로 임계영역에 무한히 진입할 수 없다)

 

2. Algorithm 2

- 두 개의 변수를 사용한다.(p1inside, p2inside)

Algorithm1 같은경우 아예 임계영역에 진입하지 못하도록 했으나, 비정상적인 중지 시 진입이 불가능하다

그런 문제를 해결하기 위해 Algorithm 2는 일단 임계영역에 진입하게 하고, 두 개의 bool 변수를 이용해

true/false를 오가며 하나가 들어가면 하나가 나오게 만든다. (기본값은 false로 초기화)

 

P2도 마찬가지

 

문제점) 두 프로세스는 동시에 돌아가기 때문에, 두개 다 임계영역에 진입하는 타이밍이 있을 수 있다.

그런 경우 상호배제를 해결할 수가 없다.

 

3. Algorithm 3

 

- 2개의 변수를 사용(p1enter, p2enter)

Algorithm2와 무엇이 다르냐?

Algorithm2는 우선 들어가고 다른 프로세스를 차단을 시켰다. 그렇기 때문에 동시에 두개가 접속되는 현상이 발생되어(두 프로세스 알고리즘이 동시에 돌아가기 때문에) 상호배제가 보장되지 않았다.

하지만 Algorith 3의 경우 들어가기 전에 차단을 시키고 들어간다. 이런 경우 우선 들어가기 전에 차단을 시켜버리기 때문에 두 개의 프로세스가 동시에 들어가는 일은 없어 상호배제가 보장된다.

 

문제점) 들어가기 전에 우선 다른 프로세스를 차단하고 시작해버리기 때문에 두 프로세스 모두 다 들어가지 못하는 현상이 발생한다. 동시에 False로 적용되어 Deadlock이 발생하여 아무도 임계영역에 못들어가는 상황이 발생한다.

동시에 False로 바꾸는 경우가 문제이므로 상대적인 시간차를 주면 해소할 수도 있다.

 

4. Algorithm 4

 

- 두 개의 변수를 똑같이 사용하되(Algorithm 3과) delay 함수를 도입하여 상대적인 시간차를 부여하여 해결

- Algorithm 3과 똑같지만 각자의 플래그를 false/true로 바꾸기 전에 delay를 강제로 부여한다.

 

문제점) Delay를 부여하다보니 단순히 성능이 안좋아진다(상대적인 속도 예측 불가/무한연기 문제 발생)

 

5. 데커 알고리즘

 

- p1enter, p2enter, fprocess라는 세개의 변수 사용

- fprocess변수를 통해 순서의 개념을 도입한다.

- 동시에 2개의 프로세스가 임계영역에 들어가려 할 때 fprocess 변수로 순서를 정해준다.

 

문제점) 너무 지엽적 - 2개의 프로세스에 대한 알고리즘이므로 다른 곳에 적용하기 힘들다

 

---

세마포어

 

- 기존의 상호배제 해법(Algorithm 1,2,3,4)로는 임계영역 문제를 일반화하기 힘듬(다른 곳에 적용하기 힘들기 때문이다)

- 이를 해결하기 위해 제시된 것이 세마포어

 

세마포어 변수(S)를 이용하여

S가 0보다 작을 경우 no-op(기다림)

특정 시점에서는 세마포어 변수의 값을 올려줌

이렇게 세마포어 변수의 값에 While을 부여하여 세마포어 변수가 특정 조건에 부합한 경우에만

실행되도록 함

 

Ex) 

P3의 경우 P1,P2의 값이 구해져야만 k값을 구할 수 있으므로

자연히 P1,P2 실행-> P3 실행의 순서를 갖게된다.

 

이런식으로 기존의 알고리즘들과는 달리 세마포어 변수를 통하여 더 여러개의 프로세스에도 적용하기 쉽게 일반화한다.

 

 

1. Busy Waiting 문제 해결

세마포어 변수를 변화시켜 일정 시점에서는 대기 큐에 추가 , 일정 시점에서는 대기 큐에서 제거하고 준비 큐에 추가

 

2. 특징

 

1) 세마포어를 실행하는 동안에는 인터럽트나 이벤트에 의해 중지되지 않아야 함 -> 원자적 명령

-> 세마포어 변수 역시 여러개의 프로세스가 공유하는 개념이므로 갑자기 중지될 경우 여태까지 한 작업이 무의미해진다.

 

2) 세마포어를 사용하면 N개의 임계영역 문제를 해결할 수 있고 , N개 프로세스의 상호배제를 구현할 수 있다

-> 다양한 경우에 일반화할 수 있다.