[OS] Synchronization 2

Types of Semaphores

• Binary semaphore (mutex)
  • Semaphore value is initialized to 1
  • Guarantee mutually exclusive access to resource
• Counting semaphore
  • Semaphore value is initialized to N
  • Represent a resource with many units available
  • Allow threads to enter as long as some units are available

Classical Problems of Synchronization

• Bounded-buffer problem
• Reader and writers problem
• Dining-philosophers problem

Bounded buffer Problem (Producer / consumer problem)

• There is a set of resource buffers shared by producers and consumers
• Producers insert resources into the buffer
• Consumers remove resources from the buffer

• Producers and consumers execute at different rates

• No synchronization case

• Using mutex or semaphore case

Readers-Writers Problem

• Sharing resource among multiple readers and writers
  • An object is shared among several threads
  • Some threads only read the object, others only write it
  • We can allow multiple readers at a time
  • We can only allow one writer at a time
• Implementation with semaphores
  • readcount : # of threads reading object
  • mutex : control access to readcount
  • rw : exclusive writing or reading

• If there is a writer
  • The first reader blocks on rw
  • All other readers will then block on mutex
• Once a writer exits, all readers can fall through
  • Which reader gets to go first?
• The last reader to exit signals waiting writer
  • Can new readers get in while writer is waiting?
• When a writer exits, if there is both a reader and writer waiting, which one goes next is up to scheduler

Dining Philosophers Problem

• Each philosopher repeats forever:
  • Thinking
  • Pick up two forks (chopsticks) -> left first, if can’t then wait
  • Eating
  • Put down two forks (chopsticks)

• Deadlock occur
  • Mutual Exclusion : A chopstick can be used by one philosopher at a time
  • Hold and wait : Philosophers hold one chopstick and wait for the other
  • No preemption : Nobody can take other’s chopsticks
  • Circular wait : All philosopher wait for their right-side chopstick