[운영체제] Concurrency: Mutual Exclusion and Synchronization - 3

Semaphore

 

- 시그널을 위해 세마포어라고 불리는 특수 변수들을 사용한다.

- 시그널이 전달될 때까지 프로세스는 suspend가 된다.

 

 

Semaphore는 integer 변수 s로 나타내며 가능한 연산은 다음과 같다.

 

- Initialization : 음수가 아닌 값으로 초기화

 

- Wait : 세마포어 값을 감소, 만일 값이 음수가 되면 semWait을 호출한 프로세스는 블록, 음수가 아니라면 프로세스는 계속 수행

 

- Signal : 세마포어 값을 증가, 값이 양수가 아니면(0이거나 음수면), semWait 연산에 의해 블록된 프로세스들을 깨운다.

 

 

 

 

 

 

 

 

예시1

프로세스 A,B,C를 세마포어를 사용해 구현한 것이다.

 

 

1. 세마포어가 1이기 때문에 A에서 Semwait()을 호출하면 lock 값이 1 감소되어 0이되고 프로세스 A를 ready queue에 놓은 뒤 A를 수행한다. (ready queue -> running)

 

2. A가 수행중에 B가 만약 수행이되려하면 B에서도 Semwait을 호출해 lock 값이 -1 감소되어 lock 값이 -1이되어버려 

프로세스 B가 blocked queue에 들어가게 된다. 

 

3. 마찬가지로 프로세스 C도 2번과 같은 행동을 한다. (lock값은 -2)

 

4. 프로세스 A가 임계영역에서 수행을 다 끝내면 semSignal()을 호출하여 1 증가하여 lock값은 -1이되고 A를 다시 ready queue에 놓는다. 그 뒤에 B를 ready queue에 놓고 수행한다.

 

5. 같은 방식으로 작동한다.

 

위 그림을 통해 알수 있는 것은

 

Semaphore 값이 0보다 크거나 같을 때

- Semaphore 값 = block 되지 않고 semWait을 수행해서 무사 통과할 수 있는 프로세스의 개수

 

Semaphore 값이 음수일 때

- Semaphore의 절댓값 = semaphore queue에서 기다리고 있는 프로세스의 개수

 

 

 

큐에 여러 프로세스들이 연결되어 있을 때 무슨 프로세스부터 깨워야 하는가?

Strong semaphore : 선입선출(FIFO)의 정책을 사용하여 가장 오래 블록되어 있던 프로세스부터 깨운다. -> starvation이 발생하지 않음

Weak semaphore : 큐에서 제거되는 순서를 명시하지 않음 -> starvation이 발생할 수 있음

 

 

Semaphore를 사용하면 Busy-Waiting도 없고, Starvation도 해결하게 된다.

 

Compare & Swap을 할때는 while();를 통해 while문이 참이 될때 까지 변수를 테스트하는 명령을 반복실행 하지만,

세마포어는 semWait, semSignal을 통해서만 수행하기 때문에 Busy-Waiting이 없다.

 

 

 

Producer & Consumer Problem

 

Strong semaphore 예시2

 

 

1. s = 1인 상태에서 프로세스 A가 스케줄링되어 프로세스 A가 수행중이다. A는 semWait을 호출하여 s가 1감소하여 s=0이되고, ready queue에 들어가게 된다.

 

2. 다음 B가 스케줄링되어 B역시 semWait을 호출하면 s = -1 이되어 B가 blocked queue에 들어가게 된다.

 

3,4. 그 후에 프로세스 D가 스케줄링되어 D는 producer기 때문에 semSignal을 호출한다. 그러면 다시 s=0이되고 프로세스 B를 blocked queue에서 ready queue로 가져온다.

 

5,6. 그후 C가 수행되지만 semWait을 호출하여 -1이되므로 C를 blocked queue에 보내고 A,B도 똑같은 방식으로 blocked queue에 보내진다.

 

7. 다시 D가 수행되면서 semSignal을 호출하여 blocked queue에 있던 C를 호출한다.

 

 

 

- 하나 또는 그 이상의 생산자는 데이터를 생성하고 이것을 버퍼에 저장한다.

- 소비자는 한번에 하나씩 버퍼에서 데이터를 꺼내 소비한다.

- 버퍼 접근이 중첩되어서는 안된다.

 

버퍼가 가득차면 생산자는 버퍼에 데이터를 추가하지 않아야한다.

버퍼가 비어있다면 소비자는 데이터를 제거하지 않아야한다.

 

 

 

 

 

생산자와 소비자의 작업을 가상 코드로 표현하면 위와 같다.

 

* in <= out이면 소비자가 생산자를 앞서가는 것이므로 빈 공간에서 데이터를 꺼내가는 것이기에 do nothing을 처리해준 것이다.

 

 

그림으로 나타내면 다음과 같다.

 

 

Infinite Buffer

 

위 무한버퍼에서 문제점은 빈 버퍼에서 생산자 프로세스먼저 실행될 경우 in == out이 같기 때문에 아무것도 수행을 하지 않는다.

 

그래서 이를 해결하기위해 n이라는 변수를 추가하여 아래와 같이 나타낸다.

 

 

 

 

Finite Buffer (Circular Buffer)

유한 버퍼를 사용하는 경우 다음과 같이 나타낼 수 있다.

생산자의 역할은 in+1 을 n값으로 나눈 것이 out의 인덱스와 똑같다면 큐가 full인 상태이므로 아무것도 수행하지 않고,

아니라면 in에 생산한 v 값을 저장하고 in을 1 증가시킨다.

 

소비자의 역할은 in과 out이 같다면 큐가 empty 상태이므로 아무것도 수행하지 않고, 아니라면 out에 있는 값 w를 소비한다 그 뒤 out을 1 증가시킨다.

 

 

 

 

 

하지만 위의 코드에서의 문제점은 만약 생산만 계속할 경우 버퍼가 가득 찼는데도 계속 생산할 수 있다는 것이다.

 

이를 막기위해 e 라는 변수를 추가해 버퍼의 크기를 저장해 생산할때마다 1씩 줄어들게하는 것이다.

 

 

위와 같이 설계를하고 생산만한다고 가정했을 때, 버퍼의 크기는 16이므로 1씩 줄어들게 하는 것이다. 그렇게 되어 꽉차게 되면 버퍼의 크기는 0이 되어 만약 생산하려고 semWait(e)을 호출하면 -1이 되므로 blocked될것이다.

그렇기 때문에 위 코드로 구현할 수 있다. 

 

 

 

 

---

What If

위 무한버퍼 코드에서 생산자의 semWait()과 semSignal()을 바꾸면 어떻게 될까?

 

 

 

-> Mutual Exclusion 발생!!

 

 

 

semWait(n) 과 semWait(s)를 바꾸면 어떻게 될까?

 

-> Deadlock 발생!!