Critical code section

A critical code section is a piece of software that must be executed atomically to preserve data integrity, hardware integrity, and access serialization.

The ability of code to work properly when two or more threads that use a certain resource are executing at the same time is referred to as concurrency; see ``Concurrency''.

Critical code sections include all of the following:

• Data structure access.

• Most manipulation of linked lists.

• Code that increments a counter. For example, consider the following:

     i = i + 1
  

  If i is initially set to zero and two processes both execute this code, the value of i should be incremented to 2. If Process A executes the code and then Process B does, the result will be correct. However, if A executed and, during the increment instruction, process B also executed the same code, i would only be incremented to 1.

• Multiple-bit-flag words where only one operation will be completed if manipulated by multiple processors. For example, there are two assignments as follows:

     flag |= 1;
  

  and

     flag &= ~2;
  

  Each assignment is being executed by a different processor; although both operations will be completed, it is likely that only one will have an effect. It is similar to the situation in which two users are using vi to edit the same file at the same time; when the edited files are saved, only the changes made by one of the users will be recorded.
  

• Functions that block a driver such as SV_WAIT(D3) or sleep(D3) and sleep(D3oddi) and functions that unblock a driver such as SV_SIGNAL(D3) SV_BROADCAST(D3), or wakeup(D3) and wakeup(D3oddi) need to be protected to avoid a situation in which the unblocking call could be executed before the blocking call and perform a context switch.

• Any instance of inb(D3) and outb(D3) (or inb(D3oddi) and outb(D3oddi)) functions.

On uniprocessor systems, kernel context preemption points are standardized and well-defined; calling spl(D3) or spl(D3oddi) to prevent interrupts from being serviced while a critical region executes is adequate. Multiprocessor systems require more sophisticated mechanisms to protect critical code than uniprocessing systems.

On a multiprocessor system, multiple requestor-level or process-level contexts may be executing on different processors at any given time, and the kernel is completely preemptable so executing driver code can be preempted under most circumstances, unless it is holding a lock. spl( ) only prevents interrupts from being serviced on the processor where the code is executed; the interrupt may be serviced (handler executed) on another processor.

Timeout routines are also inadequate for protecting critical code on multiprocessors because the actual execution of all callback routines is not only asynchronous but also could be executed on any processor. The only way to protect any driver code is to use locks to fulfill this need; see ``Synchronization primitives''. Acquiring locks guarantees serialized access to critical regions of code and protects the calling contexts from being preempted in favor of another context, until the lock is dropped.

To be precise, locks do not protect critical regions of code, but rather protect critical data structures during simultaneous access by multiple contexts executing the same code at the same time. Not all data structures are critical, and multiple reads of an otherwise critical data structure would not require protection, but simultaneous reads and writes would. Furthermore, critical data structures are not critical under all circumstances. For example, access to data structures in the initialization context does not need to be protected because only one context can access the data structure at that time.

Locks are used in a number of situations to protect critical data structures. Some common situations for which locks are appropriate are:

• Preventing lost updates, where different contexts test and update/increment global variables

• Avoiding inaccurate pointers, when multiple contexts try to manipulate global queues simultaneously

• Presenting a consistent view of global data structures, when different contexts update several elements of a data structure, and the total picture is a function of values of different elements taken together.