Abstract:
A method and system of managing resources in a host bridge by determining whether resources are deficient, preventing a second device from obtaining further resources and if this measure does not enable a first device to obtain resources, guaranteeing all resources to the first device.

Description:
BACKGROUND 
     The invention relates to managing resources in a bus bridge. 
     A Peripheral Component Interconnect PCI bus, for example, may connect peripheral devices (“PCI masters”) such as CD-ROM drives, graphics accelerators and sound cards to other computer system components. Each master can send transaction requests, such as read and write requests, to main memory through the PCI bus. 
     Requests made from a PCI master to main memory must pass through a PCI host bridge, which can only accommodate a limited number of transactions due to finite internal buffer resources. When more than one device makes a request, the PCI host bridge acts as an arbiter and grants access to one or more of the PCI masters to increase use up to the limit of its resources. 
     The host bridge may use round-robin arbitration to grant access to requests in its buffer in first-in, first-out (FIFO) order. 
     In a conventional round-robin arbitration, aggressive PCI masters may make so many requests in a short time that all the buffer resources of the host bridge may be used before other devices can make a request. Even if a device resubmits its rejected request later, the request may be rejected repeatedly if the PCI resources are not available. Thus, a PCI master might have its requests rejected indefinitely and be effectively locked out, unable to send or receive data. 
    
    
     DESCRIPTION OF DRAWINGS 
     FIG. 1 shows an exemplary computer system. 
     FIGS. 2 and 3 illustrate the use of buffer resources. 
     FIG. 4 illustrates a relationship among states of resource allocation. 
     FIG. 5 is a flow chart of a method of managing resources according to the invention. 
    
    
     DESCRIPTION 
     FIG. 1 illustrates a computer system  5  that contains two PCI buses  10 ,  20 . Although two PCI buses are shown, computer system  5  can contain a greater or lesser number of buses. PCI masters  18 ,  28  are connected to PCI buses  10  and  20 , respectively. PCI master  18  is denoted a normal speed device, and PCI master  28  is denoted a graphics device. In other implementations, each of PCI buses  10 ,  20  may carry a different type and/or different number of devices than those shown. ISA bus  25  also is connected to PCI bus  20 . ISA bus  25  is considered a PCI master with respect to PCI bus  20 . 
     The PCI masters can initiate data transactions independently of each other. Each request is transferred along the PCI bus  10 ,  20  which can have a high clock rate and high carrying capacity, allowing it to transport many PCI master requests simultaneously. Requests can be directed, for example, to main memory  50 , which functions as the working memory for a CPU  60  and generally includes an array of memory devices such as dynamic access memory (DRAM). A local bridge  40 , called the system data/address controller (system d/a controller), regulates transactions between the CPU  60  and main memory  50 . 
     When a device connected to an individual PCI bus  10 ,  20  initiates a data transaction with another device connected to the same PCI bus or with main memory  50 , the transaction request passes through a PCI host bridge  30 . Those transactions are known as inbound transactions. The following discussion assumes that transactions are inbound, but the techniques described below apply to outbound transactions as well, such as transactions between CPU  60  and PCI masters  18 ,  28  or between masters on different PCI buses. 
     The PCI host bridge  30  can be implemented as part of a chipset. The chipset may be, for example, an Intel 460GX™ or any other compatible chipset. The PCI host bridge  30  acts as a gatekeeper, limiting the number of transactions that occur between the PCI devices  18 ,  28  and main memory  50 . 
     PCI master requests enter a transaction queue  34  of the PCI host bridge  30 . Each request includes a header that contains information about the source and target of the request, and a payload that contains the data being transported. The header and payload are divided within the PCI host bridge  30 . The header information enters the transaction queue  34  and, if memory is available, the payload information enters a transaction data buffer  36 . 
     As shown in FIG. 2, an exemplary transaction queue  34  contains the header information for four transactions labeled  1  through  4 . An arrow points from each transaction in the queue  34  to a corresponding block of memory space within the transaction data buffer  36 , indicating that each transaction header holds information required to associate it with its corresponding payload data. 
     The transactions can carry different amounts of data that occupy different amounts of memory. The transaction data buffer  36  contains extra memory space  37  because the four transactions do not occupy the full capacity of the buffer. 
     Data in the transaction data buffer  36  that is targeted to main memory is transported from the buffer through an expander bus  38 . In this manner, the transaction data buffer  36  is drained of data and can expend its resources on other transactions. 
     FIG. 3 illustrates a different set of transactions  5 - 8 . In this case, all resources of the transaction data buffer  36  are used by requests  5  and  6 , leaving transactions  7  and  8  without any buffer space in which to store their payloads, and those requests are rejected by the PCI host bridge  30 . To prevent a PCI master from becoming starved for resources indefinitely, the host bridge  30  stores and executes a resource starvation prevention algorithm, which can be enabled or disenabled by an administrator. The algorithm can be implemented, for example, as a state machine and associated registers and logic gates. 
     As shown in FIG. 4, the state machine includes three distinct states: a first “normal” state, a second “lock-out” state, and a third “lock-in” state. In the normal state, all PCI masters  18 ,  25  and  28  are given equal access, meaning that if resources are available, no PCI master  18 ,  25 ,  28  will be denied access to the buffer resources of the host bridge  30 . Then, if a PCI master, such as graphics device  28 , is unable to obtain resources, the algorithm proceeds to the lock-out state in which one of the PCI masters that already has been granted access is prevented from obtaining further access for a specified period of time. The algorithm can proceed back to the normal state from the lock-out state if the starved master  28  obtains access. Alternatively, it can proceed to the lock-in state, in which only the starved master is permitted access to the buffer resources of the host bridge  30 . 
     By implementing a three-state system, the algorithm provides both an intermediate resource-limiting state (the lock-out state) that is suited for cases of milder resource starvation, and a more extreme resource-limiting state (the lock-in state) that provides resources to PCI masters that are continually starved. Using different levels of resource-starvation prevention, the PCI host bridge  30  can prevent such starvation at an early stage and promote a more evenly balanced allocation of resources among the PCI masters  18 ,  25 ,  28 . 
     During the execution of the resource-starvation prevention algorithm, the PCI host bridge  30  employs a PCI timer  32  (FIG. 1) to reset the system to the normal state if a PCI master fails to return and claim resources on its behalf. The timer, which can be implemented in hardware or software, allows the system to remain in the lock-out or lock-in state for a specified time t 1 , that is greater than the average amount of time it takes for the expander bus  38  to drain the transaction data buffer  36 . 
     Further details of the operation of the PCI host bridge  30  are explained with reference to FIG.  5 . Initially, the timer  32  is reset  100 , any software flags (described below) that identify particular PCI masters  18 ,  25 ,  28  are removed. The PCI host bridge  30  proceeds  110  to the next transaction in its transaction queue  34  and determines  120  whether the total remaining buffer resources are sufficient to accommodate the next transaction. If there are enough remaining resources, the host bridge  30  proceeds  110  to another transaction in the buffer  34 . 
     If there are not enough buffer resources to accommodate a transaction, the transaction request is rejected  125 . Unless it is determined  128  that a PCI master has already been marked, the PCI master that added the most recently accommodated transaction is marked  130  with a first software flag as a “consumer”. After marking a PCI master “consumer” the host bridge proceeds  110  to the next transaction. If it is determined  128  that a “consumer” has already been marked, the host bridge  30  then determines  140  whether a non-marked master was rejected in  125 . If the last rejected transaction request was sent from the PCI master marked “consumer”, then the prevention system remains in its normal state and cycles back, proceeding  110  to a new transaction. If the rejected transaction request came from a PCI master that is not marked as a consumer, then that PCI master is marked  150  with a second software flag as “starving.” The host bridge  30  operates in the lock-out state, the timer  32  starts  155 , and the master that previously was marked “consumer” is prevented  160  from receiving any further resources. 
     After the host bridge proceeds  170  to the next transaction, it is determined  175  whether the timer has reached t 1 . If the timer has reached t 1 , the system returns to the normal state, and the timer and software flags are reset  100 . If, while in the lock-out state, the timer has not reached t 1 , the host bridge  30  determines  180  whether the PCI master marked “starving” has requested resources. If the PCI master has not requested resources, the host bridge  30  proceeds  170  to the next transaction. If the “starving” PCI master has requested resources and it is determined  190  that there are enough resources to accommodate its request, the system returns to the normal state and resets  100 . If there are not enough resources to accommodate the “starving” PCI master&#39;s request, the transaction request is rejected  195 , and the system changes to the lock-in state. 
     Upon entering the lock-in state, the timer  32  is reset  200  and starts  210  again. The host bridge  30  prevents  220  all other PCI masters except for the “starving” master from obtaining resources. The host bridge  30  proceeds  230  to the next transaction and determines  240  whether the timer  32  has reached t 1 . If the timer has reached t 1 , the system returns to the normal state and resets  100 . If the timer has not reached t 1 , it is determined  250  whether the “starving” PCI master has obtained the resources it requests. If it has, the system returns to the normal state and resets  100 . If it has not, the system cycles back and proceeds  230  to the next transaction. 
     Various features of the system can be implemented in hardware, software, or a combination of hardware and software. For example, some aspects of the system can be implemented in computer programs executing on programmable computers. Each program can be implemented in a high level procedural or object-oriented programming language to communicate with a computer system. Furthermore, each such computer program can be stored on a storage medium, such as read-only-memory (ROM) readable by a general or special purpose programmable computer, for configuring and operating the computer when the storage medium is read by the computer to perform the functions described above. 
     Other implementations are within the scope of the following claims.