Content deleted Content added
m link term (WP:BUILDTHEWEB) |
BrainStack (talk | contribs) Link suggestions feature: 3 links added. |
||
Line 14:
This problem (called a ''race condition'') can be avoided by using the requirement of mutual exclusion to ensure that simultaneous updates to the same part of the list cannot occur.
The term mutual exclusion is also used in reference to the simultaneous writing of a [[memory address]] by one thread while the aforementioned memory address is being manipulated or read by one or more other threads.
==Problem description==
The problem which mutual exclusion addresses is a problem of resource sharing: how can a software system control multiple processes' access to a shared resource, when each process needs exclusive control of that resource while doing its work? The mutual-exclusion solution to this makes the shared resource available only while the process is in a specific [[code segment]] called the [[critical section]]. It controls access to the shared resource by controlling each mutual execution of that part of its program where the resource would be used.
A successful solution to this problem must have at least these two properties:
Line 48:
Busy-waiting is effective for both uniprocessor and [[multiprocessor]] systems. The use of shared memory and an [[Linearizability|atomic]] [[test-and-set]] instruction provide the mutual exclusion. A process can [[test-and-set]] on a ___location in shared memory, and since the operation is atomic, only one process can set the flag at a time. Any process that is unsuccessful in setting the flag can either go on to do other tasks and try again later, release the processor to another process and try again later, or continue to loop while checking the flag until it is successful in acquiring it. [[Preemption (computing)|Preemption]] is still possible, so this method allows the system to continue to function—even if a process halts while holding the lock.
Several other atomic operations can be used to provide mutual exclusion of data structures; most notable of these is [[compare-and-swap]] (CAS). CAS can be used to achieve [[wait-free]] mutual exclusion for any shared [[data structure]] by creating a [[linked list]] where each node represents the desired operation to be performed. CAS is then used to change the [[Pointer (computer programming)|pointers]] in the linked list<ref>{{cite journal |last1=Harris |first1=Timothy L. |title=A Pragmatic Implementation of Non-blocking Linked-lists |journal=Distributed Computing |series=Lecture Notes in Computer Science |date=2001 |volume=2180 |pages=300–314 |doi=10.1007/3-540-45414-4_21 |isbn=978-3-540-42605-9 |url=https://timharris.uk/papers/2001-disc.pdf |access-date=1 December 2022 |language=en}}</ref> during the insertion of a new node. Only one process can be successful in its CAS; all other processes attempting to add a node at the same time will have to try again. Each process can then keep a local copy of the data structure, and upon traversing the linked list, can perform each operation from the list on its local copy.
===Software solutions===
| |||