Chapter 5-4. Concurrency : Mutual Exclusion and Synchronization

Semaphore

• semWait : Process 를 Block 시킬 수 있는 명령어이다.
• semSignal : 내가 아니라 Queue에 있는 프로세스를 Ready로 옮겨 실행할 수 있게 해준다.

Semaphore는 Critical Section뿐 아니라, 많은 동기화 문제에 사용된다.
↳ 특히 Critical Section을 다룰 때는 무조건 초기 세마포 변수 값을 1로 설정해야 한다!

• Race Condition : 실행 순서에 따라 결과가 어떻게 될지 모르는 상황
  → 여러 프로세스가 Critical Section 을 동시 접근할 때 발생한다.

어느 위치에 semWait과 semSignal를 사용할지 잘 선택해야 한다.

Mutual Exclusion Using Semaphore

하늘색 네모 부분은 해당 프로세스가 Blocked Queue 에서 대기하고 있다는 의미이다.

세마포 방과 문에 비유하기

step1

여러 프로세스들이 Critical Section에 진입하려고 문에 서 있다고 가정해보자.

step2

Process 2가 먼저 문을 열고 Critical Section에 들어가서 문을 닫아버리고 s 값을 0으로 바꾼다.
이후 접근하는 프로세스들은 s 값이 음수가 되기 때문에 Blocked Queue에 들어가서 대기하게 된다.

• s <= 0 : 문이 닫힌 상태
• s > 0 : 문이 열린 상태

step3

Process2가 Critical Section 실행을 마친 후,
나갈 때 semSignal 명령어를 통해 대기하던 프로세스를 문 안으로 데려온다.
s > 0 (s == 1) 이되면, 문이 다시 열리는 것을 의미한다.

Semaphore는 좋은 도구인가?

1. Mutual Exclusion O
2. Deadlock X
3. Livelock X
4. Busy-Waiting X
5. Starvation △
   • Strong Semaphore X (Queue 순서대로 진행)
   • Weak Semaphore O

---

Binary Semaphore Primitives

지금까지 진행했던 Semaphore 는 Counting Semaphore 이다.
Binary Semaphore는 Semaphore 값을 0 아니면 1만 설정 가능하다.

Binary Semaphore는 작은 group의 문제들을 해결할 수 있다.

semWaitB

Binary Semaphore 에서는 Semaphore 값 S가 0이 되면 무조건 Block을 시킨다.
→ 몇 개가 block 되어 있는지는 알 수 없다.

semSignalB

Queue에서 프로세스를 꺼낼 때 Semaphore 값 S를 보고는 몇개의 프로세스가 Queue에 있는 지 알 수 없다.
⇒ Queue 자체를 확인한다. → isEmpty()

---

Buffer

Producer Process

데이터를 생성해서 Buffer에 쓴다.

Consumer Process

Buffer에서 데이터를 읽어서 작업한다.

Producer Process와 Consumer Process는 한 번에 하나만 Buffer에 접근할 수 있다!

위의 버퍼를 I/O Buffer라고 가정하자.
Memory Data → I/O buffer → I/O Device 출력

두 Producer Process 가 동시에 버퍼에 접근하여 데이터를 쓸 수 있고, 두 Concumer Process가 동시에 버퍼에 접근하여 데이터를 출력할 수 있다.
이렇게 프로세스가 동시에 버퍼에 접근하는 문제는 Critical Section 해결 방법과 동일하게 해결할 수 있다!

동시 buffer 접근 문제

Critical Section 해결 방법과 동일하게 해결할 수 있다!

Buffer가 비어 있는 문제

Consumer Process 가 Buffer에서 데이터를 가져갈 수 없다.

Buffer의 크기 제한

Producer Process 가 Buffer에 데이터를 쓸 수 없다.

⇒ Buffer의 크기 문제를 해결해야 한다!

---

Producer/Consumer Problem

1. 보통의 상황:
   • Producer는 데이터를 생성하고 buffer 에 데이터를 놓는다.
   • Consumer 는 buffer에서 item을 가져간다.
   • 오직 한번에 하나의 Producer나 Consumer만 buffer에 접근할 수 있다.
2. 문제:
   Producer가 꽉찬 buffer에 데이터를 추가하지 못하거나 Consumer가 비어있는 buffer에서 데이터를 가져가지 못하는 상황

---

Bounded Buffer

처음엔 버퍼가 비어 있다.

In

Producer Process가 다음에 Data를 쓸 위치

Out

Consumer Process가 다음에 Data를 읽을 위치

in > out

out > in

위의 그림에서 아래 그림으로 바뀌는 동안, Producer 는 b[5] 부터 한바퀴를 돌아 b[2]까지 데이터를 쓴 것이고, Consumer는 b[4]까지 데이터를 읽은 것이다.

Buffer 가 비었을 때?

in == out → 데이터가 빈 것이라고 볼 수 있다.

Buffer 가 꽉찼을 때?

in == out → 데이터가 꽉 것이라고 볼 수 있다.

⇒ 그렇다면 어떻게 Buffer가 비고 꽉찼는지 구분할 수 있을까?
↳ 버퍼가 꽉차기 전에 버퍼 하나를 비워둔다.

⇒ 즉, in == out-1 → 버퍼가 꽉 찼다고 인식한다.

---

Funcions in a Bounded Buffer

Producer

• (in + 1) % n == out → Buffer가 가득찬 상황이므로 while문에 걸린다.
• 그 밖의 경우에는 buffer에 데이터 값을 넣고 in값을 하나 증가시킨다.

Consumer

• in == out → Buffer가 빈 상황이므로 while문에 걸린다.
• 그 밖의 경우에는 buffer에서 데이터를 읽고 out 값을 하나 증가시킨다.

Busy-Waiting O & Buffer 1개 낭비

좋은 Solution이 아니다.
⇒ Semaphore 를 이용해서 해결하자

---

Bounded Buffer using Semaphores

• semWait : 상황에 따라 프로세스를 기다리게 한다.
• semSignal : 상황에 따라 기다리고 있던 프로세스를 풀어준다.

프로세스가 기다려야 하는 상황 3가지

1. Producer Process의 입장에서 buffer가 가득 찼을 때
2. Consumer Process의 입장에서 buffer가 비었을 때
3. Producer Process와 Consumer Process가 Critical Section에 진입할 때 → 한 번에 하나만 접근해야하므로 기다려야 한다.

Producer Process, Consumer Process, Critical Section 의 Blocked Queue를 하나로 관리하지 않는다.
⇒ 3개의 Queue에서 3개의 Semaphore를 관리해야 한다.

Semaphores Logic

1. 프로세스가 기다려야 하는 상황을 생각해야 한다. (n개)
2. n → 같은 Queue에서 기다려도 되는 프로세스들인지 판단하여 필요한 Queue의 개수를 판단한다.

Semaphore를 사용한 Buffer 관리 코드

/* program boundedbuffer */
const int sizeofbuffer = /* buffer size */;
semaphore s = 1, n = 0, e = sizeofbuffer;
void producer()
{
	while(true) {
    	produce();
        semWait(e);
        semWait(s);
        append();
        semSignal(s);
        semSignal(n); // 버퍼에 데이터가 하나 증가한다. + blocked된 Consumer가 있으면 다시 Ready 상태로 깨워준다.
    }
}
void consumer()
{
	while(true) {
    	semWait(n);
        semWait(s);
        take();
        semSignal(s);
        semSignal(e); // 버퍼에 데이터가 하나 지워진다. + blocked된 Procuder가 있으면 다시 Ready 상태로 깨워준다.
        consume();
    }
}
void main()
{
	parbegin(producer, consumer); // 여러개의 producer들과 consumer 들이 함께 작업한다.
}

producer()

semSignal(n)의 의미:
버퍼에 데이터가 하나 증가한다. + blocked된 Consumer가 있으면 다시 Ready 상태로 깨워준다.

consumer()

semSignal(e)의 의미:
버퍼에 데이터가 하나 지워진다. + blocked된 Procuder가 있으면 다시 Ready 상태로 깨워준다.

즉, Producer와 Consumer는 서로 blocked 된 프로세스를 깨워준다.

---

Semaphore를 사용한 Buffer Logic

세개의 Semaphore 를 사용한다.
→ n, e, s
⇒ Semaphore 값이 어떻게 변하는지 알아야 한다.

s

Critical Section 처리 Semaphore

Critical Section에 여러 프로세스가 들어가려고 대기하면, s 값이 음수가 될 수 있다.

e

초기값: 버퍼의 크기

어느 순간 버퍼에 있는 빈칸의 수

• e > 0: 쓸 수 있는 버퍼의 수
• e <= 0: 버퍼가 꽉차, 버퍼에 데이터를 쓰기 위해 Blocked queue에서 대기 중인 Producer Process의 수

n

초기값: 0

어느 순간 버퍼에 있는 데이터의 개수

• n > 0: 읽을 수 있는 데이터의 수
• n <= 0: 버퍼가 비어있어, 버퍼의 데이터를 읽기 위해 Blocked queue에서 대기 중인 Consumer Process의 수

n+e

버퍼의 크기 (단, n > 0, e > 0 ⇒ blocked queue에 프로세스가 대기 중이지 않은 경우만 성립한다.)

n == 0 → 버퍼가 비었다.
e == 0 → 버퍼가 가득 찼다.

---

Q. 코드 순서를 변경할 때, 문제가 발생할 수 있다.

/* program boundedbuffer */
const int sizeofbuffer = /* buffer size */;
semaphore s = 1, n = 0, e = sizeofbuffer;
void producer()
{
	while(true) {
    	produce();
        /*순서 교체*/
        semWait(s);
        semWait(e);
        /*순서 교체*/
        append();
        semSignal(s);
        semSignal(n); // 버퍼에 데이터가 하나 증가한다. + blocked된 Consumer가 있으면 다시 Ready 상태로 깨워준다.
    }
}
void consumer()
{
	while(true) {
    	/*순서 교체*/
        semWait(s);
        semWait(n);
        /*순서 교체*/
        take();
        semSignal(s);
        semSignal(e); // 버퍼에 데이터가 하나 지워진다. + blocked된 Procuder가 있으면 다시 Ready 상태로 깨워준다.
        consume();
    }
}
void main()
{
	parbegin(producer, consumer); // 여러개의 producer들과 consumer 들이 함께 작업한다.
}

코드 순서를 변경할 때, 숫자 값의 변화는 없어도, Deadlock이 발생할 수 있다.
semWait(e) ↔ semWait(s) 이나 semWait(n) semWait(s) 를 바꾸는 경우 문제 발생

1. buffer가 어떤 상황일 때 어떤 순서로 producer와 consumer가 도착했을 때 Deadlock이 발생하는가?
   → 2가지 case가 존재한다.
2. 시스템이 Semaphore 제공 X → hardware instruction으로 구현해야 한다.
   → hardware instruction으로 buffer 문제 해결이 가능한가?
   → 가능하다면, 어떻게 구현해야하는가? swap&compare, exchange가 몇 개 필요한가?