summaryrefslogtreecommitdiff
path: root/labs
diff options
context:
space:
mode:
authorFrans Kaashoek <[email protected]>2019-07-29 15:49:47 -0400
committerFrans Kaashoek <[email protected]>2019-07-29 15:49:47 -0400
commit34980381bd75ce28ffea2113559aefa1b02c64f0 (patch)
tree413700348cc302bdd7a58aeb22d8eb8c729f3ab3 /labs
parent005773c0c3cf3119273d1fd001c01241f7eae5c2 (diff)
downloadxv6-labs-34980381bd75ce28ffea2113559aefa1b02c64f0.tar.gz
xv6-labs-34980381bd75ce28ffea2113559aefa1b02c64f0.tar.bz2
xv6-labs-34980381bd75ce28ffea2113559aefa1b02c64f0.zip
checkpoint
Diffstat (limited to 'labs')
-rw-r--r--labs/lock.html45
1 files changed, 40 insertions, 5 deletions
diff --git a/labs/lock.html b/labs/lock.html
index fe2da45..b43a51b 100644
--- a/labs/lock.html
+++ b/labs/lock.html
@@ -84,12 +84,47 @@ workloads.
<h2>Lock-free bcache lookup</h2>
-<p>Modify <tt>bget</tt> so that succesful lookups don't need to
- acquire <tt>bcache.lock</tt>. The challenge is
- concurrent <tt>brelse</tt>, which modify the list that <tt>bget</tt>
- traverses. (Hint: there is no need for <tt>bget</tt> to use the
- list.)
+
+<p>Several processes reading different files repeatedly will
+ bottleneck in the buffer cache, bcache, in bio.c. Replace the
+ acquire in <tt>bget</tt> with
+ <pre>
+ while(!tryacquire(&bcache.lock)) {
+ printf("!");
+ }
+ </pre>
+
+ 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
+ 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.
+
+<p> There are several races that <tt>bcache.lock</tt> protects
+against, including:
+ <ul>
+ <li>A <tt>brelse</tt> may set <tt>b->ref</tt> to 0,
+ while concurrent <tt>bget</tt> is incrementing it.
+ <li>Two <tt>bget</tt> may see <tt>b->ref = 0</tt> and one may re-use
+ the buffer, while the other may replaces it with another block.
+ <li>A concurrent <tt>brelse</tt> modifies the list
+ that <tt>bget</tt> traverses.
+ </ul>
+
+<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>.
+
+<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
+ </ul>
</body>
</html>