 |
Description  |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to digital data processing apparatus in which two or
more processes which have access to one or more serially reusable
resources within the addressable storage of the apparatus are performed
concurrently.
2. Description of the Prior Art
The invention is applicable to data processing systems in which any or all
of the following conditions hold:
1. concurrent processes may be performed by one or by many computers having
access to the same addressable storage;
2. a controlling process or processes allocates the use of the computer or
computers in the system to some or all of the processes in the system
according to some scheme of priorities;
3. a process may either temporarily or permanently and either in the course
of its normal performance or in the event of interruption by some other
process, including input and output operations and machine and program
malfunction, either itself abandon or be forced to surrender the use of a
computer which was performing it;
4. a process, when it has temporarily either abandoned or been forced to
surrender the use of a computer, may be restarted using either the same or
another computer and either at the point where use of the computer was
lost or at another point in the program or programs being then executed;
5. a paging mechanism is implemented either by hardware or by both hardware
and programming whereby,
some or all of the processes in the system may address not only data,
including programs, in the main storage of the apparatus but also data
held on peripheral storage including magnetic disks and drums, and
upon reference by a process to data within its addressable storage but not
in the main storage of the apparatus that process may lose the use of the
computer performing it until such time as the paging mechanism has copied
the required data from the device on which it resided at the time of
reference into the main storage of the apparatus.
Terms and Expressions
In this description the term, process, is defined as a unit of work
requiring the use of a computer and therefore may denote what are
variously called jobs or job steps, tasks, exit processes, program
threads, or service requests. Processes may be identified by the extents
of storage allocated to them. At an instant each computer in a data
processing system may identify one process, termed the active process on
that computer which is the process being performed by that computer at
that instant. This identification of an active process is effected by the
values held in one or more registers which are component parts of the
computer performing the process. Processes may be said to compete for the
use of the computers in a data processing system this competition
entailing such effects as: interruption of one process by another, and
selection of one process rather than another to become the active process.
A scheme of process priorities in a data processing system may be defined
to determine of each pair of processes which, if either, may interrupt the
other, and which will be selected in preference to the other. A process
which may interrupt or which will be selected is said to be of higher
priority than another process which may be interrupted by it or which may
not be selected before it.
A process is to be distinguished from an operation which is a significant
modification of values held within a data processing system, and from a
program which is the embodiment of an algorithm serving to instruct a
computer to execute one or more operations for its active process.
The term, addressable storage, is defined as part or parts of a data
processing system which contains data, including programs, accessible by a
process without the process itself moving that data from one part or type
of storage to another.
The term, paging mechanism, is defined as a part or parts of a data
processing system which so manages the data held in the addressable
storage of processes that when a process attempts to access the data held
in its addressable storage but not in the main storage of the apparatus
the mechanism interrupts the process, initiates the movement of the
referenced data into the main storage of the apparatus, and permits the
interrupted process to resume use of a computer only when the data has
been moved.
The term, serially reusable resource, is defined as part or parts of a data
processing system which may be required for use in any process. It may be
used repeatedly either by one or by many processes but it may not be used
concurrently by two or more processes. If two or more processes have
access to a serially reusable resource, some mechanism is required to
ensure their serial use of it. An otherwise serially reusable resource may
be concurrently reusable with respect to certain operations in particular
those operations which access but do not modify the resource.
Among the serially reusable resources in a data processing system are
lists, queues, and chains, hereafter collectively termed lists. A list
comprises one or more extents of addressable storage commonly accessible
by two or more processes and containing such values than when a process
has located one extent of storage, termed the anchor, it may by
manipulating the values held in it and in the other extents of storage,
hereafter termed elements, locate each element in series. Each element of
a list, with the exception of one element called the tail, is succeeded by
another, no two elements having the same successor. Each element of a list
therefore, with the exception of one element called the head, is preceded
by another. A list may be singulary when it has just one element which is
both the head and the tail, or it may be empty when it has no elements.
By allowing some or all of the elements of a list to serve as anchors for
other lists, more complex structures may be constituted out of lists and
manipulated by similar algorithms.
A list may be said to be in normal form when it is not allocated to a
process. When a list is in normal form, the values in its anchor and
elements are such as to enable any process to locate each element as
described above and then to manipulate the list. Once a process has
started but has not completed an operation on a list it may be that
modifications made by the process to the values in the anchor and elements
would prevent any other process correctly locating each element or
correctly manipulating the list: a list in such a state would not be in
normal form.
Usage of Lists In Data Processing Apparatus
Resource management programs, including operating systems, data base
control programs, and timesharing and data communication monitors, are
largely occupied in manipulating lists in order to allocate resources of
the system to processes, to mark the release of resources by processes,
and to identify and control the processes holding resources. Many such
lists not only are themselves serially reusable resources but are used in
the control of serially reusable resources. For example, the IBM OS
ENQUEUE (IBM is a Registered Trademark of International Business Machines
Corporation) facility is used to ensure the serial use of data held on
magnetic media and itself employs lists of names such that the presence of
a name in a list indicates the allocation of the data associated with that
name to some process. Clearly, such a mechanism for the control of
serially reusable resources cannot upon pain of infinite regress be used
for the control of lists themselves.
Frequently encountered types of lists include chains of main storage
buffers either allocated to a process or available for such allocation,
queues of requests for the use of some resource such as an output device,
and chains or queues of processes using or waiting to use some resource
such as a program or a computer.
Current List Protection Mechanisms
Among the current methods of ensuring the serial use of lists are
programmed locking mechanisms, disabling, and serializing hardware
instructions. Locking mechanisms are of two kinds: suspend locks,
sometimes called latches or gates, and spin locks.
A lock is a switch indicating whether its associated serially reusable
resource is allocated to some process and possibly to which process it is
allocated. If its associated resource is allocated a lock is said to be
held. A process attempting to obtain a resource and finding the associated
lock held will, if it is a suspend lock, abandon its use of any computer
until the resource becomes available and the lock is released, or, if it
is a spin lock, continue to use the computer but in an unproductive way
looping within a program that intermittently checks the lock until it is
released.
Disabling is a hardware mechanism whereby a process prevents the computer
it is using being seized by some other process. It may be used with the
intention that a process running disabled should be the only process being
performed in a system but this intention is not achieved if either there
is more than one computer in the system or the process being performed
references data in its addressable storage but not in main storage thereby
permitting the paging mechanism and thereafter some other process to use
the computer. In current systems therefore it is ensured that all storage
reference by a process that is running disabled is main storage and in
systems with more than one computer disabling is used only as an adjunct
to other mechanisms.
Serializing hardware instructions effect the controlled modification of
small extents of storage. During the execution of such an instruction for
a process, no other process, even if it is being performed on another
computer, can modify the same storage. A serializing hardware instruction
effectively acquires, uses, and releases a small extent of serially
reusable storage in the course of its execution. Such instructions are
used by locking mechanisms to hold and release locks. A process executing
a serializing hardware instruction will either succeed in effecting a
modification of storage, or fail if some other process had modified the
same storage at or about the time of execution of the instruction.
Disadvantages and Limitations of Current Mechanisms
Locks suffer from these disadvantages:
Suspend Locks
1. force a computer to idle or to perform work of a lower priority than
that of the suspended process;
2. they require extra use of a computer to control the suspension and
resumption of processes;
3. if a paging mechanism is implemented, a process suspended on requesting
a held lock may have some of its data transferred from main storage to
peripheral storage and thereafter incur extra use of a computer and delay
in performance owing to the execution of the paging mechanism.
Spin locks avoid these disadvantages but at the cost of wasted computer
use. Locks of both kinds suffer from these disadvantages:
4. a process holding a lock may be delayed in its performance by a variety
of causes, including interruption by other processes and execution of a
paging mechanism, so imposing these delays on any other processes obliged
to be suspended or to spin on finding the lock held;
5. a process holding a lock may terminate abnormally without releasing the
lock, therefore mechanisms must be created to release locks under these
cirsumstances and extra use of the computer be incurred in executing these
mechanisms.
Processes holding or attempting to hold locks may be forced to use
disabling or other mechanisms in order to reduce the risk of suspension
while holding a lock. Disabling reduces the responsiveness of a system,
that is to say that when a process is running disabled no process of
higher priority may seize the computer performing it, thus the intention
of the priority scheme is thwarted.
Locking and disabling are not themselves list manipulation mechanisms; they
are merely methods of serializing the use of lists. The actual list
manipulation is performed by normal programming. For example, a list in
normal form, and not allocated to a process, might have an anchor
containing addresses of the head and the tail, and elements each
containing the address of its successor except that the tail might contain
the value zero. In adding a new element to the end of the list a process
might:
1. place the value zero in the new element, thus preparing it to become the
tail;
2. acquire the list by holding its associated lock;
3. place the address of the new element in the tail thereby making the new
element the tail;
4. place the address of the new element in the anchor.
Between (3) and (4) the list is not in normal form because the anchor does
not contain the address of the tail.
It is because during its manipulation a list is not in normal form that the
list is not concurrently usable but only serially reusable. Moreover,
should a process terminate while a list being manipulated by it is not in
normal form a recovery mechanism must be executed in order to restore the
list to normal form. One of the principal objectives in creating a list
manipulation mechanism is therefore to minimize the time during which
lists are not in normal form. This objective is achieved to a high degree
but within strict limitations by the serializing hardware instructions.
Serializing hardware instructions, such as the IBM System/370 Compare and
Swap (CS) and Compare Double and Swap (CDS) described in the "IBM
System/370 Principles of Operation", pp. 310-314, effect the conditional
modification of small contiguous extents of addressable storage. When a
process employs such an instruction to modify an extent of storage no
other process can modify the same storage during the execution of the
instruction. Consequently, if some operation can be executed on a list
using just one serializing hardware instruction, the list being in normal
form both immediately before and immediately after the execution of that
instruction, then with respect to that operation the list is effectively
concurrently usable.
Characteristically lists consist of several extents of storage at different
locations so that, in all but the simplest cases, two or more
non-contiguous extents of storage must be modified in order to execute
some operation and return the list to normal form, as in the example
above. As the serializing hardware instructions manipulate only small
extents of contiguous storage, operations on such lists are currently
executed under the protection of such mechanisms as locking.
It may be noted that a lock itself may be regarded as a degenerate case of
a list which can only be either empty or singulary, such a simple list
being manipulable by the serializing hardware instructions.
The advantages of the serializing hardware instructions are then that no
process can be delayed, thereby delaying other processes, nor terminated,
thereby requiring list recovery, while allocated a list manipulated by
these instructions.
The invention, by means of programming or the equivalent of such
programming implemented in hardware, extends the use of serializing
hardware instructions to manipulate complex lists with minimal cost in
computer use and minimal loss of responsiveness. It permits temporary or
permanent loss of a computer by a process at any time during list
manipulation without requiring the list being manipulated either to be
released from such a process or to be restored to normal form before being
manipulated by some other process. It permits the performance of a process
to be resumed either at the point where it lost the use of a computer or
at some other point.
The invention allows for the use of indefinitely many computers in a system
and for the execution of paging mechanisms. It never requires a process to
abandon the use of a computer nor to spin unproductively nor to disable
and it permits a process to suffer delay caused either by the intervention
of other processes or by the execution of a paging mechanism while
manipulating a list without imposing that delay on other processes
requiring access to the same list.
In sum, the advantages of the invention are just those of the serializing
hardware instructions, but it does not suffer their rigid limitations.
Analysis of Operations On Lists
In order to understand the invention, it is necessary to analyze the
operations executed on a list, these operations being the insertion,
removal, and modification of elements in the list.
The anchor and elements of a list are held in storage addressable by two or
more processes. Each process may also address storage exclusive to itself.
A process may be said to own both the storage exclusive to itself and any
elements which it has removed from a list.
Any operation executed on a list involves one or more transformations, a
transformation being the modification of the anchor or an element in a
list, which, according to the invention, is performed by means of a
serializing hardware instruction. An operation either about to be started
by a process or already partially executed may therefore be defined by an
agenda or ordered set of transformations.
At an instant a list is in some state in the sense that there are certain
values in the anchor, that certain elements are in the list, and that
these elements are in a given sequence and contain certain values.
The definition of an algorithm to execute a set of operations on a list
requires for each operation to be executed when the list is in each state
a specification of the change of state to be effected and therefore a
specification of the transformations required to that end. In current list
processing algorithms no such specification is available when a list is in
certain states, namely those states when the list is not in normal form.
A list may at an instant be such that either no operation or some operation
which may be termed an active operation is being executed on it. If an
operation is permitted to be executed on a list before the previously
started operation has been completed, that is to say, on a list with an
active operation, the integrity of the list may be lost. For this reason
lists are, in general, serially reusable. Current algorithms debar a
process not merely from starting an operation on such a list but from
modifying the list at all.
SUMMARY OF THE INVENTION
According to the invention there is provided a data processing system in
which one or more processes may attempt to execute an operation on a list
at a time when an active operation has been only partially executed on
that list, characterized by a mechanism that operates to ensure only one
active operation is permitted on a list at any instant, each process
attempts to complete the active operation before starting any other
operation, the active operation is executed by one or more of the
processes attempting to execute it, and all operations on a list are
executed serially irrespective of the number and priorities of processes
starting those operations.
BRIEF DESCRIPTION OF THE DRAWINGS
In order that the invention may be fully understood embodiments of its
principal concepts and some currently known mechanisms, and preferred
embodiments of the invention will now be described with reference to the
accompanying drawings, in which:
FIG. 1 is the key to the other figures.
FIGS. 2 and 3 illustrate possible formats for a First-In, First-Out Queue.
FIG. 4 illustrates formats for a currently implemented Last-In, First-Out
Queue.
FIG. 5 illustrates formats for an embodiment of the invention, First-In,
First-Out Queue,
FIGS. 6 to 8 illustrate formats for another embodiment of the invention, a
Last-In, First-Out and Priority Queue.
DESCRIPTION OF PREFERRED EMBODIMENTS
Annex 1 describes the terms and expressions used in the formal definitions
of algorithms.
Annex 2 formally defines an embodiment of a currently implemented
algorithm.
Annex 3 formally defines an embodiment of the invention, the First-In,
First-Out Queue whose formats are shown in FIG. 5.
Annex 4 formally defines an embodiment of the invention, the Last-In,
First-Out and Priority Queue whose formats are shown in FIGS. 6 to 8.
Annex 5 formally defines a partial embodiment of the invention,
illustrating a general algorithm, modifications of which could generate
algorithms for other disciplines of list manipulation.
In FIG. 1, an Anchor 10 is shown on the left. Two fields of the Anchor 10
are shown: Head 11 and Tail 12. Head 11 points to an element 13, shown
centre: the line 14 indicates this relationship. Tail 12 is null.
The centre element 13 points to (an element which points to . . . ), i.e.
is chained to, the element 15 shown on the right: the line 16 indicates
this relationship. Zero or more elements may lie within the chain. A
single field is shown in the first element 13: Next.
In the element 15 on the right Next is undefined--it may have any value;
this element also has a Priority value, marked as "t".
Serializing Hardware Instructions--Operation
A serializing hardware instruction is to be understood as operating in the
following manner:
the instruction has three operands, each of which is an extent of storage;
the first and second operands are private to the executing process, the
third operand is accessible by all processes that may execute the
instruction;
the values in the operands are called respectively the old, new and current
values;
upon execution of the instruction, all processes accessing the third
operand complete that access and are then not permitted to access that
operand until the instruction is complete; the old value is compared with
the current value, if not equal the instruction completes, otherwise the
new value is placed in the third operand, becoming the current value and
the instruction completes;
following the execution of the instruction, the process that executed it
can test whether it succeeded on an equal comparison or failed on a not
equal comparison and therefore whether it did or did not replace the
current value.
In the IBM System/370 the first two operands are general purpose registers,
the third is part of main storage; the Compare and Swap instruction
accesses four, and the Compare Double and Swap accesses eight contiguous
bytes (eight bit characters) in each operand. On a not equal comparison
these instructions load the current value into the first operand but this
feature is inessential and is ignored hereafter. The term SWAP is used
hereafter in reference to a serializing hardware instruction as described
above.
A SWAP is used in the following way: to update an extent of storage
accessible by many processes, copy the contents of that extent of storage
into storage private to the executing process thus establishing the old
value; calculate the required new value and hold that also in storage
private to the process--the extent of storage to be updated now contains
the current value, which may be the old value; and SWAP the new value into
the extent of storage to be updated, checking the old and current values
and leaving the current value unchanged if they are unequal.
If the SWAP fails on a not equal comparison, restart the entire algorithm
by again copying the contents of the extent of storage.
It will be seen that the essence of this method is to work on data in
private storage, unaffected by other processes, and then to update
commonly addressable storage just if the information on which the update
is based is still valid.
List Formats
A list consists of one or more parts each of which is a block, i.e.
contiguous extent of addressable storage namely an anchor and zero or more
elements. Each block may be divided into fields.
Each part of a list contains at least one pointer. A pointer is a field
used to contain either the address of another block, to which it is said
to point, or a value from which such an address can be calculated, or it
may for special purposes either point to the block in which it is itself
contained or contain a nominated value, generally zero, indicating that it
points nowhere: this nominated valud is called NULL and a pointer
containing it is called a NULL pointer.
An anchor generally contains a pointer to the first element, or head, of
the list and may contain a pointer to the last element, or tail, of the
list. Characteristically, such pointers will be NULL if the list is empty.
An anchor may contain other data such as a count of elements on the list
or a value associated with the control of serial use of the list.
An element generally contains a pointer to its successor and may contain a
pointer to its predecessor. Characteristically, such pointers in the tail
and head respectively will be NULL. An element may contain other data such
as priority values used in placing new elements in the list or a value
associated with the control of serial use of the list.
Generally, each list in a system has just one anchor, and each anchor is
associated with just one list. Elements however, may be moved from list to
list.
The various states in which a list may be found can be classified into
formats, thus a list which is singulary may be said to be in the Singulary
Format, so that this one format comprises any one of a large number of
states characterized by the list having just one element. The formats of a
list may themselves be classified according to whether they comprise
states which arise when no operation is active on the list or when an
operation is active on the list: such formats may be respectively termed
Basic Formats and Active Formats.
As provided in the invention, a list in an Active Format must indicate what
agenda of transformations remain to be performed in order to complete the
active operation. Such a list and its agenda may be said to be bound to
each other. In practice, it is convenient to set a value in the anchor to
show that a list has an active operation on it and therefore is bound to
an agenda. Unless the final transformation of the bound agenda modifies
the anchor such a switch may be left on when the operation is complete,
and in consequence the list may appear from its anchor to be in an Active
Format but examination of its elements may reveal that no further
transformations are required: a list in such a state may be called
pseudo-bound or bound to an empty agenda. Certain of the Active Formats of
a list comprise one of these pseudo-bound states. It is therefore
convenient to further classify list formats into those which are properly
Active in that they comprise a state with a non-empty agenda, and those
which are either Basic or comprise a pseudo-bound state: such formats may
be respectively termed Routed Formats and Unrouted Formats.
List Operations
The principal operations executed by list manipulation algorithms are the
placing of an element into a list hereafter called a PUT and the removal
of an element from a list hereafter called a TAKE.
The PUT operations include (but are not exhausted by) the following:
PUT HEAD--place an element into a list as the first element of the list;
PUT TAIL--place an element into a list as the last element of the list;
PUT by Priority--place an element into a list at a position determined by
priority values associated with it and with the other elements in the
list.
The TAKE operations include (but are not exhausted by) the following:
TAKE HEAD--remove the first element from the list;
TAKE Specific--remove a given element from the list.
In addition to these operations, complementary operations may be defined.
Certain processes, when they fail to remove an element from a list either
because the list is empty or because there is no suitable element on the
list, suspend their performance until an element is put into the list by
another process. In order to facilitate the resumption of such a suspended
process, a complementary element may be placed in the list when a TAKE
fails. This complementary element indicates which process should be
resumed when a normal element is placed in the list.
In an algorithm allowing complementary elements therefore a TAKE request
may be either conditional or unconditional: the former will result in a
take operation or a PUT Complement. A PUT request will result in either a
PUT operation or, if there are complementary elements in the list, a TAKE
Complement.
Generally, each list in a system is associated with a particular processing
discipline which determines which operations may be performed on the list:
a list restricted to PUT Head and TAKE Head is called a Last-In, First-Out
(LIFO) Queue;
a list restricted to PUT Tail and TAKE Head is called a First-In, First-Out
(FIFO) Queue;
a list restricted to PUT by Priority and TAKE Head is called a Priority
Queue.
Analysis of List Processing Operations--Current Limitations
Given the processing discipline to be applied to a list, the analysis of
operations on the list requires definition of: the Formats of the list,
the Changes Of Format effected by each operation, the agenda of
Transformations which constitute each operation, each of which effects one
Change of Format, and the Storage Accesses involved in each
Transformation.
The limitations of current methods of list manipulation may be demonstrated
by applying this method of analysis to a FIFO Queue. The Basic Formats of
the list are shown in FIG. 2. In principle, indefinitely many formats
could be defined for lists having zero, one, two and so on elements; in
practice, because the list is modified only at its ends, only one format
(FIG. 2C) is defined for lists having two or more elements.
This format is defined using the is chained to rather than the points to
relationship: if an element, say E, either points to another element, say
F, or points to an element which points to F, or points to an element
which points to an element which points to F, and so on, then E is said to
be chained to F. Formally, is chained to is the ancestral of points to.
The Active Formats of the list may be defined as shown either in FIG. 3A
and B, or in FIG. 3C and D: the former pair of formats require that a PUT
Tail first make the old Tail element point to the new element then make
the anchor point to the new element, the latter pair require these
transformations to be performed in the reverse sequence. Either method may
be selected.
The Changes of Format may now be defined, that is to say for each format
and each operation, if that operation is attempted on the list in that
format, to which new format, or series of formats, will the list be set.
These Changes of Format may be conveniently summarized in a table (here
the Active Formats shown in FIGS. 3A and B have been selected):
______________________________________
In Format:
Operation 2a 2b 2c 3a 3b
______________________________________
TAKE Head 2a 1 2a 2b or
2c2
PUT Tail 2b 3a-2c 3b-2c
3
______________________________________
Notes:
1 TAKE fails on empty list
2 Format with one less element
3 Format with one more element
In this table, formats are listed along the top line and operations down
the leftmost column, entries in the table indicate the resultant format or
sequence of formats. Notes show where an operation fails and where an
element has been added or removed (where there might be ambiguity).
It will be observed that certain entries have been left blank: these
represent the coincidences of formats and operations that a locking
mechanism would be required to prevent by delaying the process attempting
the operation. In effect a locking mechanism identifies normal form with
Basic Format.
From the Changes of Format the required Transformations may be defined:
for TAKE Head,
if Empty--no change, TAKE fails,
if Singulary--Anchor Head and Tail pointers set to NULL,
if Multiple--Anchor Head pointer reset to value of Head element Next
pointer,
if Post-singulary or Post-multiple--undefined;
for PUT Tail,
if Empty--Anchor Head and Tail pointers set to point to new element,
if Singulary or Multiple--Tail element Next pointer set to point to new
element, then Anchor Tail pointer set to point to new element,
if Post-singulary or Post-multiple--undefined.
The Storage Accesses required by each Transformation, can be classified
according to the addressability of the storage and the effect of the
access.
Extents of storage used in list manipulation include those in storage
addressable by only one process, hereafter termed private, and those in
storage addressable by more than one process, hereafter termed public.
Lists are held in public storage--their elements may be termed listed
elements. If a process executes a TAKE it thereby acquires an element
which was, but is now not, part of a list: such an element may be termed
an unlisted element. A process executing a PUT must have acquired the new
element to be added to the list, probably by a previous TAKE: such an
element will be an unlisted element before the execution of the PUT.
Each unlisted element therefore is owned by just one process but is in
public storage so the list manipulation algorithm must ensure that
processes other than the owning process do not modify an unlisted element.
The principal obstacle to a process modifying an unlisted element that it
does not own is that no pointer to the element is to be found in public
storage. On a TAKE Head for example, the only pointer to the head element
in public storage namely that in the anchor is overwritten in the
performance of the TAKE. Of course, some process may have copied such a
pointer into its private storage before the TAKE was performed: the list
manipulation algorithm must ensure either that such a copy is not made or
that if made it is not used to modify the now unlisted element. Generally,
once a pointer to an unlisted element is placed into some part of a list,
as by a PUT, that element becomes listed.
A Storage Access may either change, or simply reference the value held in
the storage:
the term transaction may be applied to a change of public storage, either
an anchor or a listed element, in any embodiment of the invention
invariably effected by a SWAP,
the term preparation may be applied to a change of an unlisted element,
generally in the course of a PUT,
the term examination may be applied to a reference (with no change) of
public storage, either an anchor or listed element,
private storage accesses are of less significance and will not require
separate designation.
As an example of this detailed level of analysis, the first transaction of
the PUT Tail operation can be defined as:
the preparation of the new element (an unlisted element) by setting its
Next pointer to NULL,
an examination of the Anchor to determine from its Tail pointer the
location of the Tail element,
the examination of the Next pointer of that element: copying it into
private storage as the old value for the next SWAP, and
the transaction of SWAPPing a pointer to the new element into the Tail
element Next pointer.
The presence of two or more transformations in one operation may
necessitate locking in current list processing algorithms, but even where
each operation can be reduced to a single transformation, for example, by
omitting the Tail pointer from the Anchor of a FIFO Queue and searching
down the elements to find the last one, it may not be possible to avoid
locking. Though only a single transformation is required, it contains
multiple examinations. The information gained from those examinations may
be incorrect by the time the final transaction is executed (the extreme
case being where the list has been emptied by some other process). Thus,
locking is currently required not only to protect lists in active formats
from manipulation by processes other than the active process, but also to
ensure the validity of information gleaned from the list by a process in
the course of a single transformation.
Some currently available list processing algorithms do ensure serial use of
lists by serializing hardware instructions alone but they impose one or
more of the following restrictions:
each operation is to consist of just one transformation;
no operation is to include multiple examinations;
certain operations, such as PUT Tail, are to be performed by just one
process on any given list;
each process is to be allocated a distinct priority and while a process is
performing an operation on a list no other process of lower priority is to
obtain the services of any computer in the system. This restriction can be
enforced only in single computer systems and requires that no paging
mechanism shall seize control of the computer from a process which is
performing an operation on a list.
The invention removes all these restrictions.
List State Control
Certain information about the state of a list must be available to any
process placing an element into or removing an element from that list. For
example, a process removing an element from a LIFO queue needs to know the
address of the first element in the queue and the address of the second
element in the queue, which it will be making the new first element. This
information is obtained by one or more examinations of a part or parts of
the list, preparatory to a SWAP or SWAPs.
It will be recognized that a SWAP fails when the value of the third operand
changes between the copying of the old value and the execution of the SWAP
Instruction. If a part of the list such as the anchor is updated by a SWAP
this update is performed conditionally upon the maintenance of the state
of the list insofar as the state of the list is reflected in the part
being updated. If a SWAP is used to manipulate a list, assuming that the
algorithm is otherwise correctly coded, it is therefore a sufficient
condition for the maintenance of integrity of the list that the checking
in the SWAP detect any state change that has occurred in the list since
the relevant part or parts of it were copied into private storage.
Ensuring that this condition holds may be termed List State Concentration:
the state of a list has been concentrated for a SWAP when that SWAP will
fail if the information on which it relies has changed since it was
obtained by examination of the list.
One mechanism which is currently used, and which is extensively employed in
the invention, to detect state changes is the incrementation of a modulus
in a part of a list, generally the anchor. A modulus is a number which can
be incremented to some maximum value depending on the length of storage
available for it and which returns to its minimum value when a process
attempts to increment it past its maximum. The use of a modulus can best
be seen by considering the following mistaken algorithm.
A LIFO Queue consists of an Anchor which contains just a Head pointer and
elements which each contain just a Next pointer, the Tail element's Next
pointer being NULL.
PUT Head is performed by:
pointing the New element's Next pointer to the Head element of the list,
and
SWAPPing a pointer to the new element into the Anchor's Head pointer.
TAKE Head is performed by:
identifying the Head element from the Anchor's Head pointer,
SWAPPing the Head element's Next pointer into the Anchor's Head pointer.
Appropriate modifications of these operations are used for empty lists, but
these are not relevant to the example.
The flaw in the algorthm can be seen by considering what might happen
during a TAKE.
Let the list consist of the anchor (A) and two elements (E and F), this may
be simply represented as:
A.fwdarw.E.fwdarw.F
the active process copies A so creating the old value namely a pointer to
E. E is now located and copied so creating the new value namely a pointer
to F. The process is now ready to SWAP the new value into A in order to
create a list consisting of just A and F:
A.fwdarw.F
but let the process now be interrupted before it executes this SWAP, and
let another process or processes become active and execute the following
sequence of operations:
TAKE--element E leaves the list--
A.fwdarw.F
TAKE--element F leaves the list--
which is now empty,
PUT a new element (G) into the list--
A.fwdarw.G
PUT the element E into the list again--
A.fwdarw.E.fwdarw.G
Let the interrupted process now resume and attempt to SWAP the new value
into the anchor. Despite the change of state of the list, the old and
current values are equal, both being pointers to E: the SWAP therefore
succeeds. The list should consist of A and G, E having been removed--
A.fwdarw.G
in fact consists of A, F, and those elements, if any, following F in
whichever list F has been placed--
A.fwdarw.F.fwdarw.?
and the integrity of the list has been lost.
Clearly the contents of the anchor in such a list do not adequately reflect
th | | |
