Race Condition
race condition 이란 두 개 이상의 프로세스가 공통 자원을 사용할 때, 접근 순서에 따라 다른 결과가 발생하는 현상을 일컫는다. 즉, 두 개의 스레드가 하나의 자원을 놓고 경쟁하는 상황을 말한다. 이를 해결하는 방법 3가지를 알아보자.
Mutual Exclusion
race condition 을 막기 위해서는 두 개 이상의 프로세스가 동시에 하나의 자원을 사용할 수 없도록 막아야한다. 한 프로세스가 공용 데이터를 사용하고 있으면, 그 동안은 다른 프로세스가 해당 자원을 사용할 수 없도록 막아햐 한다. 이것을 상호 배제(Mutual Exclustion) 이라고 한다.
Progress
아무도 CS 에 있지 않은 상탱서 CS 에 들어가고자 하는 프로세스가 있으면 CS 에 들어가게 해주어야한다. turn 변수를 활용한 엄격한 교대 알고리즘은 이 조건을 충족하지 못한다.
Bounded Waiting
프로세스가 CS 에 들어가려고 요청한 후부터 그 요청이 허용될 때까지 다른 프로세스들이 CS 에 들어가는 횟수에 한계가 있어야한다. (기다리는 시간의 유한성 보장)
Peterson 알고리즘
flag 와 turn 변수를 활용한다. 상대가 flag 를 들고있고, 이번에 상대방 차례임을 둘 다 만족할때 계속 기다린다. 그리고 빠져나올 때 flag 를 내려놓는다. 이는 위의 3가지 조건을 모두 만족시킨다.
하지만 이 코드 또한 Busy Waiting(spin lock) 이라는 문제가 있다. 즉, 계속 CPU 와 메모리를 사용하면서 While 문을 돌며 기다린다는 것이다.
Test and Set
위의 고급언어 하나 하나를 실행하는 동안 전체 동작이 되기 전에 CPU 를 빼앗길 수 있는 상황을 고려해야되다보니 코드가 길어진다. 하지만 하드웨어의 도움을 받은 Test and Set 명령어를 사용하면 코드를 단축시킬 수 있다.
Test and Set 명령어는 특정 변수 값을 읽어들이고, 1 로 그 값을 세팅하는 작업을 atomic 하게 동작 가능한 명령어다.
Semaphores(세마포어)
세마포어 S 는 일종의 추상 자료형이다. 세마포어에는 두 가지 연산이 존재한다. P 연산과 V 연산이다. 또한 공유자원의 획득과 반납을 세마포어를 통해 처리할 수 있다.
P 연산은 공유데이터를 획득하는 과정이고, V 과정은 공유데이터를 반납하는 과정이다. S 는 정수 값을 가질 수 있는데, 이는 자원의 갯수다. 만약 S = 5 면 현재 자원이 5개라는 것이다. 따라서 P(S) 연산을 5 회 감당할 수 있다.
락을 걸고 푸는 과정은 세마포어 S = 1 인 경우를 생각하면 된다. 이 상황에서 P(S) 는 락을 거는 연산일 것이고, V(S) 는 락을 푸는 연산일 것이다.
세마포어 변수 S 에 대해서 P(S) 연산을 하게된다면 S 값이 0 이하인 동안에 while 문을 돌려서 아무것도 안하며 기다리게 된다. 누군가가 자원을 반납하여 S 값이 양수가 되면, P 연산을 통해 자원을 획득한다. 사용이 다 끝나면 V(S) 연산을 통해 자원을 반납한다.
위의 과정에서 P(S) 와 V(S) 연산은 atomic 하다는 것을 가정해야한다. 하지만 이 역시 busy waiting 문제는 발생한다. while 문을 계속 돌아야 하기 때문이다.(spin lock)
하지만 세마포어는 busy waiting 방식으로만 구현해야 하는 것이 아니다. block and wakeUp 방식으로 구현할 수 있기에, 이는 sleep lock 구현이라고 한다.
만약 세마포어를 획득할 수 없으면 해당 프로세스를 block 시키고 해당 프로세스의 PCB 를 세마포어에 대한 wait queue 에 넣는다. 이후 누군가가 세마포어를 사용하고 나서 반납하게 되면 block 된 프로세스중 하나를 wakeUp(P) 하여 깨운다.
sleep lock 방식에서는 P(S) 연산 도중 자원이 있다면 실행이 되고, 자원이 없다면 해당 프로세스는 block 된다. V(S) 연산은 자원을 반납하고, 잠들어있는 프로세스가 있다면 wakeUp(P) 를 실행한다.
이 방식에서는 S 의 의미가 조금 다르다. S 값이 음수라면 현재 누군가가 자원을 기다리고있다는 의미가 되고, 양수라면 자원에 여분이 있다는 의미가 된다. 단순 갯수를 의미하지 않는다.
CS 의 길이가 매우 짧은 경우는 busy waiting 방식이 오버헤드가 적어 적절할 수 있지만, 대부분의 경우 block-wakeUp 방식이 더 좋다.
0 와 1 값만 가질 수 있는 바이너리 세마포어는 mutex 라고 부른다. 또한 세마포어 변수의 값이 더 높은 경우는 counting 세마포어라고 한다. 자원의 수가 여러개여서 여분이 있는 경우를 말한다.
Deadlock 과 Starvation
세마포어를 사용할 시 조심해야한다. P 와 Q 두 가지 자원을 모두 획득해야 실행가능한 프로세스 2 개가 있는 경우, 서로가 선점한 자원을 기다리면서 무한 대기 상황에 빠지는 경우를 DeadLock(교착 상태) 이라고 한다.
해결을 위해서는 자원의 획득 순서를 정해두는 방법을 사용하면 된다. P 를 획득한 후 Q 를 획득해야되는 명확한 순서가 있다면, 위의 문제를 해결할 수 있다.
특정 프로세스가 자원을 얻지 못하고 무한 대기하는 현상을 starvation 이라고 한다. dead lock 또한 starvation 의 일종이다. 여기서 특별히 이야기하는 starvation 은 특정 프로세스끼리만 자원을 독점하며 다른 프로세스는 영원히 대기하게 만드는 현상을 말한다. Dining-philosophers 문제가 대표적인 사례다.
