Lock (computer science)

In computer science, a lock or mutex (from mutual exclusion) is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. A lock is designed to enforce a mutual exclusion concurrency control policy.

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.

The simplest type of lock is a binary semaphore. It provides exclusive access to the locked data. Other schemes also provide shared access for reading data. Other widely implemented access modes are exclusive, intend-to-exclude and intend-to-upgrade.

Another way to classify locks is by what happens when the lock strategy prevents progress of a thread. Most locking designs block the execution of the thread requesting the lock until it is allowed to access the locked resource. With a spinlock, the thread simply waits ("spins") until the lock becomes available. This is efficient if threads are blocked for a short time, because it avoids the overhead of operating system process re-scheduling. It is inefficient if the lock is held for a long time, or if the progress of the thread that is holding the lock depends on preemption of the locked thread.

Locks typically require hardware support for efficient implementation. This support 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.

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 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 free, set it
    lock = myPID;
}

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.

Careless use of locks can result in deadlock or livelock. A number of strategies can be used to avoid or recover from deadlocks or livelocks, both at design-time and at run-time. (The most common strategy is to standardize the lock acquisition sequences so that combinations of inter-dependent locks are always acquired in a specifically defined "cascade" order.)

Some languages do support locks syntactically. An example in C# follows:

class Account {    // this is a monitor of an account
    long val = 0;
    object thisLock = new object();
    public void deposit(const long x) {
        lock(thisLock) {    // only one thread at a time may execute this statement
            val += x;
        }
    }
    public void withdraw(const long x) {
        lock(thisLock) {    // only one thread at a time may execute this statement
            val -= x;
        }
    }
}

The code lock(this) is a problem if the instance can be accessed publicly.[1]

Similar to Java, C# can also synchronize entire methods, by using the MethodImplOptions.Synchronized attribute.[2][3]

[MethodImpl(MethodImplOptions.Synchronized)]
public void someMethod() {
    // do stuff
}

Granularity

Before being introduced to lock granularity, one needs to understand three concepts about locks:

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. Granular locking where each process must hold multiple locks from a common set of locks can create subtle lock dependencies. This subtlety can increase the chance that a programmer will unknowingly introduce a deadlock.

In a database management system, for example, a lock could protect, in order of decreasing granularity, part of a field, a field, 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.

Database locks

Main article: Lock (database)

Database 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.

There are mechanisms employed to manage the actions of multiple concurrent users on a database—the purpose is to prevent lost updates and dirty reads. The two types of locking are pessimistic locking and optimistic locking:

Where to use pessimistic locking: this is mainly used in environments where data-contention (the degree of users request to the database system at any one time) is heavy; where the cost of protecting data through locks is less than the cost of rolling back transactions, if concurrency conflicts occur. Pessimistic concurrency is best implemented when lock times will be short, as in programmatic processing of records. Pessimistic concurrency requires a persistent connection to the database and is not a scalable option when users are interacting with data, because records might be locked for relatively large periods of time. It is not appropriate for use in Web application development.
Where to use optimistic locking: this is appropriate in environments where there is low contention for data, or where read-only access to data is required. Optimistic concurrency is used extensively in .NET to address the needs of mobile and disconnected applications,[4] where locking data rows for prolonged periods of time would be infeasible. Also, maintaining record locks requires a persistent connection to the database server, which is not possible in disconnected applications.

Disadvantages

Lock-based resource protection and thread/process synchronization have many disadvantages:

Some concurrency control strategies avoid some or all of these problems. For example, a funnel or serializing tokens can avoid the biggest problem: deadlocks. Alternatives to locking include non-blocking synchronization methods, like lock-free programming techniques and transactional memory. However, such alternative methods often require that the actual lock mechanisms be implemented at a more fundamental level of the operating software. Therefore, they may only relieve the application level from the details of implementing locks, with the problems listed above still needing to be dealt with beneath the application.

In most cases, proper locking depends on the CPU providing a method of atomic instruction stream synchronization (for example, the addition or deletion of an item into a pipeline requires that all contemporaneous operations needing to add or delete other items in the pipe be suspended during the manipulation of the memory content required to add or delete the specific item). Therefore, an application can often be more robust when it recognizes the burdens it places upon an operating system and is capable of graciously recognizing the reporting of impossible demands.

Lack of composability

One of lock-based programming's biggest problems is that "locks don't compose": it is hard to combine small, correct lock-based modules into equally correct larger programs without modifying the modules or at least knowing about their internals. Simon Peyton Jones (an advocate of software transactional memory) gives the following example of a banking application:[5] design a class Account that allows multiple concurrent clients to deposit or withdraw money to an account, and to transfer money from one account to another. The lock-based solution to the first part of the problem is:

class Account:
    member balance : Integer
    member mutex : Lock
    method deposit(n : Integer)
           mutex.lock()
           balance ← balance + n
           mutex.unlock()
    method withdraw(n : Integer)
           deposit(−n)

A transfer routine that is correct for sequential programs can now be written

function transfer(from : Account, to : Account, amount : integer)
    from.withdraw(amount)
    to.deposit(amount)

In a concurrent program, this algorithm is incorrect because when one thread is half-way through transfer, another might observe a state where amount has been withdrawn from the first account, but not yet deposited into the other account: money has gone missing from the system. This problem can only be fixed completely by taking locks on both account prior to changing any of the two accounts, but then the locks have to be taken according to some arbitrary, global ordering to prevent deadlock:

function transfer(from : Account, to : Account, amount : integer)
    if from < to    // arbitrary ordering on the locks
        from.lock()
        to.lock()
    else
        to.lock()
        from.lock()
    from.withdraw(amount)
    to.deposit(amount)
    from.unlock()
    to.unlock()

This solution gets more complicated when more locks are involved, and the transfer function needs to know about all of the locks, so they cannot be hidden.

Language support

Programming languages vary in their support for synchronization:

See also

References

  1. "lock Statement (C# Reference)".
  2. "ThreadPoolPriority, and MethodImplAttribute". http://msdn.microsoft.com/en-us/magazine/cc163896.aspx: MSDN. p. ??. Retrieved 2011-11-22.
  3. "C# From a Java Developer's Perspective". http://www.25hoursaday.com/CsharpVsJava.html#attributes. Retrieved 2011-11-22.
  4. "Designing Data Tier Components and Passing Data Through Tiers". Microsoft. August 2002. Retrieved 2008-05-30.
  5. Peyton Jones, Simon (2007). "Beautiful concurrency" (PDF). In Wilson, Greg; Oram, Andy. Beautiful Code: Leading Programmers Explain How They Think. O'Reilly.
  6. Marshall, Dave (March 1999). "Mutual Exclusion Locks". Retrieved 2008-05-30.
  7. "Synchronize". msdn.microsoft.com. Retrieved 2008-05-30.
  8. "Apple Threading Reference". Apple, inc. Retrieved 2009-10-17.
  9. "NSLock Reference". Apple, inc. Retrieved 2009-10-17.
  10. "NSRecursiveLock Reference". Apple, inc. Retrieved 2009-10-17.
  11. "NSConditionLock Reference". Apple, inc. Retrieved 2009-10-17.
  12. "NSLocking Protocol Reference". Apple, inc. Retrieved 2009-10-17.
  13. "Synchronization". Sun Microsystems. Retrieved 2008-05-30.
  14. Lundh, Fredrik (July 2007). "Thread Synchronization Mechanisms in Python". Retrieved 2008-05-30.
  15. "Programming Ruby: Threads and Processes". 2001. Retrieved 2008-05-30.
  16. ISO/IEC 8652:2007. "Protected Units and Protected Objects". Ada 2005 Reference Manual. Retrieved 2010-02-27. A protected object provides coordinated access to shared data, through calls on its visible protected operations, which can be protected subprograms or protected entries.
  17. ISO/IEC 8652:2007. "Example of Tasking and Synchronization". Ada 2005 Reference Manual. Retrieved 2010-02-27.

External links

This article is issued from Wikipedia - version of the Saturday, April 16, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.