Synchronization, Part 7: The Reader Writer Problem - tcloaa/SystemProgramming GitHub Wiki

Imagine you had a key-value map data structure which is used by many threads. Multiple threads should be able to look up (read) values at the same time provided the data structure is not being written to. The writers are not so gregarious - to avoid data corruption, only one thread at a time may modify (write) the data structure (and no readers may be reading at that time).

<<<<<<< HEAD The is an example of the Reader Writer Problem. Namely how can we efficiently synchronize multiple readers and writers such that multiple readers can read together but a writer gets exclusive access?

1. There can be multiple active readers
   True (you don't change the content, so this is all good)
2. There can be multiple active writers
   False (you don't want to start writing over each other)
3. When there is an active writer the number of active readers must be zero
   True (you can't try to change what someone is reading while they're reading it)
4. If there is an active reader the number of active writers must be zero
   True (you can't read while someone is modifying what you're reading)
5. A writer must wait until the current active readers have finished
   True (it does get priority over future readers, though)

An incorrect attempt is shown below ("lock" is a shorthand for pthread_mutex_lock):

read() {
  lock(&m)
  // do read stuff
  unlock(&m)
}

write() {
  lock(&m)
  // do write stuff
  unlock(&m)
}

Not good: Reader 竟然要等reader!

read() {
  while(writing) {/*spin*/}
  reading = 1
  // do read stuff
  reading = 0
}

write() {
  while(reading || writing) {/*spin*/}
  writing = 1
  // do write stuff
  writing = 0
}

错在：race condition

• P1 call read, P2 call write
• sdf

imagine if two threads both called read and write (or both called write) at the same time. Both threads would be able to proceed! Secondly, we can have multiple readers and multiple writers,

so lets keep track of the total number of readers or writers. Which brings us to attempt #3,

read() {
  lock(&m)
  while (writers) {
    pthread_cond_wait(&cv,&m)
  }
  readers++
  // do read stuff
  readers--
  pthread_cond_signal(&cv)
  unlock(&m)
}

write() {
  lock(&m)
  while (readers || writers) {
    pthread_cond_wait(&cv,&m)
  }
  writers++
  // do write stuff
  writers--
  pthread_cond_signal(&cv)
  unlock(&m)
}

This solution might appear to work when lightly tested however it suffers from several drawbacks - can you see them? We will discuss these in a future section.