multiprocessor Multiprocessing is the use of two or more central processing units (CPUs) within a single computer system. The term also refers to the ability of a system to support more than one processor or the ability to allocate tasks between them. There ar ...

computer systems, software lockout is the issue of performance degradation due to the idle wait times spent by the CPUs in

kernel Kernel may refer to: Computing * Kernel (operating system), the central component of most operating systems * Kernel (image processing), a matrix used for image convolution * Compute kernel, in GPGPU programming * Kernel method, in machine learn ...

-level

critical section In concurrent programming, concurrent accesses to shared resources can lead to unexpected or erroneous behavior, so parts of the program where the shared resource is accessed need to be protected in ways that avoid the concurrent access. One way to ...

s. Software lockout is the major cause of

scalability Scalability is the property of a system to handle a growing amount of work by adding resources to the system. In an economic context, a scalable business model implies that a company can increase sales given increased resources. For example, a ...

degradation in a multiprocessor system, posing a limit on the maximum useful number of processors. To mitigate the phenomenon, the kernel must be designed to have its

s as short as possible, therefore decomposing each data structure in smaller substructures.

Kernel-level critical sections

In most multiprocessor systems, each processor schedules and controls itself, therefore there's no "supervisor" processor, and kernel data structures are globally shared; sections of code that access those shared data structures are

s. This design choice is made to improve scaling, reliability and modularity. Examples of such kernel data structure are ready list and

communication channel A communication channel refers either to a physical transmission medium such as a wire, or to a logical connection over a multiplexed medium such as a radio channel in telecommunications and computer networking. A channel is used for informa ...

s. A "conflict" happens when more than one

processor Processor may refer to: Computing Hardware * Processor (computing) **Central processing unit (CPU), the hardware within a computer that executes a program *** Microprocessor, a central processing unit contained on a single integrated circuit (I ...

is trying to access the same resource (a memory portion) at the same time. To prevent critical races and inconsistency, only one processor ( CPU) at a given time is allowed to access a particular data structure (a memory portion), while other CPUs trying to access at the same time are locked-out, waiting in idle status.Madnick 1968, p.19 Three cases can be distinguished when this idle wait is either necessary, convenient, or not convenient. The idle wait is necessary when the access is to a ready list for a low level

scheduling A schedule or a timetable, as a basic time-management tool, consists of a list of times at which possible tasks, events, or actions are intended to take place, or of a sequence of events in the chronological order in which such things are ...

operation. The idle wait is not necessary but convenient in the case of a critical section for synchronization/ IPC operations, which require less time than a context switch (executing another

process A process is a series or set of activities that interact to produce a result; it may occur once-only or be recurrent or periodic. Things called a process include: Business and management *Business process, activities that produce a specific se ...

to avoid idle wait). Idle wait is instead not convenient in case of a kernel critical section for device management, present in

monolithic kernel A monolithic kernel is an operating system architecture where the entire operating system is working in kernel space. The monolithic model differs from other operating system architectures (such as the microkernel architecture) in that it alone ...

s only. A

microkernel In computer science, a microkernel (often abbreviated as μ-kernel) is the near-minimum amount of software that can provide the mechanisms needed to implement an operating system (OS). These mechanisms include low-level address space management, ...

instead falls on just the first two of the above cases. In a multiprocessor system, most of the conflicts are

-level conflicts, due to the access to the kernel level critical sections, and thus the idle wait periods generated by them have a major impact in performance degradation. This idle wait time increases the average number of idle processors and thus decreases

and relative efficiency.

Analytical studies

Taking as parameters the average time interval spent by a

in kernel level critical sections (''L'', for time in locked state), and the average time interval spent by a processor in tasks outside critical sections (''E''), the ratio ''L/E'' is crucial in evaluating software lockout. Typical values for ''L/E'' range from 0.01 to 0.1. In a system with a ''L/E'' ratio of 0.05, for instance, if there are 15 CPUs, it is expected that on average 1 CPU will always be idle;Madnick 1968, p.20 with 21 CPUs, 2.8 will be idle;Raynor 76, p.62 with 40 CPUs, 19 will be idle; with 41 CPUs, 20 will be idle. Therefore, adding more than 40 CPUs to that system would be useless. In general, for each ''L/E'' value, there's a threshold for the maximum number of useful CPUs.

Software lockout mitigation

To reduce the performance degradation of software lockout to reasonable levels (''L/E'' between 0.05 and 0.1), the kernel and/or the operating system must be designed accordingly. Conceptually, the most valid solution is to decompose each kernel data structure in smaller independent substructures, having each a shorter elaboration time. This allows more than one CPU to access the original data structure. Many

uniprocessor A uniprocessor system is defined as a computer system that has a single central processing unit that is used to execute computer tasks. As more and more modern software is able to make use of multiprocessing architectures, such as SMP and MPP, t ...

systems with hierarchical protection domains have been estimated to spend up to 50% of the time performing "supervisor mode" operations. If such systems were adapted for multiprocessing by setting a lock at any access to "supervisor state", ''L/E'' would easily be greater than 1, resulting in a system with the same throughput as the uniprocessor despite the number of CPUs.

Notes

References

Madnick, Stuart Elliot
(1968)
Multi-processor software lockout
Proceedings of the 1968 23rd ACM national conference, pp. 19 – 24 * M. Dubois, F. Briggs
The run-time efficiency of parallel asynchronous algorithms
' IEEE Transactions on Computers, November 1991 (Vol. 40, No. 11) pp. 1260–1266 * Randy J. Raynor, John M. Gwynn, Jr.
Minimization of supervisor conflict for multiprocessor computer systems
' ACM SIGSIM Simulation Digest. Volume 7, Issue 4 (July 1976). pp. 61 – 69

Kernel-level critical sections

Analytical studies

Software lockout mitigation

See also

Notes

References

Further reading