ConcLinkedList

OVERVIEW

This library contains the skeleton code for implementing and evaluating two concurrent linked lists: a lock-free and a lock-based. The implementations should work on any Linux-based x86 environment.

Both lists are sorted and provide three main operations: (i) adding an element to the list (if not already in the list) (ii) removing an element from the list (if already in the list) (iii) looking for an element in the list

In our case, a node of the list contains at least an integer key.

The lock-based implementation will use a technique called "hand-over-hand locking", while the lock-free will be based on Harris' algorithm (reference below).

REFERENCES

A thorough explanation of the algorithms we will implement: http://www.cs.nyu.edu/courses/fall05/G22.2631-001/lists.slides2.pdf

Lock-free linkedlist implementation of Harris' algorithm "A Pragmatic Implementation of Non-Blocking Linked Lists" T. Harris, p. 300-314, DISC 2001.

INSTALL

You can compile the code (in Linux) by calling: make in the base directory (./ca-linkedlist)

If the number of cores on your processor is not recognized properly, fix it in include/utils.h file under the "#if defined(DEFAULT)" definitions.

RUN

The two executables are in the ./bin folder: lb-ll and lf-ll, for the lock-based and lock-free implementations respectively.

./bin/lb-ll -h ./bin/lf-ll -h

will print the options that the benchmarks accept. Notice you can compile and execute these benchmarks, but they do not provide the intended functionality, i.e., the implementations of the linked lists are empty.

SCRIPTS

You can find several useful scripts that will help you test and evaluate your implementations.

In details:

• ./scripts/test_correctness.sh : test the correctness of an implementation, by stressing it
• ./scripts/scalability1.sh : benchmark 1 application and get its throughput and scalability
  E.g., ./scripts/scalability1.sh all ./bin/lb-ll -i128
• ./scripts/scalability2.sh : benchmark 2 applications and get their throughput and scalability
  E.g., ./scripts/scalability2.sh all ./bin/lb-ll ./bin/lf-ll -i100
• ./scripts/run_ll.sh : execute the workloads that will be part of the deliverable
• ./scripts/create_plots_ll.sh : generate the plots (int plots folder) of the data generated with
  ./scripts/run_ll.sh
  Notice!! You need gnuplot (http://gnuplot.info/) installed

Notice!! You need to execute the scripts from the base folder.

IMPLEMENT

You need to change the: (i) linkedlist.h and (ii) linkedlist.c files in the src/linkedlist/ src/linkedlist-lock/ folders in order to implement the lists.

You can find an easy-to-use interface for atomic operations in include/atomic_ops.h.

(i) linkedlist.h :: contains the interface and the structures of the list. You only need to change the llist_t and node_t structures to reflect the list and a node of a list of your implementations respectively.

Notice!! These two structures might be different for the lock-free and lock-based versions of the list.

(ii) linkedlist.c :: contains the implementations of the operations of the list, i.e., creating a new list and a new bucket, freeing the list, and, of course, adding, removing, and looking for an element in the list.

Additionally, for the lock-based version, you need to implement and use some locks. You can find the skeletons for initializing, freeing, locking, and unlocking a lock in include/lock_if.h

Notice!! The template we provide you with is in C. However, if you are convinced that you will not be able to complete the project due to the language, please contact the TAs to discuss the possibility to implement the assignment in Java.

DETAILS

Memory management is one of most cumbersome problems on lock-free data structures. In other words, when a thread removes an element (a node) from the structure, it cannot always free the memory for that node, because other threads might be holding a reference to this memory.

In this project, we will disregard the memory management part. This means that on a remove operation the memory of the removed node will not be freed. Additionally, this approach entails to every insertion allocating a new node (new memory).

When using locks, memory management is rather straightforward, because of the mutual exclusion property of locks. You can optionally implement memory management on the lock-based version.

An "easy" way to get the necessary results is to execute the experiments using: ./scripts/run_ll.sh and then plots the grapsh using: ./scripts/create_plots_ll.sh