Readers-writers problem

Readers-writers problem

In computer science, the first and second readers-writers problems are examples of a common computing problem in concurrency. The two problems deal with situations in which many threads must access the same shared memory at one time, some reading and some writing, with the natural constraint that no process may access the share for reading or writing while another process is in the act of writing to it. (In particular, it "is" allowed for two readers to access the share at the same time.) A readers-writer lock is a data structure that solves one or more of the readers-writers problems.

The first readers-writers problem

Suppose we have a shared memory area with the constraints detailed above. It is possible to protect the shared data behind a mutex, in which case clearly no thread can access the data at the same time as another writer. However, this solution is suboptimal, because it is possible that a reader "R1" might have the lock, and then another reader "R2" request access. It would be foolish for "R2" to wait until "R1" was done before starting its own read operation; instead, "R2" should start right away. This is the motivation for the first readers-writers problem, in which the constraint is added that "no reader shall be kept waiting if the share is currently opened for reading." This is also called readers-preference.--

The second readers-writers problem

Suppose we have a shared memory area protected by a mutex, as above. This solution is suboptimal, because it is possible that a reader "R1" might have the lock, a writer "W" be waiting for the lock, and then a reader "R2" request access. It would be foolish for "R2" to jump in immediately, ahead of "W"; if that happened often enough, "W" would starve. Instead, "W" should start as soon as possible. This is the motivation for the second readers-writers problem, in which the constraint is added that "no writer, once added to the queue, shall be kept waiting longer than absolutely necessary." This is also called writers-preference.

The third readers-writers problem

In fact, the solutions implied by both problem statements result in starvation — the first readers-writers problem may starve writers in the queue, and the second readers-writers problem may starve readers. Therefore, the third readers-writers problem is sometimes proposed, which adds the constraint that "no thread shall be allowed to starve"; that is, the operation of obtaining a lock on the shared data will always terminate in a bounded amount of time. Solutions to the third readers-writers problem will necessarily sometimes require readers to wait even though the share is opened for reading, and sometimes require writers to wait longer than absolutely necessary.

ee also

* Producers-consumers problem
* Dining philosophers problem
* Cigarette smokers problem
* Sleeping barber problem


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Readers–writer lock — In computer science, a readers writer or shared exclusive lock (also known as the multiple readers / single writer lock[1] or the multi reader lock,[2] or by typographical variants such as readers/writers lock) is a synchronization primitive that …   Wikipedia

  • Readers-writer lock — In computer science, a readers writer lock (also known by the name multi reader lock , or by typographical variants such as readers/writers lock) is a synchronization primitive that solves one of the readers writers problems. A readers writer… …   Wikipedia

  • Dining philosophers problem — In computer science, the dining philosophers problem is an example problem often used in concurrent algorithm design to illustrate synchronization issues and techniques for resolving them. It was originally formulated in 1965 by Edsger Dijkstra… …   Wikipedia

  • Producer-consumer problem — In computer science, the producer consumer problem (also known as the bounded buffer problem) is a classical example of a multi process synchronization problem. The problem describes two processes, the producer and the consumer, who share a… …   Wikipedia

  • Sleeping barber problem — In computer science, the sleeping barber problem is a classic inter process communication and synchronization problem between multiple operating system processes. The problem is analogous to that of keeping a barber working when there are… …   Wikipedia

  • Monty Hall problem — In search of a new car, the player picks a door, say 1. The game host then opens one of the other doors, say 3, to reveal a goat and offers to let the player pick door 2 instead of door 1. The Monty Hall problem is a probability puzzle loosely… …   Wikipedia

  • LETTERS AND LETTER WRITERS — The letter holds an honored place in Jewish history and literature and includes diplomatic correspondence, state papers, and letters as vehicles of religious or secular literature and as a means of polemics in communal and spiritual matters,… …   Encyclopedia of Judaism

  • Semaphore (programming) — For other uses, see Semaphore (disambiguation). In computer science, a semaphore is a variable or abstract data type that provides a simple but useful abstraction for controlling access by multiple processes to a common resource in a parallel… …   Wikipedia

  • Communications protocol — For other senses of this word, see Protocol. A communications protocol is a system of digital message formats and rules for exchanging those messages in or between computing systems and in telecommunications. A protocol may have a formal… …   Wikipedia

  • JOB, BOOK OF — (named for its hero (Heb. אִיּוֹב), ancient South Arabian and Thamudic yʾb; Old Babylonian Ayyābum, Tell el Amarna tablet, no. 256, line 6, A ia ab; either from yʾb, to bear ill will or compounded of ay where? and ʾab (divine) father ), one of… …   Encyclopedia of Judaism

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”