Lab: locks

Memory Allocator (moderate)

• Original Version: All kernel threads will allocate and free memory by the same allocator, which contains a free buffer linked list and a single lock. This will lead to heavy lock contention when multiple threads are allocating physical memory.

• Refined Version: All CPUs have their own memory allocator (a free buffer linked-list) and their own lock to protect the list. Ideally, there will be no lock contention and all CPU threads manipulate their own list.

  struct {
    struct spinlock lock;
    struct run *freelist;
  } kmem[NCPU];
  

There is a problem: When a list on one CPU has run out, this CPU thread has to borrow a free buffer from another CPU’s allocator. And this will cause one CPU to hold the other one’s lock and hence incurs lock contention. But this situation occurs very rarely.

The basic idea of kalloc():

1. Initialize all buffers onto one single list of the CPU.

2. kalloc will acquire the current lock, search the list for an available buffer to use. If there is one, pick it off the list.

3. If no available buffer is on the current list, it has to borrow one from others’ lists. It needs to traverse along all lists, hold their locks, try to pick one buffer off the list and release the lock.

   Remember: release current kmem lock before your traversal to avoid deadlock.

4. Return the available block.

• code

kfree() is straight-forward: attach the freeing block to the current free list. You can just change the code by using array indices.

Buffer Cache (hard)

The refined cache uses hash table to scatter visits uniformly. All buckets in the table are implemented as linked-lists and protected with separate locks. Therefore, visits to different buckets will have no lock contention.

#define BUCKNUM 29

struct bucket {
  struct spinlock lock;
  struct buf *head;                // head of the linked list
};

struct {
  struct spinlock lock;
  struct buf buf[NBUF];            // buffer array contains data

  struct bucket table[BUCKNUM];    // hash table contains buffer pointers
} bcache;

int hash(uint dev, uint blockno) { return (dev * 67 + blockno) % BUCKNUM; }

bget using hash table:

1. Computes the hash value (bucket index) based on the dev and blockno values.
2. Acquire the lock of specific bucket and search for the buffer wanted.
   1. If found: Increment reference count, release the bucket lock and reacquire the buffer lock.
   2. If not found: find the unused buffer with the oldest usage time (ticks) in the whole cache and reattach it to the list of current bucket. Overwrite the buffer information and return.

brelse using hash table:

1. Acquire the bucket lock and decrement the reference count.