Week 11

Consider this Reader/Writer Lock implementation. Select all that hold.

• Prioritizes readers.

• Prioritizes writers.

• Would also work when replacing notifyAll() with notify().

Fill in the blank for the while(......) condition in acquire_read(), s.t:

- the lock works correctly

- AS FAIR AS POSSIBLE (given the available variables)

- it's not completely inefficient

• writers>0 || readers>0

• writers>0 || writersWaiting>0

• writers>0 || (writersWaiting>0 && writersWait<=0)

• writers>0 || (writersWaiting>0 && writersWait>0)

• writers>0 || writersWait<=0

Fill in the blank for the while(.....) condition in acquire_write() method, s.t:

- the lock works correctly

- lock is AS FAIR AS POSSIBLE (given available variables)

• writers>0 || readers>0

• writers>0 || writersWait>0

• writers>0 || readers>0 || readersWaiting>0

• writers>0 || readers>0 || writersWait>0

Implementing the methods this way corresponds to:

• optimistic locking

• fine-grained locking

• lazy locking

• coarse-grained locking

This is the add() method of a concurrent linked list. What holds (multiple can be correct) given multiple threads can access add() concurrently?

• No bad interleavings possible.

• Bad interleavings possible.

• Implementation uses fine-grained locking

• Implementation uses coarse-grained locking.

This is the add() method of a concurrent linked list. What holds (multiple can be correct)?

• No bad interleavings possible (correct implementation).

• Bad interleavings possible (incorrect implementation).

• Uses hand-over-hand locking.

• Uses optimistic locking.

Fine-grained Locking (using hand-

over-hand locking) on a linked list re-

quires us to validate if a node is still

reachable before deleting it.

• True

• False

What are advantages of optimistic synchronization over hand-over-hand locking (in a concurrent linked list)?

• Does not require locks.

• Less lock acquisitions/releases.

• Requires less list traversals.

• No contention during list traversal.

OPTIMISTIC implementation of ADD() method. Are bad interleavings possible?

• No, code is correct.

• Yes, because curr and pred being unlocked in wrong order.

• Yes, because of an error in the code logic.

• Yes, because pred.next is set before entry.next.

Consider the LL on the blackboard. How many lock acquisition/release pairs happen when using COARSE-GRAINED SYNCHRONIZATION?

• 11

• 2

• 10

• 1