Synchronization?
프로세스나 스레드가 동일한 shared resoure에 access하지 못하도록 하는 것이다.
두 프로세스가 하나의 변수에 접근해서 각자 값을 바꿔버리면 안될것이기 때문이다. 아래 예시를 보자.
ATM에서 돈을 인출하는 process인데, synchronization에 대한 고려가 없이 프로그래밍 되어있다.
즉, A와 B라는 프로세스가 있으면 둘 다 동시에 withdraw함수와 변수에 접근할 수 있는 것이다. 근데 만약 두 사람이 동시에 다른 지점에서 돈을 전부 인출하면?
두 프로세스 모두 잔액이 있다고 판단하므로, 은행은 막대한 손해를 볼 것이다.
이런 상황을 race condition이라고 한다.
따라서 멀티 프로세스/스레드 프로그래밍에서 synchronization에 대한 고려는 필수인데, 이것이 어떻게 수행되는지 알아보자.
Synchronization Tool의 요구사항
동기화를 시켜주는 여러 tool들을 알아볼 것이다. 그 tool들에게 공통적으로 요구되는 사항은 당연히,
'한 프로세스가 critical section(shared resource)을 수행하고 있을 경우, 다른 프로세스는 그 section에 access 할수 없게해야한다'는 것이고, 이를 Mutual Exclusion라고 한다.
synchronization을 구현하는 여러 방식들이 있다.
-
Locks
-
Mutex lock
-
Semaphore
-
Monitors
이중 Locks는 Low-level, 즉 OS 레벨에서 사용하는 방식이고 나머지는 High-level, 즉 application 레벨에서 사용하는 synchronization 방식이다.
Locks
- 프로세스 또는 스레드가 critical section(임계 영역) 에 들어가면 lock을 호출하여 다른 프로세스의 access를 막고, 나갈때 unlock한다.
위 그림을 보면 T1 스레드가 critical section에 들어가면서 lock을 걸었기 때문에
T2 스레드는 waiting상태가 된 것을 볼 수 있다. 그리고 T1의 할 일이 끝나면 T2의 access가 가능해진다. 이제 lock을 뜯어보자.
가장 쉽게 생각할 수 있는 방식이다. held가 1이면 이미 다른 프로세스가 실행중인 상태이므로, 무한루프를 돌게된다. held가 0이면 값을 1로바꾸고 빠져나가서 하던 일을 수행한다. 이와 같은 방식을 spin lock 방식이라고 한다.
하지만, 위 방식은 잘못됐다.
held값을 판별하는 도중 interrupt가 걸리면 held값이 1로 바뀌기 전이므로, 역시 critical section에 두개의 쓰레드가 들어가는 경우가 발생하기 때문이다.
따라서,
- Hardware Atomic Instruction
1-1) Test-and-Set
1-2) Compare-and-Swap - Disabling Interrupt
와 같은 방식을 쓴다.
1. Haredware Atomic Instruction
cpu instruction으로 lock을 구현하는 방식으로,
Test-and-Set, Compare-and-Swap 방식이 있다.
i) Test-and-Set
먼저 Test-and-Set 방식은 held값의 판별과 held를 1로만드는 작업을,
하나의 cpu instruction으로 처리해 버리는것이다.
그러면 중간에 interrupt에 걸릴 일이 없다.
ii) Compare-and-Swap
하지만 실제로 사용되는 방식은 Compare-and-Swap이다. (intel x86에서 사용)
위와 원리는 비슷하지만 key라는 true값과 held의 값을 바꿔주는 것이다.
※ spin lock방식은 무한루프를 돌게 해 cpu 낭비가 심하므로, Application이 아니라 OS만이, 짧은 critical section에 사용해야한다.
2. Disabling Interrupt
이 방법은 애초에 interrupt가 걸려 다른 프로세스가 진입하는게 문제이니, 아예 interrupt를 못걸게, 또는 interrupt를 지연시키는 것이다.
※ interrupt 는 모든 cpu로 가므로, single-cpu일때만 사용한다.
cpu가 두개 이상이면 Compre-and-Swap방식 사용!
