Lock (computer science)
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.
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.
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.
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.
Locks require hardware support for safe implementation.
This is usually provided by a special "atomic" instruction such as "test-and-set" or "fetch-and-add" or "compare-and-swap". Uniprocessor architectures have the option of using uninterruptable sequences of instructions, using special instructions or instruction prefixes to "disable interrupts" temporarily -- but that won't 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.
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.
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 is less overhead when a single process is accessing the protected data, but a 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 granular 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.
One strategy is to avoid locks entirely by using lock-free (non-blocking) programming techniques.
See also
