Operating Systems: Three Easy Pieces Ch. 31

Semaphores

• both locks and condition variables to solve a broad range of relevant and interesting concurrency problems
• POSIX standard
  • sem_wait()
  • sem_post()
  • sem_init()
    • Second argument → 0: it will be shared between threads on same process
• Binary Semaphores
  • it will wait only if the value is not greater than or equal to 0
  • scheduler state
    • Run
    • Ready
    • Sleep
• Semaphores for ordering
  • Ordering primitives
  • the parent will call sem wait() before the child has called sem post(); we’d like the parent to wait for the child to run.
    • Only when the initial value is 0 is possible
• Producer/Consumer Problem
  • Need to add mutual exclusion
    • using two locks
    • There is a simple cycle here. The consumer holds the mutex and is waiting for the someone to signal full. The producer could signal full but is waiting for the mutex. Thus, the producer and consumer are each stuck waiting for each other: a classic deadlock.
  • Avoiding Deadlock
    • we simply must reduce the scope of the lock
    • using two locks in specific sequences
  • Sometimes, bound buffer
• Reader-Writer Locks
  • The code is pretty simple. If some thread wants to update the data structure in question, it should call the new pair of synchronization operations
  • when the first reader acquires the lock; in that case, the reader also acquires the write lock
  • once a reader has acquired a read lock, more readers will be allowed to acquire the read lock too

  KOCW 운영체제 7: 독자 저자 문제(Readers-Writers Problem)

• dining philosopher’s problem
  • each has times where they think and don’t need any forks, and times when they eat a philosopher needs two forks, both the one on their left and the one on their right
  • deadlock. If each philosopher happens to grab the fork on their left before any philosopher can grab the fork on their right, each will be stuck holding one fork and waiting for another
  • Breaking The Dependency
    • gets the forks in a different order than the others; the put forks() code remains the same
    • cigarette smoker’s problem or the sleeping barber problem

[OS] 식사하는 철학자들 문제(The Dining-Philosophers Problem)

• Thread Throttling
  • A simple semaphore can solve this problem. By initializing the value of the semaphore to the maximum number of threads you wish to enter the memory-intensive region at once, and then putting a sem wait() and sem post() around the region, a semaphore can naturally throttle the number of threads that are ever concurrently in the dangerous region of the code
• Zemaphores