9. Synchronization(동기화)-1

Race Condition

: 공유 데이터에 대해 여러 프로세스가 동시 접근 및 변경을 시도하는 상황

 

-> 이러한 동시 접근 및 변경은 데이터의 일관성(Consistency)을 해침.

 

Race Condition 예시

은행의 입출금 문제

: 1000원의 잔고가 있는데, 여기에 500원 입금, 500원 출금이 동시에 일어남. 결과는?

입출금 소스코드

이 소스코드들은 컴파일러에 의해 분해되기에 레지스터 수준에서 봐야함.

분해된 소스코드. 결과적으로 500이 남게 되었는데 이는 1500이 될 수도 있다. 하지만 둘 다 원하는 결과가 아님!!!!!!

Critical Section

: 여러 프로세스들이 공유하는 데이터에 접근하는 Code 영역

ex. 위 입출금 문제 예제에서는 Balance = Balance + 500; , Balance = Balance - 500;

 

Race Condition을 방지하기 위해!!!

한번에 단 하나만의 프로세스가 Critical Section에 진입해야 함.

 

Critical Section을 가진 프로세스의 Modeling

Critical Section 문제 해결 알고리즘의 조건 3가지

1) Mutual Exclusion(상호 배제)

: 만약 어떤 프로세스가 Critical Section에 진입해 있다면, 다른 모든 프로세스는 진입할 수 없어야 함.

 

2) Progress(진행)

: 만약 어떤 프로세스가 Critical Section에 들어가려 한다면, Remainder Section에서 실행 중이 아닌 프로세스들만이 누가 진입할지 결정할 수 있어야 함.(실행 중인 놈들은 빠져있어! 진입하려는 애들끼리의 싸움이다!), 결정은 무한히 연기될 수 없음.

 

3) Bounded Waiting

: 프로세스가 Critical Section에 진입 시까지 걸리는 시간에 Limit이 존재해야 함.(계속 기다리는 놈이 생길 수도 있잖아? 걔는 적당히 기다리다가 Limit된 시간이 되면 걔부터 실행시켜주는 거임.)

 

알고리즘 예시 1

P0 -> P1이면 해당 알고리즘은 만족하겠지만, 두 프로세스의 수행 순서가 바뀌면 진행이 안되고 무한정 대기해야 하는 경우가 생김.

 

알고리즘 예시 2

만약 P0에서 flag[0] = true; 를 실행 후 Context Switching이 되어서 P1을 실행하면 flag[0], flag[1] 둘 다 true가 되어버림.

그 결과 둘 다 Critical Section에 진입이 불가능해짐.

 

해결 방법 - Peterson Solution

-> 앞서 본 두 알고리즘을 복합해서 만든 코드임.

Critical Section의 3가지 조건을 모두 만족함.

 

오우 좋네~~~

 

근데..!! Peterson Solution도 문제가 있음!

Peterson Solution의 한계

1) Peterson Solution의 확장이 가능?

: 즉, 3개 이상의 프로세스에서는 어떻게 구현할 건데...??

 

2) 확장된 알고리즘의 증명은 어떻게 할 건데?

: 어떤 경우에도 동작함을 보여줘야 함.

 

3) 일반적으로 이런 증명은 NP 문제임.

: 즉, 증명이 되더라도 매우 복잡함.

 

4) HW로 처리하면 알고리즘이 매우 간단해짐.

Lock이라는 HW로 해결 가능.

근데... 이거 HW로 구현하면 비용이 많이 듦.

-> 어? 이거 Critical Section에 들어가면서 Interrupt를 disable하게 하면 되지 않음?

-> 아...근데 그거 User 프로그램 수준에서 Interrupt를 컨트롤하는건 바람직하지 않아...

(시스템 성능, 관리적 시점에서 좋지 못함.)

+ 프로세스가 많아지면 문제가 생길 수 있음.(Scalable하지 않음)

-> 동기화를 위한 Instruction이 도입됨.

Synchronization Instruction(동기화 명령)

: CPU에서 지원하여 원자적으로(Atomically: 명령어가 수행되는 동안 방해받지 않음.) 수행되는 명령어를 이용함.

 

Mutual Exclusion with Test-and-Set

Test and Set 명령어를 수행 시에는 어떤 방해도 받지 않음.

-> Test and Set은 인자로 들어온 값을 True로 바꿔주고 들어왔던 값을 return해주는 역할을 함.

false 값인 lock이 프로세스를 진행하면 TestAndSet(&lock)은 false를 리턴하고 내부에선 lock값을 true로 바꿈.

-> critical Section을 진행한 후 lock값을 다시 false로 바꾼 뒤 Remainder Section에 들어감.

 

Mutual Exclusion with Swap

 waiting 배열에서 실행하려는 i번째 프로세스에 대한 값 waiting[i]를 true로 바꿔주고, while문을 통과

-> 이때 lock이 true이면 swap 시 lock도 true, waiting[i]도 true되고 이후 critical section 진행하고, lock 다시 false로 바꾸고, remainder section 진행

-> 근데 만약 lock이 false였다면 swap 결과 waiting[i]가 false가 되어서 while문 빠져나와서 진행 X.

 

 

이런 Instruction 방식의 한계점

1) Mutual Exclusion은 해결되지만 Bounded Waiting은 모두 해결되지 않음.(다음에는 어떤 프로세스가 Lock을 가질지와 같은게 정해지지 않음.)

∴ 이건 User 프로그램이 제공해야 했음.

 

2) Bounded Waiting이 주어진 문제마다 조금씩 차이가 있기에 User 프로그램이 제대로 처리하는 것은 기대 hard...

 

3) 좀 더 포괄적인 동기화 방식이 필요함.

 

Semaphores(세마포어)

: 2개의 우너자적 연산을 가지는 정수 변수

- Wait() or P() : Critical Section에 들어가기 전에 수행됨

- Signal() or V() : Critical Section을 나와서 수행됨.

-> 세마포어는 이 2가지의 원자적인 연산에 의해서만 접근됨. + 이 두 연산은 서로 독립적이고, 원자적으로 수행됨.

(따라서, 하나의 프로세스에서 P를 수행해서 세마포어의 값을 수정하는 동안에는 다른 프로세스에서는 P or V를 수행할 수 없기에 같은 세마포어의 값을 수정하지 못함.)

세마포어 예시

세마포어의 구현 - Busy Waiting

: Critical Section에 진입할 조건이 될 때까지 Loop을 돌며 기다림.

- 단점

1) CPU Cycle을 낭비함.

2) 대기 중인 프로세스 중에서 누가 Critical Section에 진입할지 결정하지 않음.

 

Busy Waiting 방식의 CPU Cycle 낭비 문제 해결하기 위해 등장한게...!!

세마포어의 구현 - Sleep Queue

: 세마포어의 자료구조에 Sleep Queue를 추가하여, 대기 중인 프로세스를 관리함.

-> 세마포어의 값이 양수가 되어 Critical Section에 진입이 가능하게 되면, Sleep Queue에서 대기 중인 프로세스를 깨워 실행시킴.

- list: Critical Section에 들어가기를 기다리는 프로세스 리스트.

- block(): sleep하는 것. 실행 중인 프로세스를 멈추고 다른 프로세스로의 Context Switching 유도함.

- wakeup(p): 프로세스 p를 실행함.

세마포어의 종류

1) Counting Semaphore

- 세마포어의 값은 범위가 정해져 있지 않음.

- 초기 값은 가능한 자원의 수로 정해짐.

 

2) Binary Semaphore

- 세마포어의 값은 0 or 1임.

- Counting Semaphore보다 구현이 간단함.

 

- Binary Semaphore를 이용해서 Counting Semaphore를 구현 가능.

- Binary Semaphore는 test-and-set과 같은 HW의 도움받아 구현 가능.

(세마포어는 P, V operation으로 이루어져있는데 얘네는 atomic해야 함. 그래서 이런 HW의 도움을 받아서 구현할 수 있다.)

 

Binary Semaphore의 구현

- Test and Set 명령어로 구현함.

- Semaphore S: 현재 Critical Section에 진입한 프로세스가 있는지 나타냄.(T / F)

 

P(S)

- while(test_and_set(&S));

- S의 값이 return되고 S는 true로 바뀜.

(즉, S가 false이면 while로 loop안 돌고 바로 Critical Section 진입함. 근데 만약 S가 true이면 while로 계속 loop 도는게지...!)

 

V(S)

-  S = false;

- 진입한 프로세스가 없음으로 바뀌기에 wait()에서 대기 중인 프로세스를 진입 가능하게 함.

- V가 실행된다는 것은 Critical Section에서 실행 중인 프로세스가 없다는 것을 의미함.

 

Counting Semaphore의 구현

이때,

S1: C를 위한 세마포어

S2: block / wake up을 위한 세마포어

 

Semaphore의 구현

1) 커널이 Single Thread인 경우

- P / V를 System Call로 실행.

- 커널 내에서 세마포어의 동작을 구현함.

- 커널 내의 수행이 Non-Preemptive하므로, 커널에 들어간 것 = Critical Section에 들어간 것.

 

2) 커널이 Multi Thread인 경우

- P / V를 System Call로 실행.

- 커널 내에서 별도로 동기화 작업이 필요함.

세마포어의 단점

1) Deadlock이 발생할 가능성이 있음.

2) P와 V의 연산이 분리되어 있기에 잘못 사용 시에 대책이 없음.

- High-level 언어에서 동기화를 제공하는 방법이 필요해짐.

Deadlock

: 2개 이상의 프로세스들이 끝없이 이벤트를 기다리고 있는 상황으로 그 이벤트는 기다리고 있는 프로세스만이 발생시킬 수 있음.

P0가 S를 가져가고 P1이 Q를 가져간 상태 - P0에서 Q를 가져가려는데 아직 P1에서 풀어주질 않음, P1에서 S를 가져가려는데 아직 P0에서 풀어주질 않음 - 무한 대기

 

이런 Deadlock 없는 방법 없음?!!?!?!?!!?!?!?!?!?!

그래서 나온게...!!

Monitor

: High-level 언어에서의 동기화 방법.

- 한 순간에 하나의 프로세스만 모니터에서 활동하도록 보장.

- 유저 레벨에서는 P / V 연산없이 Procedure를 호출하는 것만으로도 동기화 해결 가능.

(세마포어 중 멀티 쓰레드 커널에선 커널 내에서의 동기화도 해야 하므로 P,V를 잘 사용해야 함. 즉, Deadlock을 방지하기 위한 책임이 프로그래머에게 있음. 근데 모니터는 따로 동기화 해결이 필요가 없으니까 얼마나 편하냐~~!?~~!?)

 

세마포어와 모니터의 차이

1) 모니터는 Java에서 모든 객체에 기본적으로 제공하지만, C에서는 사용이 불가능함.

2) 세마포어는 프로그래머가 Mutual Exclusion및 정렬 목적으로 사용 시 Counter 변수값을 지정하는 불편함 있지만,

모니터는 이런 기능들이 캡슐화(synchronized, wait, notify 등의 키워드)되어 있어서 동기화에 용이함.

Monitor 코드 예시

프로세스들이 Queue에 들어가고 각각은 Shared Data를 쓰기 위해operation으로 condition(false 시 wait, true 시 Procedure들 진행)을 확인 후 Procedure를 진행한다.

 

Monitor 예시: DB의 Transaction

하나의 트랜잭션이 실행될 때 다른 트랜잭션의 개입으로 인해 값이 바뀌면 트랜잭션이 값을 보장할 수가 없음.

∴  트랜잭션의 실행 시 Monitor를 통해 트랜잭션 단위로 반드시 완전히 수행되도록 보장함.