Lock

Under a lock or locking ( English for lock or locks ) are understood in the computer science blocking access to a resource . Such a lock enables a process to have exclusive access to a resource, i. H. with the guarantee that no other process reads or changes this resource as long as the lock exists.

Locking is often used in process synchronization and in file and database systems to ensure atomic and consistent read and write requests.

Locking types

If a process wants exclusive access to a resource, it must request a lock from an administrative process (e.g. a locking manager). In order not to completely lock the requested resource, there are two basic types of locks:

Read lock

Has a resource a read lock ( "read lock", or shared lock , "shared lock"), one would like the process that has set this lock to read from the resource only. This means that other processes can also read this resource, but are not allowed to change it.

Write lock

A resource with write lock ("write lock", or also exclusive lock , "exclusive lock") prevents the resource from being read or written by other processes because the process that set the lock wants to change the resource. The method is also known as pessimistic locking , since it assumes that the data will usually be updated. When optimistic locking is assumed that is usually not updated or is updated simultaneously by two users is not likely. It is only checked when updating whether the status quo still applies.

Lock release

When the process that requested a lock is done, it must remove the lock again. Processes that could not access a resource due to a lock have to wait and are queued. There are several ways in which this queue is designed, e.g. B. priority-controlled, FIFO-controlled etc.

Starving

If a process does not remove a lock, other processes may wait indefinitely for this release. These processes “starve” (English starve ).

deadlock

Setting a lock can cause deadlocks , namely when two processes are waiting for each other to release the resource locked by the other.

Example: There is (as resources) a bicycle and a city map. Two bike couriers are supposed to deliver a package each and need a bike and a city map. Courier A can reserve the bike, courier B the city map. You are now in deadlock as both are waiting for each other's resource (endlessly).

Hierarchical locking

With hierarchical locking, resources are combined into larger logical units. It is now possible to lock the entire logical unit. This brings a gain in performance, since not all elements of the unit need to be locked and monitored separately. The right choice of the granularity of the logical units is of great importance.

Hierarchical locking is mainly used in database systems. It can e.g. B. a data field, a data record, a file, or the entire database can be locked. The best practice in each case depends on the type of database, the frequency of changes and the number of concurrent users.

Multi-locking

Multi-locking belongs to pessimistic locking and enables deadlock-free programming. With the MultiLock, the locks are reserved right at the beginning of the synchronization block and form a MultiLock. No deadlocks can occur with MultiLocks because a MultiLock is only started when all the required locks are available. New locks cannot be used while MultiLock is running. However, the individual locks belonging to the MultiLock can be released and used in other MultiLocks.

implementation

The central aspect of locks is the ability to make a process that cannot be “operated” at the moment wait until the lock is free - this corresponds to the function warte_bisthat will be used in the pseudocode below. There are basically two ways to wait for a condition:

The first possibility is implementation with the help of the process scheduler (i.e. the operating system or the runtime environment , see time sharing ): The scheduler knows the lock and does not allocate any computing time to the process until the lock is free. This is usually only possible if the lock mechanism is provided by the operating system (or the runtime environment), because only then can the scheduler know the lock and its current status. Alternatively, the runtime environment can also support a monitor concept in which this is implemented using the functions wait(on a condition variable ) and notify(ends wait on the condition variable) - the condition is then checked in a critical section of the monitor. The implementation of warte_biswould then be possible as follows:

Funktion warte_bis( Parameter bedingung ) {
   solange ( nicht bedingung ) wait(); // bei jedem notify wird die Bedingung erneut geprüft
}

This assumes that when the variable to which the condition relates is changed, it is always notifycalled so that the condition is checked again.

The second option is implementation as a spin lock: the process constantly checks in a loop whether the lock is free and only then continues. This is also possible without the support of the scheduler, but has the disadvantage that the process consumes computing time while it is waiting ( "active waiting" or "busy waiting" ). If the operating system (or the runtime environment) offers the possibility of letting a process "sleep" for a specified period of time ( sleep), this is not so unfavorable, as some computing time is only required at regular intervals to check the lock (one also speaks of slow busy waiting or lazy polling ). However, if the operating system does not offer this option, the process uses the full processing power of the system while it is waiting and thereby slows down other running processes . The implementation of warte_biswould be similar to the above with the possibility of sleeping, the only difference being that the condition is checked at regular intervals and not (only) when the relevant variables change:

Funktion warte_bis( Parameter bedingung ) {
   solange ( nicht bedingung ) sleep( 1 Sekunde ); // die Bedingung wird einmal pro Sekunde geprüft
}

Locking is easy to implement if there is an atomic instruction for the sequence “set the blocking if it is currently free” . If, on the other hand, a second process can also check between the check whether the lock is currently free and its occupancy, then both decide that the lock is to be set and now "belongs to them". The same applies in particular to multiple threads of a process.

example

Without locking (so-called *race condition* )
Process 1	Process 2
reads from resource
	reads from resource; changed data; writes on resource
changed data; writes on resource

The changes made by process 2 are thus overwritten by process 1 and are lost. Such errors are sometimes difficult to reproduce because they occur randomly.

With locking
Process 1	Process 2
Resource is reserved; reads from resource
	tries to read from resource; must wait ("lock engages")
changed data; writes to resource; Resource is released
	Resource is reserved; reads from resource; changed data; writes to resource; Resource is released

Both changes are included in the resource.

A clearer example could be an incorrectly implemented ATM:

Without locking
(credit account: 100 €)
Person 1	Person 2
reads account balance (100 €)
	reads balance (100 €); Withdraws € 100; writes new account balance (100 € -100 € = 0 €)
pays 50 €; writes new account balance (100 € + 50 € = 150 €)

New stand: € 150 wrong!

With locking
(credit account: 100 €)
Person 1	Person 2
Access to bank account is reserved; reads account balance (100 €)
	tries to read account balance; Lock engages, Person 2 has to wait.
pays 50 €; writes new account balance (100 € + 50 € = 150 €); Access to the bank account is released
	Lock free; Access to bank account is reserved; reads balance (150 €); withdraws € 100; writes new account balance (150 € -100 € = 50 €); Access to the bank account is released

New stand: 50 € correct!

literature

James H. Anderson, Yong-Jik Kim, Ted Herman: Shared-memory mutual exclusion: major research trends since 1986 . In: Distrib. Comput. tape 16 , no. 2-3 . Springer-Verlag, September 2003, ISSN 0178-2770 , p. 75-110 , doi : 10.1007 / s00446-003-0088-6 .
M. Raynal, D. Beeson: Algorithms for mutual exclusion . MIT Press, Cambridge MA 1986, ISBN 0-262-18119-3 .