This is not the best solution since there is no concurrency. It may be fine if the application does not spend a lot of time with the linked list.
muchanon
This solution is suboptimal since a node could be inserted at location 10 and location 20 at the same time. If the linked list is long, the insert/delete operation could take a long time. To take advantage of the independence which exists, we need finer grained locking.
bochet
Be careful to not miss the unlock in the if condition of delete. Otherwise, the lock will be a dead lock.
Master
A note on busy waiting (spin lock):
Busy waiting is more suitable for the case that the critical section is small.
To be more specific, as the size of the critical section increases, the thread may be interrupted by the OS scheduler many times while holding the lock. If this happens, other threads will be just busy waiting trying to acquire the lock, while the thread holding the lock is not making progress towards releasing it. In this case, the thread holding the lock will take very long to finish as most of the time is spent on spinning.
locked
@master I think this will happen if it is a single core machine.
o_o
By having the lock lock the entire linked list, this makes it so that there is no parallelism when it comes to modifying this linked list. All threads that want to modify the linked list will have to wait for other threads to insert/delete one node, and the threads will be doing it sequentially. Thus, there would be a bottleneck here, where all threads are contending for the entire linked list. This is because the granularity is too large, we are locking the entire list even if two threads can potentially insert/delete a node at different parts of the list.
fxffx
Protect the list with a single lock can guarantee correctness, but it's not efficient because different threads may modify different region of the list and could've been executed concurrently.
This is not the best solution since there is no concurrency. It may be fine if the application does not spend a lot of time with the linked list.
This solution is suboptimal since a node could be inserted at location 10 and location 20 at the same time. If the linked list is long, the insert/delete operation could take a long time. To take advantage of the independence which exists, we need finer grained locking.
Be careful to not miss the unlock in the if condition of delete. Otherwise, the lock will be a dead lock.
A note on busy waiting (spin lock):
Busy waiting is more suitable for the case that the critical section is small.
To be more specific, as the size of the critical section increases, the thread may be interrupted by the OS scheduler many times while holding the lock. If this happens, other threads will be just busy waiting trying to acquire the lock, while the thread holding the lock is not making progress towards releasing it. In this case, the thread holding the lock will take very long to finish as most of the time is spent on spinning.
@master I think this will happen if it is a single core machine.
By having the lock lock the entire linked list, this makes it so that there is no parallelism when it comes to modifying this linked list. All threads that want to modify the linked list will have to wait for other threads to insert/delete one node, and the threads will be doing it sequentially. Thus, there would be a bottleneck here, where all threads are contending for the entire linked list. This is because the granularity is too large, we are locking the entire list even if two threads can potentially insert/delete a node at different parts of the list.
Protect the list with a single lock can guarantee correctness, but it's not efficient because different threads may modify different region of the list and could've been executed concurrently.