semaphore 와 monitor 로 synchronization 해결하기
Synchronization 에서 Semaphore를 이용해서 해결할 수 있는 전형적인 문제들
생산자-소비자 문제, bounded-buffer problem
readers and writers problem
식사하는 철학자 문제, dining-phillosophers problem
Semaphores
앞의 방식들을 추상화시킨다.
Semaphore S
interger value
P(S) : S가 양수일 경우, 이를 감소시키면서 자원을 획득하는 연산과정
V(S) : 자원 반납의 연산 과정
값이 1로 초기화 : lock
값이 1이 아니면 : 남아있는 자원의 개수를 세는 역할을 함
Block and wakeup 방식으로 구현됨
문제 1. Bounded Buffer Problem
버퍼의 크기가 유한한 환경에서 생산자-소비자 문제가 발생할 수 있음
복수의 생산자 프로세스와 복수의 소비자 프로세스가 있음
발생할 수 있는 문제
배타적 접근의 문제 : lock을 걸고 풀어야 하는 문제
버퍼 가용 자원의 수를 관리하는 문제 : 생산자와 소비자의 수가 불균형한 문제
버퍼가 full 상태일때 버퍼를 비우는 소비자가 나타날떄까지 생산자는 기다려야한다.
버퍼가 empty 상태일때 버퍼를 채워주는 생산가자 나타날때까지 소비자는 기다려야한다.
해결방법
생산자와 소비자는 각각 5가지 정도의 작업을 순차적으로 수행하여 문제를 예방한다.
sudo code
변수
full 개수
empty 개수
mutex : lock
P 연산 : 자원획득
V 연산 : 자원 반환
문제 2. readers and writers problem
한 프로세스가 DB 에 write 중일 때, 다른 process 가 접근하면 안된다.
read는 동시에 여럿이 해도 된다.
해결방법
writer 가 db에 접근 허가를 아직 얻지 못한 상태에서는 모든 대기중인 reader 들을 다 DB 에 접근하게 해준다.
writers는 대기중인 reader 가 하나도 없을 때 DB 접근이 허용된다.
일단 writer 가 db에 접근 중이면 reader 들은 접근이 금지된다.
writer 가 db에서 빠져나가야만 reader의 접근이 허용된다.
shared data
db 자체
readcount : 현재 db에 접근 중인 reader의 수
synchronization variables
mutex : 공유변수 readcount를 접근하는 코드(critical section)의 mutext exclution 을 보장하기 위해 사용한다.
db : reader와 writer 가 공유 db 자체를 올바르게 접근하게 하는 역할
if (readcount==1) P(db): 최초의 reader 만 writer 를 막기 위해서 lock 을 걸고, 나머지 reader 에 대해서는 접근을 허용해준다.starvation 문제 발생의 가능성이 있다.
만약에 도착 순서가 : reader → writer → 100 개의 readers 라면,
첫번째 reader 에 의해서 db 는 lock 될 것이고, writer 는 우선 기다릴 것이다.
이후에 도착한 reader 들은 계속 db 접근이 가능하므로 읽을 것이다.
하지만 writer 가 기다리는 동안 계속 해서 reader 가 도착한다면, writer 의 대기시간은 무한정 길어질 수 있다.
starvation에 대한 해결 방법이 있을까?
reader queue 에 우선순위를 두어, 어느정도 선까지 도착한 reader 만 허용하고, db 자원을 반납해 writer 가 들어올 수 있도록 해준다.
마치 신호등이 있어서 끊임없이 오는 차들을 잠시 막고 사람들이 틈틈히 건너갈 수 있도록!
문제 3. 식사하는 철학자 문제, dining-phillosophers problem
다섯명의 철학자가 원탁에 둘러 앉아 토론을 하고 있다.
그들이 하는 일은 두가지이다. 생각하거나 밥을 먹거나.
각 철학자들은 배가 고픈 시점이 제각각이다.
밥을 먹기 위해서는 젓가락 두쪽을 모두 잡아야 한다. 젓가락은 왼쪽과 오른쪽 두 곳으로 나누어져 있다.
발생할 수 있는 문제점
deadlock 가능성이 있다.
모든 철학자가 동시에 배고파서 왼쪽 젓가락을 동시에 잡았다면, 아무도 오른쪽 젓가락을 잡을 수 없어서 무한 대기하는 상황이 발생하게 된다.
해결방안
4명의 철학자만이 테이블에 동시에 앉을 수 있도록 한다.
젓가락을 두개 모두 잡을 수 있을 때에만 젓가락 잡을 수 있게 한다. → 권한
비대칭 : 짝수 철학자는 왼쪽 젓가락부터 잡고, 홀수 철학자는 오른쪽 젓가락부터 잡을 수 있도록 한다.
식사하는 철학자의 경우, semaphore 보다 monitor 코드가 더 이해하기에 쉽다.
권한을 두어 해결하는 방법의 예시 코드
일반적인 semaphore 코드는 자원의 개수를 세고 초기값을 두는경우가 많은데, 아래의 코드는 0의 상태에서 진행된다. → semaphore 코드답지 않다고 느끼는 이유
Monitor
semaphore 의 문제점
코딩하기 힘들다
문제가 생겼을 때, 버그잡기가 쉽지 않다.
한번 실수가 모든 시스템에 치명적인 영향을 끼친다.
정확성의 입증이 어렵다.
자발적 협력이 필요하다.
monitor
동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high level synchronization construct
모니터 내부에 공유데이터와 공유데이터에 대한 프로시저를 정의하고 프로시저를 통해서만 접근을 가능하게 한다.
모니터 내에서는 한번에 하나의 프로세스 만 활동이 가능하다.
프로그래머가 동기화 제약 조건을 명시적으로 코딩할 필요가 없다.
semaphore 는 lock 를 걸고 해제하는 작업을 프로그래머가 직접 해줬어야 하는데, monitor 는 설계 자체가 동시접근이 안되도록 되어있기 때문에 개발자가 할 작업이 줄어든다.
프로세스가 모니터 안에서 기다릴 수 있도록 하기 위해서 condition variable 을 사용한다.
condition x, y;
condition variable 은 wait() 와 signal 연산에 의해서만 접근이 가능하다.
x.wait() 을 invoke 한 프로세스는 다른 프로세스가 x.signal() 을 invoke 하기 전까지는 suspend 된다.
x.signal() 은 정확하게 하나의 suspend 된 프로세스를 resume 한다. suspend 된 프로세스가 없으면 아무일도 일어나지 않는다.
waiting 을 하는 줄이 하나의 목적에 따라서 여러갈래로 나뉜다.
비교 1. bounded-buffer problem : semaphore vs. monitor
비교 2. 식사하는 철학자 문제 : semaphore vs. monitor
비교 : semaphore vs. monitor
사실 semaphore 와 monitor 버전의 코드는 상호 변환이 용이하다.
| semaphore | monitor | |
|---|---|---|
값 | 있음 | 없음 |
동시접근 | 자원을 획득하기 위해 프로그래머가 P연산, V연산을 해주어야 한다. | monitor 차원에서 지원해주어 프로그래머가 신경쓰지 않아도 된다. |
Last updated
