summaryrefslogtreecommitdiff
path: root/labs/lock.html
blob: 5eddc58b51dfb33d922402de17dabbba73e06e10 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
<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>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.
  
</body>
</html>