[운영체제 - 김덕수 교수님] 프로세스 동기화, 상호 배제 - Semaphore(5/7)

Semaphore

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

‏‏‎ ‎

Semaphore의 종류

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

‏‏‎ ‎

• P(S) 연산
  • 물건이 없을 땐 빙빙 s Q로 가서 기다린다. Block된 상태(busy waiting X)
• V(S) 연산
  • 대기실에 있는 애 중 하나를 깨워준다.
• 모두 Indivisible 연산
  • OS Support 보장
  • 전체가 한 instruction cycle에 수행됨

‏‏‎ ‎

Semaphore 로 해결 가능한 동기화 문제들

• 상호배제 문제
  • Mutual exclusion
• 프로세스 동기화 문제
  • process synchronization problem
• 생산자-소비자 문제
  • producer-consumer problem
• Reader-writer 문제
• Dining Philosopher problem
• Etc...

‏‏‎ ‎

첫번째 문제 - 상호배제 문제

• spinlock과 비슷해 보이나, Pi는 일이 끝나면 S의 ready queue에 가서 기다림
• Pj는 일이 끝나면, V(S)를 통해서 Pi를 깨움

‏‏‎ ‎

두번째문제 - 프로세스들의 실행 순서 맞추기

먼저 Sync 라는 변수를 만듬

Pj가 제어권을 들고 있다고 한다면, Lj를 지날 때

• 대기실에 있는 Pi를 깨움
• Sync를 0 에서 1로 변경

‏‏‎ ‎

해결 !

‏‏‎ ‎

세번째문제 - 생산자 소비자 문제

• 생산자가 물건을 놓는 동안 소비자는 가져가면 안된다.
• 생산자가 물건을 놓는 동안 또 다른 소비자가 버퍼에 물건을 놓아서는 안된다.

생산에서 소비로 넘어가는 시점에 동기화가 필요하다.

해결책1 - 싱글 버퍼

• S 변수 두가지를 만든다.
  • consumed
    • 소비자가 소비했는지를 보는 지표
      • 했다면 1
      • 아직 안했다면 0
  • produced
    • 생산자가 생산을 했는지를 보는 지표
      • 생산을 했다면 1
      • 안했다면 0

‏‏‎ ‎

1. 프로듀서는 메시지를 만들고 Consumed 변수를 확인한다.
   1. create a M
   2. P(consumed)
2. 0 이라면 대기하고 1이라면 버퍼에 메시지를 담는다.
   1. buffer <- M
3. produced 변수를 1로 변경하고 소비자를 깨운 후, 다시 호출 될 때까지 레디큐에 기다린다.
   1. V(produced)
4. 컨슈머는 생산자가 생산을 했는지 확인하기위해 produced 변수를 확인한다.
   1. P(produced)
5. 1 이라면 제품을 소비한다.
   1. M <- buffer
6. 소비했다는 표시를 한다.
   1. V(consumed)
7. 대기열에 잠자고 있는 생산자를 깨우고, 생산자가 자신을 깨울 때까지 레디큐에서 잠자며 기다린다.

‏‏‎ ‎

해결책 2 - N개의 버퍼

환형 큐를 사용

• in
  • 생산자가 물건을 놓는 지점
• out
  • 소비자가 물건을 가져가는 지점

일종의 컨테이너 벨트라고 생각하면 좋을 거 같습니다.

생산자가 여러명일 수 있음 ,소비자도

• P(mutexP) ~ V(mutexP), P(mutexC) ~ V(mutexC)
  • 묶여 있는데, 한번에 한명만 일해 라고 걸어 준것
  • 지워주고 생각
• nrFull
  • 채워진 버퍼 수
• nrEmpty
  • 비어있는 버퍼 수
• nrFull + nrEmpty == N
  • 위의 공식이 항상 성립한다.

‏‏‎ ‎

생산자

1. 생산자가 공간이 있는지 확인
   1. P(nrEmpty)
   2. 공간이 없다면 공간이 생길 때 까지 큐에서 대기
      1. nrEmpty < 0
   3. 공간이 생기면 안으로 들어간다.
      1. nrEmpty > 0
2. 놓을 곳에 물건을 놓는다.
   1. buffer[in] <- M
3. 환형 큐이기 때문에, in(물건을 놓을 자리)를 업데이트 한다.
   1. in <- (in + 1) mod N
4. 물건수를 하나 늘려준다.
   1. V(nrFull)
5. 큐에서 기다리는 소비자 중 하나를 깨운다.

‏‏‎ ‎

소비자

1. 물건이 있는지 확인
   1. P(nrFull)
   2. 물건이 있다면 안으로 들어간다.
      1. nrFull > 0
   3. 물건이 없다면 생길 때 까지 기다린다.
      1. nrFull < 0
2. 꺼낼 곳에서 물건을 꺼낸다.
   1. m <- buffer[out]
3. 꺼낼 자리를 업데이트 한다.
   1. out <- (out + 1) mod N
4. 빈 공간의 수를 하나 늘려준다.
   1. V(nrEmpty)
5. 큐에서 기다리는 생산자 중 하나를 깨운다.

‏‏‎ ‎

네번째 문제 - reader -writer 문제

• Reader
  • 데이터에 대해 읽기 연산만 수행
• Writer
  • 데이터에 대해 갱신 연산만 수행
• 데이터 무결성 보장 필요
  • Reader 들은 동시에 데이터 접근 가능
  • Writer들(또는 reader 와 writer)이 동시에 데이터 접근시, 상호배제(동기화) 필요
• 해결법
  • reader / writer 에 대한 우선권 부여
    • reader preference solution
    • writer preference solution

‏‏‎ ‎

reader preference solution

‏‏‎ ‎

공유 변수

• wmutex, rmutext
  • writer 상호 배제하는 변수
  • reader 상호 배제하는 변수
• nreaders
  • 몇 명의 reader 가 읽고 있는지 나타내는 변수

‏‏‎ ‎

• writer
  • P(wmutex) ~ V(wmutex)
    • 한 명만 쓸 수 있도록 상호 배제시킴
    • 그사이에 쓰기 작업 실시
• reader
  • 1단계 P(rmutex) ~ V(rmutex)
    • 읽으러 들어가기 전 사전 작업
    • 읽는건 여러명이 할 수 있지만 사전작업은 한 명씩 가능
    • 현재 몇명의 리더가 있는지 확인
      • 0 명이라면
        • 이미 누군가 쓰지말라고 걸엇을것
      • 그 이상이라면
        • P(wmutex), 쓰지말라고 거는 것
    • 읽는 사람의 수를 증가시킴
      • nreader <- nreaders + 1
  • 2단계 P(rmutex) ~ V(rmutex)
    • 다 읽은 애가 나갈때 하는 사후작업
    • 한번에 한명 씩
    • 읽는 사람의 수를 감소시킴
      • nreader <- nreaders - 1
    • 읽고 있는 사람의 수를 파악
      • nreaders == 0 이면, 읽고 있는 사람이 없다는 뜻이므로 쓸 수있게 풀어준다.
        • V(wmutex)
      • nreaders != 0 이면, 누군가 읽고 있다는 뜻이므로 만지지 않는다.

Semaphore

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

‏‏‎ ‎