From 9c4f62e8e3e7f114c6f82a75579a815e6329d767 Mon Sep 17 00:00:00 2001
From: Frans Kaashoek <kaashoek@mit.edu>
Date: Tue, 30 Jul 2019 13:07:17 -0400
Subject: x

---
 labs/lock.html | 18 ++++++++++++++++--
 1 file changed, 16 insertions(+), 2 deletions(-)

(limited to 'labs')

diff --git a/labs/lock.html b/labs/lock.html
index a93eb3a..707d6c4 100644
--- a/labs/lock.html
+++ b/labs/lock.html
@@ -98,7 +98,7 @@ workloads.
   and run test0 from bcachetest and you will see "!"s.
 
 <p>Modify <tt>bget</tt> so that a lookup for a buffer that is in the
-  bcache doesn't need to acquire <tt>bcache.lock</tt>.  This more
+  bcache doesn't need to acquire <tt>bcache.lock</tt>.  This is more
   tricky than the kalloc assignment, because bcache buffers are truly
   shared among processes. You must maintain the invariant that a
   buffer is only once in memory.
@@ -121,8 +121,13 @@ against, including:
 
 <p>Here are some hints:
   <ul>
+    <li>Read the description of buffer cache in the xv6 book (Section 7.2).
     <li>Use a simple design: i.e., don't design a lock-free implementation.
-    <li>Use a simple hash table with locks per bucket
+    <li>Use a simple hash table with locks per bucket.
+    <li>Searching in hash table for a buffer and allocating an entry
+      for that buffer when the buffer is not found must be atomic.
+    <li>It is fine to acquire <tt>bcache.lock</tt> in <tt>brelse</tt>
+      to update the LRU/MRU list.
   </ul>
 
 <p>Check that your implementation has less contention
@@ -130,5 +135,14 @@ against, including:
 
 <p>Make sure your implementation passes bcachetest and usertests.
 
+<p>Optional:
+  <ul>
+  <li>make the buffer cache more scalable (e.g., avoid taking
+  out <tt>bcache.lock</tt> on <tt>brelse</tt>).
+  <li>make lookup lock-free (Hint: use gcc's <tt>__sync_*</tt>
+    functions.) How do you convince yourself that your implementation is correct?
+  </ul>
+  
+  
 </body>
 </html>
-- 
cgit v1.2.3