Software lockout
Encyclopedia
In multiprocessor
computer systems, software lockout is the issue of performance degradation due to the idle wait times spent by the CPUs in kernel-level critical section
s. Software lockout is the major cause of scalability
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 critical section
s as short as possible, therefore decomposing each data structure
in smaller substructures.
s are globally shared critical section
s. This design choice is made to improve scaling, reliability and modularity. Examples of such kernel data structure are ready list and communication channels.
A "conflict" happens when more than one processor 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.
Three cases can be distinguished when this idle wait is (1) necessary (2) convenient and (3) not convenient. The idle wait is necessary when the access is to a ready list for a low level scheduling
operation. The idle wait is not necessary but convenient in the case of a critical section for a synchronization
/IPC
operations, which require less time than a context switch
(executing another process
to avoid idle wait). Idle wait is instead not convenient in case of a kernel critical section for device management, present in monolithic kernel
s only. A microkernel
instead falls on just the first two of the above cases.
In a multiprocessor system, most of the conflicts are kernel-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 scalability
and relative efficiency.
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.; with 21 CPUs, 2.8 will be idle; 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.
Many uniprocessor
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 bandwidth of the uniprocessor despite the number of CPUs.
Multiprocessor
Computer system having two or more processing units each sharing main memory and peripherals, in order to simultaneously process programs.Sometimes the term Multiprocessor is confused with the term Multiprocessing....
computer systems, software lockout is the issue of performance degradation due to the idle wait times spent by the CPUs in kernel-level critical section
Critical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
s. Software lockout is the major cause of scalability
Scalability
In electronics scalability is the ability of a system, network, or process, to handle growing amount of work in a graceful manner or its ability to be enlarged to accommodate that growth...
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 critical section
Critical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
s as short as possible, therefore decomposing each data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
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 structureData structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
s are globally shared critical section
Critical section
In concurrent programming a critical section is a piece of code that accesses a shared resource that must not be concurrently accessed by more than one thread of execution. A critical section will usually terminate in fixed time, and a thread, task or process will have to wait a fixed time to...
s. This design choice is made to improve scaling, reliability and modularity. Examples of such kernel data structure are ready list and communication channels.
A "conflict" happens when more than one processor 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
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
(a memory portion), while other CPUs trying to access at the same time are locked-out
Lock (computer science)
In computer science, a lock is a synchronization mechanism for enforcing limits on access to a resource in an environment where there are many threads of execution. Locks are one way of enforcing concurrency control policies.-Types:...
, waiting in idle status.
Three cases can be distinguished when this idle wait is (1) necessary (2) convenient and (3) not convenient. The idle wait is necessary when the access is to a ready list for a low level scheduling
Scheduling (computing)
In computer science, a scheduling is the method by which threads, processes or data flows are given access to system resources . This is usually done to load balance a system effectively or achieve a target quality of service...
operation. The idle wait is not necessary but convenient in the case of a critical section for a synchronization
Synchronization (computer science)
In computer science, synchronization refers to one of two distinct but related concepts: synchronization of processes, and synchronization of data. Process synchronization refers to the idea that multiple processes are to join up or handshake at a certain point, so as to reach an agreement or...
/IPC
Inter-process communication
In computing, Inter-process communication is a set of methods for the exchange of data among multiple threads in one or more processes. Processes may be running on one or more computers connected by a network. IPC methods are divided into methods for message passing, synchronization, shared...
operations, which require less time than a context switch
Context switch
A context switch is the computing process of storing and restoring the state of a CPU so that execution can be resumed from the same point at a later time. This enables multiple processes to share a single CPU. The context switch is an essential feature of a multitasking operating system...
(executing another process
Process (computing)
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system , a process may be made up of multiple threads of execution that execute instructions concurrently.A computer program is a...
to avoid idle wait). Idle wait is instead not convenient in case of a kernel critical section for device management, present in monolithic kernel
Monolithic kernel
A monolithic kernel is an operating system architecture where the entire operating system is working in the kernel space and alone as supervisor mode...
s only. A microkernel
Microkernel
In computer science, a microkernel is the near-minimum amount of software that can provide the mechanisms needed to implement an operating system . These mechanisms include low-level address space management, thread management, and inter-process communication...
instead falls on just the first two of the above cases.
In a multiprocessor system, most of the conflicts are kernel-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 scalability
Scalability
In electronics scalability is the ability of a system, network, or process, to handle growing amount of work in a graceful manner or its ability to be enlarged to accommodate that growth...
and relative efficiency.
Analytical studies
Taking as parameters the average time interval spent by a processor 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.; with 21 CPUs, 2.8 will be idle; 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
Uniprocessor
A uniprocessor system is a computer system with a single central processing unit. As more and more computers employ multiprocessing architectures, such as SMP and MPP, the term is used to refer to systems that still have only one CPU. Most desktop computers are now shipped with multiprocessing...
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
Multiprocessing
Multiprocessing is the use of two or more central processing units within a single computer system. The term also refers to the ability of a system to support more than one processor and/or the ability to allocate tasks between them...
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 bandwidth of the uniprocessor despite the number of CPUs.
See also
- Amdahl's lawAmdahl's lawAmdahl's law, also known as Amdahl's argument, is named after computer architect Gene Amdahl, and is used to find the maximum expected improvement to an overall system when only part of the system is improved...
- Dependency issues on SuperscalarSuperscalarA superscalar CPU architecture implements a form of parallelism called instruction level parallelism within a single processor. It therefore allows faster CPU throughput than would otherwise be possible at a given clock rate...
architectures - Lockout (telecommunication)
- Concurrency control#Concurrency control mechanisms
- Schedule (computer science)#Serializable
- SerializabilitySerializabilityIn concurrency control of databases, transaction processing , and various transactional applications , both centralized and distributed, a transaction schedule is serializable, has the serializability property, if its outcome In concurrency control of databases, transaction processing (transaction...
Further reading
- Rodgers, David P. (1985) Improvements in multiprocessor system design ACM SIGARCH Computer Architecture News archive Volume 13 , Issue 3 (June 1985) table of contents Special Issue: Proceedings of the 12th annual International Symposium on Computer ArchitectureInternational Symposium on Computer ArchitectureThe International Symposium on Computer Architecture is generally viewed as the top-tier academic conference on computer architecture.-External references:* in the ACM digital library.* in DBLP.* ....
(ISCA '85) Pages: 225 - 231 Year of Publication: 1985 ISSN:0163-5964. Also published in International Symposium on Computer Architecture, Proceedings of the 12th annual international symposium on Computer architecture, 1985 , Boston, Massachusetts, United States
External links
- J. Cordsen, W. Schroder-Preikschat [ftp://ftp.gmd.de/GMD/peace/ScalableOSDesign.ps.gz Towards a Scalable Kernel Architecture] http://66.102.1.104/scholar?hl=en&lr=&safe=off&q=cache:lhotESB32V0J:ftp://ftp.gmd.de/GMD/peace/ScalableOSDesign.ps.gz+compilation+kernel+architecture In Proceedings of the Autumn 1992 Openforum Technical Conference. pp. 15{33, Utrecht, The Netherlands, November 23{27, 1992.