+ There are multiple possibilities:
+
+ - "Double-checked locking": Search for the block in the cache
+ without taking any lock. Then, take the lock and see
+ whether it's still the same block. If so, you've got locked
+ access to it. Otherwise, release the lock and start over.
+
+ - Global lock: A global lock held during the whole eviction
+ process normally does not meet the synchronization
+ requirements, which says "...when I/O is required on a
+ particular block, operations on other blocks that do not
+ require I/O should proceed without having to wait for the
+ I/O to complete." Deduct points.
+
+ - Two-level locking: Use one global lock to protect the sector
+ numbers in the list from changing, and a second per-block
+ lock to prevent eviction. In pseudo-code it looks like
+ this:
+
+ acquire global lock
+ find block in cache
+ acquire per-block lock
+ release global lock
+ do I/O
+ release per-block lock
+
+ The problem is that if thread Y wants to access block B
+ while thread X is evicting block B, any thread Z that wants
+ to access *any* block must wait for X's I/O to finish:
+
+ Thread X Thread Y Thread Z
+ ------------------ ---------------- --------------------
+
+ get global lock
+ find B in cache
+ get B's lock
+ release global lock
+ start I/O
+ get global lock
+ find B in cache
+ block on B's lock
+ block on global lock
+
+ As you can see, Y still holds the global lock while it waits
+ for B's lock, so Z has to wait for the global lock to be
+ released, which won't happen until Y can get B's lock, which
+ in turn won't happen until X's I/O is complete.
+
+ There are ways around this problem. If the students mention
+ it and describe a solution, it's fine. If they don't
+ mention it at all, deduct points.
+
+ - Only one, specialized thread is allowed to do eviction.
+