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

강의 링크 : https://www.youtube.com/watch?v=CitsUz-Dx7A&list=PLBrGAFAIyf5rby7QylRc6JxU5lzQ9c4tN&index=16

2. Semaphore

1) 특징

• 1965년 Dijkstra가 제안
• Busy waiting 문제 해결
• 음이 아닌 정수형 변수(S)
  • 초기화 연산, P(), V()로만 접근 가능
    • P : Probern(검사)
    • V : Verhogen(증가)
• 임의의 S변수 하나에 ready queue하나가 할당 됨
  • Spinlock과 가장 다른점
• 초기화 연산
  • S변수에 초기 값을 부여하는 연산
• P()연산, V()연산
  • P(S) 연산
    • 물건이 있을 때, 물건을 하나 빼고 가져감
    • 물건이 없을 때, 대기실(ready queue)에서 기다림
  • V(S) 연산
    • 대기실에 기다리는 애가 있다면, 대기실에 존재하는 것 중 하나를 wake up함
    • 대기실에 기다리는 애가 없다면, 그냥 물건 반납
• 모두 indivisible연산
  • OS의 지원을 받아 non preemtive
  • 전체가 한 instruction cycle에 수행 됨

P()연산과 V()연산

2) 종류

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

3) semaphore로 해결 가능한 동기화 문제들

• 상호배제 문제
  • Mutual exclusion
• 프로세스 동기화 문제
  • process synchronization problem
• 생산자-소비자 문제
  • producer-consumer problem
• Reader-writer 문제
  • Dining philosopher problem: 철학자들의 저녁식사

4) semaphore로 해결한 문제(1) - 상호배제 문제

P()연산과 V()연산을 이용해 상호배제 해결

• Spinlock과 비교해서 생각해보자
  • Spinlock의 경우 active=0이면 P(active)에서 while문을 이용해 뺑뺑 돌았다.
  • 하지만, Semaphore은 ready queue라는 대기실이 존재하기 때문에, 가만히 대기실에서 대기하면 된다.
  • 그리고 다른 프로세스의 V(active)에 의해 wake up되어 CS영역에 진입하면 된다.

5) semaphore로 해결한 문제(2) - 프로세스 동기화 문제

0. sync라는 변수 생성, 초기 값은 0
   • 초기에는 물건이 존재하지 않는다고 생각
   • Pj가 물건을 가지고 있었다.
1. Pj가 반납을 할 때, V(sync)연산을 호출함으로써 sync가 1이 되고, Pi의 P(sync)에서 sync가 1이되어 Pi가 물건을 가져갈 수 있게 됨
2. 만약, Pj가 반납하기 전에 Pi가 P(sync)하면 ? -> ready queue에서 대기하고 있다가 Pj가 V(sync)을 호출할 때까지 기다린다.

6) semaphore로 해결한 문제(3) - 생산자-소비자 문제

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

생산자는 buffer를 생산하고 소비자는 buffer를 소비한다.

• 왼쪽부터 buffer를 생산하는 생산자, 그렇게 쌓인 buffer, 해당 buffer를 소비하는 소비자

(1) Producer-Consumer problem with single buffer

0. 2개의 semaphore변수 (consumed, produced)
   • consumed : 소비 되었나? (1이면 소비자가 소비한 것, 0이면 소비자가 소비지하지 않은 상태)
   • produced : 생산 되었나? (1이면 생산자가 buffer를 생산한 것, 0이면 생산하지 않은 상태)
1. P(consumed) : buffer가 비었는지확인
   • 비었다면, buffer 생성
2. V(produced) : 생산했음을 알린다. (produced 1로 바꿔줌)
3. P(produced) : buffer가 생산이 되었는지 확인
4. 생산이 안되어있으면 ready queue에서 대기하다가, 생산되는 순간 대기실 내의 소비자 중 하나를 깨움.
5. wake up된 consumer는 buffer를 소비한다.
6. V(consumed) : buffer를 소비했음을 알린다. (consumed 1로 바꿔줌)

(2)Producer-Consumer problem with N-buffers

버퍼의 크기가 N인 경우

원형 큐

• 버퍼사이즈 : n
• 소비자, 생산자 여러명
• mutexP, mutexC : mutual exclusion 생산자, mutual exclusion 소비자
• nrfull : 채워진 buffer 수
• nrempty : 비어있는 bufffer수

• P(mutexP), V(mutexP), P(mutexC), P(mutexC)는 한 번에 하나의 생산자, 소비자를 처리하기 위해 만들어 놓은 것-> P(nrfull)~V(nrempty) : CS가 됨
• -> P(nrempty)~V(nrfull) : CS가 됨

0. 변수
   • nrfull : 채워진 buffer의 수 (찬 공간의 크기)
   • nrempty : 비어있는 buffer의 수 (남은 공간의 크기)
   • -> nrfull + nrempty 의 합은 항상 N이다.
1. 생산자가 생산하기 전, 공간이 있는지 확인 (P(nrempty))
2. 만약 nrempty가 0이라면 공간이 없는 것이므로 대기실에 가서 공간이 생길 때까지 기다린다.
3. 공간이 있어서 안으로 들어오게 된다면, 내가 놓을 곳 (buffer[in])에다가 buffer를 놓고, 공간을 다음 공간으로 옮겨준다. (원형큐라서 나머지 연산자인mod사용)
4. V(nrfull)에서 nrfull값을 1개 늘려줌
5. 소비자는 nrfull이 0이라면 buffer가 없는 것이므로 대기실에 가서 buffer가 생성될 때까지 기다린다.
6. buffer가 생성되었다면? 해당 buffer를 꺼냄
7. 다음에 물건을 꺼낼 위치 갱신 (원형 큐라서 나머지 연산자인 mod사용)
8. V(nrempty)에서 nrempty값을 1개 늘려줌

7) semaphore로 해결한 문제(4) - Reader-writer 문제

(1) 특징

• Reader
  • 데이터에 대해 읽기 연산만 수행
• Writer
  • 데이터에 대해 갱신 연산을 수행
• 데이터 무결성 보장 필요
  • Reader들은 동시에 데이터 접근 가능
  • Writer들이 동시에 데이터 접근시 상호 배제(동기화) 필요
  • reader와 writer가 동시에 데이터 접근 시 상호 배제(동기화) 필요

(2) 해결법

• reader/writer에 대한 우선권 부여
  • reader preference solution
    • reader가 writter에 비해 우선권을 가질 때의 해결 법
    • ex) reader1이 읽고 있는 데, writter가 와서 쓰려고 함, 하지만 이미 reader1이 접근해있기 때문에 대기 중, 그러던 도중 다른 reader2가 와서 대기. reader1이 다 읽고 나서, writter가 아닌 reader2가 먼저 읽으러 감. -> reader가 writter에 비해 우선권을 가지는 경우
  • writer preference solution
    • writter가 reader에 비해 우선권을 가질 때의 해결 법

(3) Reader-Writer problem (reader preference solution)

0. P(rmutex), V(rmutex)가 존재하는 이유
   • 읽는 것은 여러 명이 동시에 할 수 있지만, 읽기 전 사전 작업, 사후 작업은 한 명만 가능

Reader

1. enter read
   1. 현재 reader의 수 체크
      • 만약 reader의 수(nreader)가 0이라면: writter에 대해 mutex를 건다(P(wmutex)) (현재 read할거니까 write하지 못하게)
      • 만약 reader의 수(nreader)가 0보다 크다면, 누군가 이미 wmutex를 했으므로 굳이 다시 wmutex를 할 필요가 없음.
   2. 읽는 사람 수 1명 증가 (nreaders = nreaders+1)
2. 읽는 중 (Perform read operations)
   • 여기는 여러 reader 접근 가능
3. exit read (reader가 다 읽고 나갈 때)
   1. 읽는 사람 수 1명 감소 (nreaders = nreaders - 1)
   2. 만약 현재 읽는 사람이 0명이라면: V(wmutex) (=> wmutex 해제)
   3. 만약 현재 읽는 사람이 0명보다 많다면: wmutex를 해제하지 않는다.

Writer

1. P(wmutex)를 한다. (w는 동시에 데이터 접근 불가. 상호배제 필요)
2. Perform write operations
3. V(wmutex)를 한다.

7) Semaphore의 특징 정리

• No busy waiting
  • 기다려야 하는 프로세스는 block(asleep)상태가 됨
• Semaphore queue에 대한 wake-up 순서는 비결정적 (one of them)
  • Starvation problem