[Solved] COP4520 Programming Assignment 2

Design and Implementation of Concurrent Linked List:

Design a coarse-grained locking linked list, as described in Chapter 9 of the textbook. Save this version of the linked list and call it BLOCKING_LIST. Transform your algorithm into a lockfree algorithm and call it NONBLOCKING_LIST. Your implementation should be based on Tim Harris paper A Pragmatic Implementation of Non-Blocking Linked Lists. You may also use Section 9.8 of the textbook for reference.

Evaluate your approach by executing performance comparison of your BLOCKING_LIST and NONBLOCKING_LIST. In your benchmark tests, vary the number of threads from 1 to 32 and produce graphs where you map the total execution time on the y-axis and the number of threads on the x-axis. Produce at least 3 different graphs representing different ratios of the invocation of insert, delete, and find. For example, your different ratios could be:

• Mixed: 33% insert, 33% delete, 34% find
• Write-dominated: 50% insert, 50% delete, 0% find
• Read-dominated: 15% insert, 5% delete, 80% find

To avoid polluting your results with the overhead of memory management (the standard malloc and free dont scale well), you should have each thread pre-allocate its own supply of nodes, which it can keep on a private list when they are not in the list. Finally, to avoid pollution from calls to the pseudo-random (the standard rand isnt even thread-safe), you should pregenerate enough random integers to drive the choice between insert, delete, and find for the entire test run.

Provide a brief summary of your approach and an informal statement reasoning about the correctness and efficiency of your design.

Use either C or C++ for this assignment and provide a ReadMe file with instructions explaining how to compile and run your program.