From d82f43e0c747347de18737f4a446474207fb65b9 Mon Sep 17 00:00:00 2001 From: Frans Kaashoek 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 @@ + + +Lab: locks + + + + +

Lab: locks

+ +

In this lab you will try to avoid lock contention for certain +workloads. + +

lock contention

+ +

The program user/kalloctest stresses xv6's memory allocator: three + processes grow and shrink there address space, which will results in + many calls to kalloc and kfree, + respectively. kalloc and kfree + obtain kmem.lock. To see if there is lock contention for + kmem.lock replace the call to acquire + in kalloc with the following code: + + 

+    while(!tryacquire(&kmem.lock)) {
+      printf("!");
+    }
+
+ +

tryacquire tries to acquire kmem.lock: 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 tryacquire in kernel/spinlock.c. + +

A few hints: +

+ +

Run usertests to see if you didn't break anything. Note that + usertests never prints "!"; there is never contention + for kmem.lock. The caller is always able to immediately + acquire the lock and never has to wait because some other process + has the lock. + +

Now run kalloctest. You should see quite a number of "!" on the + console. kalloctest causes many processes to contend on + the kmem.lock. 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. + +

Removing lock contention

+ +

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. + +

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. + +

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. + +

Some hints: +

+ +

Run usertests to see if you don't break anything. + + + 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.

You should put the following example program in user/alarmtest.c: -XXX Insert the final program here +XXX Insert the final program here; maybe just give the code in the repo 

 #include "kernel/param.h"
 #include "kernel/types.h"
@@ -315,7 +315,11 @@ use only one CPU, which you can do by running
   
 
Once you pass test0 and test1, run usertests to
   make sure you didn't break any other parts of the kernel.
+
   
+
+
+
 
   
 
-- 
cgit v1.2.3


From bdcd23ea49885b5fd205d2856073d3d89b3a9bc2 Mon Sep 17 00:00:00 2001
From: Frans Kaashoek 
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.
 
 
Some hints:
   

 
 
Run usertests to see if you don't break anything.
-- 
cgit v1.2.3