|
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...
In computer science, especially parallel computing, synchronization means the coordination of simultaneous threads or processes to complete a task in order to get correct runtime order and avoid unexpected race conditions. ...
Many programming languages, operating systems, and other software development environments support what are called threads of execution. ...
In computer science -- more specifically, in the field of databases -- concurrency control is a method used to ensure that database transactions are executed in a safe manner (i. ...
Types
Generally, locks are advisory locks, where each thread cooperates by acquiring the lock before accessing the corresponding data. Some systems also implement mandatory locks, where attempting unauthorized access to a locked resource will force an exception in the entity attempting to make the access. Exception handling is a programming language construct or computer hardware mechanism designed to handle the occurrence of some condition that changes the normal flow of execution. ...
A (binary) semaphore is the simplest type of lock. No distinction is made between shared (read only) or exclusive (read and write) modes. Other schemes provide for a shared mode, where several threads can acquire a shared lock for read-only access to the data. Other modes such as shared, exclusive, intend-to-exclude and intend-to-upgrade are also widely implemented. A semaphore is a protected variable (or abstract data type) and constitutes the classic method for restricting access to shared resources (e. ...
Independent of the type of lock chosen above, locks can be classified by what happens when the lock strategy prevents progress of a thread. Most locking designs block the execution of the process requesting the lock until it is allowed to access the locked resource. A spinlock is a lock where the thread simply waits ("spins") until the lock becomes available. It is very efficient if threads are only likely to be blocked for a short period of time, as it avoids the overhead of operating system process re-scheduling. It is wasteful if the lock is held for a long period of time. In computing, a process is a running instance of a program, including all variables and other states. ...
In software engineering, a spinlock is a lock where the thread simply waits in a loop (spins) repeatedly checking until the lock becomes available. ...
Implementation Locks typically require hardware support for efficient implementation. This usually takes the form of one or more atomic instructions such as "test-and-set", "fetch-and-add" or "compare-and-swap". These instructions allow a single process to test if the lock is free, and if free, acquire the lock in a single atomic operation. ...
It has been suggested that this article or section be merged into Compare-and-swap. ...
In computer science, the fetch-and-add CPU instruction is a special instruction that atomically tests and modifies the contents of a memory location. ...
In computer science, the compare-and-swap CPU instruction is a special instruction that atomically compares the contents of a memory location to a given value and, if they are the same, modifies the contents of that memory location to a given new value. ...
Uniprocessor architectures have the option of using uninterruptable sequences of instructions, using special instructions or instruction prefixes to disable interrupts temporarily, but this technique does not work for multiprocessor shared-memory machines. Proper support for locks in a multiprocessor environment can require quite complex hardware and/or software support, with substantial synchronization issues. A uniprocessor system refers to a system with a single processor. ...
Multiprocessing is traditionally known as the use of multiple concurrent processes in a system as opposed to a single process at any one instant. ...
Synchronization is a problem in timekeeping which requires the coordination of events to operate a system in unison. ...
The reason an atomic operation is required is because of concurrency, where more than one task executes the same logic. For example, consider the following C code: C is a general-purpose, procedural, imperative computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system. ...
if (lock == 0) lock = myPID; /* lock free - set it */ The above example does not guarantee that the task has the lock, since more than one task can be testing the lock at the same time. Since both tasks will detect that the lock is free, both tasks will attempt to set the lock, not knowing that the other task is also setting the lock. Dekker's or Peterson's algorithm are possible substitutes if atomic locking operations are not available. Dekkers algorithm is a concurrent programming algorithm for mutual exclusion that allows two processes to share a single-use resource without conflict, using only shared memory for communication. ...
Petersons algorithm is a concurrent programming algorithm for mutual exclusion that allows just two processes to share a single-use resource without conflict, using only shared memory for communication. ...
Careless use of locks can result in deadlock. This occurs when a process holds a lock and then attempts to acquire a second lock. If the second lock is already held by another process, the first process will be blocked. If the second process then attempts to acquire the lock held by the first process, the system has "deadlocked": no progress will ever be made. A number of strategies can be used to avoid or recover from deadlocks, both at design-time and at run-time. It has been suggested that Circular wait be merged into this article or section. ...
Granularity Before introducing lock granularity, one needs to understand three concepts about locks. - lock overhead: The extra resources for using locks, like the memory space allocated for locks, the CPU time to initialize and destroy locks, and the time for acquiring or releasing locks. The more locks a program uses, the more overhead associated with the usage.
- lock contention: This occurs whenever one process or thread attempts to acquire a lock held by another process or thread. The more granular the available locks, the less likely one process/thread will request a lock held by the other. (For example, locking a row rather than the entire table, or locking a cell rather than the entire row.)
- deadlock: The situation when two tasks that are waiting on locks, each holding a lock that the other is waiting for. Unless something is done, the two tasks will wait forever.
So there is a tradeoff between decreasing lock overhead and decreasing lock contention when choosing the number of locks in synchronization.
An important property of a lock is its granularity. The granularity is a measure of the amount of data the lock is protecting. In general, choosing a coarse granularity (a small number of locks, each protecting a large segment of data) results in less lock overhead when a single process is accessing the protected data, but worse performance when multiple processes are running concurrently. This is because of increased lock contention the more coarse the lock, the higher the likelihood that the lock will stop an unrelated process from proceeding. Conversely, using a fine granularity (a larger number of locks, each protecting a fairly small amount of data) increases the overhead of the locks themselves but reduces lock contention. More locks also increase the risk of deadlock.
In a database management system, for example, a lock could protect, in order of increasing granularity, a record, a data page, or an entire table. Coarse granularity, such as using table locks, tends to give the best performance for a single user, whereas fine granularity, such as record locks, tends to give the best performance for multiple users. A database management system (DBMS) is a system or software designed to manage a database, and run operations on the data requested by numerous clients. ...
Database locks In databases, locks can be used as a means of ensuring transaction synchronicity. i.e. when making transaction processing concurrent (interleaving transactions), using 2-phased locks ensures that the concurrent execution of the transaction turns out equivalent to some serial ordering of the transaction. However, deadlocks become an unfortunate side-effect of locking in databases. Deadlocks are either prevented by pre-determining the locking order between transactions or are detected using waits-for graphs. An alternate to locking for database synchronicity while avoiding deadlocks involves the use of totally ordered global timestamps.
The problems with locks Lock-based resource protection and thread/process synchronization has many disadvantages: - It is a blocking method, which means the thread/process has to wait until a lock held by others is released.
- Using locks is a conservative approach because each thread has to acquire the lock whenever there is a possibility of access conflict, which is actually rare in real execution. A conservative approach usually induces unnecessary overhead.
- Locks are vulnerable to failures and faults. If one thread holding a lock dies, other threads waiting for the lock may wait forever.
- Programming using locks is error-prone, like the notorious deadlock.
- Using locks does not scale with problem size and complexity.
- Have to balance the granularity of locked data against the costs of fine-grain locks.
- locks are not composable. For example, deleting Item X of Table A and inserting X into Table B cannot be combined as one single atomic operations using locks.
- Priority inversion. High priority threads/processes cannot proceed if a low priority thread/process is holding the common lock.
- Convoying. All other threads have to wait if a thread holding a lock is descheduled due to a time-slice interrupt or page fault (See lock convoy)
- Hard to debug: Bugs associated with locks are time dependent. They are extremely hard to repeat.
One strategy is to avoid locks entirely by using non-blocking synchronization methods, like lock-free programming techniques and transactional memory. It has been suggested that Circular wait be merged into this article or section. ...
In computer science, a lock convoy is a type of problem that can arise in certain uses of locks for concurrency control. ...
In contrast to algorithms that protect access to shared data with locks, lock-free and wait-free algorithms are specially designed to allow multiple threads to read and write shared data concurrently without corrupting it. ...
In computer science, software transactional memory (STM) is a concurrency control mechanism analogous to database transactions for controlling access to shared memory in concurrent computing. ...
The lock keyword In the C# programming language, the lock keyword can be used to ensure that a block of code runs to completion without interruption by other threads, similar to the Java keyword synchronized. For more information, see Barrier (computer science). The title given to this article is incorrect due to technical limitations. ...
Java refers to a number of computer software products and specifications from Sun Microsystems (the Javaâ„¢ technology) that together provide a system for developing and deploying cross-platform applications. ...
In parallel computing, a barrier is a type of synchronization method. ...
See also |
Feeds |
Contact