Q:  For question 3, you are asking us about mutual exclusion.  But, any
process that waits on the same semaphore twice without a release
in-between will suspend itself, and any other processes that wait on
that semaphore, indefinitely.  So are you asking us about mutual
exclusion ignoring this fact, or do you want us to keep things like
deadlock in mind?

A:  It is not true that any process that waits twice on the same
semaphore without an intervening release (meaning "V") will
suspend itself.  Look at a "producer," for example.

A:  Consider the following people:  The person writing the
scheduler, the person designing the chip, the person writing
a large application that will spawn several threads, the person
implementing a solution to the "readers-writers" problem.  For
some of these people, it makes more sense to think of processes
running in parallel, and for others it does not.  I want you to
give a general criterion for when a person will benefit from
thinking of the processes as running in parallel.

A:  Sorry...seems to have been a mailing issue.  It is supposed
to simply be "naive."

Does that mean while k > 0?

A:  Yes.  Another mailing issue, I suppose.

In part (e), we are asked to prove that f(n)>1.5^n for ALL n.  Well, in
the case of zero, this can not be true as 1 is not greater than 1.  Am I
completely missing the boat here, or should we try to prove that
f(n)>=1.5^n?

A:  A most excellent question.  I suppose it hadn't occurred to me to
consider the "0" case.  Prove simply that it will be true, except for the
first few cases.  It turns out that it is eventually always true.

A:  Hard copy, please.

"When P3 exits, P1 must be allowed into its critical section before P2."

Does this mean that when P3 completes its CS, P1 MUST be the next process to
enter its CS, even if only P2 was waiting while P3 was in the CS?

This makes a huge difference in how I apply semaphores.

A:  No.  Sorry for the ambiguity.  I mean that if both P1 and P2
wish to enter the critical region while P3 is in there, then P2 should
be allowed in first, regardless of the order in which P1 and P2 declared
their interest.

A:  You need to address a few cases, but not many.  Perhaps even just one
if you word it right.  The idea is to discuss whether mutual exclusion can
happen with a proper initialization (which you get to do) and if it will have all
the properties we desire of a good mutual exclusion algorithm.

---You may not discuss this exam with any other student.

---You may consult your text and any other texts that you
   wish, as well as the internet.

---This document is best viewed with a fixed-width font.

1. Suppose that you wish to solve the producer-consumer
problem in the case when the buffer is not of bounded size.
Find a simpler way to achieve this than in the case
when the buffer is bounded.
 

2. Two processes share data which is accessed from within
their critical sections. Our system has none of the
synchronization primitives we discussed in class, but there
is available a machine instruction swap(r, m) which you may
use. This atomic instruction swaps the contents of
register r with the contents of memory location m. Show how
you can use this primitive to achieve mutual exclusion.
(Note: Do not worry about syntax; any way you use or call
the swap function is fine.)
 

3. A student, so impressed with the effectiveness of
semaphores and how they can guarantee mutual exclusion,
decided that using them twice would be even *more* effective.

Consider this code for two processes:
 

Initialize P1          P2 -------     ------- ...         ... P(s);       P(s); P(s);       P(s); CS---       CS--- V(s);       V(s); V(s);       V(s); ...         ...

What would you place in the "Initialize" portion of the
program (which is run once before either process is started)
to guarantee mutual exclusion? Can it be done? Either show
how it could be done, or discuss thoroughly why it cannot
be done. Note, you may only change the code in the
initialize portion.
 

4. Even though several processes are running on a single
processor, why does it make sense sometimes to think of those
processes as running in parallel. When does this make sense?
 

5. Someone wishes to protect access by two processes to some
critical shared resources in the following way:
 

Initialize P1                   P2 -------              ------- ...                  ... P(s1);               P(s2); Access resource 1    Access resource 2 P(s2);               P(s1); Access resource 2    Access resource 1 V(s2);               V(s1); V(s1);               V(s2); ...                  ...

What, if anything, could go wrong with this setup?
 

6. Three processes, P1, P2 and P3 all access a common
shared resource via their critical sections. P3 has a
rather long critical section, while P1 and P2 have shorter
critical sections. Only one process may be in its critical
section at a time. A programmer wishes to make sure that
the following will happen: If P3 is in its critical
section when P1 and P2 both try to access their critical
sections, then P1 and P2 will block (of course) until P3
exits its critical section. But when P3 exits, P1 must
be allowed into its critical section before P2. Use
semaphores to guarantee this behavior.

Note that in the naïve implementation which uses a single
mutex semaphore to protect the regions, P1 and P2 would
be served on a first-come-first-served basis, not guaranteeing
that P1 would get in first. You need to do something more
clever.
 

7. Prove that Peterson's solution avoids deadlock and
starvation.
 

8. Consider the following code:
 

#define N 2 void main(){    k = N;    while(k > 0)       if(fork() == 0)          k--;       else          k -= 2;    return(); }

a. How many distinct processes will be spawned, including
the original process?
b. Repeat part a. if you "#define N 3" instead.
c. Repeat part a. if you "#define N 4" instead.
d. Let f(n) be the number of processes spawned when the
first line is changed to "#define N n". Find a recurrence
relation for f(n).
e. Prove that f(n) > 1.5^n for all n. That is, prove that
the number of spawned processes grows exponentially with n.