CS414 Prelim 1. 10:15 to 11:25.
Three
problems, 25 points each. Closed book.
Assume that each of method is a single
thread and that the puzzle is a shared object these three threads access
concurrently. Each thread looks at the
list of questions, finds one it can answer (reading the puzzle if needed), and
then writes down the answer. Sometimes,
a guess turns out to be wrong. When a
thread realizes that an existing word is incorrect, it can also erase that
word, by “writing” blanks as necessary.
In the example below, if 1-across used to contain “dog”, perhaps the
thread that wanted to put “apple” into 1-down first erased “dog”, so that the
“a” would make sense.
For simplicity, we’re not going to think about how the threads figure
out who will work on which clue.
Instead, we’ll focus only on
the way that threads access the puzzle.
Our challenge is to maintain a high degree of concurrency, but to avoid
“conflicts” where two threads try to update the same cells in different ways at
the same time. Other aspects of solving
the problem, such as recognizing that an initial guess was wrong, marking a
clue as “apparently solved,” or putting a clue back on the list of unsolved
clues are not part
of the problem today.
Below are several options for
synchronization. In each case, comment
very briefly on whether it would work, how well it would work, and why.
A sample crossword puzzle:
Across:
1.
Witch’s
pet
2.
Apricot
_________
Down:
1.
Newton’s
inspiration
a)
Associate
a separate mutex semaphore with each square – one semaphore for each
letter. Obtain mutual exclusion prior
to reading, writing or erasing that letter.
Release it immediately after doing so, before obtaining mutex for the
next letter.
b)
Like
(a) in that we have an array of mutex semaphores, one per cell on the
puzzle. But this time, obtain mutual
exclusion prior to reading, writing or erasing each word, by waiting on the single semaphore
associated with the first letter of that word. Release the mutex after reading
or writing the whole word. To write
“apple”, number 1 down, you wait on the semaphore for the cell containing the
“a”, numbered 1-down.
c)
Same
as (c) but before writing or erasing a word, obtain mutual exclusion for every
word your word will overlap. For
example, if 9-down crosses 3-across and 6-across, first obtain mutual exclusion
using the semaphores associated with all three words. Obtain these in alphabetic order: 3-across, 6-across, 9-down,
etc.
d)
Same
as (c) but using a reader’s and writers solution, with separate semaphores for
each word. If you are reading 9-down
and it crosses 3-across, you’ll do a start-read for both words. If you are writing 9-down you’ll do a
start-write for both words before writing any letters.
e)
Does
it matter that in (c) and (d) the semaphores are obtained in alphabetical
order? Suppose we had said you can do
it in a random order. Would that make
the solution incorrect? Explain
briefly. If the solution would still
work, would it be better?
2.
Below is the Bakery algorithm, using the same code
and notation we employed in class.
Recall that (a,x)<(b,y) means “(a < b) or (a=b and x<y)”. Assume that N=5.
#define true 1
#define false 0
int number[N],
choosing[N]; /* Initially number[i] =
0, choosing[i] = false */
Process Pi:
while (1) {
do something else
choosing[i] = true;
ticket[i] =
max(number[0]…number[N-1])+1;
choosing[i] =
false;
for(k = 0; k
< N; ++k) {
while(choosing[k]
) loop;
while((number[k],k)
< (number[i],i)) loop;
}
number[i] :=
0;
}
Suppose that
process 0 is in the “do something else” code when process 2 enters the critical
section, and that process 2 has number value 5. Now suppose that process 0 finishes the “do something else code”
while process 2 is still in the critical section. The next line that process 0 will execute is “choosing[0] = true;” Which of the following are
possibilities? Explain, by reference to
the code, why each can or cannot occur, explaining the conditions that can
cause the scenario to arise, or explaining why no possible execution sequence
can cause this to happen. Don’t worry
about numbers overflowing, but do consider possible actions by other
processes.
a)
Process 2 has not yet left
the critical section, yet process 0 doesn’t wait when it executes the while
loop “while((number[2],2) < (number[0],0)) loop”
b)
Process 2 is able to leave
and re-enter the critical section three times before Process 0 is able to enter
it even once.
c)
Process 1 enters the
critical section three times before process 0 enters it even once.
d)
When process 0 enters the
critical section, it prints number[0].
The value is 1.
e)
Process 0 never enters the critical
section, although other processes continue to do so.
3. Suppose that an operating system uses read and write locks to
control file access. You can assume
that each process accesses many files, and that the order in which this happens
can’t be controlled or predicted. These
locks work like the readers and writers mechanism we discussed in class – you
obtain a read lock by calling “BeginRead” and release it with “EndRead”, etc.
a) Give a very simple execution example, with as few processes and
files as possible, in which a deadlock arises.
b) Suppose that the
operating system maintains a process-wait graph, so that if process i holds
a lock and process j is trying to obtain that lock, there will be a node
for i, a node for j, and an arrow from i to j. Now, suppose that before allowing a process
to obtain a requested lock, the operating system adds the associated wait edge
to the graph, and runs a reducibility test.
It grants the lock request only if the graph is reducible. Otherwise, the lock request fails with the
error code “EMIGHTDEADLOCK”. Would
this avoid the risk of deadlocks?
c) Same scenario as part
(b). Now suppose that when an
application gets the error code EMGHTDEADLOCK it waits for a random amount of
time between 0 and 1 second, then requests the lock again, and loops in this
manner. Would this result in a correct
system? Explain.