Weak synchronization and scheduling among concurrent asynchronous processors

Claim 1

A method for weakly synchronizing and externally scheduling a plurality of processors with reference to mutually exclusive access by one processor of the plurality to a shared resource, each processor executing tasks asynchronously with respect to the task execution by the other processors, each processor generating an associated numerically coded identity signal, comprising the steps of: (a) selectively generating one of a first set of numerically coded signals by each processor and indicative of the processor's internal state (i.e. idle, busy, waiting); (b) sensing the numerically coded signal from each processor, the sensed signals collectively constituting a second set of numerically coded signals, both the first and second sets of signals being well ordered in that there always exists at least one minimum valued signal in each set, each sensed signal also constituting a numerical bid for mutually exclusive access to the shared resource; (c) providing external indication to each processor whether its sensed signal was the minimum valued signal in the second set of signals; and at each processor, either (d) executing a task including that portion requiring uninterrupted access to the shared resource upon indication that the corresponding sensed signal was minimum valued, (e) deferring execution of a task until indication that its sensed signal is minimum valued is received, or (f) responsive to the indication that its sensed signal was not minimum valued, selecting another task.

Claim 2

A method for weakly synchronizing and externally scheduling a plurality of processors with reference to mutually exclusive access by one processor of the plurality to a shared resource, each processor executing tasks asynchronously with respect to the task execution by the other processors, each processor generating an associated numerically coded identity signal, comprising the steps of: (a) selectively generating one of a first set of numerically coded signals by each processor and indicative of the processor's internal state (i.e. idle, busy, waiting); (b) sensing the numerically coded signal from each processor, the sensed signals collectively constituting a second set of numerically coded signals, both the first and second sets of signals being well ordered in that there always exists at least one minimum valued signal in each set, each sensed signal also constituting a numerical bid for mutually exclusive access to the shared resource; (c) providing external indication to each processor whether its sensed signal was the minimum valued signal in the second set of signals; and at each processor, either (d) executing a task including that portion requiring uninterrupted access to the shared resource upon indication that the corresponding sensed signal was minimum valued, (e) deferring execution of a task until indication that its sensed signal is minimum valued is received, or (f) responsive to the indication that its sensed signal was not minimum valued, selecting another task.

Claim 5

A method for weakly synchronizing and externally scheduling n processors with reference to the mutually exclusive access by one of the processors to a shared resource, n being a positive integer, each processor executing tasks asynchronously with respect to the task execution by the other processors, each processor continuously generating a numerically coded signal from a first set of numerically coded signals resident therein and indicative of its processing state, each processor being coupled to a common evaluation facility through a counterpart port, comprising the steps of: (a) sensing the currently generated numerically coded signal from each processor 1, 2, . . . , i, . . . n either in the form of an integer magnitude in the range from 1 to n or a reserved word k; (b) converting the reserved word k sensed at the counterpart port to a unique port identity magnitude in the positive real number range k to k+1; (c) n-way comparing each currently sensed signal from each processor through its counterpart port; and (d) sending to each processor indication of whether its most recently sensed signal is the minimum of a second set of signals consisting of all the most recently sensed signals.

Claim 6

A method for weakly synchronizing and externally scheduling n processors with reference to the mutually exclusive access by one of the processors to a shared resource, n being a positive integer, each processor executing tasks asynchronously with respect to the task execution by the other processors, each processor continuously generating a numerically coded signal from a first set of numerically coded signals resident therein and indicative of its processing state, each processor being coupled to a common evaluation facility through a counterpart port, comprising the steps of: (a) sensing the currently generated numerically coded signal from each processor 1, 2, . . . , i, . . . n either in the form of an integer magnitude in the range from 1 to n or a reserved word k; (b) converting the reserved word k sensed at the counterpart port to a unique port identity magnitude in the positive real number range k to k+1; (c) n-way comparing each currently sensed signal from each processor through its counterpart port; and (d) sending to each processor indication of whether its most recently sensed signal is the minimum of a second set of signals consisting of all the most recently sensed signals.