View source for Software lockout

{{Short description|Operating system performance issue}}
{{expert needed|1=Computing|talk=Musty|date=June 2015}}
In [[multiprocessor]] computer systems, '''software lockout''' is the issue of performance degradation due to the idle wait times spent by the [[CPU]]s in [[Kernel (computer science)|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.

==Kernel-level critical sections==
In most multiprocessor systems, each processor schedules and controls itself, therefore there's no "supervisor" processor,<ref name="Madnickp19"/> and kernel [[data structure]]s are globally shared; sections of code that access those shared data structures are [[critical section]]s. This design choice is made to improve scaling, reliability and modularity.<ref name="Madnickp19"/> Examples of such kernel data structure are [[ready list]] and [[communication channel]]s.

A "conflict" happens when more than one [[CPU|processor]] is trying to access the same resource (a memory portion) at the same time. To prevent [[critical race]]s 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 [[Lock (computer science)|locked-out]], waiting in idle status.<ref name="Madnickp19">Madnick 1968, p.19</ref><ref>{{cite thesis|type=PhD|last=Saltzer|first=Jerome|url=https://web.mit.edu/Saltzer/www/publications/TRs+TMs/Multics/TR-030.pdf|title=Traffic control in a multiplexed computer system|id=MIT Project MAC MAC-TR-30|date=June 1966}}</ref>

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 (computing)|scheduling]] operation. The idle wait is not necessary but convenient in the case of a critical section for [[Synchronization (computer science)|synchronization]]/[[Inter-process communication|IPC]] operations, which require less time than a [[context switch]] (executing another [[process (computing)|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 (computer science)|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]].

==Analytical studies==
{{update|section|date=June 2015}}
Taking as parameters the average time interval spent by a [[CPU|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''),<ref name="Madnickp19"/> the ratio ''L/E'' is crucial in evaluating software lockout.

Typical values for ''L/E'' range from 0.01 to 0.1.<ref name="Madnickp20"/> 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;<ref name="Madnickp20">Madnick 1968, p.20</ref> with 21 CPUs, 2.8 will be idle;<ref name="Raynor76">Raynor 76, p.62</ref> with 40 CPUs, 19 will be idle; with 41 CPUs, 20 will be idle.<ref name="Madnickp20"/> 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]] 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,<ref name="Madnickp20"/> resulting in a system with the same throughput as the uniprocessor despite the number of CPUs.

==See also==
* [[Amdahl's law]]
* Dependency issues on [[Superscalar]] architectures
* {{Section link|Concurrency control|Concurrency control mechanisms}}
* {{Section link|Database transaction schedule|Serializable}}
* [[Serializability]]

==Notes==
{{reflist}}

==References==
* [http://web.mit.edu/smadnick/www/Resume/Publications.htm Madnick, Stuart Elliot] [http://www.lecgcp.com/resources/documents/Madnick_LECG_CV_08_2006.pdf] (1968) ''[http://doi.acm.org/10.1145/800186.810561 Multi-processor software lockout]''[http://web.mit.edu/smadnick/www/papers/P001.pdf] Proceedings of the 1968 23rd ACM national conference, pp.&nbsp;19 – 24
* M. Dubois, F. Briggs ''[http://doi.ieeecomputersociety.org/10.1109/12.102830 The run-time efficiency of parallel asynchronous algorithms]'' IEEE Transactions on Computers, November 1991 (Vol. 40, No. 11) pp.&nbsp;1260–1266
* Randy J. Raynor, John M. Gwynn, Jr.''[http://doi.acm.org/10.1145/1013610.807300 Minimization of supervisor conflict for multiprocessor computer systems]'' ACM SIGSIM Simulation Digest. Volume 7, Issue 4  (July 1976). pp.&nbsp;61 – 69

==Further reading==
* Rodgers, David P. (1985) ''[http://portal.acm.org/citation.cfm?id=327215 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 Architecture]] (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
* Jörg Cordsen, Wolfgang Schröder-Preikschat ''[http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=419C0DC4D4387053DA72AB004002FEC9?doi=10.1.1.16.9695&rep=rep1&type=pdf Towards a Scalable Kernel Architecture]'' In: Proceedings of the Autumn 1992 Openforum Technical Conference. pp.&nbsp;15–33, Utrecht, The Netherlands, November 23–27, 1992.

{{Parallel Computing}}

{{DEFAULTSORT:Software Lockout}}
[[Category:Computer performance]]
[[Category:Concurrency control]]
[[Category:Operating system kernels]]
<!-- or use the more general [[Category:Computer architecture]] -->