동시성 프로그래밍에 대해 다루는 위 링크글에서 이어지는 글입니다.
동시성 프로그래밍 상황에서 특정 자원이 공유되어 있어 경쟁 상태에 놓여 있을 때, nasty synchronization error(번역: 심각한 동기화 오류) 를 유발한다. 실행할 때 마다 다른 결과를 발생시키기도 하기에 프로그램을 짜고 한 번 테스트를 통과했다고 통과된게 아니다. 동시성 스레드들이 반복적으로 호출되어도 항상 같은 결과를 만드는 경우에 스레드-안전(thread-safe) 라고 한다.
공유 변수가 변경되는 과정을 살펴보면 L-U-S 의 과정을 거친다.
- L-oad: 공유 변수를 메모리에서 레지스터(
%rdx)로 load 하는 instruction, 단계이다. - U-pdate: 레지스터(
%rdx)로 load된 값을 update 한다. - S-tore: update 된 공유변수를 다시 메모리에 저장한다.
두 개의 스레드가 한 공유자원을 위와 같은 과정으로 update 하는 상황을 살펴보자.
그림
위와 같이 특정 스레드가 L-U-S 과정을 실행하는 도중에 다른 스레드가 해당 공유 자원에 접근하여 L-U-S 과정을 실행하게 된다면 각 스레드가 한 번씩 L-U-S 과정을 실행했음에도 그 결과는 마지막으로 Store하는 스레드에 의해 마치 한 번 수행된 것처럼 결과가 덮어씌워 지는 현상이 발생한다.
이렇게 공유자원의 L-U-S 되는 과정에서 중첩될 수 있는 영역을 critical 섹션, 영역이라고 한다. 이 크리티컬 섹션에 들어가지 않고 안전하게 실행되도록 하기 위해 고안된 방법이 semaphore 다.
semaphore
동시성 프로그래밍의 개척자인 Dijkstra 다익스트라(자주 등장하시는 대단하신분..)가 위의 언급한 문제를 해결하기 위해 세마포어를 제안하였다. 세마포어는 Window, Unix/Linux OS에서 지원한다.
세마포어는 비음수 정수(s) 값을 갖는 전역 변수로 두 개의 특별한 연산인 P,V 를 통해서만 조작한다.
-
P(s): s가 0 이 아니면P는 s를 감소시키고 즉시 리턴한다. s가 0이라면 s가 0이 아닐 때 까지 suspend 된다. 0이 아니게 되면P(s)수행하며 s를 감소시키고 리턴한다. -
V(s): s를 증가시키는 함수 이다.
위 두 함수를 함께 살펴봐야한다. 특정 공유 자원에 접근하여 update를 할 때 P를 선행해서 실행 한 뒤에 공유자원에 접근하면,다른 스레드는 P를 수행할 수 없음으로 먼저 P를 수행하여 s를 0으로 만든 스레드가 공유 자원으로 관련된 job을 다 수행후, V를 수행하면 다른 스레드가 다시 P를 수행하는 방식으로 사용된다. semaphore가 고안되기 이전 spin lock 이라는 방식에서는 s를 점유하기 위해 대기하는 스레드들이 while문이 돌면서 busy wait하는 방식으로 구현되었으나 semaphore에서는 s를 점유하지 못할 경우 queue에 들어가게 되고, V(S) 를 수행하면 queue에 들어가서 점유를 기다리는 다음 주자가 공유자원을 점유하게 된. 변수 s 하나 당 ready queue 하나가 할당된다. queue임에도 wake-up 순서가 보장되지 않아서 Starvation 현상이 발생할 수 있다. 또한 세마포어를 잘못 사용할 경우 프로세스 A는 프로세스 B가 점유한 세마포어에 의해 실행이 멈춘 상태에서, 프로세스 B 또한 프로세스 A가 점유한 자원을 필요하여 둘다 wait 상태가 될 경우 deadlock (데드락) 현상이 발생한다.
s가 0이상의 정수 값을 갖는 경우 Counting semapheore라고 하며 producer-consumer 문제를 해결하기 위해 사용한다.semaphore의 변수 s를 0과 1만을 사용하는 binary semapheore는 mutex라고 한다. 뮤텍스에서 P를 실행하는 것을 잠근다는 의미로 locking, 푸는 것은 unlocking 이라고 한다. 상호배제나 프로세스 동기화를 위해 사용한다. 또한 semaphore는 P(s)를 실행한 점유한 프로세스외에 다른 프로세스가 V(s) 할 수 있으나 lock의 경우는 점유한 프로세스만이 해당 자원을 V(s) 할 수 있다.
세마포어의 활용
위의 언급된 상호배제 외에도 세마포어를 다음과 같이 활용한다.
- 실행 순서 스케줄링
프로세스 A, B가 있는데 이 둘 사이의 실행 순서를 정해주고자 하는 경우, 세마포어를 선언하고 그 값을 0으로 초기화 한다. 먼저 실행할 프로세스가 V로 세마를 올려주면서 작업을 하게 될 경우, 다른 프로세스가 먼저 스케줄링 되더라도 해당 세마포어가 0으로 초기화가 되어있고 먼저 실행되어야할 프로세스가 실행이 끝날 때 까지 대기상태에 있게 된다.
- 생산자 - 소비자 문제
특정 프로세스들이 버퍼에 문자, 코드, 모듈등을 생산하는 중에 다른 프로세스가 이를 접근하여 사용하려고 하는 경우,
문제가 발생한다. 이를 방지하고자 세마포어를 이용한다.
생산자- 소비자의 관계에서 버퍼가 한개를 이용한다고 생각해보자.
처음 생산자가 M을 생성 후 버퍼를 채운다. 버퍼를 채우기 전에 다른 프로세스가 소비하지 못하게 막고, 생산이 끝난 후 소비자가 소비할 수 있게한다. 소비하는 프로세스는 소비 도중에 생산자가 접근하여 다른 값을 생산하고 덮어쓰지 못하도록 막는다. 소비가 끝나면 다시 생산자가 생산할 수 있도록 세마포어 점유를 내려놓는다.
이번에는 생산자와 소비자가 n 개의 버퍼를 이용하는 상황이다. 버퍼는 여러개지만 한 프로세스만 생산, 소비해야한다는 접근방법은 동일하다. 이 경우 세마포어를 이중으로 사용하는데, 바깥 세마포어는 생산, 소비를 한 프로세스만 하도록 하기 위함이며 내부 세마포어는 n개의 버퍼가 몇 개가 채워졌고, 몇 개가 비어있는지 확인한다. 이 경우 내부 세마포어는 0, 1의 변수가 아닌 0~n의 변수를 갖게 된다.
- 읽기 - 쓰기 문제
read & write 관계에서는 작성할 때는 작성하는 프로세스 외에는 어느 스레드도 접근하여선 안되지만, read의 경우는 여러 스레드가 동시에 read 하여도 무방하다. 따라서 write를 할 때는 write semaphore를 점유하고 write가 끝나면 이를 반환한다.
read 같은 경우에는 읽게 되는 read 프로세스의 수를 체크한다. 읽으러 들어가는 read 프로세스의 수를 하나씩 올리며 읽고 읽은 작업이 끝난 경우 read 프로세스의 수를 내린다. 이 수를 올리고 내릴 때는 이 count 값이 thread-safe하도록 세마포어(rmutex)를 걸어주고, reader 가 0이 되는 경우에만 write가 가능하도록 세마포어(wmutex)를 이용하게 된다.
reference
CSAPP 책 12장 - 동시성 프로그래밍
필기자료 & 강의 참고
https://www.youtube.com/watch?v=CitsUz-Dx7A&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=16
