United States Patent [191
`Christiansen et al.
`
`US005787264A
`
`‘
`
`[11] Patent Number:
`[45] Date of Patent:
`
`5,787,264
`Jul. 28, 1998
`
`[54]
`
`METHOD AND APPARATUS FOR
`ARBITRATING ACCESS To A SHARED BUS
`
`395/296
`5,572,686 11/1996 Nunziata et al.
`5,581,782 12/1996 Sarangdhar et al. .................. .. 395/800
`
`[75]
`
`[73]
`
`[21]
`[22]
`[51]
`[52]
`
`[5 8]
`
`[56]
`
`Inventors: Kevin M. Christiansen. Saratoga;
`Mark {K- Stubbs; Felton: B11196
`Eckstem- Cup?mnm all of Cahf-
`_
`Assignee: Apple Computer, Inc.. Cuperttno.
`Calif.
`
`_
`AP p 1' No" 437’233
`Film;
`May 8, 1995
`
`6
`Int. Cl. .................................................... .. H01J 13/00
`US. Cl. ........................ .. 395/293; 395/288; 395/299‘,
`395/290; 395N262 395/297
`Field of Search ................................... .. 395/290. 293.
`395/296. 297. 299. 300. 304. 800. 291.
`845. 298. 305. 726. 727. 729. 731. 732.
`303
`
`_
`Reftll‘ellces Cited
`U‘S. PATENT DOCUMENTS
`
`4,987,529
`
`l/199t Craft et a1. ............................ .. 395/293
`
`primary Examiner_AyaZ R_ sh?ikh
`Assistant Examiner-Raymond N. Phan
`Attorney Agent, or Firm—Burns. Doane. Swecker &
`Mathis. L.L.P.
`
`[57]
`
`ABSTRACT
`
`The present invention is directed to providing a computer
`system which arbitrates control of a shared bus among plural
`devices included in the computer system. In accordance with
`the present invention. at least one of the devices is afforded
`a higher priority than the’ mmainjng d¢vicCS_ yet none of the
`remaining devices are effectively denied system bus access
`or control for extended periods of time. The present inven
`tion can therefore increase operating efficiency even as the
`number of devices included in the computer system is
`increased to achieve enhanced processing power. In
`addition. the present invention can provide sophisticated
`multimedia features. including real time signal processing.
`without sacri?cing overall operating efficiency. In accor
`dance with the present invention. the plural devices arbitrate
`system bus control in a manner which achieves acceptable
`multimedia results when processing real time data streams
`
`5,237,696
`
`8/1993 Best . . . . . . . . . . . . . . .
`
`. . . .. 395/293
`
`Pucker eilal
`
`.
`
`..
`
`,
`
`,
`
`ansen et
`
`395/842
`a a1
`8/1995
`5,438,666
`395/732
`5506.989 4/1996 Boldt et a1,
`395/299
`5519.838 5/1996 Ziegler et a1. .
`5,528,767
`6/1996 Chen ..................................... .. 395/293
`
`Such as video data streams,_ audio data streams. animation
`data streams. and so forth. yet which does not sacri?ce the
`gflé'emainmg devices in the computer system to the
`'
`
`-
`
`-
`
`a
`
`-
`
`20 Claims, 3 Drawing Sheets
`
`fl 4
`PROCESSOR
`
`18
`/
`MEMORY
`CONTROLLER
`
`20
`(1
`MEMORY
`(DRAM / CACHE)
`
`REQUEST 28
`GRANT 30 I
`
`BRIDGE
`
`f1 6
`
`ARBITER
`
`<
`i-
`|
`|
`|
`|
`T
`
`P
`2
`23
`
`PCI LOCAL BUS
`[3T _|
`_
`VIDEO INPUT
`|
`E UEST 28
`__QEANL60_> DMA CONTROLLER |
`ARBCR_T_TIQ\L_32_ _ _ _ _]
`'
`
`>
`
`I25
`NON_REAL TIME REQUEST 28
`I/O NODE
`<____GRANT 50
`
`|
`|
`I
`I
`
`l
`I
`l
`T
`4 j
`i
`|__________J
`
`VIDEO DATA
`FROM EXTERNAL
`SOURCE
`
`Apple Exhibit 1011
`Page 1 of 10
`
`

`
`US. Patent
`
`Jul. 28, 1998
`
`Sheet 1 of 3
`
`5,787,264
`
`PROCESSOR f M
`
`18
`/
`MEMORY
`CONTROLLER
`16
`BRIDGE f
`
`20
`/
`MEMORY
`DRAM/CACHE
`
`1O
`
`T2
`PCI LOCAL BUS ,/
`
`l
`
`'
`
`I
`Y
`26
`24 NON-REAL TIME
`22 REAL TIME
`ARBUER f 1/0 NODEf
`I/O NOOE “f
`
`PROCESSOR
`
`14
`
`18
`/
`MEMORY
`CONTROLLER
`16
`BRIDGE f
`
`REOuEsT 2a
`GRANT 30
`
`2O
`/
`MEMORY
`(DRAM/CACHE)
`
`g _ — ~ — — — — - _ ._ _ ,_ __ __
`
`41>
`
`PC] LOCAL BUS
`
`FIG. 2
`
`REQUEST 2a
`I26
`NON_REAL ME
`1/0 NODE ‘w
`
`'-
`1
`1
`i
`I
`i
`
`I31 _]
`RE UEST 28
`AR ER <—9—— VIDEO INPUT
`|
`B“ _‘—QBA—TM OMA CONTROLLER |
`P
`ARBCREIQALJL __ _A__ _ _
`2
`r
`23
`
`i
`I
`
`'
`'
`I
`'
`T
`|—--_____J
`
`VIDEO OATA
`FROM EXTERNAL
`SOURCE
`
`Apple Exhibit 1011
`Page 2 of 10
`
`

`
`U.S. Patent
`
`Jul. 28, 1998
`
`Sheet 2 0f 3
`
`5,787,264
`
`ROUND ROBIN GRANT ASSERTED AND BUS IDLE
`
`RESET
`
`BUS TAKEN 0R TIMER HIT END COUNT
`
`COUNTING
`
`HIGH GRANT ASSERTED
`
`HIGH GRANT DEASSERTED
`
`FIG. 4
`
`Apple Exhibit 1011
`Page 3 of 10
`
`

`
`US. Patent
`
`Jul. 28, 1998
`
`Sheet 3 of 3
`
`5,787,264
`
`ENABLE COMPUTER j5°0
`SYSTEM
`
`502
`
`ARBCRIT=
`T
`
`N
`
`AWARD BUS CONTROL 512
`TO DEVICE OF 1ST f
`PRIORITY PER EQUAL
`ACCESS ARB.
`
`AWARD BUS CONTROL
`TO NEXT DEVICE OF
`1ST PRIORITY PER
`EQUAL ACCESS ARB.
`
`[-520
`SUSPEND OP'N
`OF DEVICE OF A
`1ST PRIORITY
`
`r504
`EXAMINE BUS REQUEST
`OF DEVICE OF 2ND
`PRIORITY; DISABLE LIMITED
`PERIOD OF TIME FOR
`OPERATION EXECUTION
`
`I [506
`
`EXECUTE OPERATION OF
`DEVICE OF 2ND PRIORITY
`
`EXECUTION
`COMPLETE
`
`[-510
`RETURN OPERATION TO BUS
`MASTER DEVICE OF 1ST
`PRIORITY PER
`EQUAL ACCESS ARB. OR TO
`DEVICE WHOSE OPERATION
`WAS SUSPENDED
`
`FIG. 5
`
`Apple Exhibit 1011
`Page 4 of 10
`
`

`
`5 387.264
`
`2
`of the bus. As with ?rst-in/?rst-out arbitration. daisy chain
`ing can ensure that all devices will have an opportunity to
`acquire control of the shared bus. However. this advantage
`is acquired at the expense of overall operating ef?ciency
`when. for example. multimedia features are provided. For
`example. a relatively low level device which could process
`data at a later time can be awarded control of the bus even
`though a real time signal is being received which requires
`immediate attention.
`Computer systems which use a central arbiter to arbitrate
`access to a shared bus among a plurality of devices typically
`afford each device requesting access to the bus a given
`hierarchical priority. This priority can be determined on the
`basis of predetermined criteria. such as; (l) the importance
`of the operation to be executed by the device. relative to
`those of other devices; and (2) the time which the device has
`been waiting to gain control of the shared bus. Using the
`priority of each device requesting control of the shared bus.
`the central arbiter will queue the various requests from the
`plural devices. This queuing of requests can. of course. be
`recon?gured each time a new request is received.
`An advantage to the use of a central arbiter is that the
`plurality of devices included in a computer system can be
`attributed varying priorities in gaining access to and control
`of a shared bus. such that drawbacks associated with ?rst
`in/?rst-out arbitration and daisy chaining are avoided.
`However. prioritization techniques based on the use of a
`central arbiter can be relatively complex and can often result
`in one or more lower priority devices of the computer system
`being effectively denied access to the shared bus for
`extended periods of time. For example. the possibility that
`one or more devices would be denied control of the bus is
`quite high in multimedia based systems. wherein devices
`which execute real time operations can dominate system bus
`control; when these highest priority devices are idle. system
`bus control is awarded to the next lower priority devices.
`Only when all other devices are idle do the very lowest
`priority devices. acquire system bus control. Accordingly.
`the very lowest level devices would have great di?iculty
`ever obtaining system bus control. Thus. while the use of a
`central arbiter overcomes the drawbacks of ?rst-in/?rst-out
`arbitration and daisy chaining. it suffers the drawback of
`effectively denying bus system control to some devices.
`Accordingly. it would be desirable to provide a computer
`system wherein the control of a shared bus by a plurality of
`devices included in the computer system is provided in a
`manner whereby overall operating e?iciency is enhanced
`without effectively denying one or more devices in the
`computer system from control of the bus for extended
`periods of time. Further. it would be desirable to provide a
`computer system wherein such enhanced operating e?i
`ciency can be achieved even with an increased number of
`devices included in the computer system having access to
`the shared bus. Further. it would be desirable to provide
`enhanced operating efficiency in a computer system which
`provides sophisticated multimedia features. such as real time
`audio/video data processing. animation and so forth.
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`1
`METHOD AND APPARATUS FOR
`ARBITRATING ACCESS TO A SHARED BUS
`
`BACKGROUND OF THE INVENTION
`
`1. Field Of The Invention
`The present invention relates generally to computer sys
`tem architecture and control. and more particularly to a
`method and apparatus for arbitrating the access of multiple
`devices in a computer system to a shared bus of the
`computer system.
`2. State of the Art
`As computer systems become increasingly more complex.
`the manner by which they access and control shared devices
`becomes a signi?cant factor in maintaining high system
`throughput and operating ef?ciency. For example. as the
`number of devices that share a common bus in a computer
`system is increased. the computer system must more ef?
`ciently arbitrate control of the bus among the devices.
`Known techniques for arbitrating access to a shared bus
`have been deemed acceptable. given the relatively small
`number of devices and the absence of time critical
`operations. such as real time signal processing. in conven
`tional computer systems. However. these techniques have
`etfectively limited the number and types of devices which
`can be connected to tie shared bus without affecting pro
`cessing e?iciency. For example. sophisticated multimedia
`features cannot be included in conventional computer sys
`tems without imposing a trade-off in overall operating
`e?iciency of the computer system. This is because computer
`systems which provide multimedia features must be able to
`process large quantities of data in real time; for example. real
`time audio and video data streams.
`Conventional techniques for arbitrating control of a
`shared bus in a computer system are of two general types:
`(1) those which cannot assign a high priority to a device that
`performs time critical operations. such as real time signal
`processing; and (2) those which can assign hierarchical
`priorities to all devices of the computer system but which. in
`so doing. allow the higher priority devices to dominate
`control of the computer system and effectively deny lower
`priority devices from obtaining control of the shared bus.
`Currently available arbitration techniques include: (1) ?rst
`in/?rst-out arbitration; (2) “daisy-chaining”; and (3) use of a
`central arbiter. With ?rst-in/?rst-out arbitration. individual
`requests from the plurality of devices sharing a common bus
`in a computer system are queued in the order in which they
`arrive at an arbiter of the computer system. Such a scheme
`ensures equal access among the plurality of devices to the
`bus so that no one device will be denied access to the bus for
`an extended period The disadvantage of ?rst-inl?rst-out
`arbitration is that it does not take into account the increas
`ingly more diverse and sophisticated architecture of com
`puter systems. such as multimedia computer systems.
`wherein the range of features and overall operating eli
`ciency can be enhanced by providing different devices of the
`computer system different priorities in accessing the shared
`bus.
`Daisy chaining is similar to ?rst-inl?rst-our arbitration in
`that a ?xed routine is used to arbitrate requests from plural
`devices of a computer system so that no single device will
`be denied control of the bus over extended periods of time.
`With daisy chaining. a bus available signal indicating that
`the shared bus is available for use is transmitted from one
`device to the next in a predetermined order. Once a device
`which is requesting access to the bus receives the bus
`available signal, that device can access and/or take control
`
`SUMNIARY OF THE INVENTION
`
`The present invention is directed to providing a computer
`system which arbitrates control of a shared bus among plural
`devices included in the computer system. In accordance with
`the present invention. at least one of the devices is atforded
`a higher priority than the remaining devices. yet none of the
`remaining devices are effectively denied system bus access
`or Control for extended periods of time. The present inven
`
`65
`
`Apple Exhibit 1011
`Page 5 of 10
`
`

`
`5.787.264
`
`3
`tion can therefore increase operating e?iciency even as the
`number of devices included in the computer system is
`increased to achieve enhanced processing power. In
`addition. the present invention can provide sophisticated
`multimedia features. including real time signal processing.
`without sacri?cing overall operating efficiency. In accor
`dance with the present invention. the plural devices arbitrate
`system bus control in a manner which achieves acceptable
`multimedia results when processing real time data streams
`such as video data streams. audio data streams. animation
`data streams. and so forth. yet which does not sacri?ce the
`access of remaining devices in the computer system to the
`shared bus.
`In accordance with exemplary embodiments of the
`present invention. at least one device performs time-critical
`operations such as inputting/outputting serial or real time
`data streams. and can request relatively immediate bus
`system control via a dedicated signal line The remaining
`devices are lower-priority devices which can request the
`system bus control via an equal access arbitration scheme
`whereby all of the lower priority devices have an equal
`chance of acquiring system bus control. and via the use of
`standard bus request lines. In an absence of a signal on the
`dedicated signal line from the at least one device. system bus
`control is awarded to one of the lower level devices using the
`equal access arbitration scheme.
`In accordance with exemplary embodiments. a computer
`system for processing data includes. a system bus for
`transferring signals within said computer system; a plurality
`of devices of a ?rst priority. each of said devices of ?rst
`priority generating a ?rst signal to request control of said
`system bus; at least one device of a second priority for
`generating a second signal to request control of said system
`bus; and an arbiter responsive to said ?rst signal from each
`of said plurality of devices of ?rst priority. and to said
`second signal from said at lea st one device of second
`priority. for arbitrating control of said system bus among
`said plurality of devices of ?rst priority using equal access
`arbitration in an absence of detecting said second signal and.
`upon detecting said second signal. granting control of said
`system bus to said at least one device of second priority.
`Further. exemplary embodiments are directed to a method
`for processing data in a computer system which includes
`multiple devices connected with a common system bus.
`comprising the steps of. assigning a ?rst plurality of devices
`included in said computer system a ?rst priority. each of said
`plurality of devices generating a ?rst signal to request
`control of said system bus; assigning at least one additional
`device included in said computer system a second priority.
`said at least one additional device generating a second signal
`to request control of said system bus; and controlling access
`to said system bus among said ?rst plurality of devices and
`said at least one device. said step of controlling. further
`including the steps of: arbitrating control of said system bus
`among said plurality of devices of ?rst priority using equal
`access arbitration in an absence of said second signal; and
`granting control of said system bus to said at least one device
`of second priority upon detecting said second signal.
`BRIEF DESCRIPTION OF THE DRAWINGS
`These and other features and advantages of the invention
`will be readily apparent to those skilled in the art from the
`following written description. when read in conjunction with
`the drawings. in which:
`FIG. 1 illustrates an exemplary embodiment of a com
`puter system with a plurality of devices attached to a high
`performance bus.
`
`20
`
`25
`
`35
`
`45
`
`50
`
`55
`
`65
`
`4
`FIG. 2 illustrates a computer system according to an
`exemplary embodiment of the present invention;
`FIG. 3 illustrates an equal access arbitration scheme
`according to an exemplary embodiment of the present
`invention;
`FIG. 4 illustrates an arbitration method according to an
`exemplary embodiment of the present invention; and
`FIG. 5 illustrates an exemplary ?owchart relating to an
`arbitration method in accordance with the present invention.
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENT
`FIG. 1 illustrates a computer system for processing. data.
`the computer system having a plurality of devices which
`communicate over a shared system bus 12. In the exemplary
`FIG. 1 embodiment. the system bus which is used to transfer
`signals can be. for example. a Peripheral Component Inter
`connect (PCI) local bus. A PCI Local Bus is described in
`“PCI Local Bus Speci?cation.” Review Draft Revision 2.1.
`published Oct. 21. 1994. by PCI Special Interest Group. the
`disclosure of which is hereby incorporated by reference in
`its entirety. However. it will be appreciated by those skilled
`in the art that the present invention is not limited to a PCI
`local bus. but can be used with any high performance bus for
`interconnecting plural devices. such as highly integrated
`peripheral control devices. peripheral add-on boards.
`processor/memory devices and so forth.
`As illustrated in FIG. 1. a plurality of devices are il1us~
`trated which can request control of the system bus 12 to read
`or write data from or to another device. For purposes of the
`following discussion. any device which can request access
`to or control of the system bus 12 will be referred to as a bus
`master device. Those skilled in the art will appreciate that
`any other devices which do not request system bus control
`can also be connected to the system bus 12. As illustrated in
`FIG. 1. the plurality of bus master devices can include. but
`is not limited to. a processor 14 and associated processor
`bridge 16. a real time input/output (I/O) device 24. and a
`non-real real time I/O device 26.
`The processor bridge 16 allows a processor 14. such as the
`main processor of a computer system. to access the other
`devices connected to the PCI bus. One example of this type
`of access is when the processor 14 performs read or write
`opm'ations to registers that are contained in either the real
`time I/O device 24 or the non-real time 110 device 26. The
`processor bridge 16 also allows either of the IIO devices 2A
`and 26 to access a system memory 20 via a memory
`controller 18 in known manner.
`According to exemplary embodiments of the present
`invention. each of a plurality of the devices is assigned a ?rst
`priority. At least one additional device is assigned a second
`priority. According one embodiment of the present
`invention. the bus master device assigned the second priority
`is the bus master device which handles user speci?ed
`priority operations. such as time critical processing of serial
`or real time data streams. including video data streams.
`audio data streams. animation data streams. and so forth.
`The operations assigned second priority operations are typi
`cally operations which need special attention by the com
`puter system. such as real time transfers of data which
`should not be interrupted for a given period of time.
`For example. if a video data stream is being transferred
`from an external device through the computer system to a
`display screen. interruptions in the transfer of the video data
`stream to the computer system will be noticeable to an
`observer of the display screen. In the exemplary embodi
`
`Apple Exhibit 1011
`Page 6 of 10
`
`

`
`5
`ment of FIG. 1. the real time I/O device 24 is therefore
`designated as the bus master device of second priority. In the
`exemplary FIG. 2 embodiment. the real time input/output
`device 24 is represented as a video input direct memory
`access (DMA) controller 31 which serves as the bus master
`device of second priority. The other bus master devices
`shown. namely the processor bridge 16 and the non-real time
`I/O device 26. are assigned the ?rst lower priority since they
`are not performing time critical operations: rather. the
`devices of the ?rst lower priority can. for example. perform
`any non-real time operation.
`The protocol for gaining control of the system bus is
`termed arbitration and is overseen by an arbiter means.
`represented as an arbiter 22. for arbitrating control of the
`system bus among the plurality of devices of ?rst priority
`and the at least one device of second priority. It will be
`appreciated by those skilled in the art. that the arbiter 22 can
`be located anywhere throughout the computer system. The
`arbiter 22 has a plurality of request lines 28 coming in from
`the bus master devices and a pltn'ality of grant lines 30 which
`are each connected to one of the bus master devices. The
`arbiter can. in accordance with an exemplary embodiment.
`include a processor 23 for performing the various arbitration
`functions based upon one or more user con?gurable arbi
`tration schemes. Those skilled in the art will appreciate that
`conventional programming techniques can be used to pro
`gram the arbiter to implement the functionality described
`herein.
`According to the exemplary embodiment illustrated in
`FIG. 2. the arbiter 22 is responsive to a ?rst signal from each
`of the plurality of devices of ?rst priority and to a second
`signal from the at least one device of second priority to
`arbitrate control of the system bus. The arbiter 22 is. in an
`exemplary embodiment. connected to each of the bus master
`devices by the request line 28 and by a grant line 30. Those
`skilled in the art will appreciate that a single bi-directional
`line can alternately be used. if desired. for the request and
`grant signals. According an exemplary embodiment of the
`present invention. the bus master devices of ?rst priority can
`request control of the system bus by asserting their request
`lines 28. If the arbiter grants the request. the arbiter sends a
`grant signal to the requesting bus master device. In order to
`ensure that all of the bus master devices of ?rst lower
`priority have an equal opportunity to use the bus. the arbiter
`uses an equal access arbitration scheme. For example. a
`round robin arbitration scheme which awards system bus
`control to each of any user-speci?ed bus master devices of
`?rst priority in a ?xed. sequential order. can be used as an
`equal access arbitration scheme. Alternately. any arbitration
`scheme which ensures equal access among the bus master
`devices. such as token ring protocol. can be used as well.
`Each bus master device of ?rst priority is only granted a
`user-con?gurable limited period of time to control the bus
`with each request signal. As a result. if a given bus master
`device of ?rst priority can not complete the number of
`operations associated with a given transaction within the
`limited period of time it has been assigned the bus. the given
`bus master device will have to make another request which
`will eventually be granted by the arbiter 22 pursuant to the
`round-robin arbitration scheme. The limited period of time
`can be con?gured by the user to take criteria such as the
`number of devices connected to the system bus into account.
`A possible arbitration scheme is illustrated in FIG. 3
`which has ?ve bus master devices labelled A-E of ?rst
`priority. As illustrated in FIG. 3 by arrows 1-5. if all ?ve of
`the bus master devices of ?rst priority are requesting access
`to the bus. the arbiter ?rst grants access Lo bus master device
`
`6
`Afollowed in sequence by bus master devices B.C.D. and B.
`If all of the non-priority bus master devices keep requesting
`the bus. the arbiter will continue to grant access in this
`rotating. ?xed sequence. fashion. However. should a given
`one of the bus master devices A-E not request access to or
`control of the bus at the time the arbiter would otherwise
`o?er control to that given bus master device. the arbiter
`simply skips that bus master device and offers system bus
`control to the next sequential bus master device which has
`asserted its bus request signal.
`For example. if only bus master devices A and B are
`requesting access. the arbiter will rotate access to e bus just
`between the non-priority bus master devices A and B as
`illustrated by arrows I and 6. Furthermore. if bus master
`devices A. C. and E are requesting access to the bus. the
`arbiter will rotate access to the bus between bus master
`devices A. C. and E as illustrated by arrows l1. l3. and 5.
`Thus. a ?xed rotational sequence is used to sequentially
`grant system bus control among only those bus master
`devices of ?rst priority which are asserting their bus request
`signal.
`In addition to the request line 28 and the grant line 30. the
`bus master device of second priority also has an arbitration
`critical line 32 (labelled ARBcrit in FIG. 2) connected to the
`arbiter 22. In an exemplary embodiment. when the bus
`master device of second priority wants control of or access
`to the system bus. the bus master device of second priority
`asserts its request line as well as the ARBcrit line. Upon
`receiving the request and ARBcrit signals. the arbiter then
`grants control of the bus to the bus master device of second
`priority without regard to the equal access arbitration
`scheme.
`According to an exemplary embodiment. the bus master
`device of second priority can keep control of the bus for as
`long as the bus master device of second priority asserts the
`ARBcrit signal. In other words. the ARBcrit signal blocks.
`or inhibits. the arbiter 22 from terminating control of the bus
`by the bus master device of second priority at the end of the
`user-con?gurable limited period of time normally granted to
`a requesting bus master device. As a result. the bus master
`device of second priority can perform all of the necessary
`operations for completing transfer of serial or real time data
`streams without losing control of the bus.
`According to an exemplary embodiment of the present
`invention. the arbiter 22 can immediately grant control of the
`bus to the bus master device of second priority. In alternate
`embodiment. the arbiter 22 can delay the grant for a prede
`termined period of time. for example. at least a su?cient
`amount of time for the bus master device currently in control
`of the bus to complete the single instruction it is currently
`executing and buffer status information. For example. the
`delay can be set to three or more clock cycles in an
`exemplary embodiment. This delay gives a bus master
`device of ?rst priority presently using the bus an opportunity
`to complete a current operation before the bus master device
`of second priority is granted control of the bus. and thereby
`avoids the bus master device of ?rst priority from entering
`a deadlock situation.
`According to an exemplary embodiment of the present
`invention as described above. bus masters of ?rst priority
`can be guaranteed an opportunity to complete one transac
`tion (for example. a transaction including one or more
`instructions) when granted control of the bus for the prede
`termined limited period of time. assuming that the ARBcrit
`signal is not asserted. This ensures that the remaining bus
`master devices of ?rst priority are offered a fair chance to
`
`5.787.264
`
`10
`
`15
`
`25
`
`30
`
`35
`
`40
`
`45
`
`55
`
`65
`
`Apple Exhibit 1011
`Page 7 of 10
`
`

`
`7
`use the bus. As illustrated in FIG. 4. if a bus master device
`of ?rst priority receives a grant from the arbiter to take
`control of the system bus. the bus master device granted
`control has a predetermined period of time during which it
`can take control of the bus. Again. this predetermined period
`of time is user-con?gurable. In the exemplary FIG. 2
`embodiment. this predetermined period can be a value on the
`order of 16 clock cycles of the idle time as de?ned by the
`PCI Local Bus speci?cation and the current count can be
`tracked with a counter.
`More particularly. idle time can be de?ned as the IRdy
`and Frame signals being deasserted (high) in accordance
`with PCI bus protocol. If the bus master device of second
`priority requests control of the bus during this period of
`time. the bus master device of second priority is granted
`access to the bus. In this case. the arbiter can. if desired. be
`con?gured to hold. or store. a count representing the elapsed
`idle time of a bus master device previously granted control
`of the system bus until the bus master device of second
`priority releases control of the bus. Then. the incrementing
`of the count resumes where it left o?c and continues to the
`predetermined value. If the count reaches the predetermined
`value. an internal state bit in the arbiter can be set to indicate
`that the bus master device of ?rst priority is attempting to
`hold the bus. This bit allows the arbiter to advance to the
`next requesting bus master device of ?rst priority without
`allowing a transaction from bus master device previously
`granted system bus control.
`FIG. 5 illustrates an exemplary ?owchart of an operation
`associated with the exemplary embodiment illustrated in
`FIG. 2. In FIG. 5. the computer system is enabled at block
`500. The ARBcrit signal is examined in decision block 502
`to determine whether the bus master device of second
`priority has requested system bus control. If so. operation
`proceeds to block 504 wherein the bus request line of the bus
`master device of second priority can be examined. Further.
`the predetermined limited period of time for executing an
`operation can be disabled so that the bus master of second
`priority can retain operation of the system bus for as long as
`the ARBerit signal is asserted.
`In block 506. the bus master device of second priority
`executes operations. such as time-critical operations. Deci
`sion block 508 represents an examination of the ARBcrit
`signal to determine whether the bus master device of second
`priority has completed executing its time-critical operations.
`If not. the bus master device of second priority is permitted
`to complete such operations. However. if such operations are
`complete. ?ow returns via block 510 to the bus master
`device of ?rst priority which had previously been in control
`of the system bus at the time the ARBcrit signal was
`asserted. Of course if the ARBcrit signal was asserted at
`power up (i.e.. block 502). system bus control is supplied to
`the ?rst bus master of ?rst priority which is to receive
`control pursuant to the equal access arbitration scheme.
`Returning to the decision block 502. if the ARBcrit signal
`was not asserted at the time the system was enabled. then the
`arbiter will award priority to the ?rst bus master of ?rst
`priority in accordance with the equal access arbitration
`scheme in block 512. In block 514. it is examined whether
`the bus master selected by the arbitration scheme has
`accepted the grant of the system bus. If not. decision block
`516 examines whether the predetermined time delay has
`expired. If so. operation ?ows to block 524 to select the next
`bus master of ?rst priority pursuant to the equal access
`arbitration scheme.
`Returning to decision block 514. assuming that the bus
`master device of ?rst priority selected by the arbiter has been
`
`10
`
`20
`
`25
`
`35
`
`45
`
`55
`
`65
`
`5.787.264
`
`8
`granted control of the system bus. and that the bus master
`device has accepted such control. the ARBcrit signal is
`monitored in decision block 518. Again. if the ARBcrit
`signal becomes true at any time while another bus master
`device of ?rst priority is in control of the bus. operation
`proceeds to block 520 wherein operation of the bus master
`device of ?rst priority is suspended. and operation ?ows to
`blocks 504-510.
`Assuming that the ARBcrit signal has not been asserted in
`block 518. operation ?ows to decision block 522 wherein the
`predetermined. limited period of time during which a bus
`master device of ?rst priority can execute control of the
`system bus is monitored. Provided this period has not
`expired. monitoring of the ARBcrit signal and the
`predetermined. limited period of time continue. However.
`once the predetermined. limited period of time has expired.
`operation of the bus master device of ?rst priority currently
`in control of the system bus is terminated. and operation
`returns to block 524. wherein the next bus master device of
`?rst priority is selected pursuant to the equal access arbi
`tration scheme.
`Those skilled in the art will appreciate that the present
`invention