CSE451 Midterm Solutions

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:

As can be seen from above, process 3 terminates at time 26 (end of time slot 25)

(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:

As can be seen from above, process 3 terminates at time 19 (end of time slot 18)

Two common mistakes are:

5. Describe how two threads in Java can deadlock. It is not necessary to write code, but you can if you wish. In either case, provide enough detail so that we are convinced that you could write the deadlocking code.

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!