Semaphores

세마포어가 1이면 하나의 프로세스만 접근 가능하다.

굳이 세마포어 변수를 이용하는 이유는 P와 V연산에 1을 더하고 빼는 것이 원자적으로 연산된다고 가정하는 것이다. 실제 세마포어는 synchronization hardware를 통해 구현된다.

Two Types of Semaphores

Deadlock and Starvation

P0가 S를 얻고 cpu를 빼앗기고 P1이 Q를 갖고 cpu를 빼앗기면 서로를 무한히 기다리게 된다. 이런 문제가 생기는 이유는 작업이 끝나야만 내놓기 때문이다. 자신이 한 자원을 갖고 있어도 제대로 일을 못하면 내놓는게 맞다.

Classical Problems of Synchronization

Bounded-Buffer Problem

producer-consumer problem

생산자가 빈 곳에 넣으려고 하는 순간 cpu를 뺴앗기면 다른 생산자가 해당 위치에 넣을 수도 있다. 그러면 같은 곳에 두번 쓰이게 된다. 소비자 입장에서도 마찬가지다. 따라서 공유 버퍼에 lock을 미리 걸어야한다.

생성자 입장에서는 비어있는 공간이 있어야 버퍼에 채워 넣는다. 생성자 입장에서는 빈 버퍼가 자원이다. 소비자 입장에서는 내용이 들어있는 버퍼가 자원이다.

이런 자원의 개수를 counting semaphore가 관리할 수 있고, binary semaphore를 이용해서 공유 버퍼에 락을 걸고 풀고를 할 수 있다.

P(empty)는 빈 버퍼를 얻는 과정이다. 빈 버퍼가 없으면 기다려야 한다.
P(mutex)는 다른 생산자나 소비자가 접근하는 것을 막는 것이다.

Readers-Writers Problem

공유 데이터에 대한 동시 접근을 막는 것은 DB에서 빈번하게 일어나는 문제다.

reader끼리는 서로 접근을 허용해주지만 writer는 허용해주지 않는다.

readCount가 양수이면 어떤 프로세스가 Read하고 있다는 뜻이다.
readcount에 대한 동시 접근을 막기 위해 mutex를 사용한다.

readcount가 1이라는 것은 내가 최초로 들어왔다는 의미이기 때문에 db에 락을 건다. 만약 readcount가 1초과라면 다른 리더가 있다는 뜻이므로, 락을 안걸로 db에 대한 접근을 한다.
내가 빠져나가는데 만약 마지막이라면 db에 걸려있는 락을 풀어줘야 한다.

reader가 계속 여러개가 오면 writer 입장에서는 starvation이 발생한다.
reader가 오는 족족 읽게 해주는 것이 아니라 신호등 같은 걸로 일정 시간 내에 도착한 reader에게만 허용해주면 문제를 해결할 수 있다.

Dining-Philosophers Problem

다섯명의 철학자가 동시에 왼쪽 젓가락을 집으면 데드락이 발생한다.

self[5]가 젓가락 두짝이 다 available한지 체크하는 것이다. 1이면 가능한 것이다. 초기값은 1이아닌 0에서 시작한다. 테스트해서 두짝다 잡을 수 있으면 1로 바꾼다.

pickup과 putdown함수가 추가되었다.

pickup에 가면 state 공유 변수에 lock을 걸기 위해 mutex가 있다.

테스트를 통과하면 V(self[i]);를 통해서 self[i]를 1로 만들어준다.

Monitor

모니터는 고급 언어 차원에서 제공하는 기능이다.
공유데이터를 접근할때는 monitor안에 있는 procedure를 통해서만 접근하게 하는 것이다.

하나의 프로세스가 공유데이터를 이용하고 있으면 다른 프로세스들을 막아서 entry queue에 세우는 것이다.

condition variable은 semaphore랑 비슷한 것이다. 자원의 여분이 없으면 큐에 줄 서서 block으로 바꿔야하는데 큐의 역할을 하는게 condition 변수다.

Bounded-Buffer Problem

세마포어는 mutex로 공유데이터에 접근하기 전에 락을 건다. 모니터는 락을 걸거나 푸는게 없다. 모니터의 컨디션 variable은 자원의 개수를 세지 않는다. 다만 잠 재우고 줄 세우는 역할만 한다. 모니터에서는 동시에 활성화된 프로세스를 하나로 한정한다.

full.signal은 내용이 들어있는 버퍼를 기다리는 프로세스를 꺠워준다. 없으면 아무일도 일어나지 않는다.

Dining Philosophers Example

condition variable은 양쪽을 다 잡을 수 있는지 알려주는 것이다.

putdown에서는 양 옆 철학자를 테스트하고 밥 먹는 상태를 만들고 깨워서 밥먹게 하는 것이다.

교착상태(deadlock)

The Deadlock Problem

자원은 software자원일 수도 있고 hardware일 수도 있다.

Deadlock 발생의 4가지 조건

네 가지 조건을 모두 만족해야 한다.

Resource-Allocation Graph (자원할당그래프)

R에서 P로 가는 화살표는 P가 R을 차지하고 있다이가 P에서 R로 가는 화살표는 P가 R을 기다리고 있다라는 뜻이다. Resource안에 검은색 점은 자원의 개수이다.

왼쪽에는 싸이클이 있으므로 deadlock이다. R2의 자원이 2개이긴 하지만 싸이클이 두개가 생겼기 때문이다..

오른쪽은 싸이클은 있으나 데드락이라고 확정할 수 없다. 두개씩 있는 자원 중 하나는 싸이클과 무관하기 때문이다. p4가 쓰고 반납하면 싸이클이 없어진다.

Deadlock의 처리 방법

위의 두 개는 예방 방법이고 밑의 두가지는 처리 방법이다.

prevention은 조건 중 하나를 무산해서 데드락을 방지한다는 것이다.
hold and wait을 무산시키는 방식은 기다려야하는 상황에서는 갖고 있는 자원을 내어놓게 하는 것이다.

no preemption을 없애는 방법은 빼앗기게 하면 되는 것이다. 자원 중에서는 뺴앗을 수 있는 자원이 있고 없는 자원이 있다. CPU와 메모리는 빼앗을 수 있는 자원이다. cpu를 뺴앗아도 괜찮은 이유는 그 이후 시점부터 일을 할 수 있기 때문이다.

deadlock prevention은 잘 생기지도 않는 데드락을 예방하고자 자원을 뻇고 하는 과정이 비효율적이다.

Deadlock Avoidance

처음부터 평생 자원을 얼마나 쓸 것인지 알고 있다고 가정하는 것이다.

Resource Allocation Graph Algorithm

점선은 프로세스에서 리소스로 나가는 방향만 있다. 지금은 안필요하지만 나중에 필요할 것이다라는 표시다.

실제 당장 데드락이 아니여도 발생 가능성이 있으면 보수적으로 고려하여 가용자원을 주지 않는 것이다.