Critical section

from Wikipedia, the free encyclopedia

In computer science , a serving critical section (, engl. Critical Section ') for identifying a collection of program instructions for the purpose of flow control. Only one process / thread may be present in it at a time , similar to a level crossing that can only be used by rail vehicles or only road vehicles, but not by both types of vehicle at the same time.

Critical sections consist of several individual statements, the intermediate results of which represent inconsistent states to which the other threads must not have access. The result of a critical section may only be visible to the outside as an indivisible unit .

This concept is required to ensure the consistency of the states of operating resources , e.g. data structures, connections, devices, etc., but also database contents. In the latter case, the concepts go into transaction processing .

Examples

Every two threads should increment the common variable s :
On the left, a critical section (outlined in orange) is interrupted and the result is incorrect.
The result on the right is correct because there is a maximum of one thread in the critical section at a time .

In the very simple example A , the frequency of entering the program section should be counted in the common variable counter . It is assumed here that access to zaehler is only possible by means of a read or a write operation, but not by an inherently indivisible incrementing operation (incrementing: increasing by one).

The program section is:

zaehler in lokale Variable lesen
lokale Variable um 1 erhöhen
lokale Variable in zaehler schreiben

This program section is now executed by two threads in a timed manner. The time interleaving is carried out by the operating system. By default, the threads have no influence on this. Both threads access , process and change the variable counter independently of each other :

Thread X Thread Y

1:

zaehler lesen

2:

  zaehler lesen

3:

um 1 erhöhen

4:

  um 1 erhöhen

5:

zaehler schreiben

6:

  zaehler schreiben

Before step 5, both threads read the same original value of the variable counter . The threads have this value as a private copy. In steps 3 and 4, both threads each add 1 to their private copy. In steps 5 and 6, the threads then save the new value from their private copies back to the variable counter . In the scenario described, it is thread Y whose write action is the last to be executed. It produces the wrong end result 1, which does not correspond to the task.

Example B : Example A is expanded to include a second critical section that now decrements the same variable counter and is therefore related to the first critical section. For reasons of consistency, a maximum of one thread can be in both critical sections at a time .

notation

In programming and modeling languages , the following directives are occasionally found:

  • Begin_CriticalSection
  • End_CriticalSection

or

  • EnterCriticalSection()
  • LeaveCriticalSection()

Feature and treatment of critical sections

If processes or threads are executed in parallel or in chronological order and if they use data (memory areas) or general resources (e.g. connections, devices) together, there are resources which by their nature may only be used exclusively: during the execution of a program section from a thread in which the resource is used in a changing manner, the resource must not be accessible to other threads. A program section in the program of a thread in which a resource that is shared but is to be used exclusively is accessed is a critical section.

It is important to prevent the execution of critical sections of parallel threads at different times, as this leads to unpredictable results or inconsistent states of the resources. However, it is not necessary to stipulate a strict sequence in which the equipment is used. It is sufficient to ensure mutual exclusion of accesses. When a thread is in a critical section with respect to a resource, no other thread is allowed to get into a critical section with respect to the same resource. This is achieved by any sequencing of the execution of critical sections of the accessing threads. This is a weaker requirement than the requirement for the execution of a critical section to be uninterruptible, which is often mentioned in connection with critical sections. If a critical section is executed with respect to an item of equipment, it must not be interrupted in favor of the execution of a critical section (with respect to the same, shared item of equipment) of another process.

The following requirements are made of a solution to the problem of the critical section:

  • Mutual exclusion : With regard to a resource, a maximum of one thread may be in a critical section at any one time.
  • Progress : A termination or pause of a process outside of a critical section must not affect the progress of the remaining processes.
  • Limited waiting time : No thread can be excluded from entering a critical section for any length of time.
  • The solution must not make any assumptions about the execution speed of the threads.

With the fulfillment of these requirements, the consistency of the equipment can be guaranteed. Furthermore, each thread comes into its critical section in a finite time and is not fundamentally prevented from entering its critical section.

See also

literature

  • Anderson, James H. and Kim, Yong-Jik and Herman, Ted: 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 .
  • Raynal, M. and Beeson, D .: Algorithms for mutual exclusion . MIT Press, Cambridge, MA, USA 1986, ISBN 0-262-18119-3 .

Individual evidence

  1. ^ Abraham Silberschatz, Peter B. Galvin, Greg Gagne: Operating system concepts . 7th edition. John Wiley & Sons , Hoboken (New Jersey) 2005, ISBN 0-471-69466-5 , 6.2 The Critical-Section Problem, pp. 194 (English).