|
In software engineering, a lock is a 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. Software engineering (SE) is the profession concerned with creating and maintaining software applications by applying technologies and practices from computer science, project management, engineering, application domains, and other fields. ...
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. ...
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 mechanism designed to handle runtime errors or other problems (exceptions) inside a computer program. ...
A 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 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. Process (lat. ...
(disputed — see talk page) busy waiting is now its own page. ...
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 if free, and if free, acquire the lock in a single atomic operation. ...
In computer science, the test-and-set CPU instruction is a special instruction that atomically tests and modifies the contents of a memory location. ...
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. 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 coordination with respect to time. ...
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: The C Programming Language, Brian Kernighan and Dennis Ritchie, the original edition that served for many years as an informal specification of the language The C programming language is a standardized programming language developed in the early 1970s by Ken Thompson and Dennis Ritchie for use on the UNIX operating...
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.
If atomic locking operations are not available, locks can be implemented by attempting to set the lock, waiting a brief time, and then testing to determine if you actually got the lock. The following C code illustrates this technique:
while (1) { /* loop until lock is obtained */ if (lock == 0) { /* lock not set */ lock = myPID; /* set lock with my process ID */ sleep(1); /* wait for a short time */ if (lock == myPID) break; /* we still have the lock */ } /* we still don't have the lock */ sleep(someTime); /* wait for some period of time */ } In the above example, if two (or more) tasks test the lock at the same time and find it not set, they will all set the lock to their process ID (or some other unique ID). However, only the last task will actually have the lock set. By waiting a short time, and then checking the lock again, the task can determine if they managed to set the lock, or if some other task beat them to it.
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. A deadlock is a situation wherein two or more competing actions are waiting for the other to finish, so neither ever does. ...
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 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 proceding. 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 computer program (or more typically, a suite of them) designed to manage a database, a large set of structured data, and run operations on the data requested by numerous users. ...
One strategy is to avoid locks entirely by using lock-free programming techniques. 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. ...
See also
| 
Feeds |
Contact