Login| Sign Up| Help| Contact|

Patent Searching and Data


Title:
APPARATUS AND METHOD FOR ARBITRATING BETWEEN SIGNALS
Document Type and Number:
WIPO Patent Application WO/1984/002210
Kind Code:
A1
Abstract:
An arbitration system includes a first arbitration circuit (11) which arbitrates between first and second signals (BUSY I, BUSY II) which may contend for access to a system resource (44) such as a dynamic random access memory. The successfully arbitrated signal (ACK I or ACK II) is intermittently interrupted by a gate (21 or 28) in accordance with a further input signal (R/W REQ I or R/W REQ II). The output of the gate (21 or 28) is applied to a second arbitration circuit (34) to which is also applied a third input signal (REF CYC REQ) which may be a refresh request signal provided by a refresh timer (37) for a random access memory. An output signal (RW ACK) of the second arbitration circuit (34) is applied to a safety timer (46) which resets the first arbitration circuit (11) if the output signal from the gate (21 or 28) persists for more than a predetermined time.

Inventors:
LOCKWOOD JAMES MAXWELL (US)
COCHCROFT ARTHUR FRANKLIN JR (US)
Application Number:
PCT/US1983/001876
Publication Date:
June 07, 1984
Filing Date:
November 29, 1983
Export Citation:
Click for automatic bibliography generation   Help
Assignee:
NCR CO (US)
International Classes:
G11C11/34; G06F13/00; G06F13/18; G11C11/24; G11C11/406; (IPC1-7): G06F13/00; G11C11/24
Foreign References:
US3467948A1969-09-16
US4339808A1982-07-13
US4093878A1978-06-06
US3997872A1976-12-14
Other References:
IBM Technical Disclosure Bulletin, Vol. 23, No. 1, June 1980 (New York, US) ELLIS "Read/Write/Refresh Cycle Interlocking Circuit", pages 52 and 53, see the whole document
Download PDF:
Claims:
CLAIMS :
1. Apparatus for arbitrating between a plurality of at least three input signals (BUSY I, BUSY II, REF CYC REQ) capable of controlling a system resource (44), characterized by: first and second input means (12, 13) adapted to receive respective first and second input signals (BUSY I, BUSY II), first arbitration means (11) coupled to said first and second input means (12, 13) and adapted to arbitrate between said first and second input signals (BUSY I, BUSY II) to provide a corresponding one of first and second output signals (ACK I, ACK II) on respective first and second output means in dependence on the successfully arbitrated one of said first and second input signals (BUSY I, BUSY II); interruption means (21, 28) coupled to said first and second output means and adapted to intermittently inter¬ rupt the first or second output signal (ACK I or ACK II); and second arbitration means (34) coupled to said inter¬ ruption means (21, 28) and adapted to arbitrate between the intermittently interrupted output signal and a third input signal (REF CYC REQ) to provide a controlling signal for said system resource (44).
2. Apparatus according to claim 1, charac¬ terized in that said first arbitration means includes: a latch circuit (14) coupled to said first and second input means (12, 13); a flipflop circuit (26); delay means (23) coupled to said second input means (13); and a gating device (24) having inputs coupled to an output of said latch circuit (14) and an output of said delay means (23) and an output coupled to an input of said flipflop circuit (26) whereby said flipflop circuit (26) is set to a predetermined state only when. said latch circuit (14) is in an inoperative condition.
3. Apparatus according to claim 2, charac¬ terized in that said latch circuit (14) is a non metastable latch circuit.
4. Apparatus according to claim 3, charac¬ terized by reset timing means (46) adapted to reset said latch circuit (14) and said flipflop circuit (26) if the signal presented by said interruption means (21, 28) to said second arbitration means (34) persists for more than a predetermined time.
5. Apparatus according to claim 4, charac¬ terized by: first gating means (18) having inputs coupled to said first input means (12) and to said reset timing means (46) and an output coupled to a reset terminal of said latch circuit (14) whereby either the signal on said first input means (12) or the signal provided by said reset timing means (46) can reset said latch cir¬ cuit (14); and by second gating means (27) having inputs coupled to said second input means (13) and to said reset timing means (46) and an output coupled to a reset terminal of said flipflop circuit (26), whereby when the signal on said second input means (13) or the signal provided by said reset timing means (46) can reset said flipflop circuit (26).
6. Apparatus according to claim 5, charac¬ terized in that said interruption means includes respec¬ tive third and fourth gating means (21, 28), said third gating means (21) being coupled to said first output means, being arranged to receive a fourth input signal (R/W REQ I) and being operative only in the event that both said first output signal (ACK I) and said fourth input signal (R/S REQ I) are present, said fourth gating means (28) being coupled to said second output means, being arranged to receive a fifth input signal (R/W REQ II) and being operative only in the event that both said second output signal (ACK II) and said fifth input signal (R/S REQ II) are present.
7. Apparatus according to claim 6, charac¬ terized in that said system resource is a dynamic random OMPI WIPO 7( concluded) access memory, and by a refresh timing device (37) adapted to provide said third input signal (REF CYC REQ) at periodic refresh intervals.
8. A method for arbitrating between first (BUSY I), second (BUSY II) and third (REF CYC REQ) input signals capable of controlling a system resource (44) , characterized by the steps of arbitrating between said first and second input signals (BUSY I, BUSY II) to provide a first or second output signal (ACK I or ACK II) corresponding to the successfully arbitrated one of said first and second input signals (BUSY I, BUSY II); intermittently interrupting said output signal (ACK I or ACK II); and arbitrating between the intermittently interrupted output signal and said third input signal (REF CYC REQ) to provide a controlling signal for said system resource (44) .
9. A method according to claim 8, character¬ ized by the step of interrupting the arbitration between the first and second signals (BUSY I, BUSY II) if the output signal presented for arbitration with said third input signal (REF CYC REQ) persists for more than a predetermined period of time.
Description:
APPARATUS AND METHOD FOR ARBITRATING BETWEEN SIGNALS

Technical Field

This invention relates to apparatus and a method for arbitrating between a plurality of at least three input signals capable of controlling a system resource.

The invention has a particular application when the system resource is a dynamic random access memory, wherein the first and second input signals are for controlling data access to the memory, e.g. read/write or read- odify-write cycles, and the third input signal is for controlling a refresh operation for the dynamic random access memory.

Background Art Apparatus and a method of the kind specified are known from U.S. Patent Specification No. 3,824,409, which discloses in one embodiment an arbiter having three input lines and three output lines. The known arbiter has a disadvantage when the system resource requires the application of one of the input signals, for example the third input signal, within predeter¬ mined intervals of time, and when the other two signals may require access to the system resource for longer than one of said predetermined intervals of time. This disadvantage arises since if one of the first or second signals successfully obtains control of the relevant output line of the arbiter, it may maintain control of the system resource for an indefinite period of time, whereby the third input signal fails to obtain access to the system resource within one of said predetermined intervals of time when access thereto should be granted.

Thus, where the system resource is a dynamic random access memory (DRAM) that operates on the basis of storage of an electric charge that can leak off after a certain interval of time and must be refreshed within that interval in order for the system to operate properly,

OMPI

it is unacceptable for another signal that does not have the effect of refreshing the memory, except for that part of the memory that may be used by such other signal, to latch onto control of the access to the DRAM for a period of time longer than the refresh interval .

Disclosure of the Invention

It is the object of the present invention to provide apparatus and a method of the kind specified whereby the aforementioned disadvantage may be alle- viated.

Therefore, according to one aspect of the pre¬ sent invention, there is provided apparatus for arbitra¬ ting between a plurality of at least three input signals capable of controlling a system resource, characterized by: first and second input means adapted to receive respective first and second input signals, first arbi¬ tration means coupled to said first and second input means and adapted to arbitrate between said first and second input signals to provide a corresponding one of first and second output signals on respective first and second output means in dependence on the successfully arbitrated one of said first and second input signals, interruption means coupled to said first and second output means and adapted to intermittently interrupt the first or second output signal; and second arbitration means coupled to said interruption means and adapted to arbitrate between the intermittently interrupted output signal and a third input signal to provide a controlling signal for said system resource. It will be appreciated that the interruption of the output signal of the first arbitration means en¬ ables the possibility of the third input signal acquiring access to the system resource via the second arbitration means. A further advantage is that the apparatus is capable of operating at high speed.

According to another aspect of the invention, there is provided a method for arbitrating between first,

OMH

second and third input signals capable of controlling a system resource, characterized by the steps of: arbi¬ trating between said first and second input signals to provide first or second output signal corresponding to the successfully arbitrated one of said first and second input signals; intermittently interrupting said output signal; and arbitrating between the intermittently interrupted output signal and said third input signal to provide a controlling signal for said system resource. In brief summary of a preferred embodiment of the invention, arbitration takes place among first, second and third signals in two separate arbiters. The nature of the signals is such that one of them must have access to a system resource within each periodic interval of time, the period being determined by the nature of the system resource. The other signals seeking access to the system resource are of a nature such that each of them is likely to require access to the system re¬ source for only a short interval of time after obtaining access, though it is possible that each of the latter signals may maintain control of access to the system- resource for an indeterminately long period of time. The arbiter in which the arbitration between the latter signals takes place may include a latch circuit of the type described and claimed in U. S. Patent 4,093,878.

The circuit described therein provides a clear determin¬ ation as to which of two substantially contemporaneous signals applied to its input terminals will control the output thereof. The first arbiter further includes a flip-flop circuit controlled by an output signal from the latch circuit and by one of the contending signals. The output of the latch circuit also controls a gate to allow another signal to pass through it, .and in a similar manner, the flip-flop has an output circuit that controls another gate which, in turn, controls the passage therethrough of still another input signal. The other connections between the latch and the flip-flop circuit in the first arbiter result in only one of the

two gate circuits being open at a time to allow the passage of only one signal therethrough. As will appear more clearly from the description hereinafter, this has a particular advantage where the system resource is a dynamic random access memory, where the access signals may have three subintervals, or cycles. One is a cycle in which information at a given memory location is read. A second is a cycle in which either that information or a flag bit that determines access to the memory is modified. The third is a writing cycle in which new information is written into that memory address. Such read-modify-write (RMW) cycles must be carried out in unitary fashion so that the system resource must be interactively latched to a given input terminal from the beginning of the read cycle to the end of the write cycle. Where the operation is such that the input cir¬ cuit ceases to control access to the memory during the modify portion of the RMW cycle. The utilization of the additional input signals avoids the possibility of another input signal latching onto access to the memory. If that were to happen the information received through the second input terminal would be applied as a signal to be written into the first address, which would be completely incorrect. A combining circuit, for example an OR circuit, capable of responding to output signals from either of the gate circuits transmits the winning signal of the first arbitration to one of the input terminals of a latch circuit in a second arbiter. The second arbiter has a second input terminal connected to receive signals from a third source, such as a refresh timer, and the second arbiter has interconnections between the latch circuit and a flip-flop circuit in the second arbiter such that only the latch circuit or the latter flip-flop circuit will produce an output signal at any given time. Signals from the latter latch and flip-flop circuit are both applied (but in alternate intervals of time, since they cannot overlap) to separate gates that control

access to the system resource that is to be controlled. If the third signal is in the nature of a refresh signal that must be applied during each periodic interval, such a signal may be derived from a refresh timer connected to the output circuit of the second arbiter to be con¬ trolled by signals therefrom so that the refresh oper¬ ation will take place at the end of a predetermined interval from the last such refresh as determined by an output signal from the second arbiter output circuit through which the refresh signal passes.

In addition, an output signal from the terminal at the output of the second arbiter that passes winning signals from the first arbiter may be used to control a safety timer so that if there are no individual trans- actions in the winning signal within a predetermined length of time the safety timer will be actuated to interrupt operation of the first arbiter.

Brief Description of the Drawings

One embodiment of the invention will now be described by way of example with reference to the accom¬ panying drawings, in which:

Fig. 1 is a block diagram illustrating a two- stage arbitration circuit in accordance with the present invention. Figs. 2-9 are timing diagrams used in des¬ cribing the operation of the arbitration circuit in Fig. 1.

Best Mode for Carrying Out the Invention

The arbitration system illustrated in Fig. 1 includes a first arbiter 11 having two input terminals 12 and 13 to which potentially competing signals may be applied. The competition between the signals is due to the fact that they may be applied to the terminals 12

and 13 simultaneously, or substantially so. For con¬ venience, and to be consistent with the fact that the circuit can be used with a variety of different types of signals, the signal applied to the terminal 12 is indi- cated as BUSY I, and that applied to the terminal 13 is identified as BUSY.II. The BUSY I signal is connected through the terminal 12 directly to one of the input circuits of a latch circuit 14, such as that described in U.S. Patent 4,093,878. This input circuit is one of the input circuits to an open-collector NAND gate 16, the output circuit of which is connected to the setting terminal of a flip-flop circuit 17. The input terminal 12 is also connected to one of the input circuits of an OR gate 18, the output circuit of which is connected to the reset terminal of the flip-flop 17. The nature of the signals in this part of the overall circuit is such that the signals at the terminal 12 are low-active, and the output signals of the OR gate are also low-active and are connected to a reset terminal that responds to low signals. The other input terminal 13 is connected through an inverter 19 to the other input circuit of the NAND gate 16 of the latch circuit 14.

The Q output terminal of the flip-flop 17 of the latch 14 is connected to one of the input circuits of an AND gate 21 that has another input circuit con¬ nected to receive signals applied to an input terminal 22. The latter signals are designated as read-write request I (R/W REQ I) signals, which are related to the BUSY I signals in the sense that, in normal operation, both the BUSY I signal and the R/W REQ I signal must be present at the same time to propagate a controlling signal farther along the system, and thus these signals mutually enable each other in the AND gate 21 to obtain an output signal from the AND gate only when both of these input signals are present.

The input terminal 13 that receives the BUSY II signal is also connected to a delay element 23 that

delays the BUSY II signal by an interval of time, such as about 50 ns., sufficient to be certain that the latch 14 has settled into a fixed condition in the event that both the BUSY I and the BUSY II signals are applied simultaneously or nearly so. The output of the delay element 23 and the Q/ output signal of the flip-flop 17 in the latch 14 are connected to input terminals of a NAND gate 24, the output terminal of which is connected to the setting terminal of a flip-flop circuit 26. The input terminal 13 is also connected to one of the input circuits of another OR gate 27, the output circuit of which is connected to the resetting terminal of the flip-flop 26. Like the OR gate 18, the OR gate 27 is of the type that has low active input circuits and a low active output circuit, and the resetting terminal of the flip-flop 26 is actuated by a low signal.

The Q output terminal of the flip-flop 26 is connected to one of the input circuits of an AND gate 28 that has another input circuit connected to an input terminal 29 through which another read-write request signal (R/W REQ II) is received. Propagation of a signal through the AND gate 28 requires that the BUSY II signal and the R/W REQ II signal both be present at the same ime. The output terminals of the AND gates 21 and

28 are connected to input terminals of another OR gate 31. Since a typical purpose of the output signal of the OR gate 31 is to request a read-write cycle of operation of a computer system, the signal at that point is iden- tified as R/W CYC REQ and is applied to one input cir¬ cuit of an open-collector NAND gate 32 of a latch cir¬ cuit 33 in a second arbiter 34. The latch circuit 33 is identical with the latch circuit 14, and in addition to the open-collector NAND gate 32, it comprises a flip- flop circuit 36.

The second signal to be applied to the second arbiter 34 is, in this embodiment, the output signal of

a refresh timer 37. This signal is applied through an inverter 38 to a second input circuit of the open col¬ lector NAND gate 32 and to a delay element 39 to delay the signal by, for example, 50 ns. The flip-flop 36 has a Q output terminal connected to an OR gate.41 and a Q/ terminal connected to one of the input circuits of a NAND gate 42. The NAND gate has another input circuit connected to the delay element 39 to receive delayed signals therefrom. The output terminal of the NAND gate 42 is connected to the setting terminal of a flip-flop circuit 43, and a clearing signal at the end of the refresh interval, and thus identified as REF CLR/, is connected to the reset¬ ting terminal of the flip-flop 43. A signal to clear the flip-flop 36 after completion of a read-write cycle is identified as R/W CLR/ applied to the resetting terminal of the flip-flop 36. The Q output terminal of the flip-flop 43 is connected to another input circuit of the OR gate 41, the output circuit of which is con- nected, to a system resource 44 that is to be controlled by whichever signal gains control of the second arbiter 34 at any given time. A memory in a computer is a typical system resource 44. It is to be understood that there will be occasions when no signal is being applied to either input terminal of either arbiter 11 or 34.

The Q output terminal of the flip-flop 36 is also con¬ nected to a safety timer circuit 46 that has an output terminal connected to one input terminal of each of the OR gates 18 and 27. The operation of the circuit in Fig. 1 is such that an R/W CYC REQ signal will be produced at the output of the OR gate 31 if the R/W REQ I signal and the BUSY I signal are supplied simultaneously to the input terminals 22 and 12 and no signals are applied to the terminals 13 and 29. In a corresponding manner, an output signal R/W CYC REQ will be produced at the output terminal of the OR gate 31 if a BUSY II signal is applied to the input terminal 13 simultaneously with an R/W REQ

II signal to terminal 29 and no signals, are applied to the terminals 12 and 22.

The arbitration operation comes into effect if BUSY I and BUSY II signals are applied substantially contemporaneously to the input terminals 12 and 13. The nature of the latch 14 is such that, if the BUSY I signal obtains preference, an output signal based on the BUSY I will be produced at the Q terminal of the flip- flop 17 and applied to enable the AND gate 21 to trans- mit the R/W REQ I signal therethrough. At the same time, the Q/ output signal of the flip-flop 17 goes low and disables the NAND gate 24, preventing the delayed BUSY II signal from passing through that NAND gate to the setting terminal of the flip-flop 26. On the other hand, if the BUSY II signal applied to the input terminal 13 obtains preference, it will disable the NAND gate 16 by driving the output of the inverter 19 low. Just to be sure that the latch 14 has had time to respond to a BUSY I signal, if such a signal has just preceded the BUSY II signal, the BUSY II signal is required to pass through the delay element 23 to delay it by approximately 50 ns before being applied to the NAND gate 24. If the latch 14 has not been actuated in response to a BUSY I signal, the Q/ output terminal of the flip-flop 17 will be high, so that a high output signal from the delay line 23 will result in a low signal at the output of the NAND gate 24, and this low signal will be of the proper polarity to actuate the setting of the flip-flop 26. It will thus be seen that, when the timing of the BUSY I and BUSY II signals is such that the BUSY I signal is prior to the BUSY II signal, the flip-flop 26 will be prevented from receiving a setting signal because the NAND gate 24 will be disabled by the Q/ output signal of the flip-flop 17. Conversely, when the BUSY II signal is prior to the BUSY I signal, the NAND gate 16 will be prevented from operating by virtue of the inverted BUSY II signal supplied through the inverter 19 to the input of the AND gate 16.

When the BUSY II signal applied to the input terminal 13 is successful in obtaining control of the arbiter 11, a high signal is produced at the Q output terminal of the flip-flop 26 and applied to the AND gate 28 to enable it. This allows the R/W REQ II signal applied to the terminal 29 to pass through the AND gate 28 to the OR gate 31 in the same way that the output of the AND gate 21 was able to pass through the OR gate 31. Either signal through the OR gate may be considered an R/W CYC REQ signal and used as one of the input signals to the second arbiter 34.

The operation of the arbiter 34 is similar to that of the arbiter 11, except that its two input sig¬ nals are the R/W CYC REQ signal and the output signal of the refresh timer 37. The output signal of the arbiter 34 is applied through the OR gate 41 to the system resource 44.

The operation of the system in Fig. 1 will be described in more detail with reference to the timing diagrams in Figs. 7-9. However, before considering the detailed timing diagrams, it will be helpful to refer to Figs. 2-6, which indicate the basic symbology used in the timing diagrams.

Fig. 2 illustrates a time relationship between two signals A and C. A third signal B is illustrated but has no effect on the other two during the interval illustrated. Within this interval, the signal A goes from a high level to a low level and therefore has a falling edge. A circuit that would be represented by the relationship in Fig. 2 would be one in which a component having an output signal represented by wave¬ form C was caused to go from its low level to its high level due to the falling edge in waveform A, alone. The directions, or polarities, of the transitions are not important; what is important is that an event repre¬ sented by the dot on one of the waveforms be on the arrow directed toward the other of the waveforms.

Fig. 3 is symbolic of a condition in which an event (the rising edge) oh waveform A, or an event (the rising waveform) on waveform B, or both of these events, can cause the event (falling edge) on waveform C toward which both of the arrows point.

Fig. 4 illustrates a condition in which an event (the rising edge) on waveform B and a condition (the fact that the.waveform A is at its high level) must both happen to cause an event (the falling edge) on waveform C to occur.

Fig. 5 is symbolic of a condition in which an event (the rising edge) on waveform A causes events (falling edges) on both waveforms B and C.

Fig. 6 illustrates a condition in which an event (the rising edge) in waveform B happens because a prior event (the falling edge) in waveform A occurred, but the relationship between the two is not completely described. There may be delays or additional logic dependencies that are not shown. With the symbols in Figs. 2-6 in mind, Fig. 7 will be considered. This figure illustrates signals produced during normal operation of the circuit in Fig. 1 in which read/write cycles occur without any conten¬ tion between the BUSY I and BUSY II signals. The graphs in Fig, 7 are identified by signal designation and the circuit point at which they occur. The first condition to be described with the assistance of Fig. 7 is the occurrence of a BUSY I signal along with an R/W REQ I signal . In Fig. 7, some event that precedes any of the operations in the circuit in Fig. 1 causes the BUSY I signal at the terminal 12 to go from its low value to its high value, thereby producing a rising edge 47. Since the BUSY II signal is assumed to be inactive, the terminal 13 will be at its low level, and these two conditions cause .the Q output terminal of the flip-flop 17 to go to its high condition, as indicated by the

arrow 48. This is acknowledged by a signal ACK I, which goes from its low condition to its high condition along a rising edge 49.

The R/W REQ I signal applied to the terminal 22 is produced independently of the BUSY I signal but must occur, or be true, during the time that the BUSY I signal is in existence. The existence of the BUSY I signal is proven by the fact that the ACK I signal has gone to its high level, and this, together with the existence of the R/W REQ I signal at its high level, as indicated by an arrow 51, produces a rising edge 52 in the R/W CYC REQ signal at the output of the AND gate 21 and, therefore, at the output of the OR gate 31.

It will be assumed throughout the circum- stances described with reference to Fig. 7 that the refresh timer 37 does not request a refresh cycle in contention with the R/W CYC REQ signal. As a result, the latter signal at the output of the refresh timer 37 remains at its low level throughout the period of time represented in Fig. 7 and the output of the inverter 38 remains at its high level during the same time. This condition, together with the rising edge 52 of the R/W CYC REQ signal, produces the necessary input conditions of the the NAND gate 32 to set the flip-flop 36. These conditions are represented by an arrow 53, which points to a rising edge 54 at the Q terminal of the flip-flop 36. Having the Q terminal of the flip-flop 36 in its high condition represents an acknowledgment that the read/write signal can control the system resource 44, as indicated by an arrow 56 leading from the rising edge 54 to a rising edge 57 on a START CYCLE signal, which is representative of the output signal of the OR gate 41. This is the beginning of an inverval identified as the READ I interval in which access to the system resource 44 is controlled.

The duration of the READ I interval is not determined by any of the timing means in the circuit in

Fig. 1 but by the signals applied to that circuit. As a result, the indeterminate length of the READ I interval is indicated by a dotted arrow 58. At the end of that indeterminate time, the RWACK signal is caused to return to its low value along a falling edge 59. As a result, and as is indicated by an arrow 61, the output signal of the OR gate 41 returns along a falling edge 62 from its high value to its low value. The falling edge 59 also results in a falling edge 63 in the R/w REQ I signal at the terminal 22. The time between the falling edge 59 and the falling edge 63 is indeterminate, as is indi¬ cated by a dotted arrow 64. The falling edge 63 causes the AND gate 21 to be disabled, and thus causes the output signal of that AND gate and of the OR gate 31, which is the R/W CYC REQ signal, to return along a falling edge 66 from its high value to its low value, as is pointed out by an arrow 67.

Independently, the BUSY I signal applied to the input terminal 12 drops along a falling edge 68 from its high value to its low value, and this event causes the flip-flop 17 to be reset. The causal relationship between these two events is indicated by an arrow 69 pointing toward a falling edge 71 representative of the fact that the Q output terminal of the flip-flop 17 is returning to its low level at the end of the ACK I signal. This is the end of control of the system re¬ source 44 by signals applied to the terminals 12 and 22.

When the BUSY II signal and the R/W REQ II signal are applied to the input terminals 13 and 29, respectively, the circuit shown in Fig. 1 undergoes a set of transitions similar to those just described. A rising edge 72 in the BUSY II signal, together with the fact that the ACK I signal is at its low level, estab¬ lishes the conditions, represented by an arrow 73, necessary to cause the Q output terminal of the flip- flop 26 to shift along a rising edge 74 from its low level to its high level. At a later time, the R/W REQ

OMPI

II signal rises along a rising edge 76 from its low value to its high value, and this condition and the fact that the ACK II signal is already at its high level establish the conditions, represented by an arrow 77, to cause the R/W CYC REQ signal to go from its low level to its high level along a rising edge 78. This produces an effect identical with that produced at occurrence of the rising edge 52, namely, that the rising edge 78, along with the fact that the REF CYC REQ signal is at its low level, result in a condition, indicated by an arrow 79, that causes the flip-flop 36 to be set so that the Q terminal thereof goes from its low value to its high value along a rising edge 81. This, in turn, produces a condition, represented by an arrow 82, to cause the output signal of the OR gate 41 to go from its low value to its high value along a rising edge 83 and establish the beginning of the second reading interval READ II.

As before, the duration of the READ II inter¬ val is indeterminate and at some time after the rising edge 83, and as is indicated by a dotted arrow 84, the read/write acknowledge signal RWACK at the output ter¬ minal of the flip-flop 36 is caused, by circuit elements not shown in Fig. 1, to return along a falling edge 85 from its high level to its low level . This produces a condition, indicated by an arrow 86, that causes the output signal of the OR gate 41 to return from its high level to its low level along a falling edge 87, thereby terminating the interval READ II.

Subsequently, as indicated by a dotted arrow 88, the R/W REQ II signal returns from its high level to its low level along a falling edge 89, which disables the AND gate 28 and produces a condition, indicated by an arrow 91, that causes the R/W CYC REQ signal at the output terminal of the AND gate 28 and the output ter- minal of the OR gate 31 to return from its high level to its low level along a falling edge 92. Independently, the BUSY II signal is terminated and returns from its

OMPI WIPO

high level to its low level along a falling edge 93, thereby producing a condition represented by an arrow 94 that causes the ACK II signal to return along a falling edge 96 from its high level to its low level as the flip-flop 26 is reset and the Q terminal thereof returns to its low level ,

This completes the description of non-con¬ tending operation of the circuit in Fig. 1, first by the BUSY I signal and the R/W REQ I signal, and later by the BUSY II signal and the R/W REQ II signal.

Fig. 8 represents the timing conditions when a read-write cycle is interrupted by a refresh signal from the refresh timer 37.

The read-write cycle happens to be one that originates with the BUSY I signal and the R/W REQ I signal, but it could just as well be one that originates with the BUSY II signal and the R/W REQ II signal. The initial part of the cycle is identical with the initial part of the cycle in Fig. 7, and the events and condi- tions are illustrated by the same reference numerals, up to the reference numeral 57 at the beginning of the READ I interval, and this part of the cycle will not be described again in detail .

The refresh timer 37 produces an output signal REF CYC REQ that goes from its low value to its high value along a rising edge 97 sometime during the READ I inter¬ val. However, this does not interrupt the read opera¬ tion. Instead, the REF CYC REQ signal remains at its high level until the R/W REQ I signal has finished its first active, interval and the flip-flop 36 is reset by a read/write clear (low) signal, R/W CLR/. This occurs sometime after the beginning of the READ I interval, as indicated by a dotted arrow 98 that points toward a falling edge 99 of the RWACK signal at the Q output terminal of the flip-flop 36. This supplies a low input voltage on one input circuit of the OR gate 41, as indicated by an arrow 100, and since the other input circuit of the OR gate also has a low voltage, the

output voltage of the OR gate 41 drops from its high value to its low value along an edge, indicating the end of the READ I interval and the loss of control of the system resource 44 by the R/W REQ I signal. The read portion of the R/W REQ I signal terminates at a time indicated by a dotted arrow 102 as the signal moves along a falling edge 103. This disables the AND gate 21, as is indicated by an arrow 104, and causes the output terminal of the AND gate to drop along a falling edge 106. This is the R/W CYC REQ signal that is also present at the output terminal of the OR gate 31.

The falling edge 99 of the RWACK signal, together with the high level at the output terminal of the refresh timer 37, as indicated by the REF CYC REQ signal, produces the conditions, indicated by an arrow 107, necessary to set the flip-flop 43 and cause the output terminal thereof to go along a rising edge 108 from its low value to its high value.

While there is a substantial interval indi- cated between the rising edge 97 at the beginning of the REF CYC REQ signal and the rising edge of the REFACK signal at the Q output terminal of the flip-flop 43, there is a minimum possible length of time between these two events due to the fact that the delay element 39 prevents the flip-flop 43 from being set instantan¬ eously with the occurrence of the rising edge 97. This prevents the flip-flop 43 from being set during an inter¬ val of time when an R/W CYC REQ signal might also be trying to set the flip-flop 36. This delay is very use- ful in establishing proper operation of the arbiter 34. The rising edge 108 of the REFACK signal applied to the OR gate 41 produces two effects, as indicated by arrows 109 and 111. It results in having a high signal applied to the OR gate 41, which institutes a new start cycle signal at the output of that OR gate to control the system resource 44. It also terminates the REF CYC REQ signal from the refresh timer 37 and

OMPI SNAT\

causes the latter signal to return from its high value to its low value along a falling edge 112.

While the REFACK signal is at its high level, and the system resource 44, which is assumed in this embodiment to be a dynamic random access memory, is being refreshed, the R/W REQ I signal may return from its low level to its high level along a rising edge 113 at the beginning of the WRITE interval of that signal. The BUSY I signal and, therefore, the ACK I signal have remained at their high levels since their respective rising edges 47 and 49. The fact that the ACK I signal is at its high level enables the AND gate 21 so that the rising R/W REQ I signal completes the conditions indi¬ cated by th arrow 114 to cause the output terminals of the AND gate 21 and the OR gate 31 to rise to their respective high levels at the beginning of the R/W CYC REQ signal, as indicated by the rising edge 116 in that signal .

The R/W CYC REQ signal does not immediately take over control of the arbiter 34 and the system resource 44. Instead, the refresh operation continues for such time as is necessary, as is indicated by a dotted arrow 117, and at the end of that time, the flip- flop 43 is set by a refresh clear signal REF CLR/ of the proper polarity, which causes the REFACK signal to drop along a falling edge 118 from its high level back to its low level. This makes both of the input terminals of the OR gate 41 have a low signal applied to them, which establishes the condition, indicated by an arrow 119, to cause the start cycle signal at the output terminal of the OR gate 41 to drop from its high level to its low level along a falling edge 121, thereby terminating control of the system resource 44 by the refresh cir¬ cuit. The falling edge of the start cycle signal, together with the fact that the REF CYC REQ signal at the output of the refresh timer 37 has already returned to its low level, and further coupled with the fact that

OMPI

{/Λ/ y , WIPO

the R/W CYC REQ signal is waiting at its high level, establish the conditions indicated by an arrow 122 necessary to set the flip-flop 36 and cause the RWACK signal at the Q output terminal thereof to go from its low value to its high value along a rising edge 123.

This condition, as indicated by an arrow 124, represents the application of a high voltage to the upper input terminal of the OR gate 41 and is sufficient to cause the START CYCLE output signal of that OR gate to shift along a rising edge 126 from its low level to its high level. The system resource 44 is now in its WRITE I interval, which, insofar as the circuit in Fig. 1 is concerned, is identical with the READ II interval in Fig. 7. Other components related to the system re- source 44 control the operation of the system resource to allow it to distinguish between a READ II interval and a WRITE I interval, but those components are not part of the present invention. The events that ter¬ minate the WRITE I interval are identical with those that terminate the READ I interval in Fig. 7 and are indicated by the same reference numerals. Therefore, it is unnecessary to describe the operation in detail again.

This completes the description of one of the important capabilities of the circuit in Fig. 1, that is, its ability to allow a refresh operation to take place between a read and a write cycle in a read-modify- write operation. Furthermore, this can be done without interfering with either the read operation, the write operation, or the refresh operation. Instead, the refresh operation is inserted after a read operation and before a write operation, while the system resource 44 is not under the control of either of those signals. The write operation cannot start too soon, and thereby interfere with the refresh operation, because the latter maintains control of the system resource for as long as is necessary, and during that interval, the write signal is held in a buffer (not shown).

Fig. 9 illustrates another important operating characteristic of the circuit in Fig. 1, namely the ability of either of the sets of signals applied to the first arbiter 11 to maintain control of that arbiter throughout a complete read-modify-write cycle, even though the other set of signals applied to that arbiter would attempt to take over control, and could do so during the modify portion of the cycle.

The entire first part of the operation shown in Fig. 9 is identical with the first part of the oper¬ ation shown in Fig. 7 up through the termination of the R/W CYC REQ signal at the falling edge 66. The events during that part of the cycle are illustrated by the same reference numerals, and it is therefore not neces- sary to describe this part of the operation in detail again.

In Fig. 9, the falling edge 63 of the R/W REQ I signal does not represent the end of the complete read-modify-write cycle but only the end of the read portion thereof. However, this does disable the AND gate 21, which establishes the necessary condition, indicated by the arrow 67, to cause the R/W CYC REQ signal at the output terminal of the OR gate 31 to return from its high level to its low level along the falling edge 66. In the absence of the arbiter of this invention, a contending signal applied to the terminals 13 and 29 would be able to take over control of access to the system resource 44. What prevents that from occurring in the present invention is that the Q/ output signal of the flip-flop 17 is at a low level as long as the ACK I signal is at a high level. The low level Q/ signal from the flip-flop 17 disables the NAND gate 24 and prevents the flip-flop 26 from being set by the BUSY II signal applied to the input terminal 13. As a result, the AND gate 28 is never enabled during this part of the cycle, but the AND gate 21 remains enabled by the ACK I signal so that when the R/W REQ I signal returns to its high

level at the time of the rising edge 127, the condition indicated by an arrow 128 is established to return the R/W CYC REQ signal at the output of the AND gate 21 and of the OR gate 31 to return to its high level along a rising edge 129. This places the system in the same condition as it was at the occurrence of the rising edge 52 of the R/W CYC REQ signal. In accordance with the similarity between these parts of the operating cycles, the subsequent events are identified by the same refer- ence numerals as used during the READ I interval, but with the addition of a postscript "A" . The only dif¬ ference is that the event that takes place during the interval between the rising edge 57A and the falling edge 62A is the WRITE I interval, which takes place while information related to some extent to that read during the READ I interval is being written into memory. At some time following the termination of the R/W CYC REQ signal indicated by the falling edge 66A, which time is not under the control of the circuit in Fig. 1, the BUSY I signal applied to the input terminal 12 returns from its high level to its low level along the falling edge 131, thereby establishing the necessary condition indicated by an arrow 132, to reset the flip- flop 17 and return the Q output terminal thereof to the low level, as indicated by a falling edge 133 of the ACK I signal. The BUSY II signal applied to the input terminal 13 has remained at its high level throughout the entire read-modify-write cycle of the R/W REQ I signal, and, with the occurrence of the falling edge 133, the conditions, represented by an arrow 134, are complete for setting the flip-flop 26 and thereby caus¬ ing the ACK II signal at the Q output terminal of that flip-flop to rise along the rising edge 136 from the low level to the high level thereof. This condition, to- gether with the fact that the R/W REQ II signal has long been at its high level, completes the conditions indi¬ cated by the arrow 137 necessary to enable the AND gate 28. As a result, the output signal of this AND gate,

and the output signal of the OR gate 31, R/W CYC REQ shifts along a rising edge 138 from the low level to the high level . This places the circuit in Fig . 1 in exact¬ ly the same condition that it was in at the time of the rising edge 78 of the R/W CYC REQ signal in Fig. 7. The remainder of the operation depicted in Fig. 9 will therefore be identified by the same reference numerals as the part of Fig. 7 describing the READ II interval, and this operation will not be described again in detail. It is possible for parts of the system that supply the input signals to the terminals 12, 13, 22 and 29 to malfunction so that one of the sets of signals, either the BUSY I signal and the R/W REQ I signal or the BUSY II signal and the R/W REQ II signal could have the levels necessary to maintain control of the system resource 44 for an indefinite period of time. In order to prevent this from happening, the RWACK system from the Q output terminal of the flip-flop 36 of the second arbiter 34 is connected to the safety timer 46 to gen- erate an output signal if the RWACK signal has been stationary without any shifting from a read to a write cycle for a certain period of time, such as about ten microseconds, the safety timer will produce an output signal to be applied to the low active input OR gates 18 and 27 to reset whichever one of the flip-flops 17 or 26 happens to be locked into its set condition by the malfunctioning signal. The safety timer 46 is of a type that starts its timing operation over again at the occurrence of each change of the RWACK signal and only times out if the RWACK signal remains at a constant value too long .