GB2230166A

GB2230166A - Resource control allocation

Info

Publication number: GB2230166A
Application number: GB8907246A
Authority: GB
Inventors: Daniel Matthew Taub
Original assignee: Individual
Current assignee: Individual
Priority date: 1989-03-31
Filing date: 1989-03-31
Publication date: 1990-10-10
Also published as: GB8907246D0

Abstract

In a system where a single resource in the form of a data bus BS is shared among a plurality of users in the form of Modules M, control of the bus is restricted to not more than one module M at a time. Each module is assigned a different n-digit binary identity number, all the identity numbers containing the same number m of ones, and associated with BS there are n lines AB which perform the wired-OR function. When a request for the control of BS is made, the module or modules making that request apply their identity numbers to AB, and a decoder in each module, or one common to all modules, determines whether the resulting number carried by AB contains exactly m, or more than m, ones. If it contains more than m ones, indicating two or more requestors, arbitration between them takes place in a known manner to determine which of them shall control BS first. But if the number on AB contains exactly m ones there can be only one requestor and so arbitration is dispensed-with, allowing the requestor to obtain control with less delay. In an alternative form of the invention, an additional set of bus lines allows the arbitration means to be used concurrently with the determination of the OR-function of the requestors' identity numbers, and if this shows that only one requestor is present, the arbitration process is abandoned. <IMAGE>

Description

RESOURCE CONTROL ALLOCATION NETHOD AND APPARATUS This invention relates to resource control allocation methods and apparatus in systems where a single resource is shared among a plurality of users, only one of which may control the resource at a time. There are many instances of such in computer systems, telecommunications systems and the like. A common example occurs in computer and microcomputer systems where the common resource is a data highway or 'bus', and the users are the various modules that make up the system, such as processor modules, storage modules, and controller modules for the various input/output devices.

Whenever any of these modules need to send data to another, or obtain data from it, it must first acquire control of the bus.

As the modules operate with a great deal of independence, it is possible that two or more of them may seek to get control at the same time, i.e. contention may occur, and so an 'arbitration' scheme has to be provided whereby this contention may be resolved.

Various arbitration schemes are known and have been discussed in earlier publications, for example in an article in Proceedings IEE, 1976, Vol. 123, pages 845-850, entitled 'Contention-resolving circuits for computer interrupt systems' by the present inventor, and in an article in IEEE Micro, August 1984, Vol. 4, No.4, pages 7-22, entitled 'Computer buses - a tutorial' by David B. Gustavson. Among these arbitration schemes is one that is particularly attractive because of its versatility and speed, and has become known as the 'distributed parallel arbiter'. In this, each module that may require control of the bus is allocated an identity number consisting of n binary digits, all the numbers being different, and the bus includes n arbitration lines, one for each digit of the identity numbers.These lines are 'active-low', meaning that binary 1 is represented on them by the less-positive voltage level, and the modules can apply their identity numbers to them through open-collector driver circuits. Thus when two or more modules apply a digit in their identity numbers to the corresponding line, the binary digit that appears on that line is the OR-function of the digits applied by the modules.

Arbitration takes place in the following way. Modules that require control of the bus apply their identity numbers to the arbitration lines as indicated above, but with the following proviso. If a module is applying 0 to any of the lines but detects that the state of that line represents 1, then for as long as that condition persists, it ceases to apply all the digits of its identity number that are of lower significance. The result is that when the system has settled to a steady state, the number represented on the arbitration lines is the highest identity number among the modules competing at that time, and the module with that identity number is the winner. The logic circuit within a module for implementing the above algorithm can be as shown in Figure 1; this is a pure logic diagram showing the relationship between Boolean variables rather than between electrical levels.

In Figure 1, the identity number ID of the module is applied as a set of binary digits to n identity lines ILO to IL(n-l), the most-significant digit of ID being applied to IL(n-l). Each of the identity lines feeds one input of an AND-gate Al whose output is through an open collector bus-line driver circuit D1 to the corresponding arbitration line of the lines ABO to AB(n-1). Each identity line also feeds an OR-gate Ol whose other input is from a bus line receiver circuit R1, and whose output is to one input of a second AND-gate A2. A line C to which a 'bus needed' signal is applied by the module when necessary, leads to the other inputs of AND-gates Al and A2 associated with the identity line IL(n-1) of the most significant digit of the identity number of the module.The output of the AND-gate A2 associated with this identity line is to the AND-gates Al and A2 associated with the identity line IL(n-2) of the next-most significant digit of the identity number, and so on.

The output line y of the AND-gate A2 associated with the identity line ILO of the least significant digit of the identity number, provides a signal representing 0 if the arbitration has been lost, or a 1 if the arbitration has been won.

This arbitration scheme is well-known and forms part of several bus designs covered by Standards issued by the Institute of Electrical and Electronics Engineers (IEEE) in the United States of America, for instance Standards Nos 696, 896 (Futurebus) and 960 (Fastbus). It is also used in several proprietary buses, notably Texas Instruments Corporation's 'Nubus', Intel Corporation's 'Multibus II' and IBM Corporation's 'Micro Channel Architecture'.

An important design consideration is the maximum length of time that can elapse between the start of arbitration and the final steady state being reached. Its value can be found by representing the complete arbitration network as shown in Figure 2. A logic network as shown in Figure 1 is included in each module M and the logic networks are in effect connected in parallel at various points by lines in the bus, R being the control line which causes arbitration to start, and AB(fl-1) to ABO being the arbitration lines mentioned earlier. The signal on line C in Figure 1 is derived from the signal on line R in Figure 2. The overall circuit can be regarded as a series/parallel network of logic elements, with the bus-lines introducing additional delays.The maximum settling time to may is the maximum possible delay through this network, from the point on line R where the 'start arbitration' signal is generated, to whichever point y in the modules is the last to settle. Clearly ts max depends on the end-to-end propagation time tp along the bus and on the speed and number of logic elements including line drivers and receivers in the longest path. To give an idea of the order of magnitude, in a typical microcomputer bus with tp = 10 nanoseconds, seven digits in the identity numbers, and maximum delays in each logic gate, line driver and line receiver of 5, 10 and 18 nanoseconds respectively, ts max is 389 nanoseconds.

The settling time will often be less than ts max because the particular identity numbers applied will not necessarily cause the longest-delay path through the network to be followed, and because the various delays may be less than the maximum values.

Nevertheless, for reliable operation ts max is the figure that one has to use in the design.

Until recently the ts max values obtainable were considered to be low enough, but in the high performance systems being built today they have become embarrassingly long. The present invention seeks to overcome the problem set out above by reducing the average length of time that can elapse between the need for resource control arising and the moment when control is obtained.

The invention is based on the result of simulation studies which showed that if a module needing control of the bus is to obtain it in a time which is short enough not to degrade the system performance too severely, the occupancy of the bus has to be kept down to about 20 to 30%; in other words the bus must on average be idle for some 70 to 80% of the time. This implies that a) the occasions on which two or more modules request control of the bus simultaneously will be very rare, and b) on most occasions that a bus request occurs, the previous user or Master will have already completed its data transactions, and so the bus will be idle.

These considerations are used for the main feature of the invention, which is that the arbitration process, as described above, is avoided unless there are two or more simultaneous requests.

The procedure for allocating control of the bus therefore requires two operations: a) determining whether two or more requests are present, and if so, b) arbitrating between them.

In one form of the invention operations (a) and (b) take place sequentially, in other words, the arbitration network is not made active until it has been established that arbitration is needed. In an alternative form of the invention the arbitration network is made active at the same time as operation (a) starts, so that (b) overlaps (a). Operation (a) will be completed sooner, and so if this shows that only one requestor is present, operation (b) is abandoned before the settling time ts max has elapsed.

The second arrangement requires n more bus lines together with their associated drivers and receivers, and is therefore the more expensive. Its performance is the better of the two, but only by a small margin, and so on balance, the sequential arrangement is the preferred one.

According to the invention, in a method of allocating control of a single resource shared by a plurality of users, including arbitration means to limit control to not more than one user at a time, the arbitration means is made ineffective when there is only one user requesting control of the resource.

Preferably, each potential user is assigned a different n-digit binary identity number chosen from a restricted set of numbers, such that when the OR-function of the corresponding digits of two or more identity numbers is evaluated, the result represents a number outside the restricted set.

Advantageously, each of the numbers within the restricted set of identity numbers contains the same number ni of ones, and the same number n - m of zeros.

In a preferred form of the invention a group of n OR-gates is provided, one OR-gate for each level of significance of the digits of the identity numbers. On a request for control of the resource being issued by one or more of the potential users, the group of OR-gates is used first for evaluating the OR-function of the requestors' identity numbers, and if this represents a number falling outside the restricted set of identity numbers, indicating the presence of more than one requestor, the same group of OR-gates is then used in the arbitration process.

In an alternative form of the invention two groups of n OR-gates are provided, one OR-gate in each group for each level of significance of the digits of the identity numbers. On a request for control of the resource being issued by one or more of the potential users, one of the groups of OR-gates is used for evaluating the OR-function of the requestors' identity numbers, while the second group is used concurrently with the first group for carrying out the arbitration process as if there were two or more requestors; but it the output of the first group of OR-gates is found to represent a number falling within the restricted set of identity numbers, indicating that there is only one requestor, the arbitration process is abandoned or rendered ineffective.

It will be appreciated that each OR-gate may include a conductor effectively receiving inputs from all the potential users. Such inputs may be provided by open-collector transistor circuits or current-generator circuits in the users.

The determination of the states of the outputs of the OR-gates used for evaluating the OR-function of the requestors' identity numbers may be effected by decoding means in each potential user or common to all the users.

A request for control of the resource from at least one potential user may cause all potential users to execute a sequence of operations in which they all have to complete the first operation before any of them is permitted to start the second operation, and similarly for all the operations up to the end of the sequence.

In this case the preferred form of the invention referred-to above requires that at the start of the sequence users seeking control of the resource issue a signal indicating this fact; these users then apply their identity numbers to the OR-gates; following this, all potential users examine the output of the OR-gates, and if they represent a valid identity number, indicating a single requestor, control of the resource is passed to that requestor as soon as the resource is available; but if the output from the OR-gates indicates that there is more than one requestor, arbitration proceeds.

Conveniently arbitration takes place among the requestors using the distributed parallel arbitration process in which if a requestor is applying a binary 0 to an OR-gate but detects that the output of that OR-gate represents binary 1, then while that condition persists it ceases to apply to the OR-gates all the digits of its identity number that are of lower significance; when the system has reached a steady state and the resource has become available, control is passed to the requestor whose identity number corresponds with the number represented by the output of the OR-gates.

The invention extends to apparatus for allocating control of a single resource shared by a plurality of users, including means for arbitration to limit control to not more than one user at a time, means for determining when there is only one user requesting control of the resource, and means for disabling the arbitration means when the determining means so determines.

In this case it is preferred that each user has n identity lines and each user is assigned a different n-digit binary identity number, and there is a group of n OR-gates to which the individual identity lines of all the users are connected via AND-gates, the different numbers being so chosen from a restricted set of numbers such that when the corresponding digits of two or more identity numbers are applied to the OR-gates, one for each level of significance of the digits, the output of the OR-gates represents a number outside the restricted set, whilst if the corresponding digits of only one identity number are applied, the output represents one of the restricted set, determining means in each user or common to all users responding to an output number of the restricted set to disable the arbitration means.

Advantageously, every number within the restricted set of identity numbers contains the same number, m, of ones, and the same number, n-m, of zeros.

Preferably, the apparatus includes provision for using the group of OR-gates referred-to above for two purposes in succession: first for evaluating the OR-function of the requestors' identity numbers, and then, if the number represented by this OR-function lies outside the restricted set of identity numbers, for arbitration.

Alternatively, two groups of n OR-gates are provided and are used concurrently, the first group for evaluating the OR-function of the requestors' identity numbers, and the second group for arbitration as if two or more requestors were present; and apparatus is provided for disabling the arbitration means if the output of the first group of OR-gates represents a number within the restricted set of identity numbers.

Every OR-gate referred to is formed by a conductor which can be energised by an open-collector driver or a current-generator circuit in every potential user.

Each potential user may include decoding means for determining the states of the outputs of the OR-gates which are used for evaluating the OR-function of requestors' identity numbers, or the said decoding means may be common to all users.

Means may be included responsive to a request for control of the resource from one or more potential users, to cause all potential users to execute a sequence of operations in which they all have to complete the first operation before any of them is permitted to start the second operation, and similarly for all operations up to the end of the sequence.

There may be included, in this case, means in each user to issue a signal at the start of the sequence when control of the resource is sought by that user, and means in each user to apply its identity number to the OR-gates following its issuance of such signal.

The invention in its preferred form will now be further described with reference to the following diagrams, of which Figures 1, 2 and 3 represent prior art.

Figure 1 shows an example of the arbitration logic within a single module; Figure 2 shows the overall arbitration network, in which the logic networks in Figure 1 are effectively connected in parallel at several points by the bus line R, a signal on which causes arbitration to start, and by the arbitration lines AB(fl-l) to AB0; Figure 3 shows the waveforms involved in one method of synchronising operations in the various modules; Figure 4 shows a flow diagram in skeleton form of the sequence of six operations used in the implementation of the control-acquisition procedure to be described; Figure 4.1 to 4.6 give details of Operations 1 to 6 respectively in the above procedure; Figure 5 shows a possible modification of the logic circuit in Figure 1 whereby arbitration may be made operative or inoperative as required; and Figure 6 is a general diagram showing the modules M, the lines BS in the bus concerned with data transfers and the lines AB, AP, AQ, AR and AC concerned with control acquisition in the above-mentioned procedure. T represent line-termination networks.

A computer or telecommunications system to which the present invention may be applied includes a plurality of users in the form of modules M (Fig.6) and a common resource in the form of a data highway or bus BS. Such modules M may be data processor modules, data storage modules or controller modules for various input/output devices, for example. whilst each module proceeds to operate independently for much of the time, occasions arise when access and control of the bus is needed, for example to send data to another module or to obtain data from another module. When such a need arises, the module concerned raises a request for control. In case two or more modules request control of the bus at the same time, an arbitration scheme is provided to resolve the contention.The arbitration scheme or process is subject to various rules by which priority is determined; these rules may include rules by which fairness is achieved. To operate the control-acquisition scheme, the system includes a set of lines AB to all of which all the modules that are potential users of the bus BS are connected.

In accordance with the preferred embodiment of the present invention, each module M is allocated a different identity number chosen from a restricted set, the numbers of which in binary digital form contain m ones and n - m zeros. There are n lines AB, and each module M has n output connections corresponding to the individual digits of its identity number and connected to the individual lines AB to perform the wired-OR function. These lines are further connected to decoding apparatus within each module M, which apparatus can determine when only ni of the lines AB are 'one' and when more than ni of the lines AB are 'one'.It will be appreciated that in the former case, only one module will have impressed its identity number digits on the lines AB, whilst in the latter case, two or more modules must have done so.

Such an identification scheme is usually called an 'm-out-of-n' code, and as an example, the permitted numbers, if such a restricted set is a 2-out-of-4 code, are shown in Table 1 below.

Table 1 Permitted identity numbers in 2-out-of-4 code

Binary representation Decimal Equivalent 0011 3 0101 5 0110 6 1001 9 1010 10 1100 12 The identity numbers chosen for particular modules are selected so as to assist the arbitration process. Thus the modules usually receive identity numbers indicating their priority rating in determining access to and control of the bus BS. The higher the identity number, the greater the priority allocated to a module's bus control request. Certain modifications of this are discussed later.

The procedure by which a module obtains control of the bus is as follows. It, perhaps together with other modules, issues a bus-request signal, following which the modules that have done so apply their identity numbers through open-collector stages to lines AB(n-1) to ABO in a straightforward manner, i.e. without operating the arbitration algorithm. After allowing for bus propagation delay, the lines will therefore carry the OR-function of the numbers applied. All modules then check whether this result fulfils the 'm-out-of n' condition. If it does, there can have been only one requestor, and so control of the bus is transferred as soon as permissible: if the bus is still in use, transfer is delayed until the current master completes its transactions; otherwise it takes place immediately.

If, on the other hand, the number represented on lines AB(n-l) to ABO contains more than m ones, indicating that there was more than one requestor, then all the requestors operate the arbitration algorithm described earlier, and time an interval max' long enough for the arbitration circuits to settle.

The lines AB will then carry the highest identity number of those applied, and each requestor registers whether it has won or lost. As in the one-requestor case, transfer of control to the winner takes place as soon as permissible, either immediately or as soon as the previous master's transactions are complete.

Determination of whether the number on the AB lines contains exactly ni or more than m ones can be done as follows. Within each module, the outputs from the AB-line receivers are connected to an n-way decoder, i.e. a decoder with n inputs and 2n outputs, one output corresponding to each possible combination of input digits. The decoder outputs are connected to the inputs of two OR-gates as follows. All the decoder outputs corresponding to exactly ni ones at its input are connected to one of the OR-gates, and all the decoder outputs corresponding to more than m ones at its input are connected to the second OR-gate. The outputs from these OR-gates therefore indicate whether the decoder input contains exactly m or more than m ones, respectively. (Other outputs from the decoder can be used when necessary to indicate fault conditions).

As pointed out earlier, in all but a few instances there will be only one requestor, and the bus will be idle at the time that control is sought. Therefore the average time that a requestor has to wait before getting control is much less than in the earlier schemes where every transfer of control involves an arbitration settling time.

It can be seen from the above description that the process by which a requestor acquires control of the bus involves a sequence of operations, the number of operations in the sequence depending on whether or not arbitration is necessary.

It is essential for correct operation that throughout the sequence all modules are kept in synchronism, i.e that no module starts operation (i + 1) until all the modules have completed operation i. There are two main ways of bringing this about, either of which may be used in the present invention.

One is to generate a clock waveform that is transmitted to all the modules, and the second is to use a scheme based on asynchronous circuits in which the clock waveform is dispensed with. The 'clockless' scheme has the advantage of adjusting itself automatically to the circuit speeds in the various modules, and so when these speeds vary between one module and another, the overall network will always operate at the fastest rate permissible. This is the method used in the implementation to be described below.

A complete control-acquisition scheme needs certain features additional to those already mentioned, and the implementation to be described includes the main ones found in the IEEE 896 Specification and described in an article by the present inventor intitled 'Improved control acquisition scheme for the IEEE 896 Futurebus' published in IEEE Micro, June 1987, Volume 7 No.3, pages 52 to 62. These features will now be explained.

When bus traffic is particularly heavy there would be a tendency for modules with low identity numbers to be starved of access to the bus. This tendency can be reduced by dividing the modules into two classes - a Priority class whose members are allowed to try to acquire control of the bus whenever they need it, and a Fairness class whose members, once having obtained control of the bus, are debarred from trying again until all outstanding bus requests have been fulfilled. The modules assigned to the Priority class are those that may have an urgent need for the bus possibly because of real-time constraints; their identity numbers are always higher than those of the Fairness class, so that if Fairness and Priority modules are competing against one another, the winner will always be from the Priority class.

A second feature is known as Pre-emption. If the current master is still using the bus when a bus request is made, the requestor or, if arbitration was necessary, the winner, has to wait until the master signals that it has finished. During this waiting period there is a possibility that a module of higher priority may develop an urgent need for the bus. The pre-emption feature allows this module to terminate the waiting period and to restore the situation that existed before the control-acquisition sequence started. The pre-empting module can then initiate a new sequence.

The clockless method of synchronising operations in the various modules will now be explained. It is described in EP-A-0 131 658 and also in various articles. The description of the basic method will be repeated here for completeness, following which, certain additional features needed for the present invention will be introduced.

The bus BS includes three control lines AP, AQ and AR (Fig.6).

Like the arbitration lines AB these are active-low, and modules drive them through open-collector stages. The signals that a module applies to these lines are denoted by lower case letters ap, aq and ar respectively, and so the signal on AP will be the OR-function of ap from all the modules, and correspondingly for the signals on AQ and AR. The same method of designation is used for other signals later in this Specification. When a signal has the value binary 1 it is said to be 'asserted', and when it is at binary 0, it is said to be 'released'. Thus, for example, if any ap is asserted then AP is asserted, but AP is released only when all ap signals are released.

The basic scheme operates as follows. The modules that have to carry out the sequence of operations are assumed to have circuits of different speeds, and the sequence of operations is considered to form a loop, so that as soon as the slowest module completes the last operation in the sequence, all modules start the first operation over again, and so on ad infinitum. This explanation starts at the point in the loop where all the modules are engaged on the first operation, operation 1 (see Fig. 3), but none has yet finished it. At this point, ap, aq, and ar in all the modules, and therefore the signals on bus lines AP, AQ and AR, are 1,0,1 respectively. This means AP and AR are asserted and AQ is released. The way in which these signals change as the sequence progresses is as follows: 1.As soon as each participant completes its first operation, it releases its ar. Only when the slowest has done so will line AR be released. In the example shown, the slowest module is seen to be n.

2. All participants respond to the release of AR by asserting their aq and starting their second operation. As soon as they complete it, they release their ap. The release of AP indicates that the slowest has finished. In this example it again happens to be n.

3. All participants respond to the release of AP by asserting their ar and starting their third operation. When they have completed it, they release their at, and similarly the release of AQ indicates that the slowest has finished (this time, module B).

4. All participants respond to the release of AQ by asserting their ap and starting their fourth operation. On completing it, they release their ar.

The process continues as above, the bus signals in operation 4 being the same as in operation 1, those in operation 5 being the same as in operation 2, and so on. Therefore, if the state of the bus lines at the beginning of the sequence is always to be the same, which is a requirement, the number of operations in the sequence has to be an integral multiple of 3.

A problem with wired-OR lines such as AP, AQ and AR, is that the release of a line by one module while another is still holding it asserted can cause a glitch to appear on the line.

This results from the change in the current-flow pattern. The problem is solved by taking the relevant bus-lin receiver outputs through integrators and threshold circuits. These are designed so that the longest possible glitch or succession of glitches, that can last for up to twice the end-to-end propagation time of the bus, will not cause the threshold circuit to switch.

The implementation of the invention presented here has several features in addition to those described above. They are as follows: a. Sequences are of two possible lengths: three operations or six operations. The 3-operation sequence is used when: i) there is only one requestor and no master, ii) the master is relinquishing the bus and there is no requestor, and iii) the bar on Fairness modules is being cancelled.

The 6-operation sequence is used when: i) there are two or more requestors, and ii) there is only one requestor, but the bus is still in use.

b. A pause is introduced during operation 1 to wait for one or other of the modules to request control of the bus, or for the master to complete its transactions, whichever occurs first. This is done as follows.

When modules detect AQ being released, indicating that the last operation in the preceding sequence is finished, they do not automatically assert their ap. The module or modules requiring the bus, or the master, having completed its transactions, assert ap first, and the remainder follow suit only when they detect that AP is asserted.

Until this happens, no module is permitted to signal the end of operation 1, that is, by releasing ar.

c. A pause is introduced during operation 5 mainly to wait for the current master to finish its bus transactions.

This occurs in similar fashion to the above. When AR is released indicating that all modules have completed operation 4, modules do not automatically assert their aq.

The first one to do so is either: 1) a requestor, if there is no master at the time; (The absence of a master will have been detected in operation 1 by all the AB lines being released; see Note 1 in Figure 4.1); 2) any module detecting an error, i.e. that the number represented on the AB lines does not fall within the permitted set of identity numbers; 3) a module carrying out pre-emption, i.e. a module seeking to displace the module that was waiting to be granted control of the bus, known as the master-elect; or 4) the master, when it has finished its bus transactions.

The remaining modules do not assert their aq until they detect AQ asserted, and only after this has happened are they permitted to release ap indicating that they have finished operation 5.

Operations 1 and 5 may therefore be thought of as being divided into two periods: a 'wait' period that lasts until the appropriate variable, ap or aq respectively, is asserted, and a 'completion' period that lasts from then until the required operation is over. The wait period can be arbitrarily short; for instance, a bus request can be presented immediately after the preceding sequence finishes, possibly by a Fairness module whose bar to seeking control of the bus has just been cancelled, a module that lost in the preceding arbitration, or a module that caused pre-emption to take place. In operation 5 the wait period can be arbitrarily short if there is no master.

In addition to AP, AQ, AR and the AB lines already mentioned, the implementation described here uses one extra bus line, AC (Fig. 6). Like the other lines this is active-low and driven by an open-collector driver in each module, so that the signal on the line is the OR-function of all the signals ac applied. AC is used during operations 1 and 2 to signal, on the one hand, whether a normal bus request is taking place, or on the other hand, whether the bar on Fairness-class modules is being cancelled or the master is relinquishing control of the bus and no other requestor is present. AC is used again during operations 5 and 6 to signal whether a normal transfer of control should take place or whether this should be aborted because of an error or pre-emption.

The complete control-acquisition sequence is shown in skeleton form by the flow diagram in Figure 4, details of operations 1 to 6 being given in Figures 4.1 to 4.6 respectively. The actions carried out by a module during any particular operation depend on its status at the time, e.g. whether it is a requestor, the current master etc. Details of the various states that a module can assume are shown in Table 2 below.

Table 2 Module status

Designation Meaning Definition barred under the Fairness rule, and not requesting control of the bus.

BB Barred bystander ' A module barred by the Fairness rule from seeking control of the bus, and not : needing control at the time.

FR j Free requestor i A module free to seek control of g orthe bus, and doing so.

BR i Barred requestor , A module needing control of the bus, but barred from seeking it.

ME Master-elect A module destined to become the next master, but which has not yet been granted control.

FM Free master A master free to seek control of the bus again as soon as its current tenure is over.

BN Barred master A master in this state at the conclusion of its bus tenure is barred from re-seeking control until a 'fairness release' has taken place.

In summary, the main features of the procedure are: OPERATION 1. The procedure is started by any of the following modules asserting ap: a) a module requiring control of the bus, whether or not barred by the Fairness rule; b) the current master, when it has finished its transactions and is ready to relinquish the bus.

Requestors that are not barred assert ac, and all modules register internally the OR-function of the digits on the AB lines, designated by u.

The value of u indicates whether or not a master is present.

Modules' actions during the remaining operations depend on whether or not AC was asserted. The two cases will be described separately.

CASE 1: AC asserted. This indicates that one or more requestors are present, not barred by the Fairness rule.

OPERATION 2. The requestors apply their identity numbers to the AB lines without using the arbitration algorithm. A simple way of doing so is illustrated in Figure 5 which is very similar to Figure 1 except that an additional OR-gate 02 is interposed between the output of every AND-gate A2 (except the one associated with the least-significant digit of the identity number), and one of the inputs of the AND-gate Al associated with the digit of next lower significance. The second input of each of the OR-gates 02 is connected to a common line D which, when asserted together with C, disables the arbitration algorithm ensuring that the number represented on the AB lines is the straightforward OR-function of the identity numbers applied.

OPERATION 3. Modules test the AB lines and the value of u registered during operation 1. If these indicate that there is only one requestor and that there is no master, the requestor immediately becomes the new master and the sequence returns to operation 1. If, on the other hand there is more than one requestor or a master is still present, modules register that this is a 6-operation sequence, and move on to operation 4.

OPERATION 4. If operation 3 showed more than one requestor, the requestors operate the arbitration algorithm, by releasing D in Fig. 5, and time an interval long enough for the network to settle.

OPERATION 5. Modules check that the number represented on the AB lines is a valid identity number. Modules finding an error or carrying out pre-emption assert ac to prevent bus mastership from being transferred, and assert aq to restart the sequence. Otherwise, modules wait until the sequence is restarted by the current master after it has finished using the bus.

Note that a module may pre-empt another only if it is in the Priority class and if its identity number is higher than that of the master-elect, that is, higher than the number on the AB lines.

OPERATION 6. If AC=O indicating that control of the bus is to be transferred, the master relinquishes control to the master-elect. If AC=1, the current master remains in control, and all the conditions that existed before the sequence started are re-established. Modules then return to operation 1.

CASE 2: AC released. If operation 1 finishes with AC in the released state, no requestors are present that are permitted to take control of the bus.

The actions during the remaining operations are then: OPERATION 2 If the master is ready to relinquish control of the bus, it clears its identity number from the AB lines.

OPERATION 3 Modules cancel any bar that had been imposed on them by the Fairness rule. They then return to operation 1.

The scheme just described represents only one possible embodiment of the invention, and it should be understood that many other embodiments are possible and more features can be added, e.g. a greater degree of fault detection, without departing from the main principle.

Claims

1. A method of allocating control of a single resource shared by a plurality of users including means for arbitration to limit control to not more than one user at a time, in which the arbitration means is made ineffective or not used when there is only one user requesting control of the resource.

2. A method as claimed in Claim 1, in which each potential user is assigned a different n-digit binary identity number chosen from a restricted set of numbers such that the OR-function of corresponding digits of two or more identity numbers represents a number outside the restricted set.

3. A method as claimed in Claim 2, in which every number within the restricted set of identity numbers contains the same number, m, of ones, and the same number, n-m, of zeros.

4. A method as claimed in Claim 2 or 3, in which a group of n OR-gates is provided, one OR-gate for each level of significance of the digits of the identity numbers, and on a request for control of the resource being issued one or more of the potential users, the group of OR-gates is used first for evaluating the OR-function of the requestors' identity numbers, and if this is found to represent a number falling outside the restricted set of identity numbers, the same group of OR-gates is then used in the arbitration process.

5. A method as claimed in Claim 2 or 3 in which two groups of n OR-gates are provided, one OR-gate in each group for each level of significance of the digits of the identity numbers, and on a request for control of the resource being issued by one or more of the potential users, the two groups of OR-gates are used concurrently, the first group for evaluating the OR-function of the requestors' identity numbers and the second group for carrying out the arbitration process as if there were two or more requestors; but if the output of the first group of OR-gates is found to represent a number falling within the restricted set of identity numbers, the arbitration process is abandoned or rendered ineffective.

6. A method as claimed in Claim 4 or 5, in which every OR-gate referred to is formed by a conductor which can be energised by an open-collector driver or a current-generator circuit in every potential user.

7. A method as claimed in Claim 4,5 or 6, in which the determination of the states of the outputs of the OR-gates used for evaluating the OR-function of the requestors' identity numbers is effected by decoding means in each potential user or common to all users.

8. A method as claimed in any preceding Claim, in which a request for control of the resource from one or more potential users causes all potential users to execute a sequence of operations in which they all have to complete the first operation before any of them is permitted to start the second operation, and similarly for all the operations up to the end of the sequence.

9. A method as claimed in Claim 8, in which, at the start of the sequence users seeking control of the resource issue a signal indicating this fact; these users then apply their identity numbers to the OR-gates provided for the purpose of evaluating the OR-function of the said identity numbers; following this, all potential users examine the output of these OR- gates, and if they represent a valid identity number, indicating a single requestor, control of the resource is passed to that requestor as soon as the resource is available; but if, the output from these OR-gates indicates that there is more than one requestor, arbitration proceeds.

10. A method as claimed in Claim 9, in which arbitration takes place among the requestors using the distributed parallel arbitration process in which if a requestor is applying a binary 0 to an OR-gate but detects that the output of that OR-gate represents binary 1, then while that condition persists it ceases to apply to the OR-gates all the digits of its identity number that are of lower significance; when the system has reached a steady state and the resource has become available, control is passed to the requestor whose identity number corresponds with the number represented by the output of the OR-gates.

11. A method of allocating control of a single resource shared by a plurality of users, substantially as hereinbefore particularly described with reference to the accompanying drawings.

12. Apparatus for allocating control of a single resource shared by a plurality of users, including means for arbitration to limit control to not more than one user at a time, means for determining when there is only one user requesting control of the resource, and means for disabling the arbitration means when the determining means so determines.

13. Apparatus as claimed in Claim 12, in which each user has n identity lines and each user is assigned a different n-digit binary identity number, and there is a group of n OR-gates to which the individual identity lines of all the users are connected via AND-gates, the different numbers being so chosen from a restricted set of numbers such that when the corresponding digits of two or more identity numbers are applied to the OR-gates, one for each level of significance of the digits, the output of the OR-gates represents a number outside the restricted set, whilst if the corresponding digits of only one identity number are applied, the output represents one of the restricted set, determining means in each user, or common to all users, responding to an output number of the restricted set to disable the arbitration means.

14. Apparatus as claimed in Claim 13, in which every number within the restricted set of identity numbers contains the same number, m, of ones, and the same number n-m, of zeros.

15. Apparatus as claimed in Claim 13 or 14, in which a group on fi OR-gates is used for two purposes in succession: first for evaluating the OR-function of the requestors' identity numbers, and then, if the number represented by this OR-function lies outside the restricted set of identity numbers, for arbitration.

16. Apparatus as claimed in Claim 13 or 14, including two groups of n OR-gates which are used concurrently, the first group for evaluating the OR-function of the requestors' identity numbers, and the second group for arbitration as if two or more requestors were present; apparatus being included also for disabling the arbitration means if the output of the first group of OR-gates represents a number falling within the restricted set of identity numbers.

17. Apparatus as claimed in Claim 15 or 16, in which every OR-gate referred to is formed by a conductor which can be energised by an open-collector driver or a current-generator circuit in every potential user.

18. Apparatus as claimed in Claim 15, 16 or 17, in which each potential user includes decoding means for determining the states of the outputs of the OR-gates used for evaluating the OR-function of requestors' identity numbers, or the said decoding means may be common to all users.

19. Apparatus as claimed in any of Claims 12 to 18, including means responsive to a request for control of the resource from one or more potential users, to cause all potential users to execute a sequence of operations in which they all have to complete the first operation before any of them is permitted to start the second operation, and similarly for all the operations up to the end of the sequence.

20. Apparatus as claimed in Claim 19, including means in each user to issue a signal at the start of the sequence when control of the resource is sought by that user, and means in each user to apply its identity number to the OR-gates following its issuance of such signal.

21. Apparatus for allocating control of a single resource shared by a plurality of users, substantially as hereinbefore particularly described with reference to the accompanying drawings.

Amendments to the claims have been filed as follows 1. A method of allocating control of a single resource shared by a plurality of users including means for arbitration to limit control to not more than one user at a time, in which a request for control of the resource from one or more potential users causes all potential users to execute a sequence of operations under a clockless synchronisation scheme, in which they all have to complete the first operation before any of them is permitted to start the second operation, and similarly for all the operations up to the end of the sequence, and in which the arbitration means is made ineffective or not used when there is only one user requesting control of the resource.

2. A method as claimed in Claim 1, in which the sequence of operations is in two parts, during the first part of which sequence a determination is made whether more than one user is requesting control and whether the resource has become available, and during the second part of which sequence arbitration can be made between two or more users requesting control, whereby a determination during said first part that only one user is requesting control and that the resource has become available causes the said second part not to take place.

3. A method as claimed in Claims 1 or 2, in which each potential user is assigned a different n-digit identity number chosen from a restricted set of numbers such that the OR-function of corresponding digits of two or more identity numbers represents a number outside the restricted set.

4. A method as claimed in Claim 3, in which every number within the restricted set of identity numbers contains the same number, m, of ones, and the same number, n-m, of zeros.

5. A method as claimed in Claim 3 or 4, in which a group of OR-gates is provided, one OR-gate for each level of significance of the digits of the identity numbers, and on a request for control of the resource being issued by one or more of the potential users, the group of OR-gates is used first for evaluating the OR-function of the requestors' identity numbers, and if this is found to represent a number falling outside the restricted set of identity numbers, the same group of OR-gates is then used in the arbitration process.

6. A method as claimed in Claim 3 or 4, in which two groups of n OR-gates are provided, one OR-gate in each group for each level of significance of the digits of the identity numbers, and on a request for control of the resource being issued by one or more of the potential users, the two groups of OR-gates are used concurrently, the first group for evaluating the OR-function of the requestors' identity numbers and the second group for carrying out the arbitration process as if there were two or more requestors; but if the output of the first group of OR-gates is found to represent a number falling within the restricted set of identity numbers, the arbitration process is abandoned or rendered ineffective.

7. A method as claimed in Claim 5 or 6, in which every OR-gate referred to is formed by a conductor which can be energised by an open-collector driver or a current-generator circuit in every potential user.

8. A method as claimed in Claim 5, 6 or 7, in which the determination of the states of the outputs of the OR-gates used for evaluating the OR-function of the requestors' identity numbers is effected by decoding means in each potential user or common to all users.

9. A method as claimed in any preceding Claim, in which, at the start of the sequence users seeking control of the resource issue a signal indicating this fact; these users then apply identity numbers, identifying them, to the OR-gates provided for the purpose of evaluating the OR-function of the said identity numbers; following this, all potential users examine the output of these OR-gates, and if they represent a valid identity number, indicating a single requestor, control is passed to that requestor as soon as the resource is available; but if the output from these OR-gates indicates that there is more than one requestor, arbitration proceeds.

11. A method of allocating control of a-single resource shared by a plurality of users, substantially as hereinbefore particularly described with reference to the accompanying drawings.

2. Apparatus for allocating control of a single resource shared by a plurality of users, including means for arbitrating to limit control to not more than one user at a time, means responsive to a request for control of the resource from one or more potential users, to cause all potential users to execute a sequence of operations under a clockless synchronisation scheme, in which they all have to complete the first operation before any of them is permitted to start the second operation, and similarly for all the operations up to the end of the sequence, means for determining when there is only one user requesting control of the resource, and means for disabling the arbitration means when the determining means so determines.

13. Apparatus as claimed in Claim 12, in which the sequence of operations is in two parts, during the first part of which sequence a determination is made whether more than one user is requesting control and whether the resource has become available, and during the second part of which sequence arbitration can be made between two or more users requesting control, whereby a determination during said first part that only one user is requesting control and that the resource has become available, causes the said second part not to take place.

14, Apparatus as claimed in Claim 12 or 13, including means in each user to issue a signal at the start of the sequence when control of the resource is sought by that user, and means in each user to apply its identity number to the OR-gates following its issuance of such signal.

15. Apparatus as claimed in Claim 13 or 14, in which each user has n identity lines and each user is assigned a different n-digit binary identity number, and there is a group of n OR-gates to which the individual identity lines of all the users are connected via AND-gates, the different numbers being so chosen from a restricted set of numbers such that when the corresponding digits of two or more identity numbers are applied th the OR-gates, one for each level of significance of the digits, the output of the OR-gates represents a number outsdide the restricted set, whilst if the corresponding digits of only one identity number are applied, the output represents one of the restricted set, determining means in each user, or common to all users, responding to an output number of the restricted set to disable the arbitration means.

16. Apparatus as claimed in Claim 15, in which every number within the restricted set of identity numbers contains the same number, m, of ones, and the same number, n-m, of zeros.

17. Apparatus as claimed in Claim 15 or 16, in which a group of n OR-gates is used for two purposes in succession: first for evaluating the OR-function of the requestors' identity numbers, and then, if the number represented by this OR-function lies outside the restricted set of identity numbers, for arbitration.

18. Apparatus as claimed in Claim 15 or 16, including two groups of n OR-gates which are used concurrently, the first group for evaluating the OR-function of the requestors' identity numbers, and the second group for arbitration as if two or more requestors were present; apparatus being included also for disabling the arbitration means if the output of the first group of OR-gates represents a number falling within the restricted set of identity numbers.

19. Apparatus as claimed in Claim 17 or 18, in which every OR-gate referred to is formed by a conductor which can be energised by an open-collector driver or a current-generator circuit in every potential user.

20. Apparatus as claimed in Claim 17, 18 or 19, in which each potential user includes decoding means for determining the states of the outputs of the OR-gates used for evaluating the OR-function of requestors' identity numbers, or the said decoding means may be common to all users.