CSE 221: Homework 3

Fall 2014

Due: Thursday, December 11, 2014 at 11:00am in class




I. Eraser

lock(a)
y := x + 1
lock(b)
z := y + 1
y := x + 1
unlock(a)
unlock(b)

  1. What will the lockset algorithm conclude about how x, y and z are protected? Will it report one or more races? If not, explain why not. If so, explain what they will be and why they will be reported.

  2. Now consider an additional code sequence that is also executed by multiple threads in the same program:
    lock(b)
    lock(a)
    y := x - 1
    unlock(b)
    z := z + 1
    unlock(a)

    What will the lockset algorithm conclude about how x, y and z are protected? Will it report one or more races? If not, explain why not. If so, explain what they will be and why they will be reported.

  3. Aside from data races the Eraser paper briefly mentions how a similar technique might be used to detect deadlock. Explain how such a scheme could detect a deadlock in the previous code examples (be specific about what the deadlock is).
II. Scheduler Activitations

"One issue we have not yet addressed is that a user-level thread could be executing in a critical section at the instant when it is blocked or preempted...[a] possible ill effect ... [is] deadlock (e.g., the preempted thread could be holding a lock on the user-level thread ready list; if so, deadlock would occur if the upcall attempted to place the preempted thread onto the ready list)." (p. 102)

III. LFS