From d82f43e0c747347de18737f4a446474207fb65b9 Mon Sep 17 00:00:00 2001
From: Frans Kaashoek <kaashoek@mit.edu>
Date: Sat, 27 Jul 2019 16:00:12 -0400
Subject: Checkpoint start of locking lab

---
 labs/lock.html    | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 labs/syscall.html |  6 ++++-
 2 files changed, 86 insertions(+), 1 deletion(-)
 create mode 100644 labs/lock.html

(limited to 'labs')

diff --git a/labs/lock.html b/labs/lock.html
new file mode 100644
index 0000000..1278b53
--- /dev/null
+++ b/labs/lock.html
@@ -0,0 +1,81 @@
+<html>
+<head>
+<title>Lab: locks</title>
+<link rel="stylesheet" href="homework.css" type="text/css" />
+</head>
+<body>
+
+<h1>Lab: locks</h1>
+
+<p>In this lab you will try to avoid lock contention for certain
+workloads.
+
+<h2>lock contention</h2>
+
+<p>The program user/kalloctest stresses xv6's memory allocator: three
+  processes grow and shrink there address space, which will results in
+  many calls to <tt>kalloc</tt> and <tt>kfree</tt>,
+  respectively.  <tt>kalloc</tt> and <tt>kfree</tt>
+  obtain <tt>kmem.lock</tt>.  To see if there is lock contention for
+  <tt>kmem.lock</tt> replace the call to <tt>acquire</tt>
+  in <tt>kalloc</tt> with the following code:
+
+  <pre>
+    while(!tryacquire(&kmem.lock)) {
+      printf("!");
+    }
+  </pre>
+
+<p><tt>tryacquire</tt> tries to acquire <tt>kmem.lock</tt>: if the
+  lock is taking it returns false (0); otherwise, it returns true (1)
+  and with the lock acquired.  Your first job is to
+  implement <tt>tryacquire</tt> in kernel/spinlock.c.
+
+<p>A few hints:
+  <ul>
+    <li>look at <tt>acquire</tt>.
+    <li>don't forget to restore interrupts when acquision fails
+    <li>Add tryacquire's signature to defs.h.
+  </ul>
+
+<p>Run usertests to see if you didn't break anything.  Note that
+  usertests never prints "!"; there is never contention
+  for <tt>kmem.lock</tt>.  The caller is always able to immediately
+  acquire the lock and never has to wait because some other process
+  has the lock.
+
+<p>Now run kalloctest.  You should see quite a number of "!" on the
+  console.  kalloctest causes many processes to contend on
+  the <tt>kmem.lock</tt>.  This lock contention is a bit artificial,
+  because qemu is simulating 3 processors, but it is likely on real
+  hardware, there would be contention too.
+  
+<h2>Removing lock contention</h2>
+
+<p>The root cause of lock contention in kalloctest is that there is a
+  single free list, protected by a single lock.  To remove lock
+  contention, you will have to redesign the memory allocator to avoid
+  a single lock and list.  The basic idea is to maintain a free list
+  per CPU, each list with its own lock. Allocations and frees on each
+  CPU can run in parallel, because each CPU will operate on a
+  different list.
+  
+<p> The main challenge will be to deal with the case that one CPU runs
+  out of memory, but another CPU has still free memory; in that case,
+  the one CPU must "steal" part of the other CPU's free list.
+  Stealing may introduce lock contention, but that may be acceptable
+  because it may happen infrequently.
+
+<p>Your job is to implement per-CPU freelists and stealing when one
+  CPU is out of memory.  Run kalloctest() to see if your
+  implementation has removed lock contention.
+
+<p>Some hints:
+  <ul>
+    <li>Initially divide the free memory equally among the different CPUs.
+  </ul>
+
+<p>Run usertests to see if you don't break anything.
+  
+</body>
+</html>
diff --git a/labs/syscall.html b/labs/syscall.html
index 1e6e504..68abad2 100644
--- a/labs/syscall.html
+++ b/labs/syscall.html
@@ -121,7 +121,7 @@ interrupts.
 <p>
 You should put the following example program in <tt>user/alarmtest.c</tt>:
 
-<b>XXX Insert the final program here</b>
+<b>XXX Insert the final program here; maybe just give the code in the repo</b>
 <pre>
 #include "kernel/param.h"
 #include "kernel/types.h"
@@ -315,7 +315,11 @@ use only one CPU, which you can do by running
   
 <p>Once you pass <tt>test0</tt> and <tt>test1</tt>, run usertests to
   make sure you didn't break any other parts of the kernel.
+
   
+</body>
+</html>
+
 
   
 
-- 
cgit v1.2.3


From bdcd23ea49885b5fd205d2856073d3d89b3a9bc2 Mon Sep 17 00:00:00 2001
From: Frans Kaashoek <kaashoek@mit.edu>
Date: Sat, 27 Jul 2019 20:18:40 -0400
Subject: a bit more

---
 labs/lock.html | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

(limited to 'labs')

diff --git a/labs/lock.html b/labs/lock.html
index 1278b53..5eddc58 100644
--- a/labs/lock.html
+++ b/labs/lock.html
@@ -72,7 +72,12 @@ workloads.
 
 <p>Some hints:
   <ul>
-    <li>Initially divide the free memory equally among the different CPUs.
+    <li>You can use the constant <tt>NCPU</tt> in kernel/param.h
+    <li>Let <tt>freerange</tt> give all free memory to the CPU
+      running <tt>freerange</tt>.
+    <li>The function <tt>cpuid</tt> returns the current core, but note
+    that you can use it when interrupts are turned off and so you will
+    need to turn on/off interrupts in your solution.
   </ul>
 
 <p>Run usertests to see if you don't break anything.
-- 
cgit v1.2.3