- 세마포Semaphores 란
- 동기화를 위한 알고리즘과 atomic 연산을 통해서 Mutual Exclusion를 해소할 수 있음.
- 한편, 이러한 알고리즘을 계속 구현하기보다, 해당 알고리즘을 자료형태로 추상화하여 개발을 좀 더 편하게 함.
- 세마포의 구현
- atomic한 변수를 사용(S--)하는 P연산과 변수를 반납(S++)하는 V연산을 통해 경쟁 상태를 해소.
- 한편, loop로 인한 busy-wait 문제가 발생(spin lock). block과 wakeup 방식으로 sleep lock을 구현하여 busy wait 문제를 해소
- 세마포로서 int value와 세마포를 대기하는 process queue로 구성한다. process queue에는 프로세스의 pcb를 값으로 한다.
- 세마포는 음수가 될 수 있으며, 음수는 queue에 대기 중임을 의미한다. 해당 queue는 반복문을 통해 세마포 값이 반환되기를 기다리기 보다, queue에 pcb의 값을 넣고 block을 통해 sleep 상태에 진입시킨다. 그리고 V연산에서 반납되는 값이 있으면, 하나의 프로세스를 wakeup 하여 연산한다.
- spin lock은 cpu를 사용하는 문제가 있지만 sleep은 sleep, wakeup, 배열의 구현 등 오버헤드가 발생한다. 임계 지역의 길이가 짧으면 전자, 아닐 경우 후자를 사용하지만, 대체로 block/wakeup을 사용한다.
- 세마포와 DeadLock, Starvation
- 둘 이상의 프로세스가 세마포를 차지하기 위한 경쟁 상태에 놓여있는 상태를 의미한다.
- 프로세스 P0은 세마포 S와 Q를 동시에 소유해야 끝나는 작업이 있고 프로세스 P1은 Q와 S를 동시에 소유해야 끝나는 작업이 있다고 가정하자. 그리고 각각 S와 Q를 소유하고 있다. 그럴 경우 영원히 끝나지 않는 상태에 놓인다.
- 이 경우 세마포의 소유를 프로세스 서로가 S, Q 순서로 가지게 되면, 문제가 발생하지 않는다.
- 앞서의 데드락 문제 역시 일종의 Starvation으로 볼 수 있다. 그러나 세마포의 Starvation은 특히 다른 프로세스가 세마포를 독점하고 그 외의 프로세스가 세마포를 차지할 기회를 가지지 못하는 상황을 의미한다.
- 모니터 Mornitor
- 세마포의 획득P과 반환V의 과정, 추상화된 P와 V 연산 방식 등은 세마포를 다소 어렵게 만든다. (실수로 V연산을 삽입하지 아니하면 데드락 발생)
- 모니터는 세마포의 소유와 획득과정을 모니터 자체 내에서 처리하기 때문에, 코딩하기에 조금 더 편리하며 잘못된 코딩으로 인한 문제 발생이 세마포보다 덜 하다.
- 모니터는 세마포의 block/wakeup과 유사한 wait/signal을 제공한다. 세마포는 리스트 형태로 사용하지만 모니터는 condition을 정하고, 컨디션과 wait/signal의 조합을 통해 프로세스의 상태가 결정된다. wait 상태의 프로세스는 suspend 상태가 된다.
- 구체적인 내용은 아래의 세 가지 예제로 확인하자.
<동기화에 대한 고전적인 세 가지 문제들>
- Bounded-Buffer Problem
- 유한한 버퍼 문제의 경우 사용자와 소비자가 있고, 각 각이 버퍼에 접근 할 때 mutual exclusion을 보장받아야 하는 경우에 발생하는 문제이다.
- 생산자와 소비자가 있고, buffer 자료 형태의 값이 있으며, 생산자는 Empty 버퍼에 값을 넣어 Full 버퍼를 만들고, 소비자는 Full 버퍼를 제거하여 Empty 버퍼로 만든다.
- 세마포를 통한 해결 방식은 아래와 같다.
- 버퍼의 총 숫자는 empty=n으로 하며 full은 0으로 한다. mutex는 1로 하여 하나의 프로세스만 진입하도록 한다.
- 생산을 완료한 프로듀서 프로세스는 P(empty);로서 empty 버퍼가 있을 때까지 대기한다. 비어있는 버퍼가 발생하면 P(mutex)를 통해 버퍼 전체를 잠근다. 버퍼에 추가하고 락을 푼 후 full을 반환한다. 소비자는 반대로 한다.
- 모니터는 위와 같이 한다. 먼저 buffer의 공간을 배열로서 구성한다. condition은 full과 empty 두 가지로 한다. if 문을 사용하는 등 일반 코딩 문장과 더 유사하다. 세마포를 열고 닫는 과정을 생략하며, wait/signal을 사용하는 것을 확인할 수 있다.
- Readers - Writer Problem
- 독자와 저자의 문제는, read는 값을 변경을 하지 않아 완전성이 보장되므로 다수의 독자가 데이타에 접근하도록 하되, write 작업에 대해서는 해당 데이터에 대한 저자의 독점을 보장받아야 할 때 발생하는 문제이다. 그리고 여기서의 전제 조건 중 하나는 저자는 독자가 한 명도 없을 때 write를 할 수 있다. 그러므로 모든 독자가 사라질 때까지 대기해야 한다. 참고로 이 문제는 DB과 관련이 깊다.
- 세마포의 경우 위와 같은 코드를 사용한다. 한 명의 독자가 들어올 때마다 readcount를 하나 씩 더하여 총 몇 명의 독자가 있는지를 확인한다. 그리고 처음 들어온 독자가 도서관의 문을 열어 세마포인 db가 수정되지 않도록 저자를 block한다. 독자가 나갈 때마다 readcount를 제거하여 마지막 남은 독자가 세마포인 db를 개방한다. 이때 writer는 db에 접근 가능하다. readcount의 경우 동기화 문제가 발생할 수 있음으로 그 과정에 있어서 세마포로 열고 닫는다.
- Dining-Philosopher Problem
- 5명의 철학자가 5명 정원의 식탁에서 식사를 하고 있다. 철학자 사이에는 하나의 젓가락만 있어 총 5개의 젓가락만 있다. 만약 철학자 5명이 동시에 배고파서 각자 오른쪽 젓가락을 하나씩 든 상태이면, 모두 젓가락이 하나만 있기 때문에 식사를 할 수 없다. 그래서 허기를 채우지 못하고 다들 기아 상태에 빠진다.
- 이를 해결하는 방법으로는 젓가락을 두 개만 집을 수 있을 때 젓가락을 집을 수 있도록 하는 방법이다.
- 위의 코드는 세마포를 통한 해결 방법이다. 아래의 코드는 모니터를 통한 해결 방법이다.
JAVA web developer