Source code
class NODE {
public:
int key;
NODE *next;
bool marked;
NODE(int v) {
key = v;
next = nullptr;
marked = false;
}
NODE() {
next = nullptr;
}
};
class LLIST{
private:
NODE head, tail;
public:
LLIST(){
head.key = 0x80000000;
tail.key = 0x7FFFFFFF;
head.next = &tail;
}
void Init(){
while (head.next != &tail) {
NODE *temp = head.next;
head.next = head.next->next;
delete temp;
}
}
bool Validate(NODE *pred, NODE *curr) {
return !pred->marked && !curr->marked && pred->next == curr;
}
bool Add(int x)
{
NODE *pred, *curr;
while (true) {
pred = &head;
curr = pred->next;
while (curr->key < x) {
pred = curr;
curr = curr->next;
}
pred->lock();
curr->lock();
if (Validate(pred, curr)) {
if (curr->key == x) {
curr->unlock();
pred->unlock();
return false;
}
else {
NODE *node = new NODE(x);
node->next = curr;
pred->next = node;
curr->unlock();
pred->unlock();
return true;
}
}
else{
curr->unlock();
pred->unlock();
}
}
}
bool Remove(int x)
{
NODE *pred, *curr;
while (true) {
pred = &head;
curr = pred->next;
while (curr->key < x) {
pred = curr;
curr = curr->next;
}
pred->lock();
curr->lock();
if (Validate(pred, curr)) {
if (curr->key == x) {
curr->marked = true;
pred->next = curr->next;
curr->unlock();
pred->unlock();
//delete curr; --> Memory Leak
return true;
}
else {
curr->unlock();
pred->unlock();
return false;
}
}
else{
curr->unlock();
pred->unlock();
}
}
}
bool Contains(int x)
{
NODE* curr;
while (curr->key < x) curr = curr->next;
return (curr->key == x) && (curr->marked == false);
}
};
The source code implements a lazy synchronization linked list, where elements are logically deleted but not immediately removed. The lazy approach delays certain operations to reduce contention, which can improve performance in concurrent environments.
Key Concepts in the Code:
Lazy Deletion:
- In the
Removemethod, the node is not immediately deleted when it is marked for removal. Instead, it is marked astrue(usingmarkedflag), and the node is eventually removed when no other threads reference it. This technique reduces contention during removal.
- In the
Locking Mechanism:
- The
lockandunlockmethods are used to ensure mutual exclusion when accessing or modifying the list. However, thelock/unlockimplementation is not provided in the source code, which would be crucial for actual synchronization. TheValidatemethod checks if the predecessor and current node are consistent and not marked as deleted.
- The
Node Structure:
- The
NODEclass contains:key: the value of the node.next: the pointer to the next node.marked: a flag indicating if the node has been marked for deletion.
- The
Add:
- Adds a new node to the list after validating that the predecessor and current node are not marked. If the key already exists, it returns false.
Remove:
- Marks a node for deletion and adjusts the
nextpointer of the predecessor to remove the node from the list. The memory of the deleted node is not freed immediately, causing a memory leak (commenteddeletestatement in the code).
- Marks a node for deletion and adjusts the
Contains:
- Checks if a node with a specific key exists in the list and is not marked for deletion.
Execution Time Analysis:
The performance of the lazy linked list under different thread loads is measured, and the results show how the execution time changes as the number of threads increases. Here’s the performance table:
| Number of Threads | Execution Time (ms) |
|---|---|
| 1 Thread | 1297ms |
| 2 Threads | 1066ms |
| 4 Threads | 902ms |
| 8 Threads | 5743ms |
| 16 Threads | 10618ms |
Key Insights:
Performance Scaling:
- As the number of threads increases from 1 to 4, the execution time decreases, which suggests improved parallelism and efficiency with higher concurrency.
Performance Degradation at 8 and 16 Threads:
- The performance starts to degrade significantly after 8 threads, with a sharp increase in execution time at 16 threads. This suggests that contention due to the locking mechanism, as well as overhead from marking and logical deletion, starts to affect performance at higher concurrency levels.
Lazy Synchronization:
- The lazy synchronization approach helps reduce contention during deletions, but as the number of threads increases, the cost of synchronization increases. This leads to increased contention and thus higher execution times when many threads are involved.
Hardware Specifications:
- CPU: Intel Core i5-3570 (3.40 GHz)
- RAM: 8GB DDR3
The system specifications indicate moderate processing power and sufficient memory for handling the workload, but the performance bottleneck likely arises from the synchronization approach and increased contention as the number of threads grows.
Conclusion:
- Lazy synchronization helps improve performance for small numbers of threads by reducing contention during deletions, but as the thread count increases, the performance degrades due to higher synchronization overhead.
- The use of a locking mechanism in combination with lazy deletion prevents race conditions but creates contention, which impacts performance as the number of threads grows.
- To achieve better performance in highly concurrent systems, a lock-free approach or non-blocking synchronization methods could offer better scalability and reduced contention.
This analysis highlights the trade-offs of using lazy synchronization in a linked list and provides insights into how synchronization techniques affect the performance of multithreaded applications.