$16\mathrm{.}14($Readers and Writers$)$ This exercise asks you to develop a Java monitor to solve a famous problem in concurrency control. This problem was first discussed and solved by P$.$ J$.$ Courtois, F$.$ Heymans and D$.$ L$.$ Parnas in their research paper, $$Concurrent Control with Readers and Writers,$$ Communications of the ACM, Vol. $14,$ No$.10,$ October $1971,$ pp$.667668.$ The interested student might also want to read C$.$ A$.$ R$.$ Hoare$$s seminal research paper on monitors, $$Monitors: An Operating System Structuring Concept,$$ Communications of the ACM, Vol. $17,$ No$.10,$ October $1974,$ pp$.549557.$ Corrigendum, Communications of the ACM, Vol. $18,$ No$.2,$ February $1975,$ p$.95.[$The Readers and Writers problem is discussed at length in Chapter $5$ of the author$$s book: Deitel, H$.$ M$.,$ Operating Systems, Reading, MA: Addison$-$Wesley, $1990.]$

a$)$ With multithreading, many threads can access shared objects; as we have seen, access to shared objects needs to be synchronized carefully to avoid corrupting the objects.

b$)$ Consider an airline$-$reservation system in which many clients are attempting to book seats on particular flights between particular cities. All of the information about flights and seats is stored in a common database in memory. The database consists of many entries, each representing a seat on a particular flight for a particular day between particular cities. In a typical airline$-$reservation scenario, the client will probe around in the database looking for the $$optimal$$ flight to meet that client$$s needs. So a client may probe the database many times before deciding to book a particular flight. A seat that was available during this probing phase could easily be booked by someone else before the client has a chance to book it$.$ In that case, when the client attempts to make the reservation, the client will discover that the data has changed and the flight is no longer available.

c$)$ The client probing around the database is called a reader. The client attempting to book the flight is called a writer. Clearly, any number of readers can be probing the shared object at once, but each writer needs exclusive access to the shared object to prevent the object from being corrupted.

d$)$ Write a multithreaded Java program that launches multiple reader threads and multiple writer threads, each attempting to access a single reservation record. A writer thread has two possible transactions, makeReservation and cancelReservation. A reader has one possible transaction, queryReservation.

e$)$ First implement a version of your program that allows unsynchronized access to the reservation record. Show how the integrity of the database can be corrupted. Next implement a version of your program that uses Java monitor synchronization with wait and

notify to enforce a disciplined protocol for readers and writers accessing the shared reservation data. In particular, your program should allow multiple readers to access the shared object simultaneously when no writer is active. But if a writer is active, then no readers should be allowed to access the shared object.

f$)$ Be careful. This problem has many subtleties. For example, what happens when there are several active readers and a writer wants to write? If we allow a steady stream of readers to arrive and share the object, they could indefinitely postpone the writer $($who may become tired of waiting and take his or her business elsewhere$).$ To solve this problem, you might decide to favor writers over readers. But here, too, there is a trap, because a steady stream of writers could then indefinitely postpone the waiting readers, and they, too, might choose to take their business elsewhere! Implement your monitor with the following methods: startReading, which is called by any reader who wants to begin accessing a reservation; stopReading to be called by any reader who has finished reading a reservation; startWriting to be called by any writer who wants to make a reservation and stopWriting to be called by any writer who has finished making a reservation.