Solutions to Home Work #1 CS414 Fall 2000
1a) The following is a solution for this
question.
/* shared */
semaphore limit =
2;
semaphore mutex =
1;
boolean p1free =
TRUE; /* printer one available? */
boolean p2free =
TRUE; /* printer two available? */
print_anywhere(file)
{
string pr_name; /* local (not shared) variable */
P(limit);
/* no more than two processes at a time */
P(mutex);
/* critical section to select a printer */
if (p1free) then { pr_name = "p1";
p1free = FALSE; }
else { pr_name = "p2"; p2free =
FALSE; }
V(mutex);
/* end of critical section - printer selected */
print(pr_name,file);
if (pr_name == "p1") then p1free =
TRUE;
else p2free = TRUE;
V(limit);
}
1 b) Proof sketch for various properties.
No Deadlocks:
Since mutex is a mutex semaphore and the code section
between a wait and signal of this semaphore cannot block, deadlocks cannot be
caused by waiting on mutex.
Suppose that a chain
of processes is deadlocked on limit.
Then since limit is initialized to 2 and every exit from this
function signals limit, there are at least two processes, which are
currently printing the files. Since the
print function does not block forever, these processes would eventually
not be blocking and signal the semaphore.
So no deadlocks are possible.
No Starvation:
In
this case, usage of OS defined semaphores makes sure that there is no
starvation on waiting on semaphores if there are no deadlocks.
Fair:
Suppose
one of the two printers is currently idle.
Then no process can be waiting on semaphore limit. This is because no two processes can be
printing a file. Suppose there are two
processes P1 and P2 printing the file.
Assume P1 entered the CS controlled by mutex, then when P2 would
have entered the same CS, p1free would have been false and P2 would be
printing on p2. But p2 is idle so P2 is not printing any file
i.e., P2 never entered past P(limit).
The
fairness to ensure that all processes get equal preference to access the
printers depends on the fairness used by OS on processes waiting on a
semaphore.
2 a) The following algorithm solves the problem
sufficiently.
Init:
S.count := 1; N.count := 0;
in
:= out :=0;
append(v)
b[in]
= v;
in++;
take(v)
w:=b[out];
out++;
return w;
Producer:
repeat
produce v;
append(v);
signal(N);
forever
Consumer:
repeat
wait(N);
w:=take();
consume(w);
forever
Since there are only 1 producer and 1 consumer,
only one process is going to access the in variable of the buffer
and only one process is going to access the out variable of the
buffer. So we don't need to have the
mutex semaphore S. It is deadlock free
and starvation free for the same reasons as the algo discussed in the class.
2 b) The
following algorithm solves this problem sufficiently.
Init:
SIn.count := 1; SOut.count :=
1; N.count := 0;
in
:= out :=0;
append(v)
b[in]
= v;
in++;
take(v)
w:=b[out];
out++;
return w;
Producer:
repeat
produce v;
wait(SIn);
append(v);
signal(SIn);
signal(N);
forever
Consumer:
repeat
wait(N);
wait(SOut);
w:=take();
signal(SOut);
consume(w);
forever
Since any item that is currently being appended
cannot be consumed by any consumer until, the append is completely finished
(the N semaphore is signaled after the append has returned), no producer and
consumer will be simultaneously trying to access the same item. Thus synchronization needs to be provided
only between two producers trying to append and two consumers trying to
take. This can be achieved by
introducing two semaphores SIn and SOut instead of S, as shown above. Now the consumer and producer compete
independently for appending and taking, so a consumer can access the buffer
simultaneously as a producer.
3 a) Using the following method creates the
listed problems.
disable interrupts
. enable interrupts
Enter CS Critical Section Exit CS
1. Suppose
the CS takes a very long time to execute then there is a possibility of missing
clock interrupts. This means several
time sensitive operations (CPU
scheduling, Disk accesses, Network accesses) will be severely affected.
2. Suppose
by accident or malice, the CS enters into a state of deadlock or infinite loop,
there is no way of recovering from this state because the clock interrupts
cannot be detected and so these processes will never be preempted by the
scheduler.
b) Semaphore operations signal and wait can be defined using tset or xchang (swap) as follows.
Using TSET:
Semaphore S {
int count;
Q processQ;
bool b;
}
wait(S) {
while(!tset(b)){;} /* acquire lock */
if S.count <= 0;
S.count--;
Set process state to be BLOCKED;
Enter process into S.processQ;
else
S.count--;
S.b := 0; /* release lock */
}
signal(S)
{
while(!tset(b)) {}/* acquire lock */
S.count++;
if S.processQ not empty
Exit process and set its state to READY.
S.b := 0; /* release lock */
}
Using XCHNG:
Semaphore S {
int count;
Q processQ;
int b;
}
wait(S) {
int
a = 1;
/*
acquire lock */
repeat
xchng(a, b));
until (a = 0);
if S.count <= 0;
S.count--;
Set process state to be BLOCKED;
Enter process into S.processQ;
else
S.count--;
S.b := 0; /* release lock */
}
signal(S)
{
int
a = 1;
/*
acquire lock */
repeat
xchng(a, b));
until (a = 0);
S.count++;
if S.processQ not empty
Exit process and set its state to READY.
S.b := 0; /* release lock */
}
4. The following algorithm gives one possible
solution to the problem.
a) Semaphores:
Init:
Ready.count := 0; // controls whether H atom is ready or
not.
Making.count := 1; // allows an O atom to get two H atom at a
time.
Done.count := 0; // signals the end of
reaction to the H atoms.
HReady
{
signal(Ready);
wait(Done);
}
OReady
{
wait(Making);
wait(Ready);
wait(Ready);
signal(Making);
MakeWater;
signal(Done);
signal(Done);
}
Making ensures that an O
atom always gets two H atoms at a time, i.e., suppose there are 2 H atoms and 2
O atoms, we need to make sure that 2 O atoms dont acquire 1 H atom each and
wait indefinitely for more H atoms.
This prevents any dead lock.
Ready and Done
semaphores ensure that each O atom acquires 2 H atom before reacting and each H
atom does not return until the reaction is over.
b) Condition Variables (Monitors):
Monitor {
Condition:
Ready; // H atom is ready.
Done; // Reaction is complete, H
atom can return.
Making; // O atom is trying to
make water.
int
numHatoms; // number of unreacted H
atoms currently present.
bool
waiting; // O atom waiting to make
water.
HReady {
numHatoms++;
/* signal any waiting O atom if present */
csignal(Ready);
/* wait for water to be made. */
cwait(Done);
}
OReady {
/* if another O atom is in the monitor, then wait for it to exit. */
If (waiting)
cwait(Making);
waiting := true;
/* if there is a H atom in the monitor then dont wait for it. */
If (numHatoms == 0)
cwait(Ready);
numHatoms--;
/* if there is another H atom in the monitor then dont wait for it */
If (numHatoms == 0)
cwait(Ready);
numHatoms--;
MakeWater;
/* awaken the waiting H atoms and let
them exit. */
csignal(Done);
csignal(Done);
/* signal any other O atoms if present to enter. */
waiting := false;
csignal(Making);
}
}
Note that in a monitor, a signal on a condition
variable will not perform anything if no other process is waiting on it. That is why we need variables like numHatoms
to make sure an O atom waits only if there are no H atoms already in the monitor.
In order to ensure 2 O atoms acquire both the H
atoms together, any O atom is made to wait if there is another O atom already
in the monitor.