Content deleted Content added
→See also: Aggressive pruning, as this has steadily accumulated more and more tangential links. |
→Obstruction-freedom: Optimistic concurrency control != obstruction freedom. |
||
Line 71:
Obstruction-freedom demands only that any partially completed operation can be aborted and the changes made rolled back. Dropping concurrent assistance can often result in much simpler algorithms that are easier to validate. Preventing the system from continually [[livelock|live-locking]] is the task of a contention manager.
Some obstruction-free algorithms use a pair of "consistency markers" in the data structure. Processes reading the data structure first read one consistency marker, then read the relevant data into an internal buffer, then read the other marker, and then compare the markers. The data is consistent if the two markers are identical. Markers may be non-identical when the read is interrupted by another process updating the data structure. In such a case, the process discards the data in the internal buffer and tries again.
| |||