take one of the topics in the readings, find a reference outside our readings ta
ID: 3822267 • Letter: T
Question
take one of the topics in the readings,
find a reference outside our readings talking about that topic
cite your reference
tell us a little about how the two presentations relate to each other
tell us what you have learned about that topic from your readings
Some suggested topics:
Spin locks
Atomic read/write operations vs the real world
Sequentially consistent memory
Memory barrier instructions
Test and set locks: getAndSet (), compareAndSet ()
Monitors, locks, conditions
Locked queue
Lost wake up events
Readers writers locks
Reentrant locks
Semaphores
Threads - creating and running them
Thread structure of the JVM and the Java GUI classes
Race conditions and deadlocks
Writing a concurrent program
condition variables
producer-consumer problem
finding objects
active, passive and control objects
Explanation / Answer
In computing, the producer–consumer problem (also known as the bounded-buffer problem) is a classic example of a multi-process synchronization problem. The problem describes two processes, the producer and the consumer, who share a common, fixed-size buffer used as a queue. The producer's job is to generate data, put it into the buffer, and start again. At the same time, the consumer is consuming the data (i.e., removing it from the buffer), one piece at a time. The problem is to make sure that the producer won't try to add data into the buffer if it's full and that the consumer won't try to remove data from an empty buffer.
The solution for the producer is to either go to sleep or discard data if the buffer is full. The next time the consumer removes an item from the buffer, it notifies the producer, who starts to fill the buffer again. In the same way, the consumer can go to sleep if it finds the buffer to be empty. The next time the producer puts data into the buffer, it wakes up the sleeping consumer. The solution can be reached by means of inter-process communication, typically using semaphores. An inadequate solution could result in a deadlock where both processes are waiting to be awakened. The problem can also be generalized to have multiple producers and consumers.
To solve the problem, a less experienced programmer might come up with a solution shown below. In the solution two library routines are used, sleep and wakeup. When sleep is called, the caller is blocked until another process wakes it up by using the wakeup routine. The global variable itemCount holds the number of items in the buffer.
The problem with this solution is that it contains a race condition that can lead to a deadlock. Consider the following scenario:
Since both processes will sleep forever, we have run into a deadlock. This solution therefore is unsatisfactory.
Semaphores solve the problem of lost wakeup calls. In the solution below we use two semaphores, fillCount and emptyCount, to solve the problem. fillCount is the number of items already in the buffer and available to be read, while emptyCount is the number of available spaces in the buffer where items could be written. fillCount is incremented and emptyCount decremented when a new item is put into the buffer. If the producer tries to decrement emptyCount when its value is zero, the producer is put to sleep. The next time an item is consumed, emptyCount is incremented and the producer wakes up. The consumer works analogously.
The solution above works fine when there is only one producer and consumer. With multiple producers sharing the same memory space for the item buffer, or multiple consumers sharing the same memory space, this solution contains a serious race condition that could result in two or more processes reading or writing into the same slot at the same time.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.