Review: Semaphores

• Semaphore: non-negative global integer synchronization variable. Manipulated by P and V operations.

s >=0이고 P와 V함수를 이용해서 cs를 보호할 수 있다.

• P(s)
  • If s is nonzero, then decrement s by 1 and return immediately.
  • If s is zero, then suspend thread until s becomes nonzero and the thread is restarted by a V operation.
  • After restarting, the P operation decrements s and returns control to the caller.

P가 0이 아니면 1을 줄이고 0이면 suspend한다.

• V(s):
  • Increment s by 1.
  • If there are any threads blocked in a P operation waiting for s to become non-zero, then restart exactly one of those threads, which then completes its P operation by decrementing s.

V는 s를 증가시키고 누군가 s를 기다리는 스레드가 있다면 그 중에 한 명을 깨워준다.

• Semaphore invariant: (s >= 0)

Review: Using semaphores to protect shared resources via mutual exclusion

• Basic idea:
  • Associate a unique semaphore mutex, initially 1, with each shared variable (or related set of shared variables)
  • Surround each access to the shared variable(s) with

=== Using Semaphores to Coordinate Access to Shared Resources ===

• Basic idea: Thread uses a semaphore operation to notify another thread that some condition has become true

  • Use counting semaphores to keep track of resource state and to notify other threads
  • Use mutex to protect access to resource

• Two classic examples:

  • The Producer-Consumer Problem
  • The Readers-Writers Problem

1. Producer-Consumer Problem

producer-consumer은 생성자와 소비자 문제라고 생각하면 된다. shared buffer은 array로 된 버퍼로 하나씩 채워나간다. producer입장에서는 계속 채우다가 array가 full되면 중단한다. consumer은 array가 empty가 아니면 계속 소비한다.

이 두 스레드가 concurrent 하게 돌아가면 producer은 무언가를 생성하고 concumer에게 알려준다. consumer은 item을 기다리다가 item이 있으면 buffer로 부터 아이템을 빼낸다. 만약 뺏다면 producer에게 알려준다.

• Common synchronization pattern:

  • Producer waits for empty slot, inserts item in buffer, and notifies consumer
  • Consumer waits for item, removes it from buffer, and notifies producer

• Examples

  • Multimedia processing:
    • Producer creates MPEG video frames, consumer renders them
  • Event-driven graphical user interfaces
    • Producer detects mouse clicks, mouse movements, and keyboard hits and inserts corresponding events in buffer
    • Consumer retrieves events from buffer and paints the display

Producer-Consumer on an n-element Buffer

• Requires a mutex and two counting semaphores:
  • mutex: enforces mutually exclusive access to the the buffer
  • slots: counts the available slots in the buffer
  • items: counts the available items in the buffer
• Implemented using a shared buffer package called sbuf.

producer, consumer은 n개의 element buffer을 가지고 있다. 우리가 여기에서는 두개의 counting semaphore을 가지고 있다.
mutex는 그냥 s가 1인 것을 이야기 한다.

counting semaphore은 slot이 몇개가 있느냐 즉 buffer에 몇개가 남아있는지를 카운팅한다.(Producer)

item은 buffer에 아이템을 몇개의 아이템을 집어넣었는가를 카운팅한다.(Consumer)

sbuf_t로 구현되어 있다.

sbuf Package - Declarations

buf는 array, front, rear은 array의 아이템 위치
mutex는 buffer에 접근하는 mutual exclusive를 위한 binary semaphore이다.
slots, items은 count이다.

sbuf_init으로 초기화
buf에 insert, remove -> sbuf_insert, sbuf_remove를 사용한다.

sbuf Package - Implementation

Initializing and deinitializing a shared buffer:

---

Inserting an item into a shared buffer:

insert는 producer가 호출한다.
sp->buf부분은 아이템을 집어넣는 부분으로 cs이기 때문에 잡아놓는다. 그리고 이 부분이 끝나면 깨워준다.

어떤 순서로 P, V를 하는지 잘 보자

---

Removing an item from a shared buffer:

remove는 consumer가 호출한다.

Readers-Writers Problem

• Generalization of the mutual exclusion problem

multiple reader, writer가 존재시 어떻게 mutual exclusion 문제를 해결할지이다.

• Problem statement:
  • Reader threads only read the object
  • Writer threads modify the object
  • Writers must have exclusive access to the object
  • Unlimited number of readers can access the object

문제는 object를 여러 스레드가 read, write하고 있다. Writer 입장에서는 그 object를 배타적으로 접근해야 한다. 무조건 자기혼자만 써야 한다.
만약 누군가가 read하고 있다면 무한대로 읽을 수 있다.

• Occurs frequently in real systems, e.g.,
  • Online airline reservation system
  • Multithreaded caching Web proxy

Variants of Readers-Writers

• First readers-writers problem (favors readers)
  • No reader should be kept waiting unless a writer has already been granted permission to use the object
  • A reader that arrives after a waiting writer gets priority over the writer

reader에게 우선순위를 주는 것이다. 아무도 안읽고 있을때는 writer가 쓸 수 있다. reader는 계속해서 오는 reader들이 읽을 수 있다.

• Second readers-writers problem (favors writers)
  • Once a writer is ready to write, it performs its write as soon as possible
  • A reader that arrives after a writer must wait, even if the writer is also waiting

writer에게 favor을 주는 방향은 누군가가 쓰고 있다면 그것을 빨린 끝내게 하는 것이다. 그래서 writer에게 favor을 주는 방법이다.

• Starvation (where a thread waits indefinitely) is possible in both cases

하지만 두개다 starvation문제가 존재한다.

Solution to First Readers-Writers Problem