[OS] 프로세스 동기화 : Semaphore Based Concurrent Programming_1

Semaphore을 이용하여 다음과 같은 다섯 가지 문제를 해결할 수 있다.

1. Mutual Exclusion 문제

p1~pn개의 총 n개의 프로세스가 있을 때, active라는 semaphore 변수가 있다.

semaphore을 mutual exclusion 목적으로 사용할 때에는 ⭕초기값을 1로 설정⭕한다.
active==1이면 critical section에 아무도 없고, 0이면 critical section에 다른 프로세스가 진입해 있음을 의미한다.
어떠한 프로세스가 critical section에 진입하고 싶다면 P 연산을 수행하고, 나가게 된다면 V 연산을 수행하면 된다.

☑️P(active)

active 값 = 1 (s>0)이면, active의 값을 1 줄이고 (s=0) critical section으로 들어간다.

☑️V(active)

active 값 += 1 로 해 놓고 (s=1), 나간다.

✔️만약 Pi가 Critical Section에서 실행하고 있는데 아직 나오지 못한 상태(intterupt 등으로)에서 다른 프로세스 Pj가 와서 critical section 진입을 시도하면, 그 때는 P 연산에서 active의 값이 0이므로 Pj는 Queue Semaphore에 가서 sleep하는 것이다.
✔️그 때 Pi가 나와서 V(active)를 하게 되면, 나와서 Pj를 wakeup 시킨다.
✔️Pj는 wakeup 하면 바로 Critical Section에 들어가게 된다.

2. Process Synchronization 문제

1) 문제

만약 process Pj가 Lj 영역의 코드를 실행하고 지나간 이후에야 Pi가 Li 영역의 코드 명령을 실행할 수 있다고 할 때, 프로세스는 원래 independent하기 때문에 Pi는 Pj에 대해 언제 Lj 를 실행했는지 알 수 없는 문제가 있다.

2) 해결

Sync라는 Semaphore을 이용하여 해결할 수 있다.
Sync의 초기값은 0이다. Pi는 Li 영역에서 P operation을, Pj는 Lj영역에서 v operation을 한다.

(1) Pi가 Pj보다 먼저 실행되는 경우

✔️Pi가 L영역에서 P연산을 수행하면, sync = 0일 때 wait해야 한다.
Pj가 Lj를 지나갈 때, V연산을 수행할 때, 기다리고 있는 process가 있는지 확인하고 있다면 wake up을 하면 된다.

(2) Pj가 Pi보다 먼저 실행되는 경우

✔️Pj가 먼저 실행되어서 V연산을 수행했는데 queue에 아무도 없으니 sync는 1이 증가한다.
그렇게 된다면, Pi는 L영역이 되었을 때 P연산을 하고 sync는 이미 1이 되어 있으므로 바로 실행할 수 있다.

3. Producer-consumer Problem

1) 문제

(1) Producer Process : 메세지를 만들어내는 프로세스들의 집합

(2) Consumer Process : 메세지를 소비하는 프로세스들의 집합

Producer Process가 shared memory buffer에 만들어낸 메시지를 저장하면, Consumer Process는 그 메시지를 소비한다.

문제는, Shared Memory Buffer는 하나인데 Producer Process와 Consumer Process가 하나가 아니라 각각 여러개 존재한다는 점이다. 따라서 Producer Process도 동시가 아니라 한 번에 하나만 가져가야 하고, Consumer Process도 한 번에 하나만 가져가야 한다. 그리고 Producer Process가 접근한 이후에 Consumer Process가 접근해야 한다.
즉, 이 문제는 앞선 'mutual exclusion'문제와 'process synchronization'이 모두 해결되어야 한다.

2) single buffer인 경우 해결

Sempahore 변수가 consumed, produced 2가지 있으면 된다. Producer process n개와와 Consumer process들 m개는 서로 교차해 가면서(in an alternate fashion) 움직여야 한다. producer가 가져다 두었는데 consumer가 가져가기 전에 다른 producer가 덮어쓰면 안되고, producer 한번 - consumer 한번 - producer 한번 - consumer 한번 .. 으로 이어져야 한다.

(1) Semaphore 변수의 초기값

consumed = 1
produced = 0

(2) Producer Process

• new message 를 만든다.
• P 연산을 수행하여 buffer가 비어 있는지 확인한다.
• consumed가 0보다 크면(1이면) 1 감소시키고 바로 buffer에 옮기면 된다.
• 만약 consumed가 0이면 버퍼에 무슨 메시지가 있는 것이므로, wait한다.
• 끝나면 V 연산을 하여 produced를 1 증가시켜서 1로 만든다.
  => Consumed = 0, Produced = 1로 만듦

(3) Consumer Process

• P연산을 수행하여 produced가 1인지 확인한다. 1이면 가져갈 수 있고, 0이면 가져가지 못한다. 0이면 wait해야 한다.
• m = buffer;로 메시지를 가져간다.
• V(consumed) 연산을 하여, consumed 를 1로 만들어 준다.
  => consumed = 1, produced = 0으로 만듦

BUT 문제 : Producer는 빠르게 움직이고 Consumer 는 느린 경우는?!

예를 들어 cpu 쪽은 매우 빠르게 생성해서 입출력 장치로 보내려 하는데 이 출력 장치는 느려서 제대로 못하는 경우는 producer 들이 전부 p 연산을 하면서 계속 sleep하게 된다.
혹은, 반대로 producer는 느리고 consumer는 빠른 경우도 있을 수 있다!

=> Multple Buffer을 두자 !

3) Multiple buffer인 경우 해결

=> Multiple Circular Buffer을 가진다.

Producer가 message를 채울 때에는 buffer0부터 채우고, consumer도 buffer0부터 가져간다.
다음 producer가 만약 빨라서 buffer0을 채우고, consumer가 가져가기 전에 그 다음 producer가 오면 buffer1을 채우고, 그 다음 producer가 오면 buffer2를 채운다.
consumer도 마찬가지로 buffer0부터 가져가고, 그 다음 consumer는 buffer1을 가져간다.

즉 consumer가 하나도 가져가지 않더라도 producer는 버퍼의 개수만큼 메시지를 가져다 둘 수 있다.

(1) semaphore 4개의 변수

nrfull = 0
nrempty = N
mutexP = 1
mutexC = 1

buffer[N];
in = 0 // 다음 producer가 채울 버퍼의 위치
out = 0 // 다음 consumer가 가져갈 버퍼의 치

• mutexP와 mutexC는 mutual exclusion을 위하여 사용된다. mutexP는 프로듀서 간 mutual exclusion, mutexC는 consumer 간 mutual exclusion을 위해서 사용된다.

• Producer 코드의 P(mutexP)부터 V(mutexP)까지의 구간 안에는 한 프로세스만 들어올 수 있다.

• Consumer 코드의 P(mutexC)부터 V(mutexC)까지의 구간 안에는 한 프로세스만 들어올 수 있다.

• nrfull와 nrempty는 synchronization의 목적으로 사용된다. nrfull과 nrempty는 binary semaphore가 아니라, counting semaphore이다.

• nrfull은 buffer 중 message를 가지고 있는 버퍼의 개수이다.

• nrempty는 buffer 중 message가 없는 버퍼의 개수이다.

• 즉 producer가 메세지 가져다 둘 떄마다 nrfull은 증가, nrempty는 감소할 것이다. consumer가 메세지를 가져갈 떄마다 nrfull은 감소, nrempty는 증가할 것이다.

(2) producer 코드

p(nrempty)를 하여, nrempty가 0이면 wait하게 된다. nrempty가 1 이상이면 1을 감소시키고, 내려온다.
buffer[in]=M;을 하여 버퍼에 넣는다.
in = (in+1) mod N
V(nrfull)을 하여, nrfull을 하나 증가시킨다.

(3) consumer 코드

P(nrfull)로 nrfull이 0이면 더 이상 consume을 할 수 없으므로, wait한다. 1 이상이면 감소시키고 내려간다.
m = buffer[out]을 하고,
out = (out+1)mod N을 한다.
V(nrempty)를 하여 nrempty를 1 증가시킨다.

• 만약 rnfull에서 consumer가 기다리고 있을 경우에는 producer가 produce하고 나서 consumer쪽으로 시그널을 준다.
• producer가 p(nrempty)에서 기다리고 있을 때는 consumer가 v(nrempty)에서 시그널을 준다.