Multi-threaded Topics
Miscellaneous topics of things related to multi-threaded programming.
Deadlock
A situation that occurs in a multi-threaded system when a group threads are completely blocked because they depend on another member in the group.
Race Condition
Occurs in a program when threads are required to work in a specific sequential order.
Depedendency on controlling the timing of events that are uncontrollable.
Atomic Operations
Concurrent programming is made possible with the use of a handful of hardware-specific atomic operations.
Atomicity of the instructions ensures that the operation happens without interuption.
Compare and Swap (CAP) is the most common operation. It will look at the contents of a memory address, compare it to a given value, and if they match, update (swap) the value with a provided new value.
Lock-Free Data Structures
A reminder that lock-free means that no thread is able to completely lock up the system and prevent other threads from working. Threads can still starve or stall.
A common lock-free data structure is the lock-free cue.
Here it is as a linked list:
https://en.wikipedia.org/wiki/Non-blocking_linked_list.
It basically works like a typical linked list, except that it uses CAS for insertion and deletion.
More information on non-blocking algorithms can be found here:
https://en.wikipedia.org/wiki/Non-blocking_algorithm.
Spin Lock
This is a kind of lock that continuously checks and requests access to a resource and waits ("spins") for a turn. Once accessed, it will lock, perform it's operations on the data, then release the lock.
Linus Torvalds refers to spinlcoks as a "mutal exclusion mechanism".
Spinlocks are reasonably simple to implement, and can be fairly efficient, provided that the critical sections of code are small.
Semaphore
A data type that is used to control access to a particular resource.
A binary semaphore implements the basic kind of mutex.
A counting semaphore can be thought of as a kind of throttling (eg: limiting logins to a particular server).
Linux Torvalds discussing Semaphores on the Mailing List. Linux talking about semaphores, spinlocks, and mutexes were clear to read:
https://www.yarchive.net/comp/linux/semaphores.html* Mutex A "mutal exclusion", more generally referred to as a "lock", is a primative that limits access to a particular resources when there are many threads of execution.
The wikipedia page is a tremendous resource on locks, with links to other topics related to concurrent programming:
https://en.wikipedia.org/wiki/Lock_(computer_science).
"volatile" in the context of multithreading
In C/C++ the volatile keyword indicates that the memory in question is constantly changing, even if it isn't apparent from local code. This can be used as a hint for optimizing compilers to not accidentally optimize reads/writes, and will more explicitely access more up-to-date variables.
The wikipedia very explicitely says that volatile should NOT be used in the context of shared data between threads and inter-thread communication, which probably means at one point people were using for just that.
Messages
Anything tagged with the multithread group will
show up here.
[ada6136b] 2022-06-03-20-32: Communicating Sequential Processes. https://en.m.wikipedia.org/wiki/Communicating_sequential_processes
[6bd3d3bc] 2022-06-03-20-32: A lock-free, concurrent, generic queue in 32 bits https://nullprogram.com/blog/2022/05/14/
[7027165b] 2022-03-22-06-25: mutex: an abbreviation for mutal exclusion. allows only one thread to access some data at any given time.
[24520f46] 2022-03-22-06-23: "do not communicate by sharing memory. share memory by communicating". this is a go motto, quoted in the rust book.
[3afb8826] 2022-03-21-09-42: green thread: threads that are provided by the programming language, rather than through the OS API.
[98e7c2a9] 2022-03-21-09-35: Turning concurrency runtime errors into compiler errors was a big part of the original design ethos of Rust.
[5216f541] 2022-03-21-09-33: safe concurrency is such a big part of Rust's goals. Concurrency is nearly the polar opposite of what I typically work on and think about, so this will probably be a new headspace for me.
[f8935888] 2022-03-19-10-44: a good practical resource page on threads, but in the context of audio: mu.kj.st/ctrl.
[55719f78] 2022-03-17-14-55: ABA problem: a problem that occurs in multithreaded computing, when a location is read twice, has the same value for both reads, and "value is the same" indicates "nothing has changed". Meanwhile, in between reads, another thread can change that value, do work, and change the value back, thus meaning that things have changed.
[c3a9ba06] 2022-03-17-14-36: race condition: a situation that arises when a computer program, to operate properly, depends on the sequence or timing of the program's threads.
[bd20d448] 2022-03-17-10-53: according the C++ standard, volatile is only to be used for hardware access. For interthread communication, use std::atomic
[70febbf8] 2022-03-17-10-52: in C, volatile is probably the closest way to do inter-thread communication without atomics.
[ffac70bf] 2022-03-17-10-51: volatile seems to be used when state is being manipulated as a global variable (calling this memory mapped I/O).
[0b274c1d] 2022-03-17-10-49: to add onto this, I suppose then volatile keywords could be used to implement a lock that isn't guaranteed to work all the time.
[ebd8b338] 2022-03-17-10-48: the use of volatile variables in C/C++ is apparently highly discouraged as a synchronization method in concurrent/multithreaded programming. they are not thread-safe in the vast majority of implementations.
[dd6e66f7] 2022-03-17-10-42: turns out there's a lot of great information on the wikipedia page on locking: https://en.wikipedia.org/wiki/Lock_(computer_science).
[cab30ada] 2022-03-17-10-28: Barrier: in parallel computing, a barrier is a type of synchronization method. A barrier for a group of threads or processes in the source code means any thread/process must stop at this point and cannot proceed until all other thread/processes reach this barrier.
[bcf8c5d1] 2022-03-17-10-24: Funnel: a synchronization primitive used in kernel development to protect system resources. It is a mutex mechanism that prevents more than one thread from accessing certain kernel resources at the same time.
[c6239fa2] 2022-03-17-10-22: priority inversion: a scenario in scheduling in which a high priority task is indirectly superseded by a lower priority task, effectively inverting the assigned priorities of the tasks.
[b1d0e53a] 2022-03-17-10-19: software transactional memory (STM): a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. It is an alternative to lock-based synchronization.
[eef4dad1] 2022-03-17-10-18: optimistic concurrency control: also known as optimistic locking. a concurrency control method applied to transactional systems such as relational database systems and software transactional memory.
[e43538be] 2022-03-17-10-16: 2-phase locking: a concurrency method that guarantees serializability. Abbreviated 2PL. Used in the context of database transactions, 2PL consists of two distinct, consecutive phases: expanding (growing), and shrinking (contracting).
[844dd538] 2022-03-17-10-12: a record lock is also known as a database lock.
[6fad809f] 2022-03-17-10-07: record locking: the technique of preventing simultaneous access to data in a database, to prevent inconsistent results.
[e52bf612] 2022-03-17-10-05: there is a tradeoff between decreasing lock overhead and decreasing lock contention when choosing the number of locks in synchronization.
[777a1fba] 2022-03-17-10-04: lock contention: occurs when one process or thread attempts to acquire a lock held by another process or thread.
[dc0ac8d7] 2022-03-17-10-03: lock overhead: the extra resources for using locks, like the memory space allocated for locks, the CPU time to initialize and destroy locks, and the time required for releasing locks.
[80fbebf2] 2022-03-17-10-01: lock granularity: The granularity is a measure of the amount of data the lock is protecting.
[3162a47c] 2022-03-17-09-59: spinlocks are efficient if threads are likely to be blocked for only short periods, but start to become wasteful if held for longer durations.
[afdafef6] 2022-03-17-09-58: spinlock: a lock that causes a thread trying to acquire it to simply wait in a loop ("spin") while repeatedly checking whether the lock is available.
[350727ef] 2022-03-17-09-57: a careless use of locks can result in a deadlock.
[88c97036] 2022-03-17-09-57: deadlock: a situation in concurrent computing where no member of some group entities can proceed because each waits for another member, including itself, to take action (usually releasing a lock, or sending a message).
[f2ba7cc4] 2022-03-17-09-55: If atomic locking operations are available, one can use either Dekker's algorithm or Peterson's algorithm.
[a4ca8bb6] 2022-03-17-09-53: fetch-and-add (FAA): an atomic instruction that increments a value at address x by a, and then returns the original value at x.
[c01b9b1c] 2022-03-17-09-51: atomic operations in the context of multithreading can be said to be "uninterruptable", and serve as the basis for many primitives used in multithreaded programming such as mutexes and semaphores.
[f87c5a50] 2022-03-17-09-48: atomicity: an instruction that is an indivisible and irreducable series of database operations such that either all occurs or none occurs.
[b09e7966] 2022-03-17-09-46: test-and-set: instruction used to write (set) 1 to a memory location, and return its old value as a single atomic operation.
[10a99087] 2022-03-17-09-44: the atomicity of CAS guarantees that the new value is calculated based on up-to-date information.
[2b86a04b] 2022-03-17-09-43: compare and swap (CAS): an atomic instruction used in multithreading to achieve synchronization. It compares the contents of a memory value with a given value, and if they are the same, modifies the contents of the memory location with a new given value.
[6974b4ce] 2022-03-17-09-40: the simplest type of lock (mutex) is a binary semaphore.
[9dc9f824] 2022-03-17-09-40: critical section: a shared resource in concurrent programming that needs to be protected in ways that avoid concurrent access.
[6afb2071] 2022-03-17-09-37: semaphore: a variable or abstract data type used to control access to a common resource by multiple threads and avoid critical section problems in a concurrent system.
[52e1453a] 2022-03-17-09-34: mutex: short for mutual exclusion. A synchronization primitive that enforces limits on access to a resource when there are many threads of execution.