 |
Description  |
|
|
TABLE OF CONTENTS
Subject
Abstract of the Disclosure
Related Application
Background of the Invention
Objects of the Invention
Summary of the Invention
Brief Description of the Drawings
Environment
Description of the Problem
The State of Art
The New Approach
The Detection Mechanism
The Rules for Detection and the Principle of Interference
Consequences of the Basic Concept
Restoring Actions
Elimination of an Interference Loop
Elimination of Multiple Interference
The "Free Ride" Technique of Protection
The "No Dependency" Mechanism
The No Dependency Mechanism--Detailed Description
The General Protection Mechanism
Description of the Preferred Embodiments
General Discussion
Peripheral Subsystems
Input/Output
System Organization and Management
Control Unit
The Protection Mechanism
The No Dependency Mechanism
The Fundamental Check for Interference
Description of Flowcharts for Firmware and Hardware Embodiments of Detect
Software Embodiment of Detect
Firmware and Hardware Embodiments of Detect
Resuming the Waiting Process
The General Mechanism of Protection
The Generalized Detect
The Implementation of the Generalized Detect
RELATED APPLICATION
The following application is incorporated by reference to the instant
application.
"System for Interference Protection" invented by Mario Trinchieri, filed on
Dec. 30, 1974 and having U.S. Ser. No. 537,621 (now abandoned) and
assigned to the same assignee as the instant invention.
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates generally to computer systems and more particularly
to a system and method for controlling the interference due to the sharing
of resources (data) in a multiprogramming/multiprocessing environment,
both in local and distributed system architecture.
A resource is any element, such as a database, carrying information for use
in a process. A record, a field in a record, a page of records and a
message are examples of resources in this context.
2. Description of the Prior Art
Electronic computers have grown from first generation hardware
characterized mainly by vacuum tubes, to second generation hardware
characterized by transistors, to third generation hardware characterized,
in the main, by integrated circuits. Along with these different
generations of hardware there were different generations of software,
wherein first generation software was characterized mainly by machine
language, assemblers and subroutines, and second generation software was
characterized by high-level languages, monitors and macro assemblers.
Third generation software is characterized by operating systems, on-line
real-time systems multiprogramming systems, and data management systems.
The first generation hardware in combination with first generation
software, and also the second generation hardware in combination with
second generation software were primarily oriented toward batch processing
where jobs were executed one at a time. The third generation of
hardware/software systems are also batch process oriented; however,
because of the advent of multiprocessing, several jobs may be executed in
parallel rather than serial and may compete for the utilization of the
same database.
The fourth generation system will be capable of satisfying even higher
parallelism among the activities. Real time operations, that impose
constraints on response time requirements, and the necessity of adequate
performance/cost ratios impose a multiprogramming/multiprocessing
environment where the risk of interference among the activities is very
high. Proper control of interactions among processes is vital. Some
interactions are desired and planned, like the ones based upon the
exchange of messages, but some are purely accidental and may derive from
unplanned events, like the shared utilization of a record, and they must
be carefully controlled. Hardware and software will cooperate in this
operation to insure safety at the minimum overhead cost. The fourth
generation system is also characterized by distributed system
architecture, where processing and data are distributed among physically
separated computer nodes.
Processing in the first generation hardware-software computer systems was
relatively straightforward: for each job or transaction a program
generally ran with little or no interruption until the job or transaction
was completed. Many jobs such as the compilation and execution of a high
level language program could and did run as a single uninterrupted
process. In this context a process is a concept implying the execution of
some activity and should not be confused with the concept of a program or
procedure which is the description of an activity and can be used by one
or more processes at the same time.
The concept of a process as the basic unit for a
multiprogramming/multiprocessing environment is developed later. In such
an environment many users are demanding service simultaneously and it is
natural to conceive of multiple processes competing for resources within
the computer system. Each process consists of the execution of a program
(i.e. an ordered collection of instructions) on the basis of data and
other pieces of information in order to perform a job or some part of that
job. Where many such processes are demanding simultaneous attention from
the system, the task of controlling and allocating resources (data) to
such processes, particularly in view of the requirements of fourth
generation systems, becomes extremely complex.
Generally the processes are controlled by an operating system which
implements primitives issued by the process and enforces a general
mechanism of control. The control for the sharing of resources can also be
implemented as a separate entity.
At any rate, the conventional techniques of process control introduce only
partially efficient mechanism of protection against interferences of one
process from another. Beside being confined inside subsystems (the
Database Manager in general) instead of considering the system as a whole,
they operate in a conservative manner. They do not intervene when the risk
of incorrect results is detected, but they enforce conservative
limitations which allow only a few sequences of access that are known to
be safe.
This way of reasoning has created methods based upon preassignment and
locking of resources. This basic concept is the one of assigning a
resource to one process user at a time, until completion of the process.
More refined mechanisms limit this "exclusive" mode to the case where the
resource is going to be modified by the process, and allow a "shared" mode
of access to a resource when it is going to be "read only" by the
process-users.
None of these mechanisms offers the maximum of accessability that could be
theoretically granted, and present some inherent drawback, as unnecessary
deadlocks, and/or may imply not trivial overhead.
These limitations did not stem out of lack of interest for an efficient
manner of getting higher throughput from the system, but rather from an
inadequate knowledge of the interference mechanism itself. What is needed
for fourth generation systems is a firmware/hardware mechanism which
efficiently controls or monitors the activities, provides processes with
protection from other processes and allows high level of sharing and
therefore of productivity.
OBJECTS OF THE INVENTION
It is a primary object of the invention to provide improved apparatus for
the interference protection among processes in a
multiprogramming/multiprocessing environment with local or distributed
system architecture.
It is another object of the invention to provide a family of systems and
methods for protection against interference and associated provisions
against additional inconveniences like secondary aborts, excessive space
requirements for temporary storage of uncleared version of the resources,
etc.
It is a further object of the invention to provide a computer system with a
family of hardware/firmware instructions designed to reduce overhead and
increase efficiency in the implementation of the above-mentioned new
systems and methods.
It is an additional object of the invention to provide mechanisms and/or a
set of hardware/firmware instructions to be utilized in any environment or
application where the requirements or the mathematical models are similar
to the ones discussed in conjunction with the preceding objects.
SUMMARY OF THE INVENTION
The foregoing objects are achieved according to one embodiment of the
invention and according to one mode of operation thereof by providing a
data processing system with an organized set of recorded observations and
a special type of instruction to operate on it, and executing a procedure
that utilizes such instruction to ascertain the legitimacy for a process
to utilize a resource (e.g. access a record). The request to utilize a
resource for a specific operation can be approved and, in some instances,
delayed or redirected or rejected. Rejection initiates appropriate
restoring actions.
More precisely:
The mechanism of protection monitors every request issued by any process,
observing the relationships (precedences) that the request implies if
approved.
The relations are tested against the already approved and recorded
relations.
If they fit into the preexisting picture the new relations are also
approved and recorded. The request is therefore approved for immediate or
delayed execution.
If they imply instead an absurdity i.e., a loop of precedences or
equivalent inconsistency, the mechanism suggests the appropriate
redirection of the request or a corrective action to take place.
Variations of the mechanism include the way the precedences are recorded,
which information is assumed as a basis for the detection, the mechanism
used to recognize the precedences and the formation of a loop among them
or the existence of equivalent inconsistency.
Other main variations include the addition of collateral protections and
the type of action that is suggested for recovery.
BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 indicates the basic elements of the environment where the invention
applies.
FIGS. 2, 2a, 2b, 2c, 2d, and 3 illustrate examples of interferences.
FIGS. 4, 5a, 5b, 5c, and 5d provide a graphical representation of
relationship among processes.
FIGS. 6a and 6b present the Matrix of Relations (a tool for the invention)
and a corresponding graph.
FIG. 7 shows the "No Dependency" mechanism of protection, a preferred
embodiment.
FIG. 8 shows the generalized layout of the mechanisms of protection based
upon the invention.
FIGS. 9, 10, 11, 12 and 13 show the basic components of a computer system
and details of various prior art subsystems utilized by the invention.
FIGS. 9a, 9b, and 9c illustrate the Utilization Tables, the Matrix of
Relations, and the Affected Resource Lists, basic tools of the invention.
FIGS. 14 and 15 show variations of the "No Dependency" mechanism of the
invention.
FIGS. 16a and 16b show two implementations of the basic DETECT function of
the invention.
FIGS. 17a and 17b illustrate two hardware implementations of the DETECT
instruction of the invention.
FIGS. 18 and 18a show a preferred embodiment of the releasing mechanism of
the invention.
FIGS. 19a and 19b show two implementations of the DETECT (p,q . . .)
function of the invention.
FIGS. 20a and 20b illustrate two hardware implementations of the DETECT
(p,q . . .) instructions of the invention.
GENERAL DISCUSSION OF BASIC CONCEPTS
1. Environment
An environment is utilized (e.g. a computer system) where n independent
activities (e.g. processes) are simultaneously executed. The activities
may utilize (e.g. read or write) some out of m resources (e.g. database
elements as records, pages, etc.) to perform their tasks.
The nature of the activities is such that if they were executed one at a
time in any sequence till completion, the fact that a resource has been
utilized by more than one activity is not an "interference".
The activities, i.e., processes, which are considered throughout the
specification are independent, i.e., they may be executed in any sequence
whatever in a uniprocessing environment.
When, instead, as in this environment, the activities are carried on with a
degree of simultaneity, the fact that a resource can be utilized by more
than one activity may lead to wrong results. The system, therefore, must
offer the necessary protection against the occurrence of such an
interference.
The theoretical nature of this interference has been disclosed by the
inventor in a paper entitled, "On Managing Interference caused by Database
Sharing", by Mario Trinchieri. (Published by Alta Frequenza, November
1975.)
This leads to an entirely new class of mechanisms of protection.
Here and in the referred to above, article the new concept of interference
is described. The implementation of some leading apparatus of this new
class is also presented.
2. DESCRIPTION OF THE PROBLEM
The basic elements of our environment are those indicated in FIG. 1. The
Integrity System I.S. is the element where the protection mechanism
resides.
To describe the problem let us first assume that the activities (we will
call them processes, or more precisely process-phases, with reference to
the computer environment) were executed one at a time. They will access
some resources to read, write or update an information. Since one process
is always terminated before another process is initiated, there is no
interference among them. No mechanism of protection is required.
EXAMPLE
Process a accesses a record containing the balance (100$) of the account of
Mister X, to read it. (Step 1). Then process a computes the new balance
resulting from a withdrawal that Mister X performed (100-10=90$). (Step
2). Finally process a accesses again the record to update it, i.e. to
write the new balance (90$) on it. (Step 3).
Process b, then, is activated which performs another operation (a deposit)
on the same record of Mister X. It reads (90$) (Step 4), it computes
90+20=110$ (Step 5), it writes 110$ (Step 6).
Process a and process b do not interfere.
The sequence of events is illustrated in FIG. 2, Case A.
Another perfectly legitimate sequence of actions may be the following
sequence: process b is executed first, and process a is executed second.
Case B of FIG. 2. Let us now suppose that from the previous uniprocessing
mode, we move into a multiprocessing mode: process a and process b are
simultaneously active.
The interest for such a mode is dictated by the higher utilization of the
system and therefore the higher throughput that can be achieved in
general, provided a mechanism of protection against interference exists.
To illustrate the risk of interference, let us consider again the example
case.
Process a and process b both read the old balance before any update,
perform their computations on this basis, and write down their
conclusions. The first of the two writings (case C of FIG. 2) is
overwritten by the second (as in any case must happen) but the final value
is wrong.
The interference occurs because the two processes happen to operate on the
same old balance. Since this event has only a marginal probability to
occur, the simultaneity of operation is in general useful, provided cases
like the above one are taken care of by a built in protection mechanism.
The interference that the example illustrates for the case of two processes
and one record can involve in general any number of resources and
processes in more or less complex patterns, as it will be discussed later.
The mechanism of protection must be able to recognize any of them and
provide for adequate actions.
3. The State of Art
The mechanisms of protection implemented so far are usually based upon
locking or assigning resources to the processes. Their effectiveness could
be explained on intuitive basis.
For instance: The resources needed by a process, if known in advance, are
assigned (preassigned) to that process and made available to other
processes only when the owner process is terminated. Alternatively, the
resources are assigned to a process as soon as the need for their
utilization by the process becomes evident.
In the example of the previous section (Case C), the resource, once first
utilized by process a, would have been assigned to process a upon
completion, and process b could have only waited.
These assignments and locking procedures can provide protection for
multiprocessing environments; however they do not provide all the sharing
capability that a system could afford, and they are not immune from other
drawbacks.
To illustrate this point let us consider another example. Process a wants
to read a resource; process b wants to read the same resource and update
it. FIG. 3.
A method of "exclusive assignments" locks the resource to the process that
first reads it. The other process cannot access it and has to wait until
the first process is terminated and the resource released. This results in
a loss of time for the waited process.
Another method can be devised that allows a resource to be in "shared read"
mode or in a "shared read/exclusive write" mode.
This method will allow the first two reads and permit process b to write
only when process a is terminated. This may or may not result in a delay
of process b, depending upon the relative timing.
In any case the delay is unnecessary because the reading by a would not
have caused interference.
The methods proposed (see next section) recognize this fact.
4. The New Approach
The basic idea is founded upon the observation that, by definition, there
is no interference in a uniprocessing environment (see Section 2).
Therefore if we can assure that in a multiprocessing environment the
resources are accessed by the various processes in a sequence that could
have occurred in a uniprocessing environment, interference cannot occur.
In more formal terms, we may define an interference as "the occurrence of a
sequence of accesses that could not have occurred in a non-shared (or
uniprocessing) environment and that cannot be shown to be equivalent to
one of them".
The addition of the "equivalence" clause derives from the fact that what
really matters is not the actual sequence of accesses but the data
involved in those accesses. In particular it is absolutely irrelevant that
a resource is read first by a process a and then by b or the other way
around, provided, of course, the resource had not been altered in the
meantime.
To clarify this basic aspect, let us consider the example of Section 3.
(FIG. 3).
The sequence of case 1 is typical of a uniprocessing environment, when
process a runs first, followed by b when a is terminated. The sequence is
considered therefore safe by the new approach, and the corresponding
mechanism of protection permits it to happen without any delay for process
b, no matter whether a is already terminated or not.
The sequence of case 2 cannot have occurred in a uniprocessing environment
because either b had to follow a or viceversa. Nevertheless the new
approach recognizes the fact that a would have read exactly the same
values if a had read before b; that is, the new approach recognizes that
the sequence of case 2 is equivalent to the one of case 1.
Therefore the mechanism of protection considers it safe and allows the
accesses to occur without delay.
Let us now examine the cases illustrated at Section 2 (FIG. 2).
A sequence like the one of cases A and B is approved because it is
consistent with a uniprocessing environment. A sequence like the one of
case C cannot occur in a uniprocessing environment where only cases A and
B are possible, nor can it be considered equivalent to case A or B because
the data involved are different.
Therefore the mechanism intervenes in such a case C to protect the
integrity of the results.
We have already examined the actions of conventional methods with reference
to the example of Section 3.
The actions resulted in unnecessary delays.
It is interesting to note that in this case C of FIG. 2 their actions,
instead, would have resulted either in a convenient delay of process b or
in a deadlock (deadly embrace) situation if they had allowed both
processes a and b to read. This latter situation (deadlock) arises from
the fact that the resource, already assigned in a shared reading mode,
cannot be further utilized by a nor by b to write: both processes get
caught in a situation without a way out.
5. The Detection Mechanisms
It should be clear by now that whereas the conventional mechanism of
protection operates by limiting the accessibility to the resources and
therefore in general the throughput of the system, the new proposed
mechanisms pose no limitation but continuously monitor the actual
utilization of the resources and intervene only when they detect a
dangerous pattern.
The detection mechanism is the key of these protections.
The basic concept has been presented in the previous section:
"an interference is the occurrence of a sequence of accesses to an
information base by processes executing in the computer system that could
not have occurred in a non-shared case i.e. where processes are executing
sequentially and that cannot be shown to be equivalent to one that could
have occurred in a non-shared case."
This concept is implemented by establishing which "precedences" in time
among the processes are revealed by the actual sequence of accesses to the
resources, and by rejecting the occurrence of a loop among precedences.
A loop of precedences is obviously absurd because it implies that a process
precedes and at the same time follows another process.
To clarify this point let us consider again the examples of FIG. 2.
Case A reveals a situation where the actions of process a entirely precede
the actions of process b. (See FIG. 2a). No loop. Actions are legitimate.
Case B reveals an opposite but still legitimate sequence. (See FIG. 2b.)
Case C. Since process a writes on the resources after b reads it, it is
obvious that, up to that moment, the precedence "b precedes a" has been
established. (See FIG. 2c.)
As soon as process b tries to write on it, the additional relation "a
precedes b" must be recognized and added to the diagram. (See FIG. 2d.)
This would create a loop that cannot be tolerated by the mechanism of
detection because of its absurdity.
The example refers to a two-process, one-resource situation. The general
case deals with n processes and any number of resources. The corresponding
diagram has one node per process (FIG. 4) and continuously evolves
reflecting the activity in the system.
Some nodes can show many relations, some can have no relations at all.
A variety of mechanisms of protection can be built around the basic
concept. Some implementations have been described in an article by the
inventor entitled "On Managing Interference by Data Base Sharing" and
published in ALTA FREQUENZA, N. 11, Volume XLIV-1975-da, page 351E-641A,
page 360E-650.
They all share a common feature: the search for a loop or equivalent
contradiction.
6. The Rules for Detection and the Principle of Interference
In the example of the previous section the precedences were introduced on a
rather intuitive basis. The rules upon which precedences can be
established can be described as follows:
When a process a reads a resource that was written by a process b, the time
sequence "a follows b" is noted. (See FIG. 5a.)
When a process a writes a resource that was previously read or written by a
process b, the time sequence "a follows b" is noted. (See FIG. 5b.)
When a process a reads a resource that was previously read by a process b,
the time sequence "a follows b" is not noted because the results do not
change if the time sequence is reversed.
Based upon these rules an unacceptable event is: an event that contradicts
previously established time relations, namely: an event that closes a
loop. (See FIG. 5c.)
In a more formal way the principle of interference is as follows:
"When independent processes, simultaneously executed, share resources (e.g.
data),
a process that reads a resource is said to follow the process that wrote
it.
a process that writes a resource is said to follow the process that read or
wrote it.
If the set of precedences so established forms a loop, an interference has
occurred that involves the processes joined in the loop."
It may be useful to note, for any practical implementation of the new
concept, that it makes the mechanism of protection more advanced but not
necessarily more complex. As a matter of fact the application of the
concept requires to list the
processes-users in the system and
the type of use (read/write), for each resource (each list contains only
the non already cleared processes)
This information is fundamental to any mechanism. Obviously, mechanisms
that allow very limited sharing have degenerated or very short lists.
The detection of the precedence loop, that is peculiar of this new class,
is not by itself more complex than a correspondent detection of deadlocks,
necessary in conventional mechanism.
As a matter of fact the new class can be implemented via the embodiment of
a new introduction, one macroinstruction or a small sequence of
instructions, in software, firmware or strictly hardware, depending upon
the desired degree of tradeoff between hardware and software.
For a generalized interpretation of the new concept it is useful to note
that the expression "a process reads or writes a resource" applies to any
activity that operates on a resource deriving information without altering
it, or adding information and altering it.
7. CONSEQUENCES OF THE BASIC CONCEPT
The basic concept provides a basic understanding of the interference
phenomenon and puts in a unique light all the mechanisms for controlling
shared accesses to the resources. It may be used both to suggest a new
mechanism and methods of protection and to check the validity of the
existing ones.
A protection mechanism is a system capability that permits the simultaneous
execution of processes that have been conceived as if they were executed
in a uniprogramming environment where the risk of interference is absent.
Two basic approaches can be followed to provide the necessary protection
apparatus:
1. Allow free access to the resources, but monitor the actual sequence of
operations.
2. Put properly chosen limitations on the freedom of operations so to
exclude unwanted patterns.
To these two, a third class of solutions must be added:
3. Combine the monitoring of the first approach with the impositions of
restrictions as in the second.
Absence of a general criterion on how and what to monitor suggested the
second approach for the conventional methods (assignment or locking
methods). The basic concepts of interference provides the monitor for the
first and the third approaches. As examples of the first and third
approaches (the new methods) we indicate the "Free Ride" (a Shared
Read/Shared Write method) and the "No Dependency" (a Shared Read/Exclusive
Write method), described herein infra.
It is important to note that the imposition of restrictions, typical of the
third class, leads to the introduction of the "Wait" status as a possible
outcome of the mechanism, beside the approval for continuation or the
order for a restoring action.
The third class encompasses the first which becomes a sort of subclass.
It is therefore to this (third) class that the invention to be taught infra
mainly refers. The class, in its broad definition, includes any
combination of the monitoring action with the imposition of extra
restrictions for whatever reason.
The principle of interference establishes the correctness of a "go ahead";
the additional restrictions may operate to reduce recovery, space
requirement, etc. The "No Dependency" is a special case of this class and
is discussed in section 10. The general case is presented at section 11
and later on.
8. RESTORING ACTIONS
To discuss a protection mechanism completely, it is necessary to describe
also the course of action that the mechanism follows when an interference
occurs.
Assuming that the last access, the one that closes the interference loop,
has not yet been actuated, there are two possible alternatives:
1. Avoid that access.
2. Eliminate some time relations so as to avoid the interference loop.
The first alternative does not mean to change the request issued by the
process, which would imply a capability that we generally cannot expect a
process to have. It means to satisfy the request with a different access.
This is the case of a request to read. If it is possible to access a
previous version (edition) of the same resource, the nonacceptable time
relation is reversed and becomes acceptable (solid line P.sub.1
.fwdarw.P.sub.2 of FIG. 5d instead of dashed line P.sub.2 P.sub.1). The
reader, which was not allowed to "follow" the writer of a certain version,
is now requested and allowed to precede the same writer.
Note that this "historical" reading, although highly desirable, is not a
feasible solution in certain areas of implementation.
The second alternative is implemented by aborting one or more processes.
Various methods can be suggested to decide which process or processes to
abort, since more than one solution is generally possible. The next two
subsections propose and discuss very simple methods offering a
quasi-optimal solution and more sophisticated algorithms.
Elimination of an Interference Loop
Let us establish some basic points for the discussion.
1. We assume that a previous edition also called a "before" edition of a
resource is saved when a process first modifies it and is kept until the
process that modified it has been cleared. A process could be cleared when
it is successfully terminated and all the processes on which it depends
have also been cleared. Since it may have interfered with some other
process and we want to retain the option of aborting it, if convenient, we
prefer to clear a process "when it is successfully terminated and all the
processes it follows have also been cleared." It should be noted that a
stack of previous editions can exist for a resource. Therefore the system
can abort selected processes and restore the modified resources. Lack of
this capability would have required indiscriminate rollback of all
processes and resources to some convenient checkpoint.
2. To eliminate an interference it is immaterial which process or group of
processes is aborted (primary aborts), provided the suppression opens the
loop.
3. Primary aborts may cause other processes to abort (secondary aborts) if
the validity of the latter processes depends upon the correct termination
of the former.
4. The damage associated with the abortion of different processes may be
judged to be different and a figure of weight defined for each process,
based upon such factors as the number of resources that have been
modified, the existence of messages already exchanged with the external
world, priorities, and so on.
It is now obvious that the following method can be proposed to eliminate an
interference loop:
1. Any process or group of processes which when aborted opens the loop i | | |
