Lecture Notes for Concurrent Programming

24 June 2003 - Using Semaphores

Here are the sequence of steps that will starve writers in favor of readers:

1. Start with no readers or writers at all. A writer enters and gains immediate access to the database. A reader enters next and delays on the r_go signaling semaphore. A writer enters next and delays on the w_go signaling semaphore.

2. The writer exits the database. Because dr > 0, it increases nr by one signals r_go; it then unlocks mtx and drops out of the database.

3. A new reader enters and, because there's a delayed writer, hangs itself on r_go after adding one to dr and unlocking mtx.

4. The reader in r_go that has been signaled drops out of the wait() and locks mtx. It reduces dr by one and, because there are more delayed readers, signals the next reader waiting on r_go. It then goes on to complete the rest of the entry protocol and enters the database.

5. Go to step 3.

If we assume always at least two readers in the database, each exiting reader never is the last reader in the database and so will never release the waiting writer.

This page last modified on 26 June 2003.