In
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
, especially in the fields of
computer programmingComputer programming is the process of writing, testing, debugging/troubleshooting, and maintaining the source code of computer programs. This source code is written in a programming language. The code may be a modification of an existing source or something completely new...
(see also concurrent programming, parallel programming), operating systems (see also
parallel computingParallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
), multiprocessors, and databases,
concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible.
Concurrency control in
database management systems (DBMS)A Database Management System is a set of computer programs that controls the creation, maintenance, and the use of the database in a computer platform or of an organization and its end users. It allows organizations to place control of organization-wide database development in the hands of...
ensures that
database transactionA database transaction comprises a unit of work performed within a database management system against a database, and treated in a coherent and reliable way independent of other transactions...
s are performed concurrently without the
concurrencyIn computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
violating the
data integrityData integrity is a term used in computer science and telecommunications that can mean ensuring data is "whole" or complete, the condition in which data is identically maintained during any operation , the preservation of data for their intended use, or, relative to specified operations, the a...
of a
databaseA database is an integrated collection of logically related records or files consolidated into a common pool that provides data for one or more multiple uses....
.
In
computer scienceComputer science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe and transform...
, especially in the fields of
computer programmingComputer programming is the process of writing, testing, debugging/troubleshooting, and maintaining the source code of computer programs. This source code is written in a programming language. The code may be a modification of an existing source or something completely new...
(see also concurrent programming, parallel programming), operating systems (see also
parallel computingParallel computing is a form of computation in which many calculations are carried out simultaneously, operating on the principle that large problems can often be divided into smaller ones, which are then solved concurrently . There are several different forms of parallel computing: bit-level,...
), multiprocessors, and databases,
concurrency control ensures that correct results for concurrent operations are generated, while getting those results as quickly as possible.
Concurrency control in databases
Concurrency control in
database management systems (DBMS)A Database Management System is a set of computer programs that controls the creation, maintenance, and the use of the database in a computer platform or of an organization and its end users. It allows organizations to place control of organization-wide database development in the hands of...
ensures that
database transactionA database transaction comprises a unit of work performed within a database management system against a database, and treated in a coherent and reliable way independent of other transactions...
s are performed concurrently without the
concurrencyIn computer science, concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other...
violating the
data integrityData integrity is a term used in computer science and telecommunications that can mean ensuring data is "whole" or complete, the condition in which data is identically maintained during any operation , the preservation of data for their intended use, or, relative to specified operations, the a...
of a
databaseA database is an integrated collection of logically related records or files consolidated into a common pool that provides data for one or more multiple uses....
. Executed transactions should follow the
ACIDIn computer science, ACID is a set of properties that guarantee that database transactions are processed reliably. In the context of databases, a single logical operation on the data is called a transaction...
rules, as described below. The DBMS must guarantee that only serializable (unless
SerializabilityIn databases, transaction processing, and various transactional applications, both centralized and distributed, a transaction schedule is serializable, has the Serializability property, if its outcome is equal to the outcome of its transactions executed serially, i.e., sequentially without...
is intentionally relaxed), recoverable schedules are generated. It also guarantees that no effect of committed transactions is lost, and no effect of aborted (rolled back) transactions remains in the related database.
Transaction ACIDIn computer science, ACID is a set of properties that guarantee that database transactions are processed reliably. In the context of databases, a single logical operation on the data is called a transaction...
rules
- Atomicity - Either the effects of all or none of its operations remain when a transaction is completed - in other words, to the outside world the transaction appears to be indivisible, atomic.
- Consistency - Every transaction
A database transaction comprises a unit of work performed within a database management system against a database, and treated in a coherent and reliable way independent of other transactions...
must leave the database in a consistent state.
- Isolation
In database systems, isolation is a property that defines how/when the changes made by one operation become visible to other concurrent operations. Isolation is one of the ACID properties.-Isolation levels:...
- Transactions cannot interfere with each other. Providing isolation is the main goal of concurrency control.
- Durability
In database systems, durability is the ACID property which guarantees that transactions that have committed will survive permanently.For example, if a flight booking reports that a seat has successfully been booked, then the seat will remain booked even if the system crashes.Durability can be...
- Successful transactions must persist through crashA crash or in computing is a condition where a program stops performing its expected function and also stops responding to other parts of the system. Often the offending program may simply appear to freeze...
es.
Concurrency control mechanism
The main categories of concurrency control mechanisms are:
- Optimistic
In the field of relational database management systems, optimistic concurrency control is a concurrency control method that assumes that multiple transactions can complete without affecting each other, and that therefore transactions can proceed without locking the data resources that they affect...
- Delay the synchronization for a transaction until its end without blocking (read, write) operations, and then abort transactions that violate desired synchronization rules.
- Pessimistic - Block operations of transaction that would cause violation of synchronization rules.
Many methods for concurrency control exist. Major methods, which have each many variants, include:
- Two phase locking
In databases and transaction processing, Two-phase locking, is a concurrency control locking protocol, or mechanism, which guarantees serializability . It is also the name of the resulting class of transaction schedules...
- Conflict (serializability
In databases, transaction processing, and various transactional applications, both centralized and distributed, a transaction schedule is serializable, has the Serializability property, if its outcome is equal to the outcome of its transactions executed serially, i.e., sequentially without...
, precedenceA precedence graph, also named conflict graph and serializability graph, is used in the context of concurrency control in databases.The precedence graph for a schedule S contains:* A node for each committed transaction in S...
) graph checking
- Timestamp ordering
In computer science, in the field of databases, timestamp-based concurrency control is a non-lock concurrency control method, used in relational databases to safely handle transactions, using timestamps.-Assumptions:...
- Commitment ordering
- Multiversion concurrency control
Multiversion concurrency control , in the database field of computer science, is a concurrency control method commonly used by database management systems to provide concurrent access to the database....
- Index concurrency control
Index locking is a procedure in which running one task on a database table blocks all access by other tasks to the entire table. With index locking it may be necessary to lock the index build for a column, not just the data items themselves...
(for synchronizing indexes)
Almost all implemented concurrency control mechanisms, typically quite efficient, guarantee schedules that are conflict serializable, unless relaxed forms of
serializabilityIn databases, transaction processing, and various transactional applications, both centralized and distributed, a transaction schedule is serializable, has the Serializability property, if its outcome is equal to the outcome of its transactions executed serially, i.e., sequentially without...
are allowed (depending on application) for better performance.
Concurrency control in operating systems
Operating systems, especially
real-time operating systemA real-time operating system is a multitasking operating system intended for real-time applications. Such applications include embedded systems , industrial robots, spacecraft, industrial control , and scientific research equipment.A RTOS facilitates the creation of a real-time system, but does not...
s, need to maintain the illusion that many tasks are all running at the same time.
Such
multitaskingMultitasking may refer to any of the following:*Computer multitasking - the apparent simultaneous performance of two or more tasks by a computer's central processing unit...
is fairly simple when all tasks are independent from each other.
However, when several tasks try to use the same resource, or when tasks try to share information,
it can lead to confusion and inconsistency.
The task of
concurrent computingConcurrent computing is a form of computing in which programs are designed as collections of interacting computational processes that may be executed in parallel...
is to solve that problem.
Some solutions involve "locks" similar to the locks used in databases, but they risk causing problems of their own such as
deadlockA deadlock is a situation wherein two or more competing actions are waiting for the other to finish, and thus neither ever does. It is often seen in a paradox like the "chicken or the egg."...
.
Other solutions are lock-free and wait-free algorithms.
See also
- Mutual exclusion
Mutual exclusion algorithms are used in concurrent programming to avoid the simultaneous use of a common resource, such as a global variable, by pieces of computer code called critical sections. A critical section is a piece of code where a process or thread accesses a common resource...
- Isolation (computer science)
In database systems, isolation is a property that defines how/when the changes made by one operation become visible to other concurrent operations. Isolation is one of the ACID properties.-Isolation levels:...
- Serializability
In databases, transaction processing, and various transactional applications, both centralized and distributed, a transaction schedule is serializable, has the Serializability property, if its outcome is equal to the outcome of its transactions executed serially, i.e., sequentially without...
- Schedule
In the fields of databases and transaction processing, a schedule of a system is a list of actions ordered by time from a set of transactions that are executed together in the system...
- Multiversion concurrency control
Multiversion concurrency control , in the database field of computer science, is a concurrency control method commonly used by database management systems to provide concurrent access to the database....
- Global concurrency control
Global concurrency control typically pertains to the concurrency control of a system comprising several components, each with its own concurrency control. Global concurrency control is the concurrency control of the system as a whole....
- Concurrent programming
External links