Solved-Assignment 1:- Basic Spinlocks- Solution

Description

Overview

In this assignment, we’re exploring the design space for basic spinlocks, and
in so doing developing some implementations that we can use as building blocks
later on. We’ll measure how these implementations perform at various levels of
concurrency and bus contention, and think along the way about why each idea we
introduce results in the behavior we observe.

The series of steps in this assignment build on one-another, so you’ll need to
do them in order to get things working. There are numbered questions
throughout the assignment; we recommend thinking through these questions
carefully and writing down short concrete answers before moving on to the next
section. If you’re confused by a question or don’t know where to start, you’re
free to discuss or puzzle through them with other students, and Ted and Jon are
also available to help. The point of these assignments is to develop your
understanding of the material and give you some hands-on intuition for
concurrent programming, and the questions are there to help you understand
what’s going on. If they don’t, we’d really like to know, so we can write
some better ones :)

Finally, this assignment is brand new, so there may be gaps in the
documentation and bugs in the code. Let us know about any issues you find and
we’ll resolve them as quickly as possible.

If you have questions and are comfortable sharing them, send them to the
[mailing list](mailto:cs510walpole@cecs.pdx.edu). If you would like Ted to
privately answer questions or take a look at your code, you can get in touch
with him via [email](mailto:theod@pdx.edu). He will also make an effort to
lurk on IRC in `#cs510walpole` on irc.cat.pdx.edu (see below for details).

Submission instructions

“`bash
cd CS510-Advanced-Topics-in-Concurrency
pushd Assignment_1
pushd data
# remove all data and graphs BESIDES the final ones you’d like me to look at
rm <out-of-date data and graphs>
popd
make clean
popd
# where NAME is your name separated by underscores
tar czf Assignment_1-NAME.tar.gz Assignment_1/
“`

Email the archive to [theod@pdx.edu](mailto:theod@pdx.edu) with subject
`Assignment_1-NAME` and any questions and comments you’d like to share.

What is a spinlock?

We can use a lock to make sure that one thread has mutually exclusive access to a
resource. To do so, we need to ensure that when thread A acquires a lock, no other
thread also acquires that lock until after thread A has finished accessing the resource
and releases the lock.

We can use a word `lock` in shared memory to represent a lock, which has the
value `UNLOCKED` when it is free, and the value `LOCKED` when it is held by
some thread. Then, acquiring the lock is as simple as observing `lock ==
UNLOCKED`, and then writing `LOCKED` to `lock`, right? WRONG! Let’s say that threads
A and B both observe `lock == UNLOCKED`, and then concurrently write `LOCKED`
to `lock`. Both would observe that `lock == LOCKED`, and each might conclude
that it could safely access the resource `lock` protects. This is just what a
lock is supposed to prevent, right?

We could try identifying the lock holder in `lock`, with thread A writing
`LOCKED_A` and thread B writing `LOCKED_B`. Then if thread A observed `lock ==
LOCKED_A`, it would know that B hadn’t come along and written `LOCKED_B` to
`lock`, right? WRONG! What if B just hadn’t gotten around to it yet? A observes
`lock == LOCKED_A`, then B writes `LOCKED_B` to `lock` and observes `lock ==
LOCKED_B`, and once again the threads concurrently conclude that each has
exclusive access to the resource. That doesn’t work either! Let’s abandon the
“lock tells you who has it” train of thought for now; we’ll come back to it in
a later assignment.

Let’s again consider the case where threads A and B are racing to write
`LOCKED` to `lock`. If each thread could tell the computer to only write
`LOCKED` to `lock` if nobody else has snuck in and done it yet, and the
computer lets the thread know whether the attempt succeeded or failed, then the
thread whose attempt succeeded would know that it had exclusive access to the
resource, while the thread whose attempt failed would know that it didn’t.

Primitives

Modern multicore computers offer atomic compare and exchange instructions to
enable this way of using words in memory to implement locks and other
concurrent objects. In particular, the `x86_64` instruction set offers a
“`lock; cmpxchgq`” instruction that we’ve exposed as
a macro you can use in C code `lockcmpxchgq(ptr, old, new)` that has the
following behavior:
* If `*ptr == old`, atomically store new to `*ptr` and return `old`.
* Otherwise, return the value of `*ptr` without changing it. This is the
primitive we’ll be using to implement our spinlocks!
The `q` stands for “quad word”, which is Intel’s backward-looking way of saying
“as long as 4 2-byte words, or 8 bytes (64 bits) long”. Going forward, this
what we mean when we say “word”. We’ll use the C type `uint64_t` to represent
these words.

NOTE: There are a variety of interesting solutions to the critical section
problem that don’t use atomic instructions, such as
[Peterson’s Algorithm](https://en.wikipedia.org/wiki/Peterson%27s_algorithm)
and
[Simpson’s 4-slot Algorithm](http://deploy-eprints.ecs.soton.ac.uk/116/1/sld.ch7.conc.pdf)
(slides 7 and on), we just aren’t exploring them in this assignment.

To keep the compiler from rearranging our code, e.g. during optimizations, we
need to use some other macros: If another thread might be loading from or
storing to `x`, write `_CMM_STORE_SHARED(x,v);` instead of `x = v;`, and
`CMM_LOAD_SHARED(x)` instead of `x` whenever we load `x`. For example, if we
were looping on the value of `x`, we would write `while(CMM_LOAD_SHARED(x)) {
… }` instead of `while(x) { … }`, and if we were loading `x` into a local
variable `y`, we would write `y = CMM_LOAD_SHARED(x)`.

Note that storing an aligned `uint64_t` with `_CMM_STORE_SHARED()` is atomic on
`x86_64`. It doesn’t prevent accesses that would normally be reordered across a
store (only subsequent loads on `x86_64`) from being reordered across it at
runtime, but if you don’t care about that, you can safely use this macro to
unconditionally and atomically update a word that other threads may access.

## Building Spinlocks

`spin_try_lock()`

First, we’ll write some code that tries to acquire a spinlock, returning `1` if
it succeeds and `0` if it fails. Head over to `worker.c` and look for an empty
function definition for `int spin_try_lock(volatile uint64_t *lock)`. Fill in
the body of the function, using `lockcmpxchgq()` to attempt to install the
value `LOCKED` in the word that `lock` points to, which we expect to contain
`UNLOCKED`, returning `1` if we succeeded in replacing `UNLOCKED`, and `0` if
somebody else beat us to it and stored `LOCKED` at `*lock`.

Next, we need a way for a thread, having completed its critical section, to
release a lock it holds. `void spin_unlock(volatile uint64_t *lock)` will
serve this purpose, and all it needs to do on `x86_64` is store `UNLOCKED` to
`*lock` and ensure that the compiler doesn’t reorder memory accesses across
this store. Fill in the body of the function to accomplish this.

Testing your `spin_try_lock()` and `spin_unlock()` implementations

To test your implementations, build and run the test harness from a shell:
“`bash
make
./run 24 10000 1
“`

`run` takes 3 parameters, `MAX_THREADS` (how many threads the harness tests up
to), `N_OPS` (the total number of operations to run), and `N_RUNS` (how many
times to repeat the experiment). It prints diagnostic messages from the parent
thread, as well as comma-separated data for each test attempt (more on this later).

With our code in its current state, the invocation above will run the test
called `spin_try_lock_correctness_test_nograph`, which tests `spin_try_lock()`
and `spin_unlock()` on a spinlock `my_spinlock`, with 1 worker thread running
them 10000 times, then 2 worker threads running them 5000 times apiece, then 3
worker threads running them about 3333 times apiece (one does 3334), and so on
until 24 worker threads run them about 416 times apiece (one does 417). This
way we’re doing the same work every time, just changing how many workers are
splitting the job up. Every time a worker calls `spin_try_lock()`, it checks
the return value to determine whether the lock has been successfully acquired.
If it has, the worker increments a counter `my_spinlock_shared_counter` that it
shares with other workers, and records the fact that it has done so in a
thread-local counter `d->my_spinlock_counter`. Then, if the lock was
successfully acquired, the worker releases it with `spin_unlock()`.

If `spin_try_lock()` is working properly (that is, ensuring that no other
thread thinks it has acquired `my_spinlock` when `spin_try_lock(&my_spinlock)`
returns `1`), then the sum of all thread-local counters should equal the final
value of `my_spinlock_shared_counter`. On the other hand, if for example two
threads think that they both hold `my_spinlock` at once, then they may both
observe `my_spinlock_shared_counter` to have some value `5`, and both write `6`
to `my_spinlock_shared_counter`, but both also increment their local counters.
Now `my_spinlock_shared_counter` has increased by `1`, while the sum of local
counters has increased by `2`, and the sum of local counters no longer equals
the value of the shared counter.

Every time the worker threads complete a set of 10000 operations, the parent
thread checks that `my_spinlock_shared_counter` equals the sum of the workers’
local counters, and the program prints a message something like this before
exiting with status `-1`:

“`
-1: spin_try_lock_correctness_nograph failed for nt 2,
my_spinlock_shared_counter: 5208, sum: 10000, n_ops: 10000. If the lock were
working correctly, counter and sum would be nonzero and the same.
“`

All of the correctness tests we’ll use in this assignment work more or less the
same way. Feel free to experiment with adjusting the values of `MAX_THREADS`,
`N_OPS`, and `N_RUNS`.

`spin_lock()`

Once you’ve convinced yourself that `spin_try_lock()` and `spin_unlock()` are
correct by running some experiments, you’ll have seen some messages like

“`
-1: spin_try_lock_correctness_nograph succeeded for nt 24,
my_spinlock_shared_counter: 535, sum: 535, n_ops: 10000. Values are nonzero
and the same, so the lock is working correctly.
“`

If only 535 increments actually occurred, then the other 9465 attempts must
have resulted in `spin_try_lock()` returning `0`, that is, a thread observing
that some other thread currently holds `my_spinlock` and therefore failing to
acquire it and perform an increment. This isn’t too surprising, since we have
24 threads competing for `my_spinlock` in this case (note `for nt 24` above).

What we really need is a lock acquisition function that *always works*. Well,
we could just keep spamming `spin_try_lock()` until it returns `1`, right?
Let’s give that a try. Head over to `void spin_lock(volatile uint64_t *lock)`
in `worker.c`, and replace the `TODO` with some code that calls
`spin_try_lock()` in a tight loop until it returns `1`. If you’d prefer to use
`lockcmpxchgq()` directly instead of `spin_try_lock()`, that’s fine too.

This code doesn’t return until the lock is acquired; it just keeps trying to get it,
or in other words, it *busy-waits*.

We don’t need to change `spin_unlock()` to work with this implementation, or any
subsequent implementation in this assignment.

Testing your `spin_lock()` implementation

Open `tests.c` and take a look at the array `test_names`, which enumerates the
tests that are available, and the array `test_on`, which determines whether the
test at the same index in `test_names` will be run. Right now, the test
harness is set up to only run the first test,
`”spin_try_lock_correctness_nograph”`. The `”correctness”` part indicates that
it’s a test that checks whether the `spin_try_lock()` implementation is
correct, not a benchmark that measures the performance of `spin_try_lock()`.

To test the correctness of `spin_lock()`, we’ll need to change the `0` in `test_on`
corresponding to `spin_lock_correctness_nograph` to a `1`, rebuild the test
harness with `make`, and run it as before with `run`. When your implementation
is working correctly, you should see a message like

“`
-1: spin_lock_correctness_nograph succeeded for nt 24,
my_spinlock_shared_counter: 10000, sum: 10000, n_ops: 10000. Values are
nonzero and the same, so the lock is working correctly.
“`

Now the number of increments is equal to the number of operations attempted,
since each call to `spin_lock()` busy-waits until it has successfully acquired
`lock`, so workers successfully acquire the lock for each operation, and
are able to always increment the local and shared counters.

Benchmarking your `spin_lock()` implementation

Now we know that `spin_lock()` is correct, but we don’t know how efficient it is
compared to other forms of synchronization. To get an idea of how we’re doing,
we’ll use the spinlock implementation from pthreads `pthread_spin_lock` as a baseline.

We need to turn on two benchmarking tests in `test_on` in `tests.c`:
* `pthread_spin_lock`
* `spin_lock`

We aren’t including a benchmark for `spin_try_lock()` here since it’s an
apples-to-oranges comparison, as `spin_lock()` and `pthread_spin_lock()` both
busy-wait until a successful acquisition, and `spin_try_lock()` does not.

Now, rebuild the test harness and use `bench` to run benchmarks.

“`bash
make
./bench 24 300000 1
“`

You should see output that ends with some messages about generated graphs:

“`
[1] “generating data/bench_t24_2018-01-09_12-27-07.csv_ticks_0accesses.pdf”
[1] “generating data/bench_t24_2018-01-09_12-27-07.csv_ticks_8accesses.pdf”
[1] “generating data/bench_t24_2018-01-09_12-27-07.csv_ticks_80accesses.pdf”
“`

Check out the graphs; they should have one line for `spin_lock` and another for
`pthread_spin_lock`. How do the implementations compare?

Bus contention

Note that 3 different graphs are generated, one labeled to represent test runs
with “no critical section accesses” `_0accesses.pdf`, another with “1 cache
line updated during critical section” `_8accesses.pdf`, and another with “10
cache lines updated during critical section” `_80accesses.pdf`. The latter 2
tests simulate what threads usually do when they hold a lock, which is update
some other memory protected by the lock. We simulate this by doing racy
increments to words in a shared circular buffer. Because a given word in the
buffer is updated by multiple threads, increments to that word by different
threads require communication between those threads over the system bus. This
is the case whenever multiple threads try to update the same word (among other
situations that trigger bus traffic).

Questions
1. Does calling `spin_try_lock(&my_spinlock)` over and over again (even after
we’ve just observed that `my_spinlock` is held) every time we need to get
`my_spinlock` affect how long it takes to finish a set of operations? Does
each call require threads to communicate, and if so, what shared resources
does that communication use?
2. How does this implementation scale as we increase the number of threads?
Does passing the lock around and busy-waiting for it affect the time it
takes for all threads to crunch through the set of operations? If so, is the
effect different for different numbers of threads?
3. As we add bus traffic, first by updating a single cache line and then by
updating 10 cache lines while holding the lock, how do `spin_lock` and
`pthread_spin_lock` respond to this change, and why?

A note on resource sharing, measurement accuracy, and interference

Since we’ll all be using `babbage` to run these benchmarks, it’s possible that another
student could be running benchmarks at the same time. This will at the very least
make benchmarking take longer, and could make your graphs look a little strange.
To check whether this is going on, watch `htop` in another terminal to see if another
user is running a bunch of `./test` threads too. If so, get in touch with that user
in one of the following ways to negotiate a way to share benchmarking time:
1. Via the `#cs510walpole` IRC channel on `irc.cat.pdx.edu`.
See the [CAT documentation](https://cat.pdx.edu/services/irc/)
for more information about getting connected and using IRC.
2. Using the `write` command to make a message appear in their terminal:
“`bash
$ write theod
hello friend, will you be finished benchmarking soon?
(CTRL+d to end)
“`
3. Getting in touch via email. CAT and ODIN usernames are usually the same, so
`username@pdx.edu` will probably work, but you could also use the mailing list
to broadcast to everybody in the course (as a last resort) at
[`cs510walpole@cecs.pdx.edu`](mailto:cs510walpole@cecs.pdx.edu).

We’ve tuned the `./run` and `./bench` invocations in this assignment to take
a few minutes or less, so the chance of collisions between users is relatively low.
Also, note that the correctness tests work no matter what, although they make take
longer if another user is running tests.

Finally, it’s important to note that `babbage` is heavily used, and is a virtual
machine that shares a host with other heavily used virtual machines. It’s an
environment subject to frequent interference and weird behavior resulting from
virtualization and hyperthreading on the host, and benchmark results often
fluctuate. Try running a given benchmark multiple times and looking at the
graphs that are produced to get an idea of the range of results, and if you
produce a particular graph with results that just don’t make sense, try running
`./bench` again before you get too invested in being confused :)

`spin_wait_lock()`

Based on our observations in the last section, it seems that spamming
`spin_try_lock()` as quickly as possible does not scale particularly well as we
increase the number of threads, especially in the presence of other bus
traffic. Let’s see what happens when we build a delay into our lock
acquisition function; we can write this modified version of `spin_lock()` in
`void spin_wait_lock(volatile uint64_t *lock)` in `worker.c`. To be clear, the
only goal here is to poll the spinlock less frequently. For example, it is
sufficient to just add a loop that, say, decrements an `int` 500 times, and
crank through the loop in between calls to `spin_try_lock()`.

Once you’ve implemented `spin_wait_lock()`, enable
`spin_wait_lock_correctness_nograph` and `spin_wait_lock` in `test_on` in
`tests.c`, `make` again, `run` as above until you’ve passed the correctness
tests, and then `bench` again as above and take a look at the generated graphs.
There should be a `spin_wait_lock` line now in addition to the lines from
previous graphs.

Questions
4. What result did you expect? Are these graphs consistent with your expectation?
5. Does `spin_wait_lock()` result in more or less communication than
`spin_lock()`? Do the results shed any light on the relative merits of more
and less communication?
6. Communication always comes at a cost, so we need to think carefully about how
much bus traffic our implementations generate. How can we minimize communication in
our spinlock implementations? Is there more than one way?
7. If we have just observed `*lock == LOCKED`, how likely is it that
`spin_try_lock()` will succeed (returning `1`)? Do you think that
`spin_try_lock(lock)`, which can trigger an update, requires the same
amount of communication as just loading the value of `my_spinlock`? Why? Do
you think that these operations require unidirectional or bidirectional
communication, and why?

`spin_read_lock()`

Let’s explore another way to minimize communication. Instead of introducing a
delay while polling with `spin_try_lock()`, let’s poll by *loading* `*lock` in
a tight loop until we observe `*lock == UNLOCKED` before each attempt at
`spin_try_lock()`. Implement this approach in `void spin_read_lock(volatile
uint64_t *lock)` in `worker.c`. We’d like to compare the effect of delaying
with the effect of polling with loads instead of `lockcmpxchgq()`, so don’t
include the delay loop from `spin_wait_lock()` in this implementation.

Once you’ve implemented `spin_read_lock()`, enable
`spin_read_lock_correctness_nograph` and `spin_read_lock` in `test_on` in
`tests.c`, `make` again, `run` as above until you’ve passed the correctness
tests, and then `bench` again as above and take a look at the generated graphs.
There should be a `spin_read_lock` line now in addition to the lines from
previous graphs.

Questions
8. What result did you expect? Are these graphs consistent with your expectation?
9. Does `spin_try_lock(lock)` always return `1` after we observe `*lock ==
UNLOCKED`? Why or why not? If not, what does your implementation do in
this situation?
10. Do the results suggest that one way of minimizing communication is better
than the other?

(Optional) `spin_experimental_lock()`

Finally, we offer a chance for intrepid souls to explore combining the
techniques we’ve tried above, and anything else you can imagine or read about
in the realm of spinlock implementation. How close can you get to `pthread_spin_lock`?
How is `pthread_spin_lock` [implemented](https://sourceware.org/git/?p=glibc.git;a=blob;f=nptl/pthread_spin_lock.c;h=58c794b5da9aaeac9f0082ea6fdd6d10cabc2622;hb=HEAD) anyway?
You may find the `xchgq()` primitive implemented in `util.h` helpful in this exploration.
Play and trial and error are the substance of experiential learning, so go crazy.

In keeping with previous steps, implement `spin_experimental_lock()` in `worker.c`,
and turn on `spin_experimental_lock_correctness_nograph` and `spin_experimental_lock` in
`test_on` in `tests.c`, then `make`, `run`, `bench` and repeat as usual.