Enzyme promiscuity is the ability of an enzyme
to catalyse a fortuitous side reaction in addition to its main
reaction. Although enzymes are remarkably specific catalysts, they can
often perform side reactions in addition to their main, native catalytic
activity. These promiscuous activities are usually slow relative to the
main activity and are under neutral selection. Despite ordinarily being
physiologically irrelevant, under new selective pressures these
activities may confer a fitness benefit therefore prompting the
evolution of the formerly promiscuous activity to become the new main
activity. An example of this is the atrazine chlorohydrolase (atzA encoded) from Pseudomonas sp. ADP that evolved from melaminedeaminase (triA encoded), which has very small promiscuous activity toward atrazine, a man-made chemical.
Introduction
Enzymes are evolved to catalyse a particular reaction on a particular substrate with a high catalytic efficiency (kcat/KM, cf. Michaelis–Menten kinetics).
However, in addition to this main activity, they possess other
activities that are generally several orders of magnitude lower, and
that are not a result of evolutionary selection and therefore do not
partake in the physiology of the organism.
This phenomenon allows new functions to be gained as the promiscuous
activity could confer a fitness benefit under a new selective pressure
leading to its duplication and selection as a new main activity.
Enzyme evolution
Duplication and divergence
Several theoretical models exist to predict the order of duplication and specialisation events, but the actual process is more intertwined and fuzzy (§ Reconstructed enzymesbelow).
On one hand, gene amplification results in an increase in enzyme
concentration, and potentially freedom from a restrictive regulation,
therefore increasing the reaction rate (v) of the promiscuous activity of the enzyme making its effects more pronounced physiologically ("gene dosage effect").
On the other, enzymes may evolve an increased secondary activity with
little loss to the primary activity ("robustness") with little adaptive
conflict (§ Robustness and plasticitybelow).
Robustness and plasticity
A study of four distinct hydrolases
(human serum paraoxonase (PON1), pseudomonad phosphotriesterase (PTE),
Protein tyrosine phospatase(PTP) and human carbonic anhydrase II (CAII))
has shown the main activity is "robust" towards change, whereas the
promiscuous activities are weak and more "plastic". Specifically,
selecting for an activity that is not the main activity (via directed evolution),
does not initially diminish the main activity (hence its robustness),
but greatly affects the non-selected activities (hence their
plasticity).
The phosphotriesterase (PTE) from Pseudomonas diminuta was evolved to become an arylesterase (P–O to C–O hydrolase) in eighteen rounds gaining a 109 shift in specificity (ratio of KM),
however most of the change occurred in the initial rounds, where the
unselected vestigial PTE activity was retained and the evolved
arylesterase activity grew, while in the latter rounds there was a
little trade-off for the loss of the vestigial PTE activity in favour of
the arylesterase activity.
This means firstly that a specialist enzyme (monofunctional) when
evolved goes through a generalist stage (multifunctional), before
becoming a specialist again—presumably after gene duplication according
to the IAD model—and secondly that promiscuous activities are more
plastic than the main activity.
Reconstructed enzymes
The most recent and most clear cut example of enzyme evolution is the rise of bioremediating
enzymes in the past 60 years. Due to the very low number of amino acid
changes, these provide an excellent model to investigate enzyme
evolution in nature. However, using extant enzymes to determine how the
family of enzymes evolved has the drawback that the newly evolved enzyme
is compared to paralogues without knowing the true identity of the
ancestor before the two genes diverged. This issue can be resolved
thanks to ancestral reconstruction.
First proposed in 1963 by Linus Pauling and Emile Zuckerkandl, ancestral reconstruction is the inference and synthesis of a gene from the ancestral form of a group of genes, which has had a recent revival thanks to improved inference techniques and low-cost artificial gene synthesis, resulting in several ancestral enzymes—dubbed "stemzymes" by some—to be studied.
Evidence gained from reconstructed enzyme suggests that the order
of the events where the novel activity is improved and the gene is
duplication is not clear cut, unlike what the theoretical models of gene
evolution suggest.
One study showed that the ancestral gene of the immune defence
protease family in mammals had a broader specificity and a higher
catalytic efficiency than the contemporary family of paralogues, whereas another study showed that the ancestral steroid receptor of vertebrates was an oestrogen receptor with slight substrate ambiguity for other hormones—indicating that these probably were not synthesised at the time.
This variability in ancestral specificity has not only been
observed between different genes, but also within the same gene family.
In light of the large number of paralogous fungal α-glucosidase genes
with a number of specific maltose-like (maltose, turanose, maltotriose,
maltulose and sucrose) and isomaltose-like (isomaltose and palatinose)
substrates, a study reconstructed all key ancestors and found that the
last common ancestor of the paralogues was mainly active on maltose-like
substrates with only trace activity for isomaltose-like sugars, despite
leading to a lineage of iso-maltose glucosidases and a lineage that
further split into maltose glucosidases and iso-maltose glucosidases.
Antithetically, the ancestor before the latter split had a more
pronounced isomaltose-like glucosidase activity.
Primordial metabolism
Roy
Jensen in 1976 theorised that primordial enzymes had to be highly
promiscuous in order for metabolic networks to assemble in a patchwork
fashion (hence its name, the patchwork model). This primordial catalytic versatility was later lost in favour of highly catalytic specialised orthologous enzymes. As a consequence, many central-metabolic enzymes have structural homologues that diverged before the last universal common ancestor.
Distribution
Promiscuity
is not only a primordial trait, but also a very widespread property in
modern genomes. A series of experiments have been conducted to assess
the distribution of promiscuous enzyme activities in E. coli. In E. coli 21 out of 104 single-gene knockouts tested (from the Keio collection) could be rescued by overexpressing a noncognate E. coli protein (using a pooled set of plasmids of the ASKA collection).
The mechanisms by which the noncognate ORF could rescue the knockout
can be grouped into eight categories: isozyme overexpression
(homologues), substrate ambiguity, transport ambiguity (scavenging),
catalytic promiscuity, metabolic flux maintenance (including
overexpression of the large component of a synthase in the absence of
the amine transferase subunit), pathway bypass, regulatory effects and
unknown mechanisms. Similarly, overexpressing the ORF collection allowed E. coli to gain over an order of magnitude in resistance in 86 out 237 toxic environment.
Homology
Homologues are sometimes known to display promiscuity towards each other's main reactions.
This crosswise promiscuity has been most studied with members of the alkaline phosphatase
superfamily, which catalyse hydrolytic reaction on the sulfate,
phosphonate, monophosphate, diphosphate or triphosphate ester bond of
several compounds.
Despite the divergence the homologues have a varying degree of
reciprocal promiscuity: the differences in promiscuity are due to
mechanisms involved, particularly the intermediate required.
Degree of promiscuity
Enzymes
are generally in a state that is not only a compromise between
stability and catalytic efficiency, but also for specificity and
evolvability, the latter two dictating whether an enzyme is a generalist
(highly evolvable due to large promiscuity, but low main activity) or a
specialist (high main activity, poorly evolvable due to low
promiscuity). Examples of these are enzymes for primary and secondary metabolism in plants (§ Plant secondary metabolismbelow). Other factors can come into play, for example the glycerophosphodiesterase (gpdQ) from Enterobacter aerogenes
shows different values for its promiscuous activities depending on the
two metal ions it binds, which is dictated by ion availability. some cases promiscuity can be increased by relaxing the specificity
of the active site by enlarging it with a single mutation as was the
case of a D297G mutant of the E. coli L-Ala-D/L-Glu epimerase (ycjG)
and E323G mutant of a pseudomonad muconate lactonizing enzyme II,
allowing them to promiscuously catalyse the activity of
O-succinylbenzoate synthase (menC). Conversely, promiscuity can be decreased as was the case of γ-humulene synthase (a sesquiterpene synthase) from Abies grandis that is known to produce 52 different sesquiterpenes from farnesyl diphosphate upon several mutations.
Studies on enzymes with broad-specificity—not promiscuous, but
conceptually close—such as mammalian trypsin and chymotrypsin, and the
bifunctional isopropylmalate isomerase/homoaconitase from Pyrococcus horikoshii have revealed that active site loop mobility contributes substantially to the catalytic elasticity of the enzyme.
Toxicity
A
promiscuous activity is a non-native activity the enzyme did not evolve
to do, but arises due to an accommodating conformation of the active
site. However, the main activity of the enzyme is a result not only of
selection towards a high catalytic rate towards a particular substrate
to produce a particular product, but also to avoid the production of
toxic or unnecessary products.
For example, if a tRNA syntheses loaded an incorrect amino acid onto a
tRNA, the resulting peptide would have unexpectedly altered properties,
consequently to enhance fidelity several additional domains are present. Similar in reaction to tRNA syntheses, the first subunit of tyrocidine synthetase (tyrA) from Bacillus brevis adenylates a molecule of phenylalanine in order to use the adenyl moiety as a handle to produce tyrocidine, a cyclic non-ribosomal peptide.
When the specificity of enzyme was probed, it was found that it was
highly selective against natural amino acids that were not
phenylalanine, but was much more tolerant towards unnatural amino acids.
Specifically, most amino acids were not catalysed, whereas the next
most catalysed native amino acid was the structurally similar tyrosine,
but at a thousandth as much as phenylalanine, whereas several unnatural amino acids where catalysed better than tyrosine, namely D-phenylalanine, β-cyclohexyl-L-alanine, 4-amino-L-phenylalanine and L-norleucine.
One peculiar case of selected secondary activity are polymerases
and restriction endonucleases, where incorrect activity is actually a
result of a compromise between fidelity and evolvability. For example,
for restriction endonucleases incorrect activity (star activity) is often lethal for the organism, but a small amount allows new functions to evolve against new pathogens.
Plant secondary metabolism
Anthocyanins (delphinidin
pictured) confer plants, particularly their flowers, with a variety of
colours to attract pollinators and a typical example of plant secondary
metabolite.
Plants produce a large number of secondary metabolites
thanks to enzymes that, unlike those involved in primary metabolism,
are less catalytically efficient but have a larger mechanistic
elasticity (reaction types) and broader specificities. The liberal drift
threshold (caused by the low selective pressure due to the small
population size) allows the fitness gain endowed by one of the products
to maintain the other activities even though they may be physiologically
useless.
In biocatalysis,
many reactions are sought that are absent in nature. To do this,
enzymes with a small promiscuous activity towards the required reaction
are identified and evolved via directed evolution or rational design.
An example of a commonly evolved enzyme is ω-transaminase which can replace a ketone with a chiral amine and consequently libraries of different homologues are commercially available for rapid biomining (eg. Codexis).
Similarity between enzymatic reactions (EC) can be calculated by using bond changes, reaction centres or substructure metrics (EC-BLASTArchived 2019-05-30 at the Wayback Machine).
Drugs and promiscuity
Whereas
promiscuity is mainly studied in terms of standard enzyme kinetics,
drug binding and subsequent reaction is a promiscuous activity as the
enzyme catalyses an inactivating reaction towards a novel substrate it
did not evolve to catalyse. This could be because of the demonstration that there are only a small number of distinct ligand binding pockets in proteins.
Mammalian xenobiotic metabolism,
on the other hand, was evolved to have a broad specificity to oxidise,
bind and eliminate foreign lipophilic compounds which may be toxic, such
as plant alkaloids, so their ability to detoxify anthropogenic
xenobiotics is an extension of this.
In computer science, a data structure is a data organization, management, and storage format that is usually chosen for efficientaccess to data.
More precisely, a data structure is a collection of data values, the
relationships among them, and the functions or operations that can be
applied to the data, i.e., it is an algebraic structure about data.
Usage
Data structures serve as the basis for abstract data types (ADT). The ADT defines the logical form of the data type. The data structure implements the physical form of the data type.
Different types of data structures are suited to different kinds
of applications, and some are highly specialized to specific tasks. For
example, relational databases commonly use B-tree indexes for data retrieval, while compilerimplementations usually use hash tables to look up identifiers.
Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually, efficient data structures are key to designing efficient algorithms. Some formal design methods and programming languages
emphasize data structures, rather than algorithms, as the key
organizing factor in software design. Data structures can be used to
organize the storage and retrieval of information stored in both main memory and secondary memory.
Implementation
Data
structures can be implemented using a variety of programming languages
and techniques, but they all share the common goal of efficiently
organizing and storing data. Data structures are generally based on the ability of a computer to fetch and store data at any place in its memory, specified by a pointer—a bitstring, representing a memory address, that can be itself stored in memory and manipulated by the program. Thus, the array and record data structures are based on computing the addresses of data items with arithmetic operations, while the linked data structures
are based on storing addresses of data items within the structure
itself. This approach to data structuring has profound implications for
the efficiency and scalability of algorithms. For instance, the
contiguous memory allocation in arrays facilitates rapid access and
modification operations, leading to optimized performance in sequential
data processing scenarios.
The implementation of a data structure usually requires writing a set of procedures
that create and manipulate instances of that structure. The efficiency
of a data structure cannot be analyzed separately from those operations.
This observation motivates the theoretical concept of an abstract data type,
a data structure that is defined indirectly by the operations that may
be performed on it, and the mathematical properties of those operations
(including their space and time cost).
The standard type hierarchy of the programming language Python 3.
There are numerous types of data structures, generally built upon simpler primitive data types. Well known examples are:
An array
is a number of elements in a specific order, typically all of the same
type (depending on the language, individual elements may either all be
forced to be the same type, or may be of almost any type). Elements are
accessed using an integer index to specify which element is required.
Typical implementations allocate contiguous memory words for the
elements of arrays (but this is not always a necessity). Arrays may be
fixed-length or resizable.
A linked list (also just called list)
is a linear collection of data elements of any type, called nodes,
where each node has itself a value, and points to the next node in the
linked list. The principal advantage of a linked list over an array is
that values can always be efficiently inserted and removed without
relocating the rest of the list. Certain other operations, such as random access to a certain element, are however slower on lists than on arrays.
A record (also called tuple or struct) is an aggregate data
structure. A record is a value that contains other values, typically in
fixed number and sequence and typically indexed by names. The elements
of records are usually called fields or members. In the context of object-oriented programming, records are known as plain old data structures to distinguish them from objects.
Hash tables,
also known as hash maps, are data structures that provide fast
retrieval of values based on keys. They use a hashing function to map
keys to indexes in an array, allowing for constant-time access in the
average case. Hash tables are commonly used in dictionaries, caches, and
database indexing. However, hash collisions can occur, which can impact
their performance. Techniques like chaining and open addressing are
employed to handle collisions.
Graphs
are collections of nodes connected by edges, representing relationships
between entities. Graphs can be used to model social networks, computer
networks, and transportation networks, among other things. They consist
of vertices (nodes) and edges (connections between nodes). Graphs can
be directed or undirected, and they can have cycles or be acyclic. Graph
traversal algorithms include breadth-first search and depth-first
search.
Stacks and queues
are abstract data types that can be implemented using arrays or linked
lists. A stack has two primary operations: push (adds an element to the
top of the stack) and pop (removes the topmost element from the stack),
that follow the Last In, First Out (LIFO) principle. Queues have two
main operations: enqueue (adds an element to the rear of the queue) and
dequeue (removes an element from the front of the queue) that follow the
First In, First Out (FIFO) principle.
Trees
represent a hierarchical organization of elements. A tree consists of
nodes connected by edges, with one node being the root and all other
nodes forming subtrees. Trees are widely used in various algorithms and
data storage scenarios. Binary trees (particularly heaps), AVL trees, and B-trees are some popular types of trees. They enable efficient and optimal searching, sorting, and hierarchical representation of data.
A trie,
also known as a prefix tree, is a specialized tree data structure used
for the efficient retrieval of strings. Tries store characters of a
string as nodes, with each edge representing a character. They are
particularly useful in text processing scenarios like autocomplete,
spell-checking, and dictionary implementations. Tries enable fast
searching and prefix-based operations on strings.
Language support
Most assembly languages and some low-level languages, such as BCPL (Basic Combined Programming Language), lack built-in support for data structures. On the other hand, many high-level programming languages and some higher-level assembly languages, such as MASM, have special syntax or other built-in support for certain data structures, such as records and arrays. For example, the C (a direct descendant of BCPL) and Pascal languages support structs and records, respectively, in addition to vectors (one-dimensional arrays) and multi-dimensional arrays.
Most programming languages feature some sort of library
mechanism that allows data structure implementations to be reused by
different programs. Modern languages usually come with standard
libraries that implement the most common data structures. Examples are
the C++Standard Template Library, the Java Collections Framework, and the Microsoft.NET Framework.
A low-level programming language is a programming language that provides little or no abstraction from a computer's instruction set architecture—commands
or functions in the language map that are structurally similar to
processor's instructions. Generally, this refers to either machine code or assembly language.
Because of the low (hence the word) abstraction between the language
and machine language, low-level languages are sometimes described as
being "close to the hardware". Programs written in low-level languages
tend to be relatively non-portable, due to being optimized for a certain type of system architecture.
Low-level languages can convert to machine code without a compiler or interpreter—second-generation programming languages use a simpler processor called an assembler—and
the resulting code runs directly on the processor. A program written in
a low-level language can be made to run very quickly, with a small memory footprint. An equivalent program in a high-level language
can be less efficient and use more memory. Low-level languages are
simple, but considered difficult to use, due to numerous technical
details that the programmer must remember. By comparison, a high-level programming language isolates execution semantics of a computer architecture from the specification of the program, which simplifies development.
Machine code
Front panel of a PDP-8/E minicomputer. The row of switches at the bottom can be used to toggle in a machine language program.
Machine code is the only language a computer can process directly
without a previous transformation. Currently, programmers almost never
write programs directly in machine code, because it requires attention
to numerous details that a high-level programming language handles automatically. Furthermore, unlike programming in an assembly language, it requires memorizing or looking up numerical codes for every instruction, and is extremely difficult to modify.
True machine code is a stream of raw, usually binary, data. A programmer coding in "machine code" normally codes instructions and data in a more readable form such as decimal, octal, or hexadecimal which is translated to internal format by a program called a loader or toggled into the computer's memory from a front panel.
Although few programs are written in machine languages, programmers often become adept at reading it through working with core dumps or debugging from the front panel.
Example of a function in hexadecimal representation of x86-64 machine code to calculate the nth Fibonacci number, with each line corresponding to one instruction:
Second-generation languages provide one abstraction level on top of
the machine code. In the early days of coding on computers like TX-0 and PDP-1, the first thing MIThackers did was to write assemblers.
Assembly language has little semantics or formal specification, being only a mapping of human-readable symbols, including symbolic addresses, to opcodes, addresses, numeric constants, strings and so on. Typically, one machine instruction is represented as one line of assembly code. Assemblers produce object files that can link with other object files or be loaded on their own.
Most assemblers provide macros to generate common sequences of instructions.
fib:movl%edi,%eax; put the argument into %eaxtestl%edi,%edi; is it zero?je.return_from_fib; yes - return 0, which is already in %eaxcmpl$2,%edi; is 2 greater than or equal to it?jbe.return_1_from_fib; yes (i.e., it's 1 or 2) - return 1movl%edi,%ecx; no - put it in %ecx, for use as a countermovl$1,%edx; the previous number in the sequence, which starts out as 1movl$1,%esi; the number before that, which also starts out as 1.fib_loop:leal(%rsi,%rdx),%eax; put the sum of the previous two numbers into %eaxcmpl$2,%ecx; is the counter 2?je.return_from_fib; yes - %eax contains the resultmovl%edx,%esi; make the previous number the number before the previous onedecl%ecx; decrement the countermovl%eax,%edx; make the current number the previous numberjmp.fib_loop; keep going.return_1_from_fib:movl$1,%eax; set the return value to 1.return_from_fib:ret; return
In this code example, the registers of the x86-64 processor are named and manipulated directly. The function loads its 32-bit argument from %edi in accordance to the System V application binary interface for x86-64 and performs its calculation by manipulating values in the %eax, %ecx, %esi, and %edi
registers until it has finished and returns. Note that in this assembly
language, there is no concept of returning a value. The result having
been stored in the %eax register, again in accordance with System V application binary interface, the ret instruction simply removes the top 64-bit element on the stack
and causes the next instruction to be fetched from that location (that
instruction is usually the instruction immediately after the one that
called this function), with the result of the function being stored in %eax.
x86-64 assembly language imposes no standard for passing values to a
function or returning values from a function (and in fact, has no
concept of a function); those are defined by an application binary interface, such as the System V ABI for a particular instruction set.
This code is similar in structure to the assembly language example
but there are significant differences in terms of abstraction:
The input (parameter n)
is an abstraction that does not specify any storage location on the
hardware. In practice, the C compiler follows one of many possible calling conventions to determine a storage location for the input.
The local variables f_nminus2, f_nminus2, and f_n
are abstractions that do not specify any specific storage location on
the hardware. The C compiler decides how to actually store them for the
target architecture.
The return function specifies the value to return, but does not dictate how it is returned. The C compiler for any specific architecture implements a standard mechanism for returning the value. Compilers for the x86 architecture typically (but not always) use the %eax register to return a value, as in the assembly language example (the author of the assembly language example has chosen to use the System V application binary interface for x86-64 convention but assembly language does not require this).
These abstractions make the C code compilable without modification on
any architecture for which a C compiler has been written. The x86
assembly language code is specific to the x86-64 architecture and the
System V application binary interface for that architecture.
Low-level programming in high-level languages
During the late 1960s and 1970s, high-level languages that included some degree of access to low-level programming functions, such as PL/S, BLISS, BCPL, extended ALGOL and ESPOL (for Burroughs large systems), and C, were introduced. One method for this is inline assembly,
in which assembly code is embedded in a high-level language that
supports this feature. Some of these languages also allow
architecture-dependent compiler optimization directives to adjust the way a compiler uses the target processor architecture.
In digital computers, an interrupt (sometimes referred to as a trap) is a request for the processor to interrupt
currently executing code (when permitted), so that the event can be
processed in a timely manner. If the request is accepted, the processor
will suspend its current activities, save its state, and execute a function called an interrupt handler (or an interrupt service routine, ISR) to deal with the event. This interruption is often temporary, allowing the software to resume normal activities after the interrupt handler finishes, although the interrupt could instead indicate a fatal error.
Interrupts are commonly used by hardware devices to indicate
electronic or physical state changes that require time-sensitive
attention. Interrupts are also commonly used to implement computer multitasking, especially in real-time computing. Systems that use interrupts in these ways are said to be interrupt-driven.
History
Hardware interrupts were introduced as an optimization, eliminating unproductive waiting time in polling loops, waiting for external events. The first system to use this approach was the DYSEAC, completed in 1954, although earlier systems provided error trap functions.
The UNIVAC 1103A computer is generally credited with the earliest use of interrupts in 1953.Earlier, on the UNIVAC I
(1951) "Arithmetic overflow either triggered the execution of a
two-instruction fix-up routine at address 0, or, at the programmer's
option, caused the computer to stop." The IBM 650 (1954) incorporated the first occurrence of interrupt masking. The National Bureau of StandardsDYSEAC (1954) was the first to use interrupts for I/O. The IBM 704 was the first to use interrupts for debugging, with a "transfer trap", which could invoke a special routine when a branch instruction was encountered. The MIT Lincoln LaboratoryTX-2 system (1957) was the first to provide multiple levels of priority interrupts.
Types
Interrupt signals may be issued in response to hardware or software events. These are classified as hardware interrupts or software interrupts, respectively. For any particular processor, the number of interrupt types is limited by the architecture.
Hardware interrupts
A
hardware interrupt is a condition related to the state of the hardware
that may be signaled by an external hardware device, e.g., an interrupt request
(IRQ) line on a PC, or detected by devices embedded in processor logic
(e.g., the CPU timer in IBM System/370), to communicate that the device
needs attention from the operating system (OS) or, if there is no OS, from the bare metal program running on the CPU. Such external devices may be part of the computer (e.g., disk controller) or they may be external peripherals. For example, pressing a keyboard key or moving a mouse plugged into a PS/2 port triggers hardware interrupts that cause the processor to read the keystroke or mouse position.
Hardware interrupts can arrive asynchronously
with respect to the processor clock, and at any time during instruction
execution. Consequently, all incoming hardware interrupt signals are
conditioned by synchronizing them to the processor clock, and acted upon
only at instruction execution boundaries.
In many systems, each device is associated with a particular IRQ
signal. This makes it possible to quickly determine which hardware
device is requesting service, and to expedite servicing of that device.
On some older systems, such as the 1964 CDC 3600,
all interrupts went to the same location, and the OS used a specialized
instruction to determine the highest-priority outstanding unmasked
interrupt. On contemporary systems, there is generally a distinct
interrupt routine for each type of interrupt (or for each interrupt
source), often implemented as one or more interrupt vector tables.
Masking
To mask an interrupt is to disable it, so it is deferred or ignored by the processor, while to unmask an interrupt is to enable it.
Processors typically have an internal interrupt mask register, which allows selective enabling
(and disabling) of hardware interrupts. Each interrupt signal is
associated with a bit in the mask register. On some systems, the
interrupt is enabled when the bit is set, and disabled when the bit is
clear. On others, the reverse is true, and a set bit disables the
interrupt. When the interrupt is disabled, the associated interrupt
signal may be ignored by the processor, or it may remain pending.
Signals which are affected by the mask are called maskable interrupts.
Some interrupt signals are not affected by the interrupt mask and therefore cannot be disabled; these are called non-maskable interrupts (NMIs). These indicate high-priority events which cannot be ignored under any circumstances, such as the timeout signal from a watchdog timer. With regard to SPARC,
the Non-Maskable Interrupt (NMI), despite having the highest priority
among interrupts, can be prevented from occurring through the use of an
interrupt mask.
Missing interrupts
One
failure mode is when the hardware does not generate the expected
interrupt for a change in state, causing the operating system to wait
indefinitely. Depending on the details, the failure might affect only a
single process or might have global impact. Some operating systems have
code specifically to deal with this.
As an example, IBM Operating System/360
(OS/360) relies on a not-ready to ready device-end interrupt when a
tape has been mounted on a tape drive, and will not read the tape label
until that interrupt occurs or is simulated. IBM added code in OS/360 so
that the VARY ONLINE command will simulate a device end interrupt on
the target device.
Spurious interrupts
A spurious interrupt
is a hardware interrupt for which no source can be found. The term
"phantom interrupt" or "ghost interrupt" may also be used to describe
this phenomenon. Spurious interrupts tend to be a problem with a wired-OR
interrupt circuit attached to a level-sensitive processor input. Such
interrupts may be difficult to identify when a system misbehaves.
In a wired-OR circuit, parasitic capacitance
charging/discharging through the interrupt line's bias resistor will
cause a small delay before the processor recognizes that the interrupt
source has been cleared. If the interrupting device is cleared too late
in the interrupt service routine (ISR), there will not be enough time
for the interrupt circuit to return to the quiescent state before the
current instance of the ISR terminates. The result is the processor
will think another interrupt is pending, since the voltage at its
interrupt request input will be not high or low enough to establish an
unambiguous internal logic 1 or logic 0. The apparent interrupt will
have no identifiable source, hence the "spurious" moniker.
A spurious interrupt may also be the result of electrical anomalies due to faulty circuit design, high noise levels, crosstalk, timing issues, or more rarely, device errata.
A spurious interrupt may result in system deadlock or other
undefined operation if the ISR does not account for the possibility of
such an interrupt occurring. As spurious interrupts are mostly a
problem with wired-OR interrupt circuits, good programming practice in
such systems is for the ISR to check all interrupt sources for activity
and take no action (other than possibly logging the event) if none of
the sources is interrupting. They may even lead to crashing of the
computer in adverse scenarios.
Software interrupts
A
software interrupt is requested by the processor itself upon executing
particular instructions or when certain conditions are met. Every
software interrupt signal is associated with a particular interrupt
handler.
A software interrupt may be intentionally caused by executing a special instruction which, by design, invokes an interrupt when executed. Such instructions function similarly to subroutine calls and are used for a variety of purposes, such as requesting operating system services and interacting with device drivers (e.g., to read or write storage media). Software interrupts may also be triggered by program execution errors or by the virtual memory system.
Typically, the operating system kernel
will catch and handle such interrupts. Some interrupts are handled
transparently to the program - for example, the normal resolution of a page fault is to make the required page accessible in physical memory. But in other cases such as a segmentation fault the operating system executes a process callback. On Unix-likeoperating systems this involves sending a signal such as SIGSEGV, SIGBUS, SIGILL or SIGFPE,
which may either call a signal handler or execute a default action
(terminating the program). On Windows the callback is made using Structured Exception Handling with an exception code such as STATUS_ACCESS_VIOLATION or STATUS_INTEGER_DIVIDE_BY_ZERO.
In a kernel process, it is often the case that some types of software interrupts are not supposed to happen. If they occur nonetheless, an operating system crash may result.
The terms interrupt, trap, exception, fault, and abort are used to distinguish types of interrupts, although "there is no clear consensus as to the exact meaning of these terms". The term trap
may refer to any interrupt, to any software interrupt, to any
synchronous software interrupt, or only to interrupts caused by
instructions with trap in their names. In some usages, the term trap refers specifically to a breakpoint intended to initiate a context switch to a monitor program or debugger. It may also refer to a synchronous interrupt caused by an exceptional condition (e.g., division by zero, invalid memory access, illegal opcode), although the term exception is more common for this.
x86 divides interrupts into (hardware) interrupts and software exceptions, and identifies three types of exceptions: faults, traps, and aborts.
(Hardware) interrupts are interrupts triggered asynchronously by an I/O
device, and allow the program to be restarted with no loss of
continuity.
A fault is restartable as well but is tied to the synchronous execution
of an instruction - the return address points to the faulting
instruction. A trap is similar to a fault except that the return address
points to the instruction to be executed after the trapping
instruction; one prominent use is to implement system calls. An abort is used for severe errors, such as hardware errors and illegal values in system tables, and often does not allow a restart of the program.
Arm uses the term exception to refer to all types of interrupts, and divides exceptions into (hardware) interrupts, aborts, reset,
and exception-generating instructions. Aborts correspond to x86
exceptions and may be prefetch aborts (failed instruction fetches) or
data aborts (failed data accesses), and may be synchronous or
asynchronous. Asynchronous aborts may be precise or imprecise. MMU
aborts (page faults) are synchronous.
Triggering methods
Each
interrupt signal input is designed to be triggered by either a logic
signal level or a particular signal edge (level transition).
Level-sensitive inputs continuously request processor service so long as
a particular (high or low) logic level is applied to the input.
Edge-sensitive inputs react to signal edges: a particular (rising or
falling) edge will cause a service request to be latched; the processor
resets the latch when the interrupt handler executes.
Level-triggered
A level-triggered interrupt is requested by holding the interrupt signal at its particular (high or low) active logic level.
A device invokes a level-triggered interrupt by driving the signal to
and holding it at the active level. It negates the signal when the
processor commands it to do so, typically after the device has been
serviced.
The processor samples the interrupt input signal during each
instruction cycle. The processor will recognize the interrupt request if
the signal is asserted when sampling occurs.
Level-triggered inputs allow multiple devices to share a common
interrupt signal via wired-OR connections. The processor polls to
determine which devices are requesting service. After servicing a
device, the processor may again poll and, if necessary, service other
devices before exiting the ISR.
Edge-triggered
An edge-triggered interrupt is an interrupt signaled by a level transition
on the interrupt line, either a falling edge (high to low) or a rising
edge (low to high). A device wishing to signal an interrupt drives a
pulse onto the line and then releases the line to its inactive state. If
the pulse is too short to be detected by polled I/O
then special hardware may be required to detect it. The important part
of edge triggering is that the signal must transition to trigger the
interrupt; for example, if the signal was high-low-low, there would only
be one falling edge interrupt triggered, and the continued low level
would not trigger a further interrupt. The signal must return to the
high level and fall again in order to trigger a further interrupt. This
contrasts with a level trigger where the low level would continue to
create interrupts (if they are enabled) until the signal returns to its
high level.
Computers with edge-triggered interrupts may include an interrupt register
that retains the status of pending interrupts. Systems with interrupt
registers generally have interrupt mask registers as well.
Processor response
The
processor samples the interrupt trigger signals or interrupt register
during each instruction cycle, and will process the highest priority
enabled interrupt found.
Regardless of the triggering method, the processor will begin interrupt
processing at the next instruction boundary following a detected
trigger, thus ensuring:
The processor status is saved in a known manner. Typically the status is stored in a known location, but on some systems it is stored on a stack.
All instructions before the one pointed to by the PC have fully executed.
No instruction beyond the one pointed to by the PC has been
executed, or any such instructions are undone before handling the
interrupt.
The execution state of the instruction pointed to by the PC is known.
There are several different architectures for handling interrupts. In some, there is a single interrupt handler
that must scan for the highest priority enabled interrupt. In others,
there are separate interrupt handlers for separate interrupt types, separate I/O channels or devices, or both.
Several interrupt causes may have the same interrupt type and thus the
same interrupt handler, requiring the interrupt handler to determine
the cause.
If an additional component is used, that component would be
connected between the interrupting device and the processor's interrupt
pin to multiplex several sources of interrupt onto the one or two CPU lines typically available. If implemented as part of the memory controller, interrupts are mapped into the system's memory address space.
In systems on a chip
(SoC) implementations, interrupts come from different blocks of the
chip and are usually aggregated in an interrupt controller attached to
one or several processors (in a multi-core system).
Shared IRQs
Multiple devices may share an edge-triggered interrupt line if they
are designed to. The interrupt line must have a pull-down or pull-up
resistor so that when not actively driven it settles to its inactive
state, which is the default state of it. Devices signal an interrupt by
briefly driving the line to its non-default state, and let the line
float (do not actively drive it) when not signaling an interrupt. This
type of connection is also referred to as open collector. The line then carries all the pulses generated by all the devices. (This is analogous to the pull cord
on some buses and trolleys that any passenger can pull to signal the
driver that they are requesting a stop.) However, interrupt pulses from
different devices may merge if they occur close in time. To avoid losing
interrupts the CPU must trigger on the trailing edge of the pulse (e.g.
the rising edge if the line is pulled up and driven low). After
detecting an interrupt the CPU must check all the devices for service
requirements.
Edge-triggered interrupts do not suffer the problems that
level-triggered interrupts have with sharing. Service of a low-priority
device can be postponed arbitrarily, while interrupts from
high-priority devices continue to be received and get serviced. If there
is a device that the CPU does not know how to service, which may raise
spurious interrupts, it will not interfere with interrupt signaling of
other devices. However, it is easy for an edge-triggered interrupt to be
missed - for example, when interrupts are masked for a period - and
unless there is some type of hardware latch that records the event it is
impossible to recover. This problem caused many "lockups" in early
computer hardware because the processor did not know it was expected to
do something. More modern hardware often has one or more interrupt
status registers that latch interrupts requests; well-written
edge-driven interrupt handling code can check these registers to ensure
no events are missed.
The elderly Industry Standard Architecture
(ISA) bus uses edge-triggered interrupts, without mandating that
devices be able to share IRQ lines, but all mainstream ISA motherboards
include pull-up resistors on their IRQ lines, so well-behaved ISA
devices sharing IRQ lines should just work fine. The parallel port
also uses edge-triggered interrupts. Many older devices assume that
they have exclusive use of IRQ lines, making it electrically unsafe to
share them.
There are 3 ways multiple devices "sharing the same line" can be
raised. First is by exclusive conduction (switching) or exclusive
connection (to pins). Next is by bus (all connected to the same line
listening): cards on a bus must know when they are to talk and not talk
(i.e., the ISA bus). Talking can be triggered in two ways: by
accumulation latch or by logic gates. Logic gates expect a continual
data flow that is monitored for key signals. Accumulators only trigger
when the remote side excites the gate beyond a threshold, thus no
negotiated speed is required. Each has its speed versus distance
advantages. A trigger, generally, is the method in which excitation is
detected: rising edge, falling edge, threshold (oscilloscope can trigger a wide variety of shapes and conditions).
Triggering for software interrupts must be built into the
software (both in OS and app). A 'C' app has a trigger table (a table
of functions) in its header, which both the app and OS know of and use
appropriately that is not related to hardware. However do not confuse
this with hardware interrupts which signal the CPU (the CPU enacts
software from a table of functions, similarly to software interrupts).
Difficulty with sharing interrupt lines
Multiple
devices sharing an interrupt line (of any triggering style) all act as
spurious interrupt sources with respect to each other. With many
devices on one line, the workload in servicing interrupts grows in
proportion to the square of the number of devices. It is therefore
preferred to spread devices evenly across the available interrupt lines.
Shortage of interrupt lines is a problem in older system designs where
the interrupt lines are distinct physical conductors. Message-signaled
interrupts, where the interrupt line is virtual, are favored in new
system architectures (such as PCI Express) and relieve this problem to a considerable extent.
Some devices with a poorly designed programming interface provide
no way to determine whether they have requested service. They may lock
up or otherwise misbehave if serviced when they do not want it. Such
devices cannot tolerate spurious interrupts, and so also cannot tolerate
sharing an interrupt line. ISA cards, due to often cheap design and construction, are notorious for this problem. Such devices are becoming much rarer, as hardware logic becomes cheaper and new system architectures mandate shareable interrupts.
Hybrid
Some
systems use a hybrid of level-triggered and edge-triggered signaling.
The hardware not only looks for an edge, but it also verifies that the
interrupt signal stays active for a certain period of time.
A common use of a hybrid interrupt is for the NMI (non-maskable
interrupt) input. Because NMIs generally signal major – or even
catastrophic – system events, a good implementation of this signal tries
to ensure that the interrupt is valid by verifying that it remains
active for a period of time. This 2-step approach helps to eliminate
false interrupts from affecting the system.
A message-signaled interrupt does not use a physical interrupt
line. Instead, a device signals its request for service by sending a
short message over some communications medium, typically a computer bus. The message might be of a type reserved for interrupts, or it might be of some pre-existing type such as a memory write.
Message-signalled interrupts behave very much like edge-triggered
interrupts, in that the interrupt is a momentary signal rather than a
continuous condition. Interrupt-handling software treats the two in
much the same manner. Typically, multiple pending message-signaled
interrupts with the same message (the same virtual interrupt line) are
allowed to merge, just as closely spaced edge-triggered interrupts can
merge.
Message-signalled interrupt vectors can be shared, to the extent that the underlying communication medium can be shared. No additional effort is required.
Because the identity of the interrupt is indicated by a pattern
of data bits, not requiring a separate physical conductor, many more
distinct interrupts can be efficiently handled. This reduces the need
for sharing. Interrupt messages can also be passed over a serial bus,
not requiring any additional lines.
In a push button analogy applied to computer systems, the term doorbell or doorbell interrupt is often used to describe a mechanism whereby a software system can signal or notify a computer hardware
device that there is some work to be done. Typically, the software
system will place data in some well-known and mutually agreed upon
memory locations, and "ring the doorbell" by writing to a different
memory location. This different memory location is often called the
doorbell region, and there may even be multiple doorbells serving
different purposes in this region. It is this act of writing to the
doorbell region of memory that "rings the bell" and notifies the
hardware device that the data are ready and waiting. The hardware
device would now know that the data are valid and can be acted upon. It
would typically write the data to a hard disk drive, or send them over a network, or encrypt them, etc.
The term doorbell interrupt is usually a misnomer.
It is similar to an interrupt, because it causes some work to be done
by the device; however, the doorbell region is sometimes implemented as a
polled region, sometimes the doorbell region writes through to physical device registers,
and sometimes the doorbell region is hardwired directly to physical
device registers. When either writing through or directly to physical
device registers, this may cause a real interrupt to occur at the
device's central processor unit (CPU), if it has one.
Interrupts provide low overhead and good latency
at low load, but degrade significantly at high interrupt rate unless
care is taken to prevent several pathologies. The phenomenon where the
overall system performance is severely hindered by excessive amounts of
processing time spent handling interrupts is called an interrupt storm.
There are various forms of livelocks,
when the system spends all of its time processing interrupts to the
exclusion of other required tasks.
Under extreme conditions, a large number of interrupts (like very high
network traffic) may completely stall the system. To avoid such
problems, an operating system must schedule network interrupt handling as carefully as it schedules process execution.
With multi-core processors, additional performance improvements in interrupt handling can be achieved through receive-side scaling (RSS) when multiqueue NICs are used. Such NICs provide multiple receive queues
associated to separate interrupts; by routing each of those interrupts
to different cores, processing of the interrupt requests triggered by
the network traffic received by a single NIC can be distributed among
multiple cores. Distribution of the interrupts among cores can be
performed automatically by the operating system, or the routing of
interrupts (usually referred to as IRQ affinity) can be manually configured.
A purely software-based implementation of the receiving traffic distribution, known as receive packet steering (RPS), distributes received traffic among cores later in the data path, as part of the interrupt handler
functionality. Advantages of RPS over RSS include no requirements for
specific hardware, more advanced traffic distribution filters, and
reduced rate of interrupts produced by a NIC. As a downside, RPS
increases the rate of inter-processor interrupts (IPIs). Receive flow steering (RFS) takes the software-based approach further by accounting for application locality;
further performance improvements are achieved by processing interrupt
requests by the same cores on which particular network packets will be
consumed by the targeted application.
Typical uses
Interrupts
are commonly used to service hardware timers, transfer data to and from
storage (e.g., disk I/O) and communication interfaces (e.g., UART, Ethernet),
handle keyboard and mouse events, and to respond to any other
time-sensitive events as required by the application system.
Non-maskable interrupts are typically used to respond to high-priority
requests such as watchdog timer timeouts, power-down signals and traps.
Hardware timers are often used to generate periodic interrupts.
In some applications, such interrupts are counted by the interrupt
handler to keep track of absolute or elapsed time, or used by the OS
task scheduler to manage execution of running processes, or both. Periodic interrupts are also commonly used to invoke sampling from input devices such as analog-to-digital converters, incremental encoder interfaces, and GPIO inputs, and to program output devices such as digital-to-analog converters, motor controllers, and GPIO outputs.
A disk interrupt signals the completion of a data transfer from
or to the disk peripheral; this may cause a process to run which is
waiting to read or write. A power-off interrupt predicts imminent loss
of power, allowing the computer to perform an orderly shut-down while
there still remains enough power to do so. Keyboard interrupts typically
cause keystrokes to be buffered so as to implement typeahead.
Interrupts are sometimes used to emulate instructions which are unimplemented on some computers in a product family. For example floating point
instructions may be implemented in hardware on some systems and
emulated on lower-cost systems. In the latter case, execution of an
unimplemented floating point instruction will cause an "illegal
instruction" exception interrupt. The interrupt handler will implement
the floating point function in software and then return to the
interrupted program as if the hardware-implemented instruction had been
executed. This provides application software portability across the entire line.
Interrupts are similar to signals, the difference being that signals are used for inter-process communication
(IPC), mediated by the kernel (possibly via system calls) and handled
by processes, while interrupts are mediated by the processor and handled
by the kernel. The kernel may pass an interrupt as a signal to the process that caused it (typical examples are SIGSEGV, SIGBUS, SIGILL and SIGFPE).
