Project #1: Readers-Writer Locks

Project Overview

The first programming project will teach you how to use atomic operations to implement a readers-writer (multiple readers-single writer) lock. The primary goal of this assignment is to become familiar with the low-level implementation details of high-performance reader-writer locks and to learn how to use profiling tools like PERF. All the code in this programming assignment must be written in C. If you have not used C before, here's a short tutorial on the language. Even if you are familiar with C, go over this guide for additional information on writing code in the system.

This is a single-person project that will be completed individually (i.e. no groups).

Release date: Wednesday, September 24

Due date: Friday, October 03

Implementation Details

You can refer to these GNU Builtin Atomics and Memory model aware atomics for a list of atomics.

You can refer to this PERF examples documentation or this PERF tutorial on how to use PERF to profile the system. You can also refer to the thread-local storage concept taught in class to reduce the contention in the system.

In this assignment, you will only need to modify the following file:

src/lock.c

You will not need to make any changes to any other file in the system. You can locally modify the benchmark.c already included in the system to verify the correctness/performance of your implementation. But you will not submit those files.

You will also need to write a report on how you implemented the reader-writer lock.

There are two steps to implement a high-performance reader-writer lock in the DBMS:

1. Use the spin-lock to implement a single reader-single writer lock.
2. Extend it to implement multiple readers-single writer lock.

Step #1 - Use the spin-lock to implement a single reader-single writer lock

The first step is to implement a single reader-single writer lock using a simple lock. You can test this using the benchmark.c.

make benchmark
./benchmark 16 2 10000 100
  

The arguments to the benchmark are, in order:

1. nreaders: How many reader threads to launch
2. nwriters: How many writer threads to launch
3. nitems: # of items in the array
4. niters: # of iterations. In each iteration a thread acquires the lock once

All arguments must be >= 1.

Sample Output:

Running benchmark with 16 readers, 2 writers, 10000 items, 100 iterations
Threads done, stats:
Readers: min 0.000016 ms, max 1.879325 ms, mean 0.008598 ms, std_dev 0.053511
Writers: min 0.000034 ms, max 0.423291 ms, mean 0.011356 ms, std_dev 0.039250
  

Step #2 - Extend it to implement multiple readers-single writer lock

This is the most important step. We are assuming you have successfully implemented a single reader-single writer lock.

Next you need to extend it to support multiple readers using the read counter. The instructions on how to support multiple readers are provided as comments before the functions in lock.c.

In the multiple readers-single writer lock the priority should be given to the writer thread. That is, once a writer thread acquires the write lock it will wait for existing readers to finish but no new readers can acquire the read lock while the writer is active.

Instructions

You can download the Project #1 source code (as a Zip file) from Canvas. It is uploaded under files. You can extract the source code by uncompressing the zip file using the following command:

unzip p1.zip -d p1/
  

To debug any correctness issues, you can compile the main benchmark using -D flag to turn off optimizations.

make clean
make D=1 main
  

Students can ssh to either login.khoury.northeastern.edu or use the following based on the MOTD in login.

Linux at Khoury College:

Do not run your code on the login node.

PERF and other essential software are installed on all linux machines.

Submission

You need to submit a .zip file of your source code to canvas.

You should also include a report.pdf in your submission that contains:

1. A brief description on how you implemented multiple readers-single writer lock.
2. A brief description on how you employed perf to identify any hotspots.
3. To measure the performance, vary the number of readers from 1 to 16 in powers of 2 (1, 2, 4, 8, 16) while keeping the number of writers to 1.
4. Include the performance of readers (mean, max latency) as a plot.

Make sure that report.pdf is included separately and not a part of the .zip file.

We will evaluate the correctness and the performance of your implementation off-line after the project due date.

Collaboration Policy

1. Every student has to work individually on this assignment.
2. Students are allowed to discuss high-level details about the project with others.
3. Students are not allowed to copy the contents of a white-board after a group meeting with other students.
4. Students are not allowed to copy the solutions from another colleague.