summaryrefslogtreecommitdiff
path: root/labs
diff options
context:
space:
mode:
authorFrans Kaashoek <[email protected]>2019-08-01 15:46:50 -0400
committerFrans Kaashoek <[email protected]>2019-08-01 15:46:50 -0400
commit62ece4b09e6a568ede0e3b524af959194e0cb792 (patch)
tree72553e7a6c57a3298193b288db07eb1a4eab17d0 /labs
parentfb8a0099d48643775d0bca626af1a73a3ab618a4 (diff)
parent9c4f62e8e3e7f114c6f82a75579a815e6329d767 (diff)
downloadxv6-labs-62ece4b09e6a568ede0e3b524af959194e0cb792.tar.gz
xv6-labs-62ece4b09e6a568ede0e3b524af959194e0cb792.tar.bz2
xv6-labs-62ece4b09e6a568ede0e3b524af959194e0cb792.zip
Merge branch 'riscv-bcache' into riscv
Diffstat (limited to 'labs')
-rw-r--r--labs/lock.html32
1 files changed, 25 insertions, 7 deletions
diff --git a/labs/lock.html b/labs/lock.html
index b43a51b..707d6c4 100644
--- a/labs/lock.html
+++ b/labs/lock.html
@@ -82,7 +82,7 @@ workloads.
<p>Run usertests to see if you don't break anything.
-<h2>Lock-free bcache lookup</h2>
+<h2>More scalabale bcache lookup</h2>
<p>Several processes reading different files repeatedly will
@@ -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.
@@ -116,15 +116,33 @@ against, including:
<p>A challenge is testing whether you code is still correct. One way
to do is to artificially delay certain operations
- using <tt>sleepticks</tt>.
+ using <tt>sleepticks</tt>. <tt>test1</tt> trashes the buffer cache
+ and exercises more code paths.
<p>Here are some hints:
<ul>
- <li> Use an atomic increment instruction for incrementing and
- decrementing <tt>b->ref</tt> (see <tt>__sync_fetch_and_add() and
- related primitives</tt>)
- <li>Don't walk the <tt>bcache.head</tt> list to find a buffer
+ <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>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
+ on <tt>test0</tt>
+
+<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>