Critical section

Last updated

In concurrent programming, concurrent accesses to shared resources can lead to unexpected or erroneous behavior. Thus, the parts of the program where the shared resource is accessed need to be protected in ways that avoid the concurrent access. One way to do so is known as a critical section or critical region. This protected section cannot be entered by more than one process or thread at a time; others are suspended until the first leaves the critical section. Typically, the critical section accesses a shared resource, such as a data structure, peripheral device, or network connection, that would not operate correctly in the context of multiple concurrent accesses. [1]

Contents

Need for critical sections

Different codes or processes may consist of the same variable or other resources that must be read or written but whose results depend on the order in which the actions occur. For example, if a variable x is to be read by process A, and process B must write to the variable x at the same time, process A might get either the old or new value of x.

Flow graph depicting need for critical section Critical section fg.jpg
Flow graph depicting need for critical section

Process A:

// Process A..b=x+5;// instruction executes at time = Tx.

Process B:

// Process B..x=3+z;// instruction executes at time = Tx.

In cases where a locking mechanism with finer granularity is not needed, a critical section is important. In the above case, if A needs to read the updated value of x, executing process A, and process B at the same time may not give required results. To prevent this, variable x is protected by a critical section. First, B gets the access to the section. Once B finishes writing the value, A gets the access to the critical section, and variable x can be read.

By carefully controlling which variables are modified inside and outside the critical section, concurrent access to the shared variable are prevented. A critical section is typically used when a multi-threaded program must update multiple related variables without a separate thread making conflicting changes to that data. In a related situation, a critical section may be used to ensure that a shared resource, for example, a printer, can only be accessed by one process at a time.

Implementation of critical sections

The implementation of critical sections vary among different operating systems.

A critical section will usually terminate in finite time, [2] and a thread, task, or process must wait for a fixed time to enter it (bounded waiting). To ensure exclusive use of critical sections, some synchronization mechanism is required at the entry and exit of the program.

A critical section is a piece of a program that requires mutual exclusion of access.

Locks and critical sections in multiple threads Locks and critical sections.jpg
Locks and critical sections in multiple threads

As shown in the figure, [3] in the case of mutual exclusion (mutex), one thread blocks a critical section by using locking techniques when it needs to access the shared resource, and other threads must wait their turn to enter the section. This prevents conflicts when two or more threads share the same memory space and want to access a common resource. [2]

Pseudocode for implementing critical section Critical section pseudo code.png
Pseudocode for implementing critical section

The simplest method to prevent any change of processor control inside the critical section is implementing a semaphore. In uniprocessor systems, this can be done by disabling interrupts on entry into the critical section, avoiding system calls that can cause a context switch while inside the section, and restoring interrupts to their previous state on exit. With this implementation, any execution thread entering any critical section in the system will prevent any other thread, including an interrupt, from being granted processing time on the CPU until the original thread leaves its critical section.

This brute-force approach can be improved by using semaphores. To enter a critical section, a thread must obtain a semaphore, which it releases on leaving the section. Other threads are prevented from entering the critical section at the same time as the original thread, but are free to gain control of the CPU and execute other code, including other critical sections that are protected by different semaphores. Semaphore locking also has a time limit to prevent a deadlock condition in which a lock is acquired by a single process for an infinite time, stalling the other processes that need to use the shared resource protected by the critical section.

Uses of critical sections

Kernel-level critical sections

Typically, critical sections prevent thread and process migration between processors and the preemption of processes and threads by interrupts and other processes and threads.

Critical sections often allow nesting. Nesting allows multiple critical sections to be entered and exited at little cost.

If the scheduler interrupts the current process or thread in a critical section, the scheduler will either allow the currently executing process or thread to run to completion of the critical section, or it will schedule the process or thread for another complete quantum. The scheduler will not migrate the process or thread to another processor, and it will not schedule another process or thread to run while the current process or thread is in a critical section.

Similarly, if an interrupt occurs in a critical section, the interrupt information is recorded for future processing, and execution is returned to the process or thread in the critical section. [4] Once the critical section is exited, and in some cases the scheduled quantum completed, the pending interrupt will be executed. The concept of scheduling quantum applies to "round-robin" and similar scheduling policies.

Since critical sections may execute only on the processor on which they are entered, synchronization is only required within the executing processor. This allows critical sections to be entered and exited at almost no cost. No inter-processor synchronization is required. Only instruction stream synchronization is needed. [5] Most processors provide the required amount of synchronization by interrupting the current execution state. This allows critical sections in most cases to be nothing more than a per processor count of critical sections entered.

Performance enhancements include executing pending interrupts at the exit of all critical sections and allowing the scheduler to run at the exit of all critical sections. Furthermore, pending interrupts may be transferred to other processors for execution.

Critical sections should not be used as a long-lasting locking primitive. Critical sections should be kept short enough so they can be entered, executed, and exited without any interrupts occurring from the hardware and the scheduler.

Kernel-level critical sections are the base of the software lockout issue.

Critical sections in data structures

In parallel programming, the code is divided into threads. The read-write conflicting variables are split between threads and each thread has a copy of them. Data structures such as linked lists, trees, and hash tables have data variables that are linked and cannot be split between threads; hence, implementing parallelism is very difficult. [6] To improve the efficiency of implementing data structures, multiple operations such as insertion, deletion, and search can be executed in parallel. While performing these operations, there may be scenarios where the same element is being searched by one thread and is being deleted by another. In such cases, the output may be erroneous. The thread searching the element may have a hit, whereas the other thread may subsequently delete it. These scenarios will cause issues in the program running by providing false data. To prevent this, one method is to keep the entire data structure under critical section so that only one operation is handled at a time. Another method is locking the node in use under critical section, so that other operations do not use the same node. Using critical section, thus, ensures that the code provides expected outputs. [6]

Critical sections in relation to peripherals

Critical sections also occur in code which manipulates external peripherals, such as I/O devices. The registers of a peripheral must be programmed with certain values in a certain sequence. If two or more processes control a device simultaneously, neither process will have the device in the state it requires and incorrect behavior will ensue.

When a complex unit of information must be produced on an output device by issuing multiple output operations, exclusive access is required so that another process does not corrupt the datum by interleaving its own bits of output.

In the input direction, exclusive access is required when reading a complex datum via multiple separate input operations. This prevents another process from consuming some of the pieces, causing corruption.

Storage devices provide a form of memory. The concept of critical sections is equally relevant to storage devices as to shared data structures in main memory. A process which performs multiple access or update operations on a file is executing a critical section that must be guarded with an appropriate file locking mechanism.

See also

Related Research Articles

A real-time operating system (RTOS) is an operating system (OS) for real-time computing applications that processes data and events that have critically defined time constraints. An RTOS is distinct from a time-sharing operating system, such as Unix, which manages the sharing of system resources with a scheduler, data buffers, or fixed task prioritization in a multitasking or multiprogramming environments. Processing time requirements need to be fully understood and bound rather than just kept as a minimum. All processing must occur within the defined constraints. Real-time operating systems are event-driven and preemptive, meaning the OS can monitor the relevant priority of competing tasks, and make changes to the task priority. Event-driven systems switch between tasks based on their priorities, while time-sharing systems switch the task based on clock interrupts.

<span class="mw-page-title-main">Mutual exclusion</span> In computing, restricting data to be accessible by one thread at a time

In computer science, mutual exclusion is a property of concurrency control, which is instituted for the purpose of preventing race conditions. It is the requirement that one thread of execution never enters a critical section while a concurrent thread of execution is already accessing said critical section, which refers to an interval of time during which a thread of execution accesses a shared resource or shared memory.

<span class="mw-page-title-main">Thread (computing)</span> Smallest sequence of programmed instructions that can be managed independently by a scheduler

In computer science, a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system. In many cases, a thread is a component of a process.

Thread safety is a computer programming concept applicable to multi-threaded code. Thread-safe code only manipulates shared data structures in a manner that ensures that all threads behave properly and fulfill their design specifications without unintended interaction. There are various strategies for making thread-safe data structures.

<span class="mw-page-title-main">Semaphore (programming)</span> Variable used in a concurrent system

In computer science, a semaphore is a variable or abstract data type used to control access to a common resource by multiple threads and avoid critical section problems in a concurrent system such as a multitasking operating system. Semaphores are a type of synchronization primitive. A trivial semaphore is a plain variable that is changed depending on programmer-defined conditions.

In computer science, a lock or mutex is a synchronization primitive that prevents state from being modified or accessed by multiple threads of execution at once. Locks enforce mutual exclusion concurrency control policies, and with a variety of possible methods there exist multiple unique implementations for different applications.

Peterson's algorithm is a concurrent programming algorithm for mutual exclusion that allows two or more processes to share a single-use resource without conflict, using only shared memory for communication. It was formulated by Gary L. Peterson in 1981. While Peterson's original formulation worked with only two processes, the algorithm can be generalized for more than two.

In computer science, an algorithm is called non-blocking if failure or suspension of any thread cannot cause failure or suspension of another thread; for some operations, these algorithms provide a useful alternative to traditional blocking implementations. A non-blocking algorithm is lock-free if there is guaranteed system-wide progress, and wait-free if there is also guaranteed per-thread progress. "Non-blocking" was used as a synonym for "lock-free" in the literature until the introduction of obstruction-freedom in 2003.

Release consistency is one of the synchronization-based consistency models used in concurrent programming.

In computing, a memory barrier, also known as a membar, memory fence or fence instruction, is a type of barrier instruction that causes a central processing unit (CPU) or compiler to enforce an ordering constraint on memory operations issued before and after the barrier instruction. This typically means that operations issued prior to the barrier are guaranteed to be performed before operations issued after the barrier.

<span class="mw-page-title-main">Linearizability</span> Property of some operation(s) in concurrent programming

In concurrent programming, an operation is linearizable if it consists of an ordered list of invocation and response events, that may be extended by adding response events such that:

  1. The extended list can be re-expressed as a sequential history.
  2. That sequential history is a subset of the original unextended list.

In concurrent programming, a monitor is a synchronization construct that prevents threads from concurrently accessing a shared object's state and allows them to wait for the state to change. They provide a mechanism for threads to temporarily give up exclusive access in order to wait for some condition to be met, before regaining exclusive access and resuming their task. A monitor consists of a mutex (lock) and at least one condition variable. A condition variable is explicitly 'signalled' when the object's state is modified, temporarily passing the mutex to another thread 'waiting' on the conditional variable.

In computer science, a ticket lock is a synchronization mechanism, or locking algorithm, that is a type of spinlock that uses "tickets" to control which thread of execution is allowed to enter a critical section.

In computer science, the fetch-and-add (FAA) CPU instruction atomically increments the contents of a memory location by a specified value.

Lamport's bakery algorithm is a computer algorithm devised by computer scientist Leslie Lamport, as part of his long study of the formal correctness of concurrent systems, which is intended to improve the safety in the usage of shared resources among multiple threads by means of mutual exclusion.

Concurrent computing is a form of computing in which several computations are executed concurrently—during overlapping time periods—instead of sequentially—with one completing before the next starts.

In computer science, the readers–writers problems are examples of a common computing problem in concurrency. There are at least three variations of the problems, which deal with situations in which many concurrent threads of execution try to access the same shared resource at one time.

In computer science, synchronization is the task of coordinating multiple of processes to join up or handshake at a certain point, in order to reach an agreement or commit to a certain sequence of action.

The Java programming language and the Java virtual machine (JVM) is designed to support concurrent programming. All execution takes place in the context of threads. Objects and resources can be accessed by many separate threads. Each thread has its own path of execution, but can potentially access any object in the program. The programmer must ensure read and write access to objects is properly coordinated between threads. Thread synchronization ensures that objects are modified by only one thread at a time and prevents threads from accessing partially updated objects during modification by another thread. The Java language has built-in constructs to support this coordination.

This page is a glossary of Operating systems terminology.

References

  1. ↑ Raynal, Michel (2012). Concurrent Programming: Algorithms, Principles, and Foundations. Springer Science & Business Media. p. 9. ISBN   978-3642320279.
  2. 1 2 Jones, M. Tim (2008). GNU/Linux Application Programming (2nd ed.). [Hingham, Mass.] Charles River Media. p. 264. ISBN   978-1-58450-568-6.
  3. ↑ Chen, Stenstrom, Guancheng, Per (Nov 10–16, 2012). "Critical lock analysis: Diagnosing critical section bottlenecks in multithreaded applications". 2012 International Conference for High Performance Computing, Networking, Storage and Analysis. pp. 1–11. doi:10.1109/sc.2012.40. ISBN   978-1-4673-0805-2. S2CID   12519578.{{cite book}}: CS1 maint: multiple names: authors list (link)
  4. ↑ "RESEARCH PAPER ON SOFTWARE SOLUTION OF CRITICAL SECTION PROBLEM". International Journal of Advance Technology & Engineering Research (IJATER). 1. November 2011.
  5. ↑ Dubois, Scheurich, Michel, Christoph (1988). "Synchronization, Coherence, and Event Ordering in Multiprocessors". Survey and Tutorial Series. 21 (2): 9–21. doi:10.1109/2.15. S2CID   1749330.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  6. 1 2 Solihin, Yan (17 November 2015). Fundamentals of Parallel Multicore Architecture. Taylor & Francis. ISBN   9781482211184.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.