[OS] 프로세스 동기화와 상호배제 (Process Synchronization and Mutual Exclusion) - ②

OS supported SW Solutions

Spinlock(스핀락)

초기화, P(), V() 연산으로만 접근 가능한 정수형 변수 S

위의 연산들은 indivisible(atomic) 연산 (OS에 의해 지원되며, 전체가 한 instruction cycle)

 

P(S) {
    while(S <= 0) do 
    endwhile;
    S <- S - 1;
}

V(S) {
    S <- S + 1;
}

 

Spinlock(스핀락)

스핀락 변수 active가 존재하고, 이는 다음과 같이 정의됩니다.

• active = 1: 임계 영역에 실행중인 프로세스가 없음
• active = 0 : 임계 영역에 실행중인 프로세스가 있음

현재 active가 1로 초기화 되어있으므로, P연산이 실행되고, active가 0이 되면서 i 프로세스가 임계 영역에 들어갑니다. j 프로세스는 현재 active가 0이므로 P연산을 진행하지 못하고 대기합니다.

i 프로세스의 일이 끝나면 V연산을 통해 active를 반납하여 1이 되고, j는 P연산을 진행해 임계 영역에 진입할 수 있게 됩니다.

이때 P연산과 V연산은 Preemption 발생하지 않는데, 이는 OS에 의해 보장됩니다.

Spinlock 문제점

• 멀티 프로세서 시스템에서만 사용 가능
• Busy Waiting (기존의 문제를 아직 해결하지 못했음)

Semaphore(세마포어)

1965년 Dijkstra가 제안

Busy Waiting 문제 해결(드디어!)

초기화 연산, P(), V()로만 접근 가능한 음이 아닌 정수형 변수 세마포어(S)가 존재

임의의 S변수 하나에 ready queue 하나가 할당 됨

세마포어 종류는 두가지로 분류

• Binary Semaphore

  S가 0, 1 두 종류의 값만 가지는 경우

  상호배제나 프로세스 동기화의 목적으로 사용

• Counting Semaphore

  S가 0이상의 정수값을 가질 수 있는 경우

  Producer-Consumer 문제 등을 해결하기 위해 사용 (생산자-소비자 문제)

P(S) {
    if(S > 0) 
    then S <- S - 1;
    else wait on the queue Q;
}

V(S) {
    if(any waiting processes on Q) 
    then wakeup one of them;
    else S <- S + 1;
}

Semaphore로 해결할 수 있는 문제

Mutual Exclusion(상호 배제)

Semaphore(세마포어) → Mutual Exclusion 해결

Spinlock과 비슷하지만, P연산과 V연산에 각각 ready queue와 wakeup을 추가함으로써 Busy Waiting을 해결한 방법입니다.

Process Synchronization(프로세스 동기화)

Semaphore(세마포어) → Process Synchronization 해결

프로세스들은 병행적이며, 비동기적으로 수행됩니다. 이러한 프로세스들을 동기화 하기 위해서 세마포어를 사용할 수 있습니다.

세마포어 변수 sync를 0으로 초기화하고, i프로세스는 P연산, j프로세스는 V연산을 하면, i 프로세스는 j 프로세스가 V연산을 하고 sync를 반납하기 전까지 ready queue에서 대기해야합니다. 따라서 j가 끝난 후 i 를 실행하게끔 순서를 정할 수 있습니다. (동기화)

Producer-Consumer(생산자-소비자)

• 생산자 프로세스 : 메세지를 생성하는 프로세스 그룹
• 소비자 프로세스 : 메세지를 전달받는 프로세스 그룹

생산자 프로세스가 다양한 메세지를 생성하여 버퍼에 쌓아두면, 소비자 프로세스가 버퍼로부터 메세지를 전달받아 이를 사용하는 구조입니다. 그런데 이때, 생산자 프로세스가 메세지를 생성하는 동안에 소비자 프로세스가 메세지를 가져가면 안되겠죠? 또한 하나의 생산자 프로세스가 메세지를 생성하고 있는데 다른 프로세스가 또 같은 곳에 메세지를 생성하면 안되겠죠?

이러한 문제점을 해결하기 위해서 동기화가 필요합니다.

 

Semaphore(세마포어) → Producer-Consumer with Single Buffer 해결

위의 그림을 보시면 consumed, produced 2개의 세마포어 변수가 선언되었습니다. 각각의 변수는 다음과 같은 의미를 지닙니다.

• consumed : 소비되었니?
• produced : 생산되었니?

생산자 프로세스 i가 메세지를 생성해서 buffer에 넣으려고 하면 buffer가 비었는가 확인하기 위해 P연산을 실행해 consumed가 1인지 확인합니다. (== "소비자가 소비를 했나?")

만약 consumed가 1이라면 consumed를 0으로 바꾸고, buffer 안에 메세지를 두고, V연산을 통해 produced를 1로 변경합니다. (== "나 생산했어!")

소비자 프로세스 j가 메세지를 소비하기 위해서 buffer에 접근하려 하면 buffer에 메세지가 있나 확인하기 위해서 P연산을 실행해 produced가 1인지 확인합니다. (== "생산자가 생산을 했나?")

produced가 1이라면 produced를 0으로 바꾸고, V연산을 통해 consumed를 1으로 변경합니다. (== "나 소비할게!") 그러고나서 buffer 안에 있는 메세지를 소비합니다.

produced가 0이라면 생산자 프로세스가 메세지를 생성할 때 까지 ready queue에서 대기하게 됩니다. 그러면 프로세스 i가 메세지를 생성하고나서 ready queue에 대기하고 있는 프로세스가 있나 확인을 하고, 존재한다면 wakeup 하고 위의 과정을 진행합니다.

 

Semaphore(세마포어) → Producer-Consumer with N-Buffer 해결

N-Buffer는 nrfull, nrempty, mutexP, mutexC 4가지 세마포어 변수가 선언되어 있습니다. 각각의 변수는 다음과 같은 의미를 지닙니다.

• mutexP : 하나의 생산자 프로세스만 P연산, V연산 해!
• mutexC : 하나의 소비자 프로세스만 P연산, V연산 해!
• nrfull : 채워진 buffer 수
• nrempty : 비어있는 buffer 수

실행 과정은 buffer가 하나일 때와 비슷합니다. 다만 다른 점은 n개의 buffer를 circular queue로 구현되어 있다는 점입니다. 그래서 생성자 프로세스, 소비자 프로세스 모두 buffer에 메서지를 생성, 소비하고 난 후, "in ← (in + 1) mod N", "out ← (out + 1) mod N" 를 통해 다음 생산, 소비할 버퍼의 인덱스를 갱신하게 됩니다.

Reader-Writer

• Reader : 데이터에 대해 읽기 연산만 수행
• Writer : 데이터에 대해 갱신 연산만 수행
• 데이터 무결성 보장 필요
  • Reader들은 동시에 데이터 접근 가능
  • Writer들은 또는 Reader, Writer이 동시에 데이터 접근 시, Mutual Exclusion 혹은 Synchronization 필요
  • 따라서 Reader와 Writer에 대해 우선권 부여 필요

Semaphore(세마포어) → Read-Writer 해결

위의 그림을 통해 wmutex, rmutext 2개의 세마포어 변수가 선언된 것을 확인할 수 있습니다. nreaders는 reader의 수를 의미합니다.

Reader 프로세스 i가 read 작업을 하기 전에, 현재 reader의 수를 확인합니다. 만약 nreaders = 0 이라면 wmutex를 0으로 바꿈으로써 Reader i가 read 작업을 할거니까 Writer j는 write작업을 하지 못하게 하고 nreaders 수를 증가시킵니다.

readers가 0보다 크다면 이미 write작업을 한 상태이므로 해당 분기에 들어가지 않습니다.

read 작업은 rmutex에 묶이지 않으므로 여러 프로세스가 실행할 수 있습니다.

read 작업이 끝난 프로세스가 나가기 위해서 다시 P(rmutex) 연산을 실행합니다. 일단 나가므로 nreaders의 수를 감소시키는데, 만약 현재 나가려는 프로세스가 마지막 Reader였다면, Writer 프로세스 j가 write 작업을 진행할 수 있으므로 wmutex를 1로 바꾸어 write 작업을 할 수 있게끔 하고 P(rmutex) 연산을 종료합니다.

그런데 nreaders가 아직 0보다 크다면 read 작업을 하고 있는 Reader가 남아있으므로 wmutex를 변경하지 않고 그대로 P(rmutex) 연산을 종료합니다.

Semaphore 문제점

• Semaphore queue에 대한 wakeup 순서가 비결정적 → Starvation(기아 현상)

Eventcounter/Sequencer(이벤트카운터/시퀀서)

• 은행의 번호표와 비슷한 개념
• Sequencer 변수 S
  • 정수형 변수
  • 생성시 0으로 초기화, 감소하지 않음
  • 발생 사건들의 순서 유지
  • ticket() 연산으로만 접근 가능
• ticket(S)
  • 현재까지 ticket() 연산이 호출된 횟수를 반환
  • Indivisible operation
• Eventcount 변수 E
  • 정수형 변수
  • 생성 시 0으로 초기화, 감소하지 않음
  • 특장 사건의 발생 횟수를 기록
  • read(E), advance(E), await(E, v) 연산으로만 접근 가능
• read(E)
  • 현재 Eventcount 값 반환
• advance(E)
  • E ← E + 1
  • E를 기다리고 있는 프로세스를 깨움 (wakeup)
• await(E, v)
  • v는 정수형 변수
  • if(E < v) 이면 E에 연결된 Q에 프로세스 전달 (push) 및 CPU Scheduler 호출

Eventcounter/Sequencer로 해결할 수 있는 문제

Mutual Exclusion(상호 배제)

Eventcounter/Sequencer → Mutual Exclusion 해결

처음 프로세스가 임계 영역에 진입하기 위해 ticket 연산을 합니다. 처음 Sequencer 변수 S는 0이므로 v의 값은 0을 리턴합니다. await 연산에서 Eventcounter 변수 E와 v가 모두 0이므로 해당 프로세스는 임계 영역에 들어가 자신의 작업을 진행하게 됩니다.

다음 프로세스가 들어와서 ticket 연산을 합니다. 변수 S가 1증가하여 1이므로 v의 값은 1을 리턴합니다. await 연산에서 변수 E와 v가 0, 1이므로 해당 프로세스는 ready queue에서 본인의 순서인 1이 될때까지 기다립니다.

처음 프로세스가 작업을 마치고 임계 영역을 나가면서 advance 연산을 통해 E의 값을 1 증가시키고, await의 E와 v가 1, 1로 같아지므로 1번 프로세스가 임계 영역에 들어가 일을 하게 됩니다.

이런식으로 2, 3, 4 .. n번 프로세스가 들어오고 위와 같은 과정을 반복함으로써 Mutual Exclusion 문제를 해결할 수 있습니다.

Producer-Consumer(생산자-소비자)

Eventcounter/Sequencer → Producer-Consumer 해결

위의 그림에서 Pticket, Cticket 2개의 Sequencer 변수와 In, Out 2개의 Eventcounter 변수가 선언된 것을 확인할 수 있습니다. 그리고 크기가 n인 circular buffer가 존재합니다.

각각의 "await(Out, t - N + 1)" 과 "await(In, u + 1)" 이 의미하는 바가 무엇인지만 이해한다면, Semaphore에서의 방법과 비슷합니다.

await(Out, t - N + 1)은 현재 buffer에 공간이 있는 지 확인하는 로직입니다. 공간이 있다는 것은 다음과 같이 표현이 가능합니다.

빈 공간 ≥ 1

여기서 빈 공간은 buffer의 크기 N에서 현재 순서인 t를 빼준 후, Consumer가 advance한 Out(꺼낸 수)을 더해주는 것으로 표현할 수 있고 다음과 같이 정리할 수 있습니다.

N - t + Out ≥ 1 =⇒ Out ≥ t - N + 1

즉 Out < t - N + 1 이면 빈 공간이 없으므로 ready queue로 가서대기하게 되고, Out ≥ t - N + 1 이면 빈 공간이 존재하므로 t번 메세지를 buffer에 두고, In(넣은 수)을 증가시킵니다.

await(In, u + 1)은 현재 buffer에 생성된 메세지가 있는 지 확인하는 로직입니다. 생성된 메세지가 존재하는 것은 다음과 같이 표현 가능합니다.

메세지 수 ≥ 1

메세지의 수는 Consumer가 하나도 소비하지 않았다면 In 만큼 존재합니다. 그런데 ticket(Cticket) 연산을 통해 u만큼 메세지를 소비했다는 것을 의미하므로, 다음과 같이 정리할 수 있습니다.

In - u ≥ 1 =⇒ In > u + 1

즉 ln < u + 1 이면 남은 메세지가 없으므로 ready queue로 가서 대기하게 되고, In ≥ u + 1 이면 남은 메세지가 존재하므로 u번 buffer에서 메세지를 꺼내고 Out(꺼낸 수)를 더해주고 꺼낸 메세지를 소비하게 됩니다.

Semaphore → Eventcounter/Sequencer

• No busy waiting!!!
• No starvation!!!
• 보다 더 low-level control 가능!!!