9. Concurrent Data Structures: Thread-Safe Queues and Hash Tables

Learning Objectives Explain why standard data structures like queues and hash tables are not safe for use in multi-threaded programs. Define and identify a 'race condition' in a code snippet involving a shared data structure. Describe the concept of a 'lock' or 'mutex' and how it provides mutual exclusion to protect a critical section. Implement a simple producer-consumer pattern using a thread-safe queue. Compare and contrast the performance and safety characteristics of standard vs. concurrent hash tables. Analyze a concurrent programming problem and select the appropriate concurrent data structure (queue or hash table) for the solution. Imagine two people trying to update the same cell in a spreadsheet at the exact same moment. Whose change g...

TermDefinitionExample Thread SafetyA piece of code or a data structure is 'thread-safe' if it functions correctly even when accessed by multiple threads simultaneously, without causing race conditions or data corruption.A standard list is not thread-safe; if two threads try to add an element at the same time, the list's internal size counter might only be incremented once, leading to corrupted data. A 'ConcurrentList' would be thread-safe. Race ConditionA bug that occurs when the outcome of a program depends on the unpredictable sequence or timing of operations from multiple threads. It often happens when threads read and write to a shared resource without protection.Two threads read a bank balance of $100. Thread A calculates a new balance of $150. Thread B calcu...

The Lock-Work-Unlock Pattern my_lock.acquire() // --- Critical Section Start --- // Access or modify the shared resource here // --- Critical Section End --- my_lock.release() This is the fundamental pattern for ensuring mutual exclusion. Before entering a critical section, a thread must 'acquire' a lock. If another thread holds the lock, it will wait. After finishing its work with the shared resource, it MUST 'release' the lock so other threads can proceed. The Producer-Consumer Pattern // Producer Thread while (has_data_to_produce): item = produce_data() concurrent_queue.enqueue(item) // Consumer Thread while (true): item = concurrent_queue.dequeue() // This will wait if queue is empty process(item) A common concurrency pattern where one or mor...