[운영체제] ep4-1) Concurrency: Mutual Exclusion and Synchronization

ㅁ동시성(Concurrency): 여러 작업이 짧은 시간 간격으로 번갈아 가며 수행됨으로써 동시에 처리되는 것처럼 보이게 만드는 것

현대 OS는 멀티 프로그래밍, 멀티 프로세싱 등의 기법으로 동시성을 사용하는 데에 있어 발생하는 문제들을 해결해야만 한다

 

상황) 은행 계좌 파일에 있는 데이터 x를 저장, 처음 잔고는 0원이다

계좌이체 2개의 서로 다른 transaction

 

ㅇRace Condition: 결국에는 둘 중에서 마지막으로 작업한 결과만이 남는다

Race Condition의 발생을 막기 위해 critical section의 mutually exclusive한 실행이 필요하다

 

ㅇcritical section(임계구역): Race Condition이 발생할 수 있는 코드 (전혀 예측할 수 없음)

critical section은 동시에 실행시키면 안된다 따라서 mutual exclusion을 잘 지켜야만 한다

앞으로 c.s.라 많이 줄여 부르겠다

 

ㅇmutual exclusion(상호배제): 한 프로세스가 critical section을 실행하는 동안 다른 프로세스는 critical section에 진입하지 않고 대기하는 것

 

 

 

이러한 Concurrency 방안으로는 3가지가 있다

1. Software Approaches - 알고리즘을 잘 설계

2. HW instruction을 이용

3. OS가 제공하는 동기화 툴 이용 (e.g. 세마포, 모니터)

용어부터 먼저 알아보고 차례대로 알아보자

 

(Concurrency  방안 용어 정리)

ㅇbusy waiting: while문을 계속 돌며 CPU를 낭비하는 것

 

ㅇDeadlock(데드락 = 교착상태): 두 프로세스가 서로 상대편이 뭔가를 해주길 기다리면서 대기를 하는 상황

 

ㅇLivelock(라이브락):두 프로세스가 서로의 진행을 방해하지는 않지만, 계속해서 다른 프로세스의 행동에 반응하며 무한히 실행되는 상황

 

ㅇStarvation(기아): 우선순위에 계속 밀려서 CPU를 차지하지 못하는 상황

 

 

 

1. Software Approaches - 알고리즘을 잘 설계

차례대로 고안된 순서의 방안들을 알아보자

 

방안 1) 공유변수 turn

 

busy waiting ㅇ, 한 프로세스가 실패하면 다른 프로세스도 끝난다 (서로 너무 의존적)

 

 

방안2) 공유변수 flag를 2개 사용 (flag의 초기값은 false라 가정)

 

상호배제 x

 

 

방안3) 순서 change - 처음부터 critical section에 들어가겠다 선언

 

상호배제 O, but 데드락 가능성 O

 

데드락 시나리오)

P0에서 상대편 false 확인 직전에 time-out이 발생

↑↓

↑↓ 무한반복 (둘 다 flag값이 true)

↑↓

P1에서 while문 대기 중에 time-out이 발생

모식도

 

 

방안4) 양보하고 기다렸다가 다시 시도하는 코드

 

상호배제 O, 데드락 X, but 라이브락 가능성 O

 

라이브락 시나리오)

↓ P0 sets flag[0] to true

↓ time-out

↓ P1 sets flag[1] to true

↓ time-out

↓ P0 checks flag[1]

↓ time-out

↓ P1 checks flag[0]

↓ time-out

↓ P0 sets flag[0] to false

↓ time-out

↓ P1 sets flag[1] to false

↓ time-out

↓ P0 sets flag[0] to true

↓ time-out

↓ P1 sets flag[1] to true

(이후 무한반복)

 

 

방안5) 데커 알고리즘(Dekker's Algorithm)

두 개의 프로세스 중 한 개의 프로세스만 양보하도록 설계 (공유변수 turn 이용, 여기서 turn은 양보할 사람차례의 turn)

 

교대진입 X, 상호배제 O, 데드락 X, 라이브락 X, Starvation X

 

 

Q. 대기를 하는 while문에는 바깥쪽과 안쪽 2가지가 있다. 바깥쪽 while문을 돌다가 어찌저찌 상황이 바뀌어 안쪽 while문으로 가서 대기하는 상황이 가능한지

A. No, 이 질문은 현재 turn 값이 1인데 0으로 바뀌는 경우가 있냐 라는 질문과 같다 turn값을 0으로 만드는 코드는 P0에는 없고 P1의 c.s.가 끝난 후에 있다 따라서 불가능!

 

Q. 그 반대는 가능한지

A. 똑같이 No

 

 

방안6) 피터슨 알고리즘(Peterson's Algorithm)

critical section 전에 미리 양보 -> 코드가 반이나 줄었다!

 

교대진입 X

상호배제 O

데드락 X - 조건식 때문에 while문에서 멈추지 않는다

라이브락 X - while문이 하나밖에 없다

Starvation X

 

 

Q. critical section을 나온 상황에서 다른 프로세스가 while문을 돌며 기다리는데 지 혼자 제멋대로 2번 연속 critical section에 들어갈 수 있는지

A.

데커 알고리즘: Yes, but 무한히 그렇지는 않다

피터슨 알고리즘: Certainly, No! 상대편이 대기를 하고 있으면 절대 다시 들어갈 수가 없다

 

 

 

 

(1. Software Approaches 정리)

- 데커 알고리즘

- 피터슨 알고리즘

[장점]

교대진입 X

상호배제 O

데드락 X

라이브락 X

Starvation X

 

[단점]

busy-waiting O

복잡하다

2개의 프로세스만 가능하다

 

 

 

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 

 

추가) 상호배제(mutual exclusion)이 지켜지는지에 대한 확인 사항들

- 한 번에 한 프로세스만 c.s.에 들어가는지

- noncritical section일 때의 프로세스 때문에 다른 프로세스가 c.s.에 들어가지 못하는지

- 데드락 X

- Starvation X

- 아무도 c.s.을 사용하는 상황이 아니라면 내가 지연 없이 바로 들어가야 한다

- 프로세스의 속도나 개수를 고려해서는 안된다

- c.s.에서 무한루프를 돌면 안 된다

 

 

 

 

 

 

 

 

참고 및 출처: Operating Systems: Internals and Design Principles(William Stalling), Operating System Concepts(Silberschatz, Abraham)