Editing Lock (computer science) (section)

==Disadvantages==
Lock-based resource protection and thread/process synchronization have many disadvantages:
* Contention: some threads/processes have to wait until a lock (or a whole set of locks) is released. If one of the threads holding a lock dies, stalls, blocks, or enters an infinite loop, other threads waiting for the lock may wait indefinitely until the computer is [[power cycling|power cycled]].
* Overhead: the use of locks adds overhead for each access to a resource, even when the chances for collision are very rare. (However, any chance for such collisions is a [[race condition]].)
* Debugging: bugs associated with locks are time dependent and can be very subtle and extremely hard to replicate, such as [[deadlock (computer science)|deadlock]]s.
* Instability: the optimal balance between lock overhead and lock contention can be unique to the problem domain (application) and sensitive to design, implementation, and even low-level system architectural changes. These balances may change over the life cycle of an application and may entail tremendous changes to update (re-balance).
* Composability: locks are only composable (e.g., managing multiple concurrent locks in order to atomically delete item X from table A and insert X into table B) with relatively elaborate (overhead) software support and perfect adherence by applications programming to rigorous conventions.
* [[Priority inversion]]: a low-priority thread/process holding a common lock can prevent high-priority threads/processes from proceeding. [[Priority inheritance]] can be used to reduce priority-inversion duration. The [[priority ceiling protocol]] can be used on uniprocessor systems to minimize the worst-case priority-inversion duration, as well as prevent [[deadlock (computer science)|deadlock]].  
* [[Lock convoy|Convoying]]: all other threads have to wait if a thread holding a lock is descheduled due to a time-slice interrupt or page fault.

Some [[concurrency control]] strategies avoid some or all of these problems. For example, a [[funnel (Concurrent computing)|funnel]] or [[serializing tokens]] can avoid the biggest problem: deadlocks. Alternatives to locking include [[non-blocking synchronization]] methods, like [[lock-free and wait-free algorithms|lock-free]] programming techniques and [[transactional memory]]. However, such alternative methods often require that the actual lock mechanisms be implemented at a more fundamental level of the operating software. Therefore, they may only relieve the ''application'' level from the details of implementing locks, with the problems listed above still needing to be dealt with beneath the application.

In most cases, proper locking depends on the CPU providing a method of atomic instruction stream synchronization (for example, the addition or deletion of an item into a pipeline requires that all contemporaneous operations needing to add or delete other items in the pipe be suspended during the manipulation of the memory content required to add or delete the specific item). Therefore, an application can often be more robust when it recognizes the burdens it places upon an operating system and is capable of graciously recognizing the reporting of impossible demands.{{Citation needed|date=November 2013}}

===Lack of composability===
One of lock-based programming's biggest problems is that "locks don't [[Function composition (computer science)|compose]]": it is hard to combine small, correct lock-based modules into equally correct larger programs without modifying the modules or at least knowing about their internals. [[Simon Peyton Jones]] (an advocate of [[software transactional memory]]) gives the following example of a banking application:<ref>{{Cite encyclopedia |title=Beautiful concurrency |first=Simon |last=Peyton Jones |encyclopedia=Beautiful Code: Leading Programmers Explain How They Think |editor1-first=Greg |editor1-last=Wilson |editor2-first=Andy |editor2-last=Oram |publisher=O'Reilly |year=2007 |url=http://research.microsoft.com/en-us/um/people/simonpj/papers/stm/beautiful.pdf}}</ref> design a class {{mono|Account}} that allows multiple concurrent clients to deposit or withdraw money to an account, and give an algorithm to transfer money from one account to another.

The lock-based solution to the first part of the problem is:

 '''class''' Account:
     '''member''' balance: Integer
     '''member''' mutex: Lock
 
     '''method''' deposit(n: Integer)
            mutex.lock()
            balance ← balance + n
            mutex.unlock()
 
     '''method''' withdraw(n: Integer)
            deposit(−n)

The second part of the problem is much more complicated. A {{mono|transfer}} routine that is correct ''for sequential programs'' would be

 '''function''' transfer(from: Account, to: Account, amount: Integer)
     from.withdraw(amount)
     to.deposit(amount)

In a concurrent program, this algorithm is incorrect because when one thread is halfway through {{mono|transfer}}, another might observe a state where {{mono|amount}} has been withdrawn from the first account, but not yet deposited into the other account: money has gone missing from the system. This problem can only be fixed completely by putting locks on both accounts prior to changing either one, but then the locks have to be placed according to some arbitrary, global ordering to prevent deadlock:

 '''function''' transfer(from: Account, to: Account, amount: Integer)
     '''if''' from < to    ''// arbitrary ordering on the locks''
         from.lock()
         to.lock()
     '''else'''
         to.lock()
         from.lock()
     from.withdraw(amount)
     to.deposit(amount)
     from.unlock()
     to.unlock()

This solution gets more complicated when more locks are involved, and the {{mono|transfer}} function needs to know about all of the locks, so they cannot be [[Encapsulation (object-oriented programming)|hidden]].