Lock (computer science)
|
|
In computer science, 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 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.
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.
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:
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.
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.
One strategy is to avoid locks entirely by using lock-free programming techniques.