Welcome to another fascinating chapter in our course on lock-based concurrent data structures! In our previous lesson, we delved into the world of thread-safe queues using condition variables to enhance synchronization. This time, we're shifting our focus to lists. Our aim is to explore how to make a list thread-safe, ensuring that even with multiple threads modifying it, our list remains reliable and consistent. This skill is crucial as it opens up new possibilities for developing efficient and safe multi-threaded applications.
In this lesson, you'll learn how to implement a thread-safe list using locks. We'll cover various operations, such as adding, removing, and finding elements within a list. Let's take a sneak peek at some code to get a sense of what we'll be working on:
C++1class ThreadSafeList 2{ 3private: 4 struct node 5 { 6 std::mutex m; 7 std::shared_ptr<int> data; 8 std::unique_ptr<node> next; 9 10 node() : next(nullptr) {} 11 12 node(int const& value) : data(std::make_shared<int>(value)) {} 13 }; 14 15 node head; 16 17public: 18 void push_front(int const& value) 19 { 20 std::unique_ptr<node> new_node(new node(value)); 21 std::lock_guard<std::mutex> lk(head.m); 22 new_node->next = std::move(head.next); 23 head.next = std::move(new_node); 24 } 25 26 template<typename Function> 27 void for_each(Function f) 28 { 29 node* current = &head; 30 std::unique_lock<std::mutex> lk(head.m); 31 while (node* const next = current->next.get()) 32 { 33 std::unique_lock<std::mutex> next_lk(next->m); 34 lk.unlock(); 35 f(*next->data); 36 current = next; 37 lk = std::move(next_lk); 38 } 39 } 40 41 template<typename Predicate> 42 std::shared_ptr<int> find_first_if(Predicate p) 43 { 44 node* current = &head; 45 std::unique_lock<std::mutex> lk(head.m); 46 while (node* const next = current->next.get()) 47 { 48 std::unique_lock<std::mutex> next_lk(next->m); 49 lk.unlock(); 50 if (p(*next->data)) 51 { 52 return next->data; 53 } 54 current = next; 55 lk = std::move(next_lk); 56 } 57 return std::shared_ptr<int>(); 58 } 59 60 template<typename Predicate> 61 void remove_if(Predicate p) 62 { 63 node* current = &head; 64 std::unique_lock<std::mutex> lk(head.m); 65 while (node* const next = current->next.get()) 66 { 67 std::unique_lock<std::mutex> next_lk(next->m); 68 if (p(*next->data)) 69 { 70 std::unique_ptr<node> old_next = std::move(current->next); 71 current->next = std::move(next->next); 72 next_lk.unlock(); 73 } 74 else 75 { 76 lk.unlock(); 77 current = next; 78 lk = std::move(next_lk); 79 } 80 } 81 } 82};
Here, we're adding a new element to the front of the list in a thread-safe manner. Each node in our list comes with its own mutex, ensuring that a lock is only held for the node being modified. This strategy minimizes lock contention, making the list more efficient when accessed by multiple threads.
Let's explore the methods we've implemented:
push_front: Adds a new element to the front of the list. It locks the head node and then moves the new node to the front.for_each: Iterates over each element in the list and applies a function to it. It locks each node individually to prevent concurrent modifications.find_first_if: Searches for the first element in the list that satisfies a given predicate. It locks each node individually to ensure that the list remains consistent.remove_if: Removes elements from the list that satisfy a given predicate. It locks each node individually to prevent concurrent modifications.
Let's now see how we can use these methods to interact with our thread-safe list in a multi-threaded environment doing various operations:
C++1int main() { 2 ThreadSafeList list; 3 4 std::vector<std::thread> threads; 5 for (int i = 0; i < 10; ++i) { 6 threads.emplace_back([&list, i] { 7 list.push_front(i); 8 }); 9 } 10 11 for (int i = 0; i < 5; ++i) { 12 threads.emplace_back([&list, i] { 13 list.remove_if([i](int value) { return value == i; }); 14 }); 15 } 16 17 for (int i = 0; i < 2; ++i) { 18 threads.emplace_back([&list, i] { 19 auto result = list.find_first_if([i](int value) { return value == i; }); 20 if (result) { 21 std::cout << "Found: " << *result << std::endl; 22 } 23 }); 24 } 25 26 for (int i = 0; i < 2; ++i) { 27 threads.emplace_back([&list] { 28 list.for_each([](int value) { 29 std::cout << value << std::endl; 30 }); 31 }); 32 } 33 34 for (auto& t : threads) { 35 t.join(); 36 } 37 38 return 0; 39}
In this example, we're creating a list and spawning multiple threads to perform various operations on it concurrently. We have threads adding elements to the list, removing elements, searching for elements, and iterating over the list. The thread-safe list ensures that these operations can be performed safely and efficiently in a multi-threaded environment.
Understanding how to implement a thread-safe list using locks is essential for building applications that require concurrent access to a collection of items. In many real-world scenarios, such as managing a list of clients in a server application or logging events in a multi-threaded environment, efficient and safe access to shared data structures is paramount.
By mastering these techniques, you’ll gain the ability to create robust and high-performance applications. You'll also acquire insights into balancing the trade-offs between safety and performance, preparing you to tackle more advanced problems in concurrent programming confidently.
Are you eager to start bringing these ideas to life? Let’s jump into the practice section and apply what we’ve learned in exciting real-world scenarios!