Priority-based arbitrator on a token-based communication medium
First Claim
1. A method of arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities, said method comprising:
- a. maintaining a count for each of said modules of a number of units of data transferred by lower priority modules on said medium, thereby generating a plurality of counts each of said modules being assigned a corresponding limit for its said count, where latter said corresponding limit is an integer; and
b. transferring at least a unit of data by one of said modules if at least first conditions are satisfied, said first conditions being;
said one module has a request to transfer data on said medium said one module has said token, and each count, of said counts, of all of said modules having priority higher than said one module, has not reached latter said corresponding limit.
1 Assignment
0 Petitions
Accused Products
Abstract
This invention is an arbitration scheme for a token-based communications medium which is intended for use when there are timing deadlines for transactions on the medium. Initially knowledge of the expected workload is used to determine for each module its priority as well as the limit on the duration of time lower priority modules can be permitted to use the medium between request and completion of a transaction for this module. A count is maintained for each module of the number of data units that has been transferred on the medium by lower priority modules since the time this module last requested the medium. A module can transmit a selected number of data units if it has the token and the count of none of its higher priority modules has reached a corresponding limit.
-
Citations
8 Claims
-
1. A method of arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities, said method comprising:
-
a. maintaining a count for each of said modules of a number of units of data transferred by lower priority modules on said medium, thereby generating a plurality of counts each of said modules being assigned a corresponding limit for its said count, where latter said corresponding limit is an integer; and b. transferring at least a unit of data by one of said modules if at least first conditions are satisfied, said first conditions being;
said one module has a request to transfer data on said medium said one module has said token, and each count, of said counts, of all of said modules having priority higher than said one module, has not reached latter said corresponding limit.
-
-
2. An apparatus for arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities, said apparatus comprising:
-
a. a count register for each of said modules for indicating a number of units of data transferred by lower priority modules on said medium, thereby generating a plurality of counts each of said modules being assigned a corresponding limit for its said count, where latter said corresponding limit is an integer; and b. a logic device for indicating the satisfaction of at least first conditions, said first conditions being;
one module has a request to transfer data on said medium, said one module has said token and each count, of said counts, of all of said modules having priority higher than said one module, has not reached latter said corresponding limit.
-
-
3. An apparatus for arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium, each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities, said apparatus comprising:
-
a. means for maintaining a count for each of said modules of a number of units of data transferred by lower priority modules on said medium, thereby generating a plurality of counts each of said modules being assigned a corresponding limit for its said count, where said corresponding latter limit is an integer; and b. means for indicating that first conditions are satisfied, said first conditions being;
one module has a request to transfer data on said medium, said one module has said token, and each count, of said counts, of all of said modules having priority, of said priorities, higher than said one module, has not reached latter said corresponding limit.
-
-
4. A method of arbitrating access to a token-based communication medium among a plurality of modules M1,M2, . . . , Mn, wherein a token is circulated among said modules on said medium, wherein each of said modules Mi has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities, said method comprising:
-
a. maintaining a count ci for each of said modules Mi of the number of units of data transferred by lower priority modules on said medium, thereby generating a plurality of counts c1,c2, . . . , cn, where each count ci is initialized to a value ki and is changed when a module of lower priority, of said priorities, than module Mi transmits a unit of data each of said modules being assigned a corresponding limit for its said count, where latter said corresponding limit is an integer; and b. transferring at least a unit of data by one of said modules if at least first conditions are satisfied, said first conditions being;
said one module has said token, and each count of said counts, of all of said modules having priority, of said priorities, higher than said one module, has not reached its said assigned corresponding limit.
-
-
5. A method of arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium, each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities,
a. maintaining a count for each of said modules of a number of uses of said medium by lower priority modules, thereby generating a plurality of counts, each of said modules being assigned a corresponding limit for its said count, where latter said corresponding limit is an integer; - and
b. using said medium by one of said modules by transferring at least a unit of data by any one of said modules if at least first condition are satisfied, said first conditions being;
said one module has a request to transfer data on said medium, said one module has a request to transfer data on said medium, said one module has said token and each count, of all of said modules having priority, of said priorities, higher than said one module, has not reached latter said corresponding limit.
- and
-
6. An apparatus for arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium, each of said modules being assigned a priority i where i is an integer, thus having a plurality of priorities, said apparatus comprising:
-
a. a count register for each of said modules for indicating a number of uses of said medium by lower priority modules, thereby generating a plurality of counts, each of said modules being assigned a corresponding limit for its said count, where latter said corresponding limit is an integer; b. a logic device for indicating the satisfaction of at least first conditions, said first conditions being;
one of said modules has a request to transfer data on said medium, said one module has said token, and each count, of said counts, of all of said modules having priority, of said priorities, higher than said one module, has not reach latter said corresponding limit; andc. using said medium by said one module when said first conditions are satisfied for said one module.
-
-
7. An apparatus for arbitrating access to a token-based communication medium among a plurality of modules, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium, each of said modules being assigned a priority i, where i is an integer, thus having a plurality of priorities, said apparatus comprising:
-
a. means for maintaining a count for each of said modules of a number of uses of said medium by lower priority modules of said modules, thereby generating a plurality of counts; b. means for indicating that first conditions are satisfied for one of said modules, said first conditions being;
said one module has a request to transfer data on said medium, said one module has said token, and each count, of said counts, of all of said modules having priority higher than said one module, has not reached a corresponding limit, where each latter said corresponding limit is an integer; andc. means for using said medium by said one module when said first conditions are satisfied for said one module.
-
-
8. A method of arbitrating access to a token-based communication medium among a plurality of modules M1,M2, . . . , Mn, wherein a token is circulated among said modules on said medium, wherein each of said modules has a limit on the time between a request for transfer of a unit of data and transfer of said unit of data on said medium, each of said modules Mi being assigned a priority i, where i is an integer and i is a higher priority than i+1, said method comprising:
-
a. maintaining a count ci for each of said modules Mi of a number of uses of said medium, by lower priority modules of said modules, thereby generating a plurality of counts ci,c2, . . . , cn, where each count ci is initialized to a value ki and is changed when a module of lower priority than module Mi transmits a unit of data; and b. using said medium by one of said modules by transferring at least a unit of data by said one of said modules if at least first conditions are satisfied, said first conditions being;
said one module has said token, and each count of said counts, of all of said modules having priority higher than said one module, has not reached a corresponding limit, where each latter said corresponding limit is an integer.
-
Specification