Editing Mutual exclusion (section)

===Hardware solutions===
On [[Uniprocessor system|uni-processor]] systems, the simplest solution to achieve mutual exclusion is to disable [[interrupt]]s during a process's critical section. This will prevent any [[interrupt service routine]]s from running (effectively preventing a process from being [[Preemption (computing)|preempted]]). Although this solution is effective, it leads to many problems. If a critical section is long, then the [[system clock]] will drift every time a critical section is executed because the timer interrupt is no longer serviced, so tracking time is impossible during the critical section. Also, if a process halts during its critical section, control will never be returned to another process, effectively halting the entire system. A more elegant method for achieving mutual exclusion is the [[busy-wait]].

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.