1. Let L be a doubly linked
list similar to the ready list RL of your Program #1. Assume that
the list header also has forward and backward pointers. Suppose that a
thread P was inserting a new node X at the front of L
and, at the same time, another thread Q was also inserting a new
node Y at the front of L. Assume that the insertion routine
was not protected by a critical section lock.
Show how an inconsistent or incorrect
data structure L can result from these unprotected insertions. Do
this by exhibiting a sequence of atomic interleaved operations performed
by the threads.
(Draw some pictures with references
or pointers, or illustrate with code (C/C++ or Java), whichever you prefer.)
Answer:
Say the code for the insert(Node* n) looks like this:
void insert(Node* n)
{
n.prev = head.prev;
n.next = head;
head.prev
= n;
head = n;
}
Now if two processes (say P1 and P2) are allowed to call insert(Node* n) at the same time, the following sequence of execution might occur:
P1: n1.prev = head.prev;
P1: n1.next = head;
P1: head.prev = n1;
P2: n2.prev = head.prev;
P2: n2.next = head;
P2: head.prev = n2;
P1: head = n1;
P2: head = n2;
And the resulting structure of
the list would be:
Which is inconsistent.
2. Consider the solution to Question
2 of Homework #3, which presents a semaphore implementation of Mesa monitors.
Using this solution, give a semaphore implementation of the Mesa
cv.broadcast
where cv is a condition
variable.
(A Mesa broadcast is similar
to a Java notifyAll(). It wakes up all processes or threads that
are blocked on a cv.wait).
Answer:
cv.broadcast(){
while (cv_count > 0){
cv_count--;
V(cv_delay);
}
}
3. Write a disk head scheduling
monitor that uses the first-come-first-served (FCFS) policy. Your monitor
should have two procedures,
request(c: cylinder) and
release.
Use a Hoare monitor. Priority waits and an operation for testing condition
variable queues are also assumed available.
Answer:
FCFS: monitor;
busy: boolean;
nonbusy: condition;
p: integer;
headPosition:
cylinder;
procedure request(c: cylinder)
begin
if (busy)
{
p++;
nonbusy.wait(p);
}
busy := true;
headposition:= c;
end
procedure release()
begin
busy := false;
nonbusy.signal();
end
//initialization code
begin
p := 0;
busy := false;
end
4. Three processes P1,
P2,
and P3 have relative priorities P(P1)>P(P2)>P(P3),
as in the priority inversion example given in the class handout. The processes
have the code skeletons:
P1:: begin . . . lock(X); CS1;
unlock(S); . . . end
P2:: begin . . . lock(Y); CS2:
unlock(Y); . . . end
P3:: begin . . . lock(X); CS3:
unlock(X): . . . end
The X and Y locks
are initialized to unlocked or free.
Each process takes 10 time units
to execute when there is no blocking and the CPU is allocated entirely
to it, consuming 2 time units before its critical section (CS), 4 units
inside its CS, and 4 units between the end of its CS and its end.
Assume that there is one CPU
shared by all three processes, and that P1 starts at time 0, P2
at time 3, and P3 at time 6. Scheduling is preemptive
and a process will block if its
lock is not free.
(a) Diagram the execution over time of the three processes, showing preemptions and blocking. At what time does process P1 terminate?
Answer:
Time | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1
0 |
1
1 |
1
2 |
1
3 |
1
4 |
1
5 |
1
6 |
1
7 |
1
8 |
1
9 |
2
0 |
2
1 |
2
2 |
2
3 |
2
4 |
2
5 |
2
6 |
2
7 |
2
8 |
2
9 |
P1 | w | w | X | X | X | X | w | w | w | w | ||||||||||||||||||||
P2 | w | w | Y | Y | Y | Y | w | w | w | w | ||||||||||||||||||||
P3 | w | w | X | X | X | X | w | w | w | w |
Note:
(b) Repeat (a) but use the priority inheritance protocol. Indicate when priorities change.
Answer:
Time | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 1
0 |
1
1 |
1
2 |
1
3 |
1
4 |
1
5 |
1
6 |
1
7 |
1
8 |
1
9 |
2
0 |
2
1 |
2
2 |
2
3 |
2
4 |
2
5 |
2
6 |
2
7 |
2
8 |
2
9 |
P1 | w | w | X | X | X | X | w | w | w | w | ||||||||||||||||||||
P2 | w | w | Y | Y | Y | Y | w | w | w | w | ||||||||||||||||||||
P3 | w | w | X | X | X | X | w | w | w | w |
Note:
Two common mistakes are:
Answer:
There are many possible (infinite as a matter of fact!) correct answers to this question. For instance, you could very well use the example of switching the P() operations in the producer-consumer problem in Homework #2:
Producer
//Produce item
P(mutex);
P(empty);
//CS
V(mutex);
V(full);
Consumer
P(mutex);
P(full);
//CS
V(mutex);
V(empty);
//Consume item
A simple answer to this question (which also gets you full credit) is to imagine implementing a monitor with function only calling wait() but never call signal(), in which case there is nobody to wake up the sleeping thread(s) and hence deadlock occurs!