boki1 / telamon Goto Github PK

Description

Harris' Linked List was the first implementation which provide an actual well-performing lock-free data structure. The realization uses 1 CAS operation for insertion of an element and 2 for deletion. For more info (w/ additional resources) see this link.

The implementation of this linked list has the objective of confirming the proper execution of the simulation.

Task

Implement Harris' linked list and then modify it to use the simulation API and to satisfy its requirements.

Definition of Done

Successfully performing operations on the linked list using the simulation.

Description

The simulator represents the actual wait-free algorithm. It encapsulates the logic which performs directs operations to the fast or the slow path, it keeps track of the encountered contention during operation execution and it utilizes the help queue in the correct way.

The simulator contains the API to which the user of the library should adhere to. It is built as a handle structure which shares data among all active handles, e.g shared resources are the help queue, the simulated algorithm. Part of the API is dealing with managing the handles.

The most important part of the functionalities of the simulator are the fast_path, slow_path and simulate functions. They are responsible for actually executing a given operation and producing some result as an output.

Another component of the architecture is related to the value being enqueued in the help queue, represented as the types OperationRecord, OperationRecordBox, OperationState. The OperationRecordBox keeps only an atomic pointer to an OperationRecord allocated on the heap, which stores the actual meta information about the operation status. Part of it is in OperationState which is essentially a std::variant with the different possible states as types, since each of them (e.g. ExecutingCAS) requires additional data (CAS-list).

Definition of Done

The principal objective is to represent the above-described structure of the different components.

Description

During the process of helping, each owner-thread associates a state with the operation it is executing. There are specific micro-operation which should be performed according to the current state of the concrete operation and followed by a status promotion.

Task

Implement the algorithm which is responsible to keep track of the operation states and the micro-operation involved in the process of their execution.

Definition of Done

Successful implementation of the above-described structure.

Description

The algorithm is based on a wait-free queue which is responsible for keeping track of operations which did not succeed correctly and need "helping". It is implemented as a wait-free queue with peek, enqueue and conditionalDequeue operations.

Task

Provide realization for the structure which the guarantees that the queue is wait-free. Provide realization for the said operations.

Definition of Done

Full implementation of the structure with the operations required.

Task

Using the loguro logging library add enough output so that is may be used for debugging purposes. Provide option which can turn-off logging.

Definition of Done

Be able to understand and easily follow the path taken in a specific execution in the help queue.

Task

Provide tests for the operations executed on the help queue.

Definition of Done

Successfully passing tests which mock the operations executed on the help queue during the actual simulation.

Task

Provide unit tests for the functionalities that the simulator provides in order to secure a correct implementation of the algorithm.

Definition of Done

Tests covering a good proportion of the simulation algorithm (>= 75%) with correct results.

This also includes the correct execution of operation on Harris' linked list.

Description

Normalized lock-free structure is one for which each operation can be presented in three stages, such that the middle stage executes the owner CAS-es, the first is preparatory stage and the last is a post-execution step.

Other requirements defined in the paper describing the practical simulation algorithm are that:

• any modification of the shared memory is executed using a CAS operation
• the first stage (the generator) and the last stage (the wrap-up) are parallelizable and they have associated contention failure counter
• the CAS-es that the generator outputs are for fields that emply versioning (see ABA problem solutions)

Task

Implement a structure which represents the requirements above.

Definition of Done

After successful implementation of the normalized representation blueprint, the process of normalizing a given lock-free data structure should be a simple task.

Provide a normalized representation of a lock-free algorithm.