|
UNIVERSITY OF WISCONSIN-MADISON
Computer Sciences Department |
||||
|
CS 537
Spring 2000 |
CS703 - Assignment No 2 |
A. Arpaci-Dusseau
|
||
|
Solutions to Quiz #3: Wednesday,
February 23
|
Readers and Writers
The following code implements the readers-writers problem
with semaphores. It should be identical to that given to you in the Lecture
Notes (no tricks here).
The main thread of the program (not shown) creates many reader and writer
threads, starts each of them, and then waits forever for them to terminate by
calling each thread's join() method. class ReaderOrWriter implements Runnable {
private static int sharedBuffer[] = new int[1000]; private static Semaphore mutex = new Semaphore(??);
private static Semaphore OKToRead = new Semaphore(??);
private static Semaphore OKToWrite = new Semaphore(??);
private static int ActiveWriters = 0;
private static int WaitingWriters = 0;
private static int ActiveReaders = 0;
private static int WaitingReaders = 0;
public static final int READER = 0;
public static final int WRITER = 1;
private int whichAmI;
|
|
ReaderOrWriter(int ReaderOrWriter) {
whichAmI = ReaderOrWriter;
} |
|
public void run() {
while (true) {
if (whichAmI == READER) {
reader();
} else {
writer();
}
}
} |
|
private void reader() {
mutex.P();
if ((ActiveWriters + WaitingWriters) == 0){
OKToRead.V();
ActiveReaders++;
} else {
WaitingReaders++;
}
mutex.V();
OKToRead.P();
// Perform read of sharedBuffer
mutex.P();
ActiveReaders--;
if ((ActiveReaders == 0) && (WaitingWriters > 0)) {
OKToWrite.V();
ActiveWriters++;
WaitingWriters--;
}
mutex.V();
} |
|
private void writer() {
mutex.P();
if ((ActiveWriters + ActiveReaders + WaitingWriters) == 0) {
OKToWrite.V();
ActiveWriters++;
} else {
WaitingWriters++; }
mutex.V();
OKToWrite.P();
// Perform write of dataBuffer
mutex.P();
ActiveWriters--;
if (WaitingWriters > 0) {
OKToWrite.V();
ActiveWriters++;
WaitingWriters--;
} else {
while (WaitingReaders > 0) {
OKToRead.V();
ActiveReaders++;
WaitingReaders--;
}
}
mutex.V();
} |
|
You need to answer five questions about this code segment. Each will be worth the same number of points. No partial credit will be given for a question, so just state your final answer -- no need to explain your reasoning.
- What values
should each of the semaphores be initialized to?
a) mutex: 1
All semaphores used for mutual exclusion are always initialized to 1, representing the number of threads that can be in the critical section.
b) OKToRead: 0
OKToRead is set to the number of additional reader threads that are allowed to access the shared buffer. It starts out at zero, and then once a thread checks and sees that it can read the buffer, it increments the semaphore count by calling V().
OKToRead is set to the number of additional reader threads that are allowed to access the shared buffer. It starts out at zero, and then once a thread checks and sees that it can read the buffer, it increments the semaphore count by calling V().
c) OKToWrite: 0
OKToWrite is set to the number of writer threads that are allowed to access the shared buffer (it can only be 0 or 1). It starts out at zero, and then once a thread checks and sees that it can write the buffer, it increments the semaphore count by calling V().
OKToWrite is set to the number of writer threads that are allowed to access the shared buffer (it can only be 0 or 1). It starts out at zero, and then once a thread checks and sees that it can write the buffer, it increments the semaphore count by calling V().
- a)
Assume a reader is currently using the buffer.
If there are both waiting writers and waiting readers, will a writer or a reader get access to the buffer first?
No matter what type of thread is accessing the
buffer, this code gives priority to writers. Therefore a writer will always get
access to the buffer first. A reader can't access the buffer if there are any
waiting writers.
b) Assume a writer is currently using the
buffer.
If there are both waiting writers and waiting readers, will a writer or a reader get access to the buffer first?
If there are both waiting writers and waiting readers, will a writer or a reader get access to the buffer first?
As above, a writer will get access next.
- a) Is it possible for readers to starve with this code?
Yes, since writers always get priority, it is
possible a reader will always have to wait for a continuous stream of writers
to finish.
b) Is it possible for writers?
No, it is not possible. First, waiting readers
can't prevent a waiting writer from accessing the buffer as explained in
question 2. Second, because the list of waiting writers on the semaphore,
OKToWrite, is kept in FIFO order, every waiting writer thread is guaranteed to
be eventually woken up and scheduled.
- a) Can the semaphore OKToRead have a value greater than 1?
Yes, it will get incremented to the number of
readers that can still access the buffer, but haven't yet. Multiple readers can
access the buffer simultaneously (as long as there aren't any waiting writers).
b) Can OKToWrite?
No, there can be only one writer at a time.
- Assume
there are many readers currently accessing the buffer.
a) Is the first writer to execute mutex.P() guaranteed to be the first writer to use the buffer?
No, there could be a context-switch between the
time when the writer releases the mutex and when it calls OKToWrite.P(); if a
second writer is scheduled at this point, it may sneak in and execute all of
the code between mutex.P() and mutex.V() and be the first process to wait on
OKToWrite.P().
b) Is the first writer to execute OKToWrite.P()
guaranteed to be the first writer to use the buffer?
Yes, because the semaphore is implemented with a
FIFO list of waiting processes, the first process to wait will be the first
process woken up by OKToWrite.V().
