6. 프로세스 동기화 & 상호 배제 (5) - Semaphore

출처 : https://www.youtube.com/watch?v=CitsUz-Dx7A&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=16

 

 

 

Spinlock에서 P() 연산과 V() 연산이 한 번에 동작하도록 보장해줌으로써 문제를 간단하게 해결할 수 있다는 것을 확인했다. 하지만 여전히 Busy waiting 문제가 여전히 남아있다.

 

이번 장에서는 Busy waiting 문제를 해결할 수 있는 Semaphore를 알아보자.

 

 

Semaphore

 

• 1965년 다익스트라가 제안
• Busy waiting 문제 해결
• 음이 아닌 정수형 변수(S), S >= 0
  • 초기화 연산, P(), V() 로만 접근 가능
    • P : Probern (들어가기 전에 검사)
    • V : Verhogen (나올 때 돌려놔서 증가)
• 임의의 S 변수 하나에 ready queue 하나가 할당 됨

 

 

 

Semaphore

 

• Binary semaphore
  • S가 0과 1 두 종류의 값만 갖는 경우
  • 상호배제나 프로세스 동기화의 목적으로 사용
• Counting semaphore
  • S가 0 이상의 정수값을 가질 수 있는 경우
  • Producer-Consumer 문제 등을 해결하기 위해 사용
    • 생산자-소비자 문제

 

 

• 초기화 연산
  • S 변수에 초기값을 부여하는 연산
• P() 연산, V() 연산
  • P(S) : 자물쇠를 거는 연산. 물건이 있는지 확인한 다음(if S > 0), 물건이 있으면 꺼내가고(S = S - 1) 없으면 S에 할당된 queue에서 기다린다(wait on the queue Q). spinlock 에서는 while 문으로 계속 반복문을 돌면서 기다렸지만, semaphore에서는 S에 할당된 ready queue에서 기다린다. 
  • V(S) : 자물쇠를 푸는 연산. ready queue에서 기다리는 프로세스가 있는지 확인한 다음(if waiting processes on Q), 있으면 그것들 중 하나를 불러오고(wakeup), 없으면 물건을 더해준다(S = S + 1).
• 모두 indivisible 연산
  • OS support
  • 전체가 한 instruction cycle에 수행 됨. 이전에는 반복문을 돌면서 CPU를 사용했는데 이제는 queue에서 대기만 하면 됨

 

 

Semaphore in OSs

 

• windows
  • MSDN
• Unix / Linux
  • System V

 

 

• Semaphore로 해결 가능한 동기화 문제들
  • 상호 배제 문제
    • Mutual Exclusion
  • 프로세스 동기화 문제
    • Process synchronization problem
  • 생산자-소비자 문제
    • Producer-consumer problem
  • Reader-writer 문제
  • Dining philosopher problem
  • 기타

 

 

Semaphore의 Mutual exclusion 문제

 

Spinlock 문제와 동일하게 P()연산과 V() 연산으로 간단하게 해결된다.

 

Spinlock 과의 차이점은 Spinlock은 P()연산에서 반복문을 계속 돔으로써 CPU를 계속 사용했다면, Semaphore에서는 ready queue에서 대기하고 있다.

 

 

• Process synchronization
  • Process들의 실행 순서 맞추기
    • 프로세스들은 병행적이며, 비동기적으로 수행

 

 

이 Process synchronization 문제를 semaphore를 사용하면 다음과 같이 해결된다.

 

Sync라는 semaphore 변수를 두고 0으로 setup 되어있다. process-Pj가 Lj를 넘어갈 때 V()연산을 수행하면 sync가 1이 되고, 그러면 process-Pi가 Li를 넘어갈 때 P()연산을 수행할 수 있게 된다.

즉, sync 변수를 통해 Pj가 먼저 실행된 다음에 Pi가 실행되도록 만들 수 있다.

 

 

• Producer-Consumer problem
  • 생산자(Producer) 프로세스
    • 메시지를 생성하는 프로세스 그룹
  • 소비자(Consumer) 프로세스
    • 메시지 전달받는 프로세스 그룹

생산자 프로세스가 데이터를 생성해내서 버퍼에 쌓고, 소비자 프로세스가 버퍼에 쌓여있는 데이터를 가져간다. 그런데 생산자가 버퍼에 데이터를 쌓는 동안 소비자가 데이터를 가져가면 안된다. 또한 하나의 생산자가 데이터를 쌓고 있을 때, 다른 생산자가 데이터를 쌓으면 안된다.

그렇기 때문에 생산과 소비 사이에 동기화가 필요하다.

 

 

• Producer-Consumer problem with single buffer. 버퍼가 1개인 경우

2개의 semaphore 변수를 선언한다. semaphore가 1일 때(소비되었는가?), 0일 때(생산되었는가?)

 

생산자

 

P(consumed) : 생산자는 먼저 buffer가 비어있는지(소비자가 소비를 했는지)를 확인해야한다. = consumed

비어있다면(consumed == 1), consumed를 1 -> 0으로 바꾸고 buffer에 데이터를 쌓는다.

 

V(produced) : 생산을 완료하면 produced를 0 -> 1 로 바꾼다.

 

소비자 

 

P(produced) : 생산이 되었는가를 확인한다(produced 확인). 만약 생산이 안되어있다면(produced == 0) 대기실에서 대기한다. 생산자가 V 연산을 하는 순간(produced == 1) wakeup으로 인해, ready queue에 있는 프로세스가 동작하여 buffer에서 물건을 가져간다.

 

V(consumed) : 소비했다고 알린다. 즉, consumed를 0 -> 1로 바꾼다.

 

즉, 하나에 버퍼에 2개의 변수(consumed, produced)를 사용해서 생산되었는지, 소비되었는지를 체크한다. consumed와 produced 항상 상반되는 값을 가진다.

 

• Producer-Consumer problem with N-buffers : 버퍼가 N개인 경우

circular queue를 사용한다고 가정한다. 생산자가 물건을 놓는 지점(in), 소비자가 물건을 가져가는 지점(out)이 있다.

 

 

 

buffer의 사이즈가 N이고 생산자와 소비자도 여러 명이 존재하고, 변수도 다양하다.

 

공유 변수

 

mutexP : 생산자가 mutual exclusion을 하는 것. 여러 명의 생산자가 데이터를 생산 할 수 있으니까 한 명의 생산자만 일하도록 만드는 것

mutexC : 소비자가 mutual exclusion을 하는 것. 여러 명의 소비자가 데이터를 소비 할 수 있으니까 한 명의 소비자만 꺼내가도록 만드는 것

즉, P(nrempty) ~ V(nrfull) 가 CS가 되는 것이다.

 

nrfull : 채워진 버퍼의 수

nrempty : 비어있는 버퍼의 수

nrfull과 nrempty는 상반되는 변수로서 이 두개의 합은 항상 N이 된다.

 

생산자

P(nrempty) : buffer에 비어있는 공간이 있는지 확인한다. 만약 비어있는 공간이 없으면(nrempty <= 0) 생길때까지 ready queue에서 대기한다.

buffer[in] <- M : 공간이 생기면 내가 놓을 곳(in)에 물건을 놓는다.

in <- (in + 1) mod N : 다음에 물건을 놓을 장소를 갱신한다. circular queue이므로 mod N을 해준다.

V(nrfull) : 물건을 하나 놓았으므로 버퍼가 하나 채워진다. nrfull = nrfull + 1

 

소비자

P(nrfull) : buffer에 채워진 공간이 있는지 확인한다. 만약 채워진 공간이 없다면(물건이 없다면, nrfull <= 0) 생길때까지 ready queue에서 대기한다.

m <- buffer[out] : 물건이 생기면 내가 꺼낼 곳(out)에서 물건을 꺼낸다.

out <- (out + 1) mod N : 물건을 꺼낼 곳을 갱신한다.

V(nrempty) : 물건을 하나 꺼냈으므로 버퍼의 빈 공간이 늘어난다. nrempty = nrempty + 1

 

 

 

• Reader-Writer problem
  • Reader
    • 데이터에 대해 읽기 연산만 수행. 읽기는 여러 명이 동시에 수행해도 OK
  • Writer
    • 데이터에 대해 갱신 연산만 수행. 쓰기는 여러 명이 동시에 수행하면 NO. only 한 명만 가능
  • 데이터 무결성 보장 필요
    • Reader들은 동시에 데이터 접근 가능
    • Writer들 (또는 reader와 write)이 동시 데이터 접근 시, 상호 배제(동기화) 필요
    • Reader들이 읽는 동안 Writer들이 글을 쓰거나 수정하면 안됨
    • Writer들이 쓰는 동안 Reader들이 글을 읽으면 안됨
  • 해결법
    • reader / writer 에 대한 우선권 부여
      • reader preference solution : reader에게 우선권이 부여되는 솔루션. R1이 읽는 동안 W1가 도착하면 ready queue에서 기다려야 한다. 이때 R2가 도착하면 W1이 먼저왔지만 R2에게 우선권이 부여되서 R2가 읽기를 실행한다. 즉, Writer는 계속 기다려야 한다.
      • writer preference solution

 

 

• Reader-Writer problem (reader preference solution)
• 3개의 변수 존재
  • wmutex : writer들이 한 명만 들어갈 수 있도록 만듬 (Writer들의 상호 배제)
  • rmutex : reader들이 한 명만 들어갈 수 있도록 만듬 (Reader들의 상호 배제)
  • nreaders : reader의 수

Reader

1단계와 2단계로 구분지어서 보면 편하다. 이때 1단계와 2단계에서는 한 명의 Reader만 가능하다.

 

1단계 : 읽으러 들어감(사전 작업). 내가 읽을거니까 writer가 못쓰게 막고, reader의 수를 1 증가시킨다.

P(rmutex) : reader 상호 배제를 건다. reader의 수를 1 증가시켜야 되는데 한 사람이 한 명만 증가시켜야 하기 때문에 상호 배제를 거는 것이다.

if (nreaders = 0) : 현재 리더가 몇 명인지 확인한다. Reader가 0명이면 wmutex를 건다(P(wmutex)). 즉, 내가 읽을 거니까 writer의 접근을 막는다. 만약 0보다 크다면 누군가가 이미 wmutex를 걸었을테니 내가 해줄 필요 없이 넘어간다.

nreaders <- nreaders + 1 : reader의 수를 1명 증가시킨다. 나도 읽을거야!

V(rmutex) : reader 상호 배제를 푼다.

 

Perform read operations : Reader가 글을 읽는다. 여기는 여러 Reader들이 동시에 할 수 있다.

 

2단계 : 읽고 나감(사후 작업). 나 다 읽었으니까 reader의 수를 1 감소시킨다. 만약 내가 마지막 reader면 writer에게 접근 권한을 풀어준다.

P(rmutex) : reader 상호 배제를 건다. reader의 수를 1 감소시켜야 하는데 한 사람이 한 명만 감소시켜야 하기 때문에 상호 배제를 건다.

nreaders <- nreader - 1 : 내가 다 읽어서 나갈거니까 reader의 수를 1 감소시킨다.

if (nreaders = 0) : 만약 내가 마지막 reader였다면, wmutex를 푼다(V(wmutex)). 즉, reader가 없으니까 writer가 글을 써도 된다고 접근을 허용해준다. 만약 아직 reader가 남아있다면 wmutex를 풀어주면 안된다.

V(rmutex) : reader 상호 배제를 푼다.

 

Writer

P(wmutex) : Writer 상호 배제를 건다.

Perform write operations : Writer가 글을 쓴다.

V(wmutex) : Writer 상호 배제를 푼다.

 

Writer는 한 명만 쓸 수 있으니까 간단하다.

 

Semaphore

 

• 장점
  • No busy waiting : 기다려야 하는 프로세스는 block(asleep) 상태가 된다.
• 단점
  • Semaphore queue에 대한 wake-up 순서는 비결정적 -> Starvation problem