This week you will implement a simple locking construct by relying only on primitive atomic operations. You will also implement a scalable, thread-safe concurrent data-structure. This will be achieved by following two different paths:

1. using locks
2. using a lock-free algorithm.

1. Implement the spinlock that is declared in cspinlock.h to generate a library called libcspinlock.so.
2. Implement a lock-based hashmap datastructure that is declared in chashmap.h to generate a library called liblockhashmap.so.
3. Implement a lock-free hashmap datastructure that is declared in chashmap.h to generate a library called liblockfreehashmap.so.

NB: For tasks 1 and 3, only atomic primitives (e.g., compare-and-swap, atomic fetch-and-increment, etc.) are allowed. No synchronization library can be used (on Rust you can use std::sync::atomic).

You allocate datastructures via Box and cast those to/from raw pointer when implementing the alloc/free functions required by the chashmap and cspinlock interface.

There are three tests that needs to be passed to complete this task successfully.

test_mutual_exclusion.py expects libcspinlock.so and checks whether the implementation of cspinlock guarantees that no two critical sections can execute concurrently.

test_lockhashmap.py expects liblockhashmap.so and checks for the following:

1. the concurrent hashmap is implemented correctly
2. the hashmap scales with increasing number of threads

test_lockfreehashmap.py expects liblockfreehashmap.so and checks for the following:

1. the concurrent hashmap is implemented correctly
2. the hashmap scales with increasing number of threads in high contention workloads.

• Both lock-based and lock-free hashmap tests rely on the hashmap-driver.c to execute a workload on the hashmap. You can check the usage of this code to test your own.
• The hashmap does not need to check if an element is already in the hashmap before inserting
• Inserts should be relatively fast (i.e. insert at the beginning of the bucket, not the end)

1. If you want to further develop your concurrent programming skills you can check other synchronization techniques such as Read-Copy-Update (RCU) and figure out how can the hashmap use RCU.
2. Another direction that is important for lock-free programming is memory reclamation. You can try to understand how to safely reclaim deleted nodes from the hashmap.

1. MCS locks and qspinlocks
2. A Pragmatic Implementation of Non-Blocking Linked-Lists
3. Introduction to RCU
4. Reclaiming Memory for Lock-Free Data Structures: There has to be a Better Way