Assignment 2: FIFO Spinlocks Solution

Overview




In this assignment, we're exploring the design space for spinlocks that provide

a fairness property (in addition to solving the critical section problem):

If thread A's acquisition attempt takes effect before thread B's acquisition attempt,

thread A will get the lock before thread B. In all the implementations we'll explore,

this is achieved by tying the order in which threads acquire the lock to the coherence

order for a word in memory.




The series of steps in this assignment build on one-another only conceptually,

so you can complete the implementations in any order to get things working (just

compare all of them once you're done). 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_2

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_2-NAME.tar.gz Assignment_2/

```

 

Email the archive to [theod@pdx.edu](mailto:theod@pdx.edu) with subject

`Assignment_2-NAME` and any questions and comments you'd like to share.

Include your answers to the numbered questions in the assignment in the text of

the email.




Why FIFO?




If it's possible for thread A to acquire a lock many times while thread B

continues to wait to acquire the lock, then thread A may end up getting its

work done much sooner, at the expense of thread B's progress. This lack of

fairness can in extreme cases lead to complete *starvation*, e.g. thread B

continually failing to make any progress. People who write concurrent programs

observe problems resulting from unfairness in practice. For example,

Nick Piggin (a Linux contributor) cites some anecdotal evidence of this

[here](https://lwn.net/Articles/267968/):




On an 8 core (2 socket) Opteron, spinlock unfairness is extremely noticable,

with a userspace test having a difference of up to 2x runtime per thread, and

some threads are starved or "unfairly" granted the lock up to 1 000 000 (!)

times.




All of the spinlocks we've implemented so far make no guarantees about

fairness, since they're all based on some mechanism where threads race on some

atomic instruction, and the "winner" acquires the lock while other threads

retry. If we use a "talking stick" as an analogy for a lock, this is like the

holder throwing the talking stick on the ground once they've finished talking,

and letting everybody who wants to talk dive for it and fight over it. Once

the dust settles, one winner (and nothing else) is determined, so there's

nothing preventing some people from winning over and over again while others

lose over and over again. In this assignment, we'll explore a series of

approaches roughly analogous to folks forming a line behind the talking stick

holder, who then (once finished talking) passes the talking stick to the next

person in line.




As you work through the steps, think about what fairness buys us, and when

it is and isn't worthwhile.




Primitives




To complete some of the following implementations, you'll need a new primitive

that atomically adds to a word in memory and returns its previous value. We've

provided `x86_64`'s `lock; xaddq` instruction to serve this purpose; the `x` is

for "exchange" (as in `xchgq`). This primitive is exposed as a macro

`lockxaddq(ptr,val)`, which atomically adds `val` to `*ptr` and returns the

pre-add value of `*ptr`. Note that unlike the actual `lock; xaddq` instruction, this

macro does not store the old value of `*ptr` in `val`, so you need to catch the

return value.




All previously introduced primitives remain available (and will come in handy),

and are implemented and documented in `util.h`.




We'll need to use the `old = xchg(ptr, new)` primitive, defined in `util.h`.

This primitive is an atomic unconditional swap, that is, it atomically swaps

the current value in `*ptr` (returned as `old`) for `new`.




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 FIFO Spinlocks




`ticket_lock()` and `ticket_unlock()`




You can find an overview of ticket locks in

[this Linux Weekly News article](https://lwn.net/Articles/267968/)

and a description and example implementation in Section 2.2 and Figure 2, respectively, of

[Mellor-Crummey and Scott 1991](https://cis.temple.edu/~qzeng/cis5512-fall2015/papers/p21-mellor-crummey.pdf).




Basically, a ticket lock is like when you take a number at the DMV, except

there's only one desk, and it's your job to update the number on display when

you've met with the employee at the desk and finished your business. It

consists of two numbers that can be separately updated atomically:

* `next`, which is the next number that will be handed out to somebody in line

* `owner`, which is the number of the ticket that belongs to the current lock

holder.




Head over to `// define a type for ticket` in `tests.h`, and familiarize

yourself with the type `ticket_state` and the global declaration of

`my_ticket_lock`. As you implement the operations below, consider whether

`next` and `owner` should be on the same cache line or not.




Next, head over to `ticket_lock()` in `worker.c`. To acquire the lock, you

atomically increment `next`, grabbing its previous value as your number, and

then spin until another thread updates `owner` to match your number (if there's

nobody ahead of you in line, this will already be the case). Now it's your

turn to execute your critical section!




Finally, head over to `ticket_unlock()` in `worker.c`. To release the lock, you

simply increment `owner`, to let your successor know that it's their turn.

Note that only the lock holder updates `owner`, so no other thread will race

you here.




Testing your `ticket_lock()` and `ticket_unlock()` implementations




As usual, turn on `ticket_correctness_test` to test this implementation

and `ticket_lock()` to benchmark it.




Build and run the test harness from a shell:

```bash

make

./run 24 10000 1

```

Note that the correctness test for these implementations (and the others in

this assignment) is only partial: it doesn't test fairness in any way, just

whether or not the implementation solves the critical section problem. The

benchmarks may shed some light on fairness, since the times indicate how long

it takes _all threads_ to finish their work, so if some threads have been

starved and take longer than others to finish, the overall time goes up.

However, there isn't any way to distinguish between time wasted because of

unfairness and time wasted by e.g. atomic instruction overhead.




Once you're passing this correctness test, it may be helpful to compare the

performance of this implementation to some of your unfair spinlocks from the

last assignment. In particular, `spin_lock()` and `spin_read_lock()` (or

`spin_experimental_lock()`) (just paste them into `worker.c` from your previous

submission) establish helpful reference points, and `pthread_spin_lock()` is

still a good baseline.




We've observed slightly smoother data with a smaller set of operations and

multiple runs, like so




```bash

./bench 24 3000 80

```

Questions




1. How does `ticket_lock()` compare to its unfair counterparts?

2. In particular, why is there a gap between `spin_lock()` and `ticket_lock()`?

3. What memory location(s) are threads contending to update in this implementation?

4. What memory location(s) are threads spinning on in this implementation?

5. What communication (to whom) is triggered when `ticket_unlock()` writes to `owner`?




`abql_(no)sharing_lock()` and `abql_(no)sharing_unlock()`




Let's explore a queueing lock that works roughly the same way as `ticket_lock()`

on the acquisition side, but spreads out spinning and successor notifications

to per-thread words in memory on the release side, rather than the single word

`owner` used by all waiting threads in `ticket_lock()`. You've read about this

Array-Based Queueing Lock (AQBL) in

[Anderson 1990](http://www.cs.pdx.edu/~walpole/class/cs510/papers/02.pdf).

See Table V for Anderson's ABQL implementation. NOTE: Anderson's

`ReadAndIncrement` corresponds to our `lockxaddq`.




Preparing data structures




Head over to `// define a type for abql_sharing` in `tests.h` and familiarize

yourself with the `flag_sharing` type and the global declaration of `flags_sharing`.




Next, head over to `// TODO declare and initialize data for abql_sharing` in

`tests.c` and declare and initialize an array of `n_threads` `flag_sharing`s,

where the first element has `val` set to `HAS_LOCK` and each subsequent element

has `val` set to `MUST_WAIT`. Point `flags_sharing` to this array. Now

`flags_sharing` will be supplied as `flags` to each call to

`abql_sharing_(un)lock()`. Additionally, note that `queue_last_sharing` is

declared in `tests.h`, initialized to `0` in `tests.c`, and will be supplied as

`queue_last` to each call.




`abql_sharing_lock()`




Head over to `abql_sharing_lock()` in `worker.c`. Instead of atomically

incrementing `next` and then spinning on `owner` (along with all other threads

waiting for the lock) as in `ticket_lock()`, this lock acquisition operation will

atomically increment `queue_last`, and use the value handed back from the

atomic increment (the previous value of `queue_last`, uniquely returned to this

thread) as an index into `flags`, indicating which element in the array this

thread should spin on. This way, each thread in the queue ends up spinning on

a different `flags[i].val`, so updates to e.g. your predecessor's

`flags[j].val` won't require your cached copy of `flags[i].val` to be

invalidated (which takes time). Right? When you index into `flags`, though,

note that `queue_last` just keeps growing as this algorithm proceeds,

while there are only `n_threads` elements in `flags`, so you'll need to wrap

around.




Store this index in `*my_place`, because we'll need it to persist from this

call to `abql_sharing_lock()` to the corresponding call to

`abql_sharing_unlock()`. Next, wait for your flag to no longer be `MUST_WAIT`.

When this happens, it's because your predecessor in the queue is letting you

know that it's your turn, so you can just set the flag back to `MUST_WAIT` for

the next thread who ends up here, and proceed on your merry way.




`abql_sharing_unlock()`




Head over to `abql_sharing_unlock()`. We still have `*my_place` from the call

to `abql_sharing_lock()`, so we know where our flag is. The thread who entered

the queue after us got back the next value of `queue_last` as its... place, and

that is just `*my_place + 1` (we're atomically _incrementing_), so we know

where our successor's flag is, too. All that remains, then, is to tap our

successor on the shoulder and let them know it's their turn by writing

`HAS_LOCK` to their flag.




Checking for (partial) correctness




Before implementing the `nosharing` verions, it will simplify things to check

`abql_sharing_(un)lock()` by turning on `abql_sharing_correctness_nograph` in

`tests.c` and verifying that your implementations correctly solve the critical

section problem.




`abql_nosharing_(un)lock()`




Head over to `// TODO define a type for abql_nosharing` in `tests.h` and

define a type `flag_nosharing` that still contains a single `uint64_t` `val`,

but also contains enough padding to occupy an entire cache line (8 words or 64

bytes in a cache line).




Next, head over to `// TODO declare and initialize data for abql_nosharing` in

`tests.c` and declare and initialize an array of `n_threads` `flag_nosharing`s

(which is itself aligned on a cache line boundary), where the elements are

initialized as before. Point `flags_nosharing` to this array.




`nosharing` versions of all our familiar variables will be passed to

`abql_nosharing_(un)lock()` in the same way, which is convenient, because it

means we can just copy the text of the `sharing` version of each operation and

replace `sharing` with `nosharing`.




Testing your implementations




Turn on `abql_nosharing_correctness_nograph`, `abql_sharing_lock()`,

`abql_nosharing_lock()` (and leave `ticket_lock()` on) and `bench` as before.




Questions

6. How does `abql_sharing_lock()` compare to `abql_nosharing_lock()`? Why?

7. What memory location(s) are threads contending to update in this implementation?

8. What memory location(s) are threads spinning on in this implementation?

9. What communication (to whom) is triggered when `abql_nosharing_unlock()`

writes to `flags[successor_index].val`? How does this compare

to the communication triggered by `ticket_unlock()`?

10. How does `abql_nosharing_lock()` compare to `ticket_lock()` and why?




(Optional) `mcs_(no)sharing_lock()` and `mcs_(no)sharing_unlock()`




Another queueing lock is the MCS lock, described accessibly [on LWN](https://lwn.net/Articles/590243/) and originally introduced in

[Mellor-Crummey and Scott 1991](https://cis.temple.edu/~qzeng/cis5512-fall2015/papers/p21-mellor-crummey.pdf)

(see Figures 5 and 7). NOTE: This paper uses alternate names for our

primitives. `fetch_and_store` corresponds to `xchgq`, while `compare_and_swap`

corresponds to `lockcmpxchgq`.




The MCS lock, named after its inventors, is basically the linked list to ABQL's

array. To hand off the lock, the lock holder still notifies its successor that

the successor can proceed, much like how the lock holder updates its

successor's `flags_(no)sharing` value in `abql_(no)sharing_release()`. Instead

of an array of flags, we have a local pair of values `next` and `locked` for

each thread (`local_lock`), plus another global pair that new threads use to

join the queue (`global_lock`).




If `global_lock-next` is null, there is no queue (and so no tail of the

queue), and the lock is not held. This is initially the case (otherwise,

nobody could initially acquire it), see the initializations of

`mcs_global_(no)sharing` in tests.c. Otherwise, `global_lock-next` points to

the tail of the queue of local locks, each corresponding to a thread waiting in

line to acquire the lock (besides the head, which corresponds to the lock

holder).




The holder's local lock is at the head of the queue, with its

`local_lock-next` pointing to the holder's successor's lock, starting a chain

that ends at the queue tail. If `local_lock-next == local_lock` or

`local_lock-next` is null, then the holder has no successor, and is alone in

the queue (at least until one comes along, which could happen at any time).




If `CMM_LOAD_SHARED(local_lock[i]-locked) == LOCKED`, then thread `i` is

waiting for its predecessor to update `local_lock[i]-locked` to `UNLOCKED`.

This is how the predecessor hands off the lock to thread `i`. Otherwise,

`local_lock[i]- LOCKED` is always `UNLOCKED`.




Preparing data structures




To implement this, it will help to define a type for these locks. For now, we

won't worry about false sharing, and just use the definition for the type

`mcs_sharing` in `tests.h` where there it says `// define a type for

mcs_sharing`. Giving its members type `uint64_t` will necessitate some casting

back and forth between `mcs_sharing*` and `uint64_t` in the implementation, but

makes it easier to work with our primitive operations, which expect

`uint64_t`s. Also note the global declarations of `mcs_global_sharing` and

`mcss_sharing` below.




Next, head over to `// TODO declare and initialize data for mcs_sharing`

in `tests.c` and declare and initialize an array of `n_threads` `mcs_sharing`s,

each with `next` set to `0` and `locked` set to `UNLOCKED`. Point

`mcss_sharing` to this array. Now `&mcss_sharing[i]` will be supplied as

`local_lock` to each call to `mcs_sharing_(un)lock()`, where `i` is the thread

number (that is, the `i` field in `ti_data_in`) of the caller. `global_lock`

will contain another instance of `mcs_sharing`, initialized in the same way,

indicating that the lock is initially not held.




`mcs_sharing_lock()`




Now we're ready to implement the operations for this lock. Head over to the

definition of `mcs_sharing_lock()` in `worker.c`. To acquire the lock, clear

your `local_lock-next`, then `xchgq` `global_lock-next` for your `local_lock`

to install your lock as the new tail of the queue.




If it comes back that there was no old tail, you're the only thread in the

queue right now, and you're done. Otherwise, you need to put your lock after

the old tail in the queue. Since you'll be waiting for the old tail to finish,

mark `local_lock-locked` as `LOCKED`, and then let the thread corresponding to

the old tail know that you're its successor by updating the old tail's `next`

field to point to your `local_lock`. Now that your lock is linked into the

queue, all you need to do is wait for your predecessor to give you the go-ahead

by updating `local_lock-locked` to `UNLOCKED`. Once that happens, you've

successfully acquired the lock.




`mcs_sharing_unlock()`




Head over to `mcs_sharing_unlock()` in `worker.c`. To release the lock, first

check whether you have a successor (that is, whether `local_lock-next` is

non-null).




If you have a successor, all you need to do is update your successor's lock's

`locked` field to `UNLOCKED`. Now you've handed the lock off to your

successor, and are done.




If you don't have a successor, things are little more complicated. You've

observed no successor, so `global_lock-next` _should_ already be pointing to

your `local_lock` since there is nobody else in the queue, but you need to

allow for the possibility that other threads snuck in and added themselves to

the queue after you observed `local_lock-next` to be null. You can use

`lockcmpxchgq()` here to update `global_lock-next` to `0` if it still holds

`local_lock` (nobody snuck in). In this case, you've removed yourself as the

last remaining queue member, the lock is no longer held, and you're done. If

`global_lock-next` now points to a different lock (that is, `lockcmpxchgq()`

gave back a value `!= local_lock`), then some other thread has concurrently

added itself to the queue, and thinks you're its predecessor. This other

thread will eventually update your `local_lock-next` to point to its own lock

(i.e. get behind you in line), so you need to wait for it to do that (to find

out who the successor is), then update the successor's lock's `locked` field to

`UNLOCKED`. Now you've handed the lock off to your successor, and are done.




`mcs_nosharing_(un)lock()`




Let's see what the impact of false sharing is on MCS performance. Fill in

`// TODO define a type for mcs_nosharing` in `tests.h` with a version that is

padded out fill a cache line (64 bytes, or 8 `uint64_t`s).




Fill in `// TODO declare and initialize data for mcs_nosharing` in

`tests.c` with code that initializes and assigns to `mcss_nosharing` as before,

but guarantees that the array `mcss_nosharing` is aligned on cache line

boundaries (you can always declare a variable with

`__attribute__((aligned (64)))`, for instance).




Head over to `worker.c`, copy your implementations of `mcs_sharing_lock()` and

`mcs_sharing_unlock()` and replace `sharing` with `nosharing` within the copies

to obtain your `mcs_nosharing_(un)lock()` implementations. Wouldn't

language-level support for specializing polymorphic code to multiple concrete

types come in handy about now?




Alternative `mcs_(no)sharing_unlock()`




BONUS: Mellor-Crummey and Scott propose an alternative `unlock` implementation that uses

an unconditional exchange operation (such as `xchgq`) instead of

`lockcmpxchgq`, in Figure 7 of

[Mellor-Crummey and Scott 1991](https://cis.temple.edu/~qzeng/cis5512-fall2015/papers/p21-mellor-crummey.pdf)

and provide a detailed explanation (including an example) in the latter half of

Section 2.4. Implement this variant and compare your graphs.




Testing your implementations




Turn on `mcs_(no)sharing_correctness_nograph` and `mcs_(no)sharing_lock` and

rebuild to check and benchmark your implementations as usual.




Questions

11. How do the `sharing` and `nosharing` variants of MCS compare? Do they

differ as much as `abql_sharing_lock()` and `abql_nosharing_lock()`? Why?

12. How does MCS compare to ABQL? Does one consistently beat the other? If not,

when does MCS win? When does ABQL win? Why?

13. Compare Figures 15 through 17 with Figure 18 in

[Mellor-Crummey and Scott 1991](https://cis.temple.edu/~qzeng/cis5512-fall2015/papers/p21-mellor-crummey.pdf).

Do `mcs` and `anderson` (ABQL), compare in these figures the same way that

MCS and ABQL compare in your graphs?

14. Why do you think Mellor-Crummey and Scott included 3 graphs for tests with

"empty" critical sections and only 1 with a nonempty ("small") critical

section?

15. BONUS: How do the `lockcmpxchgq`-based and alternative `unlock`

implementations' performance compare? Why?

16. BONUS: Explain how the alternative `unlock` implementation breaks fairness.