GB2470809A - Control of concurrent operations in real time systems - Google Patents

Abstract

The invention provides methods and apparatus for detecting when concurrent operations (threads) are complete, avoiding the need for thread waiting thus reducing the coupling (communication) between threads. Concurrent operations (threads) share control data. Each operation, having run to completion, initiates a test of the control data to determine whether it should initiate a further task. The control data may be a thread counter to identify the last thread to complete. Initially, the counter may be set to the number of threads. Upon completion, each thread reduces the count by one and tests whether the resultant count is zero. Conditional initiation is supported; one test, and only one, will detect that counter value is zero and will initiate the further task. Alternatively, the control data may consist of a set of flags, one for each operation. When complete, each operation initiates a test to set a flag within the control data, one flag dedicated to each operation. The operation then tests whether all flags are set, initiating a further task if, and only if, all flags are set. The invention is based on a theoretical model descriptive of knowledge generation in physical systems.

Description

Control of concurrency in real time systems.

Introduction to the invention.

The invention concerns equipment in which logical operations are performed conculTently, providing methods of detecting when all are complete. CulTent methods employ cooperative communication between processing threads, one thread chosen in advance to be the last to terminate and required to await completion of all others; instead the invention provides symmetrical methods of detecting when all concurrent operations (threads) are complete, the need for waiting avoided. It also extends methods of concurrency control claimed in the inventor's British patent number GB2398 140. The invention forms part of an approach to software engineering founded on a theoretical model descriptive of knowledge generation in physical systems and impacting on all phases of projects. Claims embrace both methods and equipment.

A paper, which now follows, sets out the theoretical model, identifying some key implications for software engineering. The theory is shown to justify the methods claimed.

1. Introduction.

The long-established technology of signalling, in which facts are derived from physical signals according to a chosen convention, provides the sole means of communication within physical systems. The paper proposes that human descriptions of physical behaviour conform to structural rules necessary for signalling; signalling theory, in extended form, then provides a foundation for information science and technology. If valid the model applies to all physical sources of knowledge including those controlled by software; it implies inescapable constraints which in turn imply a need to reform software engineering methods. The author appears to be alone in exploring this form of physics-based model; however the entity life history model [Sandon and Zalewski 2006] has described the histories of "entities" in terms of the sequences of events occurring within their lives. Another paper by this author [Young 2009] covered the proposals at a more formative stage.

The model is explained according to Newtonian physics, the author not qualified to assess the relationship to its successors. The data flow architecture [Dennis 2008] uses a feature of the model proposed; however other methods, among those given under Section 3 below, may be preferable. The scientific method is adopted, the author proposing the model for appraisal by others; if accepted it will, like other scientific models, be treated as valid while its predictions remain consistent with experience. The relationship of the model to current thinking is outside the intended scope of the paper and is touched on only to aid explanation.

The hypothesis reflects experience in the physical design of knowledge-generating mechanisms: such a mechanism can acquire information only by testing physical signals. In computers the signals are, during measurement, either well above or well below the threshold used to distinguish "ones" from "noughts", thus avoiding errors. A physical test, performing measurement and computation, employs the levels of its input signals to generate the levels of its output signals; as generation cannot occur instantaneously testing, of the level of any input signal, must last for a finite period of time thus imposing limits on computation speed.

Another factor, the unwanted thermal noise inherent in signalling systems, also suggests that test-duration must be finite: noise power tends to infinity as duration tends to zero. Thus in any mechanism knowledge is represented only by physical signals each of which must last for a finite period of time; events, thought of as occurring without the passage of time, cannot be sensed by direct, instantaneous physical testing and cannot therefore have a role in any physical model.

Sensing, of physical signals generated by a test, can be achieved only by a further test or tests. Since a signal can be tested only while it exists it follows that a test must provide, for each set of signals communicating a fact true of the tested behaviour, a physical signal to indicate whether that signal-set has yet become accessible to testing; a potential reader must be able to determine whether the physical preconditions, necessary for valid reading, have yet occurred. Signalling conventions must provide for this information to be signalled by tests, each reader required to initiate an appropriate test at an appropriate time.

The treatment starts by identifying properties essential to systems in which logical operations are performed, constraints on the form of such systems explored later.

The model is based on the hypothesis that knowledge of physical behaviour originates only from the classification of physical phenomena by physical tests, a phenomenon occupying both space and time. A fact, expressed according to a language, is known to be true of a phenomenon either if a person declares it to be true or if a test, identified by that fact, succeeded when applied to that phenomenon. A phenomenon occupies both space and time; one phenomenon may "contain" others, establishing hierarchy in descriptions of behaviour. A test is itself a phenomenon.

A Prolog-like notation is used in the following account, accompanied by explanatory comment.

2. The model.

2.1 Containment.

A region of space-time is said to be closed if every pair of position/time points within it can be connected by at least one line which lies wholly within the region. A phenomenon occupies a set of one or more closed regions. Thus a phenomenon may consist of an episode or of a set of episodes, of a physical system or of a set of systems existent within some period of time, or of both.

An outer phenomenon is said to contain an inner phenomenon if at any time which may be chosen within the life of the inner the space occupied by the inner lies within that then occupied by the outer. The physics is Newtonian.

contains([P, P1).

contains([P, Q, R]).

contains([P, ([U, R], [V, RI)]).

A phenomenon named P contains itself A phenomenon named P contains another named Q which contains another named R, the order of listing denoting the hierarchy. P contains U which contains R and also contains V which also contains R; direct communication and interaction between U and V are provided only by phenomena such as R. 2. 2 Facts and tests.

A phenomenon is said to be of a class F if a fact F is true of it; knowledge that a fact F is true of a phenomenon named Q is generated in Q only if a test is performed within Q which derives the fact test(F) from the fact F, the truth of test(F) implying the truth of F. Identifiers

I

such as F are assigned by a person and apply to tests of a class specified by that person; a person's knowledge of physical behaviour originates from that person's application of physical tests. If a fact F is true of Q then Q is said to signal the truth of a boolean F. Signals within Q indicating the truth of a boolean F may be short-lived. Having become true of Q a boolean remains true of Q in perpetuity; however its truth may be accessible only to a test or tests beginning during a restricted period of time.

fact(F, Q):=fact(test(F), Q).

This mechanism of knowledge-generation is proposed to describe any Newtonian model of a physical system. Within a physical system knowledge is generated as time advances, future behaviour inaccessible to past testing.

Knowledge of future behaviour derives only from knowledge of past behaviour and of the rules which have governed it.

Where for example a phenomenon consists of the use of a thermometer and yields a particular reading then all this information might constitute the fact test(F), F stating that reading and indicating that it is the measured temperature. Again where a phenomenon consists of the use of equipment to derive a result by processing a list of numbers represented within it then all this information, including the result, might constitute the fact test(F) while F identifies a set to which the list of numbers belongs. In the most fundamental of examples a clock may be regarded as performing tests each containing two ticks, one starting when the first tick starts and one ending when the second tick ends.

fact((F1,F2), Q):=fact(F1, Q), fact(F2, Q).

The fact (F 1 and F2) is known to be true of Q if the facts F 1 and F2 are both known to be true of Q. Knowledge of a phenomenon consists of a set of facts all of which are true of that phenomenon.

A test F is equivalent to a pair of tests G and 5, the genus G specifying all that is known about the test other than its outcome 5, S known to be true when a subsequent test S succeeds.

Thus G identifies a particular class of test equipment used within a particular class of environment. Knowledge of G implies knowledge of the permissible values of S. Where S has only one permissible value, the test G always succeeding, then tests F and G are equivalent.

The following rule declares that a fact F, true of a phenomenon Q, remains inaccessible to tests performed within Q until at least one boolean, identified as port(N, F), has become accessible to such tests and has become true, the port now open. N identifies a particular port among those which, when open, allow access to F. not(accessible(F, Q)) : = fact(test(F), Q), not(fact(port(N, F, open), Q), accessible(port(N, F,_), Q)).

A fact-set is now defined as a set of booleans which becomes accessible when a boolean, outside the set, becomes true. This boolean is termed a port and is open when the boolean is true. A port is closed when it first becomes accessible to testing; a test, having made a new fact accessible, sets open the port or ports which control access to it, these actions necessary to indicate when reading of a fact-set may commence, these ports accessible to readers before they open. A fact-set may contain ports and may thus contain fact-sets accessible through those ports; it may grow in extent as time advances, ports opening to give access to new fact-sets. New fact-sets become accessible only through ports within fact-sets which have become accessible. Figure 1 shows a fact, an instance of a fact-set. Booleans, both true and false, are represented by squares each representing a permitted outcome of a test; black-filled squares denote booleans which have become true. These squares are contained in rectangles each denoting a fact-set. Arrows connect ports, already open, to fact-sets accessible through them.

Where signals indicating the truth of a fact F are volatile its truth can be tested only by tests initiated when a port, indicating that F has become accessible, opens. A model of a knowledge-generating mechanism is invalid if it allows a test to be initiated too late to sense the intended boolean; for that reason a port, once opened, remains open in the model proposed; the states, of booleans other than ports, never change.

A prime fact-set is a fact-set in which: exactly one boolean is true in any instance of it, each boolean corresponding to a particular fact, and no subset is accessible without first accessing the set.

A fact-set may be represented as a set of prime fact-sets; it may also be represented as a set of booleans of which exactly one is true in any instance of it. In figure 1 a prime fact-set is shown by enclosing booleans within a rectangle which contains no other rectangle. A prime fact is an instance of a prime fact-set.

The truth of one outcome of a test may or may not imply that another permitted outcome is untrue; for example a grossly approximate measurement might be stated with great precision, the measured signal described with equal validity by any one of many stated values. A fact identifies uniquely the outcome of a test; its physical implications reflect the physics of that test.

2.3 Descriptions of phenomena.

Human experience is seen as a phenomenon within which other phenomena, of various classes, are observed to occur. The occurrence of one such phenomenon (as where a journey starts) may imply the start of another (the journey) which contains it, the class of the first implying that of the second and thus allowing the second to be described according to a method appropriate to phenomena of that class. Such a phenomenon may prove to contain further phenomena, its description then containing theirs; in this way a hierarchy of descriptions may be generated within a phenomenon, a hierarchy which originates from human knowledge of the start of that phenomenon and which may be accessible, in whole or in part, to human observers. The space occupied by one phenomenon may contain, at any time, the spaces occupied by a time-varying population of others.

A test, capable of detecting the occurrence of a phenomenon of some given class, must have access to a port which is closed initially; having detected such a phenomenon the test opens the port thereby indicating that the phenomenon, previously non-existent, now exists. A description of a phenomenon Q is then a fact, a data structure accessible only when this port has opened and which may already contain an initial fact, a fact which may contain ports giving access to other facts. If known to run only after this initial fact has become accessible a test may access an initial fact unconditionally, as is the case when a designed system runs; other tests can access it only through a port which indicates whether the fact is accessible.

In order for a data structure to be legible each port must indicate when open that a test, of some genus G assigned according to the signalling convention to that port, will succeed when applied and will yield an outcome S chosen from those permitted. The state of any given boolean within a description may then be read by applying a succession of tests, the succession identified by a list in which each entry is the genus of a test; the first test, identified by the first entry, tests whether the description is accessible, each subsequent test detecting whether a particular boolean is true. All these booleans, other than the last, are ports, the last may or may not be a port. The listed tests succeed only if the target boolean has become accessible and if the final test succeeds; they may fail either because the target boolean has not yet become accessible, or because it will not exist within the particular description, or because testing of the target boolean fails. Such a list will be termed an address of that boolean within a description; a given boolean may be accessible through more than one address, all of its addresses sharing the same initial and final entries. A boolean is uniquely identified within a description by any one of its addresses. Because one phenomenon may contain others its description may contain their descriptions, a boolean having at least one address within every description which contains that boolean.

Within a description the time order in which two ports opened is defined only if an address of the later contains an address of the earlier.

In figure 1 the boolean marked q is true and represents an open port showing that the phenomenon Q has begun, an initial fact composed of four prime facts having become accessible when this port opened. The boolean marked e, at the top right of the figure, has the two addresses [q, a, c, e] and [q, b, d, e] when accessed by tests which check that the phenomenon Q has started.

Since an address of a boolean must specify the logical role of that boolean a signalling convention must specify how those roles map to, and are mapped from, these addresses. Tests must write data to addresses which conform to the signalling convention, the derivation of a boolean dictating its addresses and the purposes for which its state may be used. Thus the meaning of a boolean is determined by its address or addresses according to a signalling convention employed by the reader.

A test performed in any phenomenon Q maps a first value of its description to a second; this second will contain the first and will contain at least one fact extending it unless the logic dictates otherwise, for example because required data are not yet available. Other conculTent tests may create their own extensions. A test therefore maps a first value of the description to a second value embodying the first, that second value embodied in a third value which may contain facts contributed by other tests. Changes in the content of a description result only from tests, the model invalid if any other change may occur.

A test, extending a description of Q in this way, is initiated when a fact becomes true of Q and is equivalent to three tests: A test which assembles, conditionally or unconditionally from the description of Q, an "input" fact composed of prime facts relevant to the derivation, the first value of the description mapped to this input fact; each of these prime facts is copied from the

description.

A test mapping this fact to another containing the entire outcome of the test; Tests distributing facts, contained within this outcome, to physical representations accessible to their readers, the readers accessing them by tests chosen according to the convention which links the derivation of each fact to the test by which its content can be accessed. These tests will normally open ports to make the new facts accessible

within the description.

In many cases these internal tests proceed concurrently, some facts distributed and made accessible while assembly of the input fact is still continuing; indeed any period of run-time may be regarded as performing a test of this form. It is perhaps noteworthy that each of these internal tests maps one fact to another.

A description of a phenomenon may be specified by specifying all the addresses of those booleans, contained in the description, which are true. A truth set, of phenomena of a chosen class described according to a chosen method, is then the set which contains every description capable of resulting when that method is applied. A method may be specified by specifying every address at which a boolean may exist. Reasoning, about behaviour past or future, requires knowledge of truth sets.

2.4 Detecting completion of concurrent tests.

A test F terminates by setting a port or ports to indicate that a fact test(F) has become accessible within a description; however where the fact test(F) is created by assembling a number of facts each contributed by one of a number of concunent tests there is a need for a mechanism to detect that all concurrent tests are complete before test(F) can be made accessible, the mechanism generating this additional fact. In hardware it is common simply to allow enough time to ensure that a set of concurrent tests will be complete, a timing signal indicating completion; for example where the contents of one register are copied to another the copy is made accessible only after a time delay sufficient to ensure true copying of all bits. In software more elaborate methods are needed: "cooperative communication between concurrent threads" is currently used, one test required to await completion of another, completion associated with message-passing and with synchronisation. Hardware designers use this technique only to meet specialised requirements, notably in the asynchronous transmission of queued messages and in initiating retransmission of garbled messages.

In software the fundamental requirement is to cause one thread and one only, drawn from the concurrent threads, to continue after creation of the fact test(F) is complete, this thread proceeding first to open the port or ports which will give access to test(F) within the description and second to perform once and once only the subsequent workload by entering the conesponding program only after single-thread working has been resumed. Any other thread terminates immediately after detecting that it is not the thread selected to continue, releasing its processor for other tasks. There is no need for synchronisation or for direct communication between threads beyond that needed for threads to perform this detection.

The most direct response to this requirement is to maintain a count of the number of threads currently in progress: on completing its contribution to the fact test(F) each thread reduces this count by one, testing whether the resultant count is zero. Where the number of concurrent threads is known before initiation starts the count may be set to that number initially, as figure 2 illustrates; in the general case the count is set to zero initially, the count increased by one before a corresponding thread starts and reduced by one after its task has been performed.

Where one thread initiates all others (as in figure 3 where one thread is shown as initiating two others) this mechanism will ensure that all threads have been initiated and have become complete before the fact test(F) is made accessible. This method also supports conditional initiation, threads initiated only if needed. Counting operations, performed on any single counter, must of course be performed sequentially to prevent malfunction. Threads may be interrupted, both mechanisms operating correctly whatever the durations of the threads.

These techniques can also be applied to the design of hardware and of microprograms.

Within a set of concurrent threads any thread may embody a further set of concunent threads equipped with its own thread count to detect completion of the threads of that further set.

In obeying an instruction a computer will employ concurrency, the obeying of a program seen as a sequence of tests each employing concurrency in generating a fact represented in the registers and memory.

2.5 Real time systems.

These systems are marked first by their ability to generate knowledge throughout an unlimited period of time and second by their reporting of the latest-available facts descriptive of past behaviour, facts retained only while needed. These observations suggest: That a real time system must employ a finite set of tests each of which is applied repeatedly throughout the life of a phenomenon which occurs within that system; each such succession of tests must generate a list descriptive of that phenomenon, a phenomenon occurring either throughout a "run" of the system or within it.

That such a list must employ a "short cut" which provides immediate access to its latest entry through its first without recourse to other entries, also allowing historic entries to be discarded when no longer needed. An address of the first entry of a list is then also an address, direct or indirect, of every prime fact within its latest entry.

Where each entry of a list contains an address of its preceding entry a reader, entering the list through its latest entry, may read the entire list.

Of these lists some identify the members of a population of phenomena of some specified class, these member phenomena culTently proceeding within the phenomenon described by that list; these lists describe how the hierarchy of phenomena varies as mn-time advances, populations changing as phenomena begin and end, split and merge. Other lists are non-hierarchic, each serving to report other new knowledge of the physical properties of the phenomenon it describes. In a hierarchic list each entry may describe a member of a population, the entire list then describing the cunent population and serving as the latest entry of another list entered through its latest end. For this reason such hierarchic lists may be entered at either end; their entries may also be chained to identify particular classes of member (for example those still proceeding and those already complete), chains also used to indicate time order, for example of completion. Where a population will never exceed some known number of members the hierarchy may be hidden by providing the same number of lists, each list then marked to show whether it is currently in use.

The information communicated by any given set of lists may equally be communicated within a single list, a factor which allows diversity in design; however the combining of lists may complicate designs and may needlessly limit concurrency in processing. Within any list an entry is a description of a phenomenon, its structure limited only by the constraints set out under 2.4 above. Where all information, obtained by reading from a list on previous occasions, is regarded as contained within the first entry of that list then the generic class of the test used to read from the list must be independent of the content of the list.

A "run" of a real time system is then a phenomenon occulTing in the computer system and in those physical systems controlled or monitored by it. Lists describe: All physical behaviour sensed or controlled by the computer system.

Successions of messages entering or leaving that system, these including timing signals and interrupt calls.

The histories of populations of phenomena.

The histories of individual phenomena.

Where a test, of a genus g. is initiated repeatedly each such test maps a first value of a description to a second value as was explained under 2.3 above. Such a test may collect system input information, the output fact then identifying the input fact; or it may generate system output data, the input fact then used to control behaviour outside the computer system; or it may perform internal processing, the values of output facts extended by facts derived from the input fact. A test may also combine two or more of these operations.

A test of genus g, applied on the rth occasion within a phenomenon Q, maps an input fact di(g, r), drawn from a description during the test, to an output fact do(g, r) contained in that

description when the test is complete:

fact(di(g, r), Q):=fact(do(g, r), Q).

The input fact di(g, r), like the output fact do(g, r), then consists of a set in which each member is a value of a list; each such test attaches, to each list within do(g, r), a new entry which contains only an initial fact. An entry of such a list is a description of a phenomenon reported to begin when the entry becomes accessible and which has an internal structure of the form common to all such descriptions; thus it may contain ports allowing new facts to be attached to it. These facts may include further lists entered through their initial entries.

The initial facts, contained within entries within a single list, do not necessarily result from the application of tests of a single genus such as g. Tests of different genii may contribute initial facts to a single list; however these initial facts, or the list containing them, must contain data allowing entries to be interpreted correctly by a reader unless such data is available from some other source; thus an encryption system may generate a list accessible only to readers with access to a changing decryption key.

2.7 Concurrency in real time systems.

Concurrency, in performing tests each making a fact accessible through a port used by them all may, in particular applications, have no ill-effects; such multiple tests may be equivalent to a single test. However in a real time system a pair of tests, even if initiated at the same time and sharing the same genus, may in reading the current content of a description return different but equally valid values, proceeding to generate conflicting values of the same fact.

Control of concurrency is therefore essential in real time applications.

The order, in which facts become accessible within a description of a "run" of a real time system, may be defined by the order in which the corresponding access ports, each giving access to one of those facts, appear in that description. The order of two facts is defined only if each has an access port within a succession of ports such that any rth port makes accessible, when it opens, an rth fact which includes the (r+ 1)th port. Signalling conventions may use this ordering to communicate information about derivation: thus the (r+ 1)th fact may be derived from the rth or from the content of a list terminating in the rth, the ordering of facts communicating this aspect of their derivation; the ordering may equally communicate, whether alternatively or additionally, knowledge that each fact within the succession is derived from relevant parts of a description at least as extensive as that used to derive its predecessor.

Where tests, using the content of the first r facts in deriving an (r+ 1)th fact to extend such a succession, may proceed concurrently one test must claim the sole right to extend the succession, proceeding to read from the latest content of the succession of facts, to derive the new fact and to attach it to the succession only after the claim has succeeded. This restriction of concurrency is necessary to prevent unwanted interactions between tests. Where the initial fact, of an entry within a list, is to be attached it is necessary to claim that list; where a fact is to become accessible through an uniquely-identified port within an uniquely-identified entry it will be sufficient to claim that particular port.

Similar arrangements ensure that successive facts derive from descriptions at least as extensive as those used in deriving their predecessors: a test, using the content of one succession of facts to generate a new fact which will extend another such succession, must first claim the right to do so. A system should not appear to have "forgotten" any fact previously used in generating another. This requirement appears to apply to lists which cannot be replaced by two or more other lists but not necessarily to other lists; for example a succession of messages might be transmitted to a receiver through two paths, one path introducing a delay far greater than the other; in the receiver the rule would then apply to lists each formed by listing messages from a single path but would not apply to a single list formed by listing, in order of arrival, messages from both paths.

3 Notes on application to real time systems.

This section outlines an approach to project implementation suggested by the theory.

A logical model, on which requirement definition and implementation are to be based, derives from identification of a hierarchy of phenomena. Such a hierarchy leads to the identification of lists and of data structure within their entries. Requirements are then stated as rules in which the existence of a fact, or of a set of facts, within a description requires the existence of facts of some stated class within that description. Facts are time-stamped, the rules requiring response-time requirements to be met.

When it runs a program reads from the description of the run during some period of time, extending that description unless the fact thus read does not justify any extension. A program is initiated to perform a task specified to it; it then runs to completion with or without interruption. A first program may interact with a second to specify and to initiate a task performed by the second or to control or limit concurrency in their performance of a task.

Where concurrency may cause malfunction programs embody their own protection; concurrent programs (threads) employ a thread-counter to identify the last thread to complete.

A task, performed by a program, may be specified by the address of a program and by the addresses of the ports which are to provide access to its input data and, where necessary, of the ports which will give access to its output data. The address of a port may be specified by an address of a data structure within a description, the data structure a list, or an entry, or a fact within an entry.

Response-time performance is determined by the conditions under which tasks are initiated and by the rapidity with which they are executed; the facilities afforded by a system are determined independently by the specifications of its tasks. Timing signals, and signals interrupting programs, are seen as sources of input data. The performance of a task is initiated when a port, of a class specified in the design, opens. One task may initiate others; a task may be initiated when a new entry becomes accessible within any list named in the design, or when a new fact becomes accessible within a particular entry. Supervisory programs may also supervise the initiation of tasks.

In reading from a description of the run-time phenomenon inconsistencies may arise from timing problems as the duration of the described phenomenon changes as reading progresses, and as some facts may reach the description before others, and as a reader may read some parts of the description before others. It is sometimes necessary to ensure that facts derive from a complete description of a consistently-defined phenomenon. Where for example the occurrence of a first phenomenon is reported in two lists each describing a phenomenon which contains that first phenomenon then inconsistencies may arise; such cases occur where a single transaction implies changes in two bank accounts or where a collision affects the paths of two objects. Where inconsistency must be avoided access must take place through a single port which is open only when both reports have become accessible.

Populations of phenomena may alter as time passes due to the merging of phenomena to form one and to the splitting of one to form others; phenomena may also begin and end. Thus groups of aircraft may merge or may split, take off or land. Where a description of a population is to be revised to describe how one set of phenomena gives rise to another concurrent performances of a single revision must be prevented.

Recycling of memory capacity is required, new facts recorded in place of facts no longer needed. This aspect of design may be accommodated intuitively as in current methods. It may prove possible to devise general-purpose garbage-recycling aids.

4 Conclusions.

Progress in physics and in information science and technology may be aided by improved understanding of the relationship between physics and information; a model based on Newtonian physics has been proposed. It may have relevance to more modern scientific thinking; it also suggests improved approaches to software engineering, approaches which may help to overcome the serious difficulties experienced by designers.

REFERENCES.

SANDEN B AND ZALEWSKI J, 2006. Designing state-based systems with entity life modelling, in J. Syst. and Sofiw. Vol. 79 Issue 1 Jan pp 69-78.

YOUNG A P, 2009, Information science and technology as applications of the physics of signalling, iittp:/iarxiv.org/abs/090 1.2723 DENNIS J B, 1980. Data Flow Supercomputers, in IEEE Comp. Vol. 18 No. 11, pp 48-56.

The technical paper ends at this point.

The invention.

Where concurrent operations, each obeying a computer program or microprogram, read data and generate data they may be designed to read and to record those data according to a chosen convention; there is then no need to employ "co-operative communication between concurrent threads" as the conventional method of assembling the fact generated by the threads, nor is it necessary for one operation to await completion of a concurrent operation.

Once initiated a thread may run to completion, recording data as the need arises and when complete releasing the hardware resources it occupied. There remains however a requirement to detect that the facts generated by all threads have become accessible allowing a new fact, embodying these facts, to be made accessible to its readers; only when completion has been detected may new work be initiated. The invention provides equipment, and a method of designing equipment, to meet this need.

According to the invention a set of operations shares control data; each operation, having run to completion, initiates a test of these control data to determine whether it should initiate a further task. The control data and the tests are designed in such a way that one test, and only one, will initiate the further task whatever the time order in which tests are initiated; this can be achieved in a number of ways which are readily devised. Initiation of the further task is a return to single-thread operation; however the further task may consist of one thread or of more than one and must be obeyed once and once only.

In a preferred method the control data consists of a counter; a test reads a value of the counter and tests whether that value is zero: if so it initiates the further task. If that initial value is non-zero the test stores a new value of the counter, formed by reducing the initial value by one; to ensure correct counting these counting actions, each reading the content of the counter and reducing it by one, must be performed sequentially as concurrent counting operations, performed on a single counter, may cause false counting. Using this method one test, and only one, will detect that the value of the counter is zero and will proceed to initiate the further task; this mechanism will operate correctly whatever the times at which operations become complete. Operations may therefore be interrupted and later resumed. Figures 2 and 3 illustrate applications of this method.

In another method the control data consists of a set of flags, one for each operation: when complete each operation initiates a test to set a flag within the control data, one flag dedicated to each operation. The operation then tests whether all flags are now set, initiating the further task if and only if all flags are now set. Where actions, to set and test in this way, occur sequentially this method is sufficient to ensure that the further task is initiated only once.

Conditional execution of a thread may then be provided by performing a null operation in its place where that thread is not required.

Where one operation within a set initiates all other operations within that set the operation may, before initiating one or more operations, alter the stored value of the control data correspondingly; figure 3 describes a method of achieving this when the control data consists of a counter. This method ensures that completion can be detected only after all operations have been initiated. It also allows the number of concurrent operations or threads to be chosen at mn-time; initiation may also be conditional on data accessible to the operation which initiates all others. Counting might best be performed using indivisible "read/modify/write" actions in each of which the content of the counter is read, and is either increased or reduced, within a single access to a random access store.

One operation, within a first set of operations employing control data to detect completion of all operations, may embody a second set of operations employing its own control data to detect completion of its own operations.

Thus the methods which have been set out enable concurrent operations to be performed with great freedom whether by concurrent execution of computer programs or by other physical mechanisms or by both.

Methods according to the invention may be applied to data structures of the form which, according to the theory which has been presented, applies to all information generated in physical systems. A set of operations may be performed on facts within a single entry, reading from that entry and writing to it; or may be performed on facts within a list or within a set of lists, these lists containing data generated during run-time. Thus a number of concurrent operations might be performed on data within an entry, each operation employing its own boolean to attach a new fact to the entry; of these operations some may have been initiated only after tests, on data generated by others of them, had indicated that their initiation should take place.

The invention also provides a method of designing and constructing systems which perform logical operations concurrently whether in a single physical processor or in multiple physical processors.