동기화_Low Level Synchronization Tools(Spin Lock, Disabling interrupts)

Synchronization Tools

여러개의 프로세스(스레드)들이 공유자원에 동시에 접근하여 비의도적으로 공유자원의 값이 변경되거나 오염되는 상태를 Race Condition이라고 합니다.  이를 해결하는 방법론이 Synchronization(동기화)이며, 어떠한 프로세스가 critical section을 실행하고 있을 때 다른 프로세스는 critical section에 접근할 수 없도록 하는 개념입니다.

(자세한 설명은 여기에)

 

이번 포스팅에서는 OS level에서 사용하는 동기화 방법들에 대해 소개합니다.

 

 

Low Level mechanism

Spin Lock(+ Hardware atomic instructions)

 

 

Critical Section을 보호하는 가장 기본적인 방법은, critical section이 시작할 때 lock()을 걸어 다른 프로세스가 진입하지 못하도록 하는 것입니다. 프로세스가 critical section을 모두 수행한 이후에는 unlock()으로 자물쇠를 풀어주면 됩니다. 

 

lock()과 unlock()의 구조는 다음과 같습니다. critical section이 잠겨있으면 held = 1, 열려있으면 held = 0 인 상태가 됩니다.

 

 

특정 프로세스가 critical section에 진입할 때(lock에 진입) 이를 실행하고 있는 다른 프로세스가 없다면 held 변수는 0일 것입니다. 그렇다면 while 문을 바로 빠져 나와 critical section 으로 진입하고 held = 1이 됩니다.

 

특정 프로세스가 critical section에 진입할 때 이를 실행하고 있는 다른 프로세스가 있다면 held 변수는 1일 것입니다. 다른 프로세스가 unlock()으로 held 값을 수정할 때까지 while 문 안에서 대기하다가 대기가 끝나면 held 값을 1로 바꾸고 critical section에 진입합니다. 

 

언뜻보면 이러한 방식이 꽤 합리적으로 보이지만, 치명적인 문제점이 있습니다.

분명 critical section을 보호하기 위해서 held 변수를 만들었습니다. 그런데, held 변수 조차 공유 자원이 되어 synchronization problem이 발생하게 됩니다. lock() 함수에서 while ()문과 l->held = 1 사이에 contextswitching이 일어날 경우, 동시에 두가지 프로세스가 critical section에 진입할 수 있게 됩니다. 

 

이러한 문제를 해결하는 방법이 Hardware atomic Instruction 입니다.

운영체제 버전에 따라 Test and Set, Compare and Swap 등 다양한 버전이 있지만, 공통된 개념은 while (1->held) 와 l->held = 1를 하나의 instruction으로 만들어 두 코드의 중간에 interrupt가 발생하지 않도록 하는 것입니다. Hardware automic instructions 은 CPU의 지원을 받기 때문에 CPU dependency가 높습니다. 

 

 

Spin Lock 방법은 critical section을 수행하고 있는(공유 자원을 사용하고 있는) 프로세스가 unlock() 신호를 보낼 때까지 while 문을 돌며 대기합니다. while 문을 돌며 빙글빙글 도는 방식을 busy waits, spin lock 으로 표현하는데, 이러한 방식은 cpu utilization이 떨어져 OS level에서만 사용합니다. 

 

 

Disable/Re-enable interrupts

 

Race condition 문제가 발생하는 근본적인 이유를 생각해보면, critical section을 실행하고 있는 동안 context switching이 일어나기 때문입니다. Disable/Re-enable interrupts는 Critical section에 진입할 때 interrupt 기능을 끄고, 탈출할 때 interrupt 기능을 켜서 해당 섹션이 수행되는 동안 context switching을 완전히 차단하는 방법입니다.

 

 

일반적으로, lock() 함수에는 cli()(clear interrupts), unlock() 함수에는 sti() (set interrupts) 시스템 콜을 사용합니다. Interrupt를 끄고 켜는 것은 User application이 아닌 OS의 권한이기 때문에 해당 방식 또한 OS level에서만 사용합니다.