0x361 Computing
This note is about topics related to shared-memory concurrent programming.
1. Concurrent Computing
1.1. Data Structure
Lock based concurrent data structure looks interesting. The most simple approach is to have a big lock on the entire data structure, which has the performance issue. A better approach is to have multiple locks locking parts of the data structure. For example
Concurrent counter: An interesting approach is an approximate counter which maintains a global counter and multiple local counters and corresponding locks on each core, each thread is updating its core's counter and sometimes the local counter propagate its value to the global counter Concurrent list: hand-over-hand locking approach prepares each node a lock, when processing the list, unlock the previous one and lock current one. Concurrent queue: One implementation is to put a lock on the first and last element respectively. To keep the first and last to be different, always insert a tmp element. Concurrent hash: maintain multiple buckets which have different locks.
2. Transaction
property (ACID)
- Atomicity: commits are either fully successful or roll back to the prior states completely
- Consistency: maintaining database invariants: transaction wil bring from one valid state to another
- Isolation: any transaction will not be affected by other transaction
- Durability: successful commit will survive permanently (usually meaning recorded in non-volatile memory)
2.1. Transaction Isolation
2.1.1. Read-Committed Isolation
2.1.2. Serializable Isolation
2.2. Concurrency Control
We have 3 categories
Optimistic concurrency control (OCC)
Allows transactions to execute concurrent read/write operations, and determines whether or not the result of the combined execution is serializable. If there is a conflict, one of the conflicting transactions is aborted.
Multiversion concurrency control (NVCC)
Pessimistic concurrency control (PCC)