프로세스 동기화 - (4)

1. Race Condition 과 Critical Section 이란

 

• Race Condition = 경쟁 상태

- 두 개 이상의 프로세스가 공용 자원을 병행적으로 읽거나 쓰는 작업을 하는 상태

-> 공통 데이터에 대한 접근이 어떤 순서에 따라 이루어졌는지에 따라 그 실행 결과가 달라진다

• Critical Section = Race Condition 이 발생할 수 있는 부분

- 프로그래밍 코드 상에서 공유 데이터를 접근하는 부분을 뜻한다. 여기에서 문제점들이 발생함.

->  이 영역에 한번에 한 프로세스만 들어올 수 있도록 해야함 = 동기화의 필요성

=> 모든 프로세스가 읽을 수 있는 공유 변수(Synchronization variable)를 놓고 알고리즘을 설계하기 시작

 

**프로세스는 크게 4가지 구역으로 나뉜다

do {

1. entry section /* critical section 에 진입 요청을 하는 부분 */
2. critical section /* 허락받고 들어가는 임계 구역 */
3. exit section /* critical section 에서 퇴출되는 부분 */
4. remainder section /* 나머지 코드 부분 */

} while(true)

 

 

 

2. 일단 Critical Section 문제를 해결하려면 어떤 조건을 충족해야 되는 거니

 

1. 상호 배제(Mutual Exclusion) : Critical Section 에는 한번에  하나의 프로세스만 들어와서 작업할수 있다
2. 진행(Progress) : Critical Section이 비어있는데 어 나 쓸래! 하는 프로세스가 있으면 바로 들어와서 쓸수 있도록 해줘야 한다
3. Bounded Waiting (한정 대기) : Critical Section 에 들어가려고 대기표 끊어놨는데 내 앞으로 쓸수 있는 매직패스 티켓 수를 한정해 놓는 것! = 무한정 기다리게 하면 안됨

 

 

---

 

 

3. Synchronization을 위해 나온 여러 가지 방법 들을 알아보쟈

 

1) 소프트웨어적 방법 - 초기

 

• 첫째, 둘째 - 시도는 좋았으나 fail

• 피터슨 알고리즘(Peterson's Algorithm) = flag, turn 변수를 동시에 사용

-Mutual Exclusion, Progress, Bounded waiting 모두 만족!!

 

▷ 단점 및 문제점

• 소프트웨어적인 방법으로 속도가 느리다
• 프로세스가 두 개인 경우에만 적용이 가능
• 자원을 많이 소모한다(Busy Waiting)
• 현대 컴퓨터에서는 정상 작동하지 않는다

 

2) 하드웨어적 방법

 

엔지니어들은 초기 소프트웨어적인 방법으로 임계 영역 문제를 해결하는 것은 한계가 있다는 것을 깨닫고 이번에는 하드웨어적인 방법을 고안했다.

하드웨어적 방법은 원자적 실행 단위를 보장하기 때문에 코드의 순서가 바뀌거나 하는 일이 없어서 좀 더 간단하게 이 문제를 해결할 수 있었다.

 

 

▷TestAndSet()

 

 

**하지만 이 방식은 프로세스의 도착 순서와 무관하게 임계 영역에 진입할 프로세스가 정해졌기 때문에 Bounded Waiting 문제를 해결할 수 없었다.

waiting array 를 추가하여 보완할 수 있었지만 복잡하고 어려워 소프트웨어 툴인 Mutex(Mutual Exclusion) 가 만들어졌다.

 

 

3) Mutex Locks

 

한 프로세스에 의해 소유될 수 있는 key(object)를 기반으로 한 상호배제 기법이다.

key에 해당하는 객체, lock을 소유한 프로세스만이 공유자원에 접근할 수 있다.

 

하지만 Mutex Lock 도 마찬가지로 원자적으로 수행되고 Busy Waiting 문제점을 개선하지 못했다.

(lock을 얻지 못하여 Critical section에 들어가지 못하는 동안 acquire 함수 내에서 while문을 돌고 있어야 함 = Spin Lock)

 

 

3) Semaphore

 

 

자원을 얻는 P 연산과 자원을 반납하는 V 연산 과정을 통해 이뤄지는 자료형이며 그 값은 공유 자원의 개수를 의미한다.

Semaphore와 Mutex Lock 모두 busy waiting 이라는 단점을 발생할 수 있기 때문에

세마포어를 구현할때 프로세스를 연결하기 위한 큐를 추가로 정의하게 된다.

 

**이런 구현 방식을 Block/Wake-up 이라고 하며 대기해야 할 프로세스에서 CPU를 뺏어서 수면 상태에 빠지게 한다고 Sleep Lock이라고도 한다

=>  Block/Wake-up가 Spin Lock 보다 일반적으로 더 좋지만 Critical Section 의 길이가 짧을 경우에는 과한 방식이 될수 있다

 

 

 

▷ DeadLock과 Starvation

 

DeadLock : 두 개 이상의 프로세스가 서로 상대방의 작업이 끝나기만을 기다리며 다음 단계로 진행하지 못하는 상태

 

[해결방법]

• 예방

- Mutual exclusion(상호 배제) 조건의 제거: critical section 제거

- No Preemption(비선점) 조건의 제거: 선점 가능 기법을 만들어줌

- Hold and wait(점유 대기) 조건의 제거: 한 번에 모든 필요 자원 점유 및 해제

- Circular wait(순환 대기) 조건의 제거: 자원 유형에 따라 순서를 매김

 

• 회피

- 자원 요청에 대한 부가정보를 이용해서 자원 할당이 deadlock으로부터 안전(safe)한지를 동적으로 조사해서 안전한 경우에만 할당하는 것

=> 가장 단순하고 일반적인 모델은 프로세스들이 필요로하는 각 자원별 최대 사용량을 미리 선언하도록 하는 방법이다. 

 

Starvation: 특정 프로세스의 우선순위가 낮아서 자원을 계속 할당받지 못하는 상태

 

[해결방법]

• 프로세스 우선순위를 수시로 변경해서 각 프로세스가 높은 우선순위를 가질 기회주기
• 오래 기다린 프로세스의 우선순위를 높여주기
• 우선순위가 아닌 요청 순서대로 처리하는 FIFO 기반의 요청 큐 사용