EP0214961A1 - Procedure and device for allocating the right of access - Google Patents

Abstract

The allocation of access to a common device (3) shared between several items of equipment is defined by a value transition of a signal which can take several values and is circulated on a unidirectional closed control loop equipped with a means modifying the value at a point of the loop and of access allocation control circuits assigned individually to the equipment, each of these circuits, on the one hand, being transparent to any transition of its input signal (E) on the loop in the absence of an access request (D) from his equipment and, on the other hand, blocking any transition of his input signal during an access request from his equipment in order to grant him access to said organ common.

Description

Method and device for assigning access rights

The present invention relates to methods and devices for allocating access rights to an organ used in shared mode between several pieces of equipment, such as those applied in electronic and computer systems of local area networks or in switching systems of local area networks. transmission in which the equipment, such as terminal units or stations, are connected to a computer bus or communication channel which they must share in response to their access request. In such systems, the free transmission by any equipment as soon as it desires access to the common organ has the drawback of leading to a situation of collision between messages transmitted simultaneously by several equipment, the frequency of such a situation then being all the greater as the number of equipments is high. If such a mode of "taking" of the common organ can remain suitable for systems with a reduced number of devices, it cannot be suitable for extended systems which have to process a large number of messages. In addition, the need to repeat messages altered by a collision affects the final efficiency of the system. To limit possible collisions between messages, it is known to block any device wishing to send a message when the common unit is already used by another device. This mode of "taking" the common organ which can be designated by the expression

"listen before transmitting" does not yet avoid a collision between messages from two or more devices, ready to transmit and simultaneously awaiting the appearance of the "free" status before their own individual transmission.

This is why other modes of "taking" the common organ coexist. Among these other modes of "taking" the common organ, one of them consists in coming to interrogate successively from a controller, centralized or not, the different equipment arranged according to a fixed chain to interrupt this interrogation or consultation as soon as the the equipment then consulted is ready to transmit, this for the duration of its own transmission and to continue the consultation at the end of the transmission of the previous message. Such an exploration particularly affecting equipment not wishing to access, gives an equitable allocation of access between the equipment but nevertheless affects the efficiency of the system taking into account a significant exploration time at the level of each equipment, whether it is a requester or not. Above all, such an exploration has the disadvantage of being definitively interrupted in the event of a failure of the centralized controller or one of the equipment in the chain, which can put the entire system out of service.

Yet another mode of "taking" the common organ consists of assigning different priorities to the different equipment likely to access the common organ. This can be obtained, in particular, either by varying, in a variable way from one equipment to another, the attributions of access to the common organ so that among the equipments wishing to access the common organ it is the one to which is granted the shortest time for granting access which has priority, or by assigning to the various equipment different priority codes which define between them a sequence of priorities so that only the equipment with the highest priority has the 'access to the common organ.

In these modes of "taking" the common organ according to priorities, access to the common organ is not equitable, the equipment having high priorities always remains favored in the case of simultaneous access requests. Even in the case of priorities established according to evolutionary sequences to compensate for this lack of equity, the fact remains that the functional arrangement of the equipment resulting from each of the successive sequences leads to access allocations remaining inequitable during the lapse of application time of each sequence. In addition, the interactions between the equipment and the centralized controller or between the equipment in the absence of a centralized controller, to allow the allocation of access to a single equipment, require numerous interconnections and therefore lead to a complexity of the system.

The object of the present invention is to define a mode of allocation of access and therefore "of taking" of the body shared between different equipment making it possible to benefit from the advantages of the various aforementioned modes while avoiding their drawbacks. The present invention therefore relates to an allocation method of rights of access to a common organ shared between a plurality of devices, characterized in that it consists:

to define an access right by a value transition of a signal, having several possible values, circulated on a closed unidirectional access control loop associated with all of the individual pieces of equipment considered successively,

- to locally block this transition on said loop by the equipment which is requesting and the first encountered, during its period of use of said member and, - to modify at a point of said loop the value of the signal which propagates there .

It also relates to a device for allocating access rights to a common member shared between a plurality of equipment connected to this member, characterized in that it comprises a closed unidirectional control loop carrying said signal, a means for modifying at a point of the loop the value of said signal propagating on the loop, and a plurality of logic control circuits mounted on said loop and assigned individually to the equipment to which they are connected, to receive their own signal for requesting access to the common unit and issue them an access authorization signal, each capable of maintaining the circulation of the signal value transition on the loop in the absence of an access request signal received from its equipment , and block this transition to deliver the access authorization signal to its equipment during an access request emanating from it, during its period of use. ilisation of the common organ.

Other characteristics and advantages of the present invention will appear more clearly during the description given below of an exemplary embodiment with reference to the attached drawings. In these drawings:

FIG. 1 represents the device for assigning access rights, according to the invention, to a common bus, for example of a computer, in a computer system,

- Figure 2 illustrates by different diagrams the operation of the device according to the invention. In FIG. 1, a computer system has been diagrammed in which a plurality of devices 1-1, 1-2, ..., 1-n, can, at the request of each of them, access a computer 2 by a common bus 3 and in which a device for allocating access rights is used to resolve possible access conflicts of these equipments to the common member, in this case bus 3, while offering in an extremely simple fair and fast access to all equipment.

Of course, as a variant, in a switching system, the common member will be a switching channel shared between the various pieces of equipment or terminal stations.

This device, according to the invention, forms a circuit independent of that 3 assigned to the transmission of data or messages; it constitutes a unidirectional closed loop 5, called a control loop, successively passing through logic circuits 6-1, 6-2, .., 6-n assigned individually to the equipment 1-1, 1-2, ... 1- n, to which they are connected respectively.

According to the invention, the right of access of the equipment to the common member 3 is defined by a value transition of a signal which can take several possible values and kept in circulation permanently on the loop 5. In the example of embodiment described below, it has simply been considered that this signal, called loop signal, can take two possible values translated by the binary states 1 and 0, respectively. Of course this loop signal can take a larger number of values and define by all or part of the possible value transitions a right of access.

In Figure 1, the loop. 5 is equipped at one point with an inverter 7 for the change of binary state of the signal which it conveys, this inversion thus ensuring the presence of at least one transition on the loop. Logic circuits 6-1 to 6-n, each capable of assigning the access right of its equipment to bus 3 and said logic circuit for controlling access allocation, are identical to each other. Each of them is connected to its equipment by a link 8 called access request link by which it receives a significant access request signal simply called access request signal D, by convention in binary state 1 as soon as its equipment requests access and in binary state o otherwise. Each of them is also connected to its equipment by a second link 9, called the access authorization link, by which it delivers a significant access authorization signal known as simply the authorization signal A to its equipment, by convention. in binary state 1 as soon as the access right is assigned to its equipment and in binary state o otherwise. Each of these logic circuits also includes means, not shown, such as a flip-flop, capable of maintaining the state of the signal which it delivers on its output.

These logic control circuits which are identical to each other are easy to make, not illustrated, which is simply defined by the following logic equations, which govern the function of each of them in the control loop 5:

A = D. [(E⊕S) + A] (2)

In these equations the signs "+", "." And "⊕" translate the logical functions "OR", "AND", and "exclusive OR", respectively. In these equations (1) and (2) S is the output signal applied to the loop by any of the logic circuits considered, D is the access request signal it receives from its equipment, E its signal input received from the loop and to the access authorization signal which it delivers to its equipment.

The operation of the control loop 5 according to FIG. 1 is given below.

The functions performed by each of the logic circuits 6-1 to 6-n, which are indicated in the form of logic equations given above, show that in the absence of an access request, D = o and any logic circuit is transparent for its input state, that is to say copies on its loop output the state presented by its loop input and refuses its equipment the access authorization signal, A = o.

Under these conditions of no access request received by the successive logic circuits, the binary state taken by the output signal S of loop of one of these circuits becomes, by the loop section not including the inverter 7, the state of the input signal E of the logic circuit directly downstream. This same state of signal E therefore propagates from one logic circuit to another along the loop and is inverted by the loop section including the inverter to constitute a transition: this new input state will propagate identically to the previous one along the loop.

These same equations show that in the presence of an access request, D = 1, received by one of the logic circuits, at the arrival of a transition 1 / o or o / 1 caused by the inverter 7 and propagated, up to this logic circuit concerned, by the upstream circuits not requesting access and the loop sections not comprising the inverter, there is on the one hand blocking of the transition in this logic circuit by forced hold from its output S to its previous state and on the other hand access authorization issued to its equipment. For the correct accomplishment of these two functions performed by this logic circuit concerned, namely blocking of the transition then authorization of access, these will be obtained successively, by introducing a slight delay or a time delay in use, during the arrival of an input transition, of the signal D for obtaining the signal A, that is to say by allowing this logic circuit to "take" the transition, to authorize access, only if he previously blocked it. Such a delay guarantees, in the event of an almost simultaneous arrival of a transition and an access request on the corresponding inputs of the logic circuit considered, that an access authorization issued has been preceded by the internal blocking of this transition in question or that in the absence of blocking this transition there is no access authorization then granted. As soon as the access authorization is issued, A = 1, this blocking of the transition also has the effect of making the logic circuit insensitive to possible accidental fluctuations of its input signal, its output state being kept fixed. as long as the access request signal remains present therefore the message is not fully transmitted.

At the end of the transmission of the message, leading to the suppression of the access request signal D applied until this moment to the logic circuit concerned having issued the access authorization, there is copy of the input state E on the output S of this logic circuit and withdrawal of the access authorization signal, A = o. The transition, having allowed the previous access authorization while it was temporarily blocked on the loop during the transmission of the message, then crossed this logic circuit and occurs on the input of the logic circuit directly downstream.

The operation of the device according to Figure 1 is also illustrated in Figure 2. In this Figure 2 there are shown four diagrams illustrating the possible state o or 1 of the input signal E of one of the logic circuits, the state possible from the access request signal D received, state o or 1 taken by its output signal, as a consequence of the two previous signals, and state o or 1 of the access authorization signal A which results therefrom .

With regard to these diagrams, a phase I and a phase II corresponding to crossing the logic circuit have been caused by a transition o-1, and 1-o, respectively, in the absence of an access request: in these two phases the state of the output signal is the copy of the state of the input signal while the access authorization signal A remains at zero. We also revealed a phase III in which we illustrated the arrival of a transition o-1 on the logic circuit already receiving from its equipment an access request signal D, then the deletion of this request signal d 'access D, D = o. In this phase III we see that as long as the input E and output S states are identical, the access request D is not satisfied and the signal A remains at o. On the other hand, when a transition created by the inverter arrives at its input, the logic circuit blocks this transition, by maintaining its loop output signal in its previous state, and authorizing access, A = 1. When the access request disappears, D = o, corresponding to the end of message transmission, the output state S copies the input state E for the propagation of this transition to the following logic circuit and signal A takes level o. In this phase III, a dotted access request was further illustrated on the signal D, compared to that shown in solid lines, to schematize the minimum delay or offset indicated above and identified by t in the use of the access request to obtain the access authorization signal, A = 1.

In a phase IV, the arrival of a new transition 1-o of the state of the input signal has been represented, while the access request signal is present and then disappears after transmission of the corresponding message. This phase is analogous to phase III: there is a temporary blockage of the transition for the duration of the transmission. In phase IV, a pair of transitions resulting from a "parasitic" pulse on the signal E have also been illustrated, while the access authorization signal is already present, A = 1; these transitions appearing under such conditions do not disturb the transmission in progress, due to the maintenance of the authorization signal in its state 1 during the maintenance of the access request signal. When the access request signal disappears, there is a copy of the input state at the loop output, thus causing the natural disappearance of such parasitic transitions.

The presence of the inverter 7 on the control loop 5 makes it possible to guarantee that a transition remains continuously in circulation on the loop. If, of course, the circulation of such a transition is too rapid, in particular in application contexts where all of the common bus user equipment feels few and therefore can simultaneously be non-requesting access, there is instead of introducing one or more local timers on the control loop 5 to reduce the loop travel frequency, so as to assign a minimum period between two successive transitions.

The access allocation system ensures equitable distribution of access between all requesting devices, while avoiding multiple access conflicts. The simplicity of implementation, allows a very high speed of access, moreover, guarantees a good functioning of the system by the permanent maintenance of a transition in circulation on the control loop.

The present invention has been described with reference to an exemplary embodiment illustrated in the drawings; it is obvious that modifications can be made to it by replacing certain means with other equivalent means without departing from the scope of this invention. In particular, the realization of the logic circuits can be defined on the basis of logic functions different from those indicated, capable from the maintenance of a transition circulating on the loop of blocking this transition for the authorization of access and during the duration of access to the joint body.

Claims

1 / Method for assigning access rights to a common organ shared between a plurality of devices, characterized in that it consists of - defining an access right by a value transition of a signal having several possible values and put into circulation on a closed unidirectional access control loop associated with all of the individual pieces of equipment considered successively,

coming to locally block this transition on said loop by the equipment which is requesting access and the first encountered, during its period of use of said member, and

- to modify at a point in the loop the value of the signal known as the loop signal which propagates there.

2 / Device for allocating access rights to a common member shared between a plurality of equipment connected to this member implementing the method according to claim 1, characterized in that it comprises a closed unidirectional control loop , conveying said loop signal, means for modifying at a point in the loop the value of said loop signal and a plurality of logic control circuits mounted on said loop and assigned individually to the equipment to which they are connected to receive their own significant signal requesting access (D) to the joint body and providing them with a significant access authorization signal (A), each capable of maintaining the circulation of the transition in the absence of an access request signal received from his equipment, and block this transition to deliver the authorization signal (A) to his equipment during an access request emanating from it, during s the duration of use of the common organ. 3 / Device according to claim 2, characterized in that said logic circuits are identical to each other and each include combinatorial circuits transparent to the input signal for its output copying on said loop in the absence of a request signal access of the equipment to which the considered logical circuit is assigned and of combinational circuits blocking the passage of this transition during a request for access of the equipment to which it is assigned for authorize the access of this equipment to the common organ. 4 / Device according to one of claims 2 and 3, characterized in that said loop signal is a binary signal and that each of said logic circuits is defined by the logic equations:

A = D. [(E⊕S) + A] in which S is its output signal on the loop, E its input signal of the loop, D the access request signal received from its equipment and A the access authorization signal which it delivers to its equipment, and in which the signs "." "+" and "⊕" translate the logical functions "AND", "OR" and "exclusive OR", respectively.