Back to results
US 4,682,284 AGranted
Queue administration method and apparatus
AssigneeAmerican Telephone & Telegraph Co., AT&T Bell Lab.
InventorEldred P. Schrofer
Life of this patent
Estimating the term…
Loading patent…
Loading patent…
AssigneeAmerican Telephone & Telegraph Co., AT&T Bell Lab.
InventorEldred P. Schrofer
Estimating the term…
A memory subcontroller (203) of a computer (100) includes a queue (301) for storing read and write requests issued by memory using units (101-103) to a memory (104), apparatus (303, 304) for executing requests on the memory, and a circuit (302) for administering the queue. When the queue is empty and the executing apparatus is ready to receive a request for execution, a request incoming from a using unit bypasses the queue: it is received by the executing apparatus directly and is not stored in the queue. Otherwise, the queue administration circuit stores the request in the queue and then awaits results of validity checks on the stored request. If the request is found to be invalid, generally the administration circuit discards the request from the queue by freeing the queue location (210) or locations that store the invalid request to store the next received request. The invalid request is then overwritten by the next received request.
An arrangement comprising:
An arrangement comprising:
A control apparatus for interfacing a resource to at least one unit issuing tasks to the resource, comprising:
A control apparatus for interfacing a resource to at least one unit issuing tasks to the resource, comprising:
A computing system comprising:
A computing system comprising:
A method of administering a queue in a computing system having a resource, at least one resource using unit for making requests of the resource, and storage apparatus organized as the queue having a tail end, the storage apparatus including a plurality of storage locations for holding resource requests, the method comprising the steps of:
A method of administering a queue in a computing system having a resource, at least one resource using unit for making requests of the resource, each request having at least one part, storage apparatus organized as the queue having a head end and a tail end, the storage apparatus including a plurality of storage locations for sequentially holding a series of resource requests, each location for holding one request part, a head end pointer for pointing to the first location holding a request part at the head end of the queue, and a tail end pointer pointing to the first free location at the tail end of the queue, the method comprising the steps of:
Dependencies are inferred from the claim text.
Drawings are temporarily unavailable. Open the PDF at USPTO
For changing the speed of data flow, i.e. speed regularising or timing, e.g. delay lines, FIFO buffers; over- or underrun control therefor: having…
Based on arbitration: with request queuing
Computing and data processing
Term ended 6 Dec 2004 (estimated)
USPTO file history isn’t available for this patent, so only indexed dates are shown.
This invention relates to storage control procedures and circuits generally, and in particular relates to methods of and apparatus for queue administration in computing systems.
In processing systems, a queue is commonly used to store a backlog of tasks that have been assigned to a unit of the system by other system units. A queue is implemented as memory, or a portion of a memory, in which items of information--queue entries--are stored in the order in which they are received from the task requesting units, and from which they are retrieved in the same order by the task performing unit.
Two implementations of queues are common. One is a first-in, first-out (FIFO) memory, having the property that an item of information loaded into its input register which is located at the tail end of the queue automatically propagates--falls through--empty memory locations toward the output register located at the head end of the queue, and is stored in the first empty location closest to the output register. Retrieval of an item of information from the output register causes all items remaining in the FIFO to shift one location closer to the output register. The other common implementation is a circular buffer having a read and a write pointer associated therewith. The read pointer indicates the location at the head end of the queue from which the next item of information is to be retrieved and the write pointer indicates the location at the tail end of the queue into which the next item of information is to be stored. Retrieval of an item causes the read pointer to point to the next consecutive location that holds information, while storage of an item of information causes the write pointer to point to the next consecutive free location, available for information storage.
FIG. 1 is a block diagram of a computing system including an illustrative embodiment of the invention;
FIG. 2 is a block diagram of the main store unit of the system of FIG. 1;
FIG. 3 a block diagram of a subcontroller of the main store unit of FIG. 2;
FIG. 1 shows in block diagram form an illustrative computer 100 comprised of a plurality of functional units 101-107 interconnected for communication by a system bus 108. The computer 100 is a multiprocessor system: the functional units 101-102 include a plurality of processing elements 101-102, which are for example microprocessors and which together form what may be referred to as the central processing unit of the computer 100. Each processing element 101-102 has its own cache memory unit 106-107, respectively. The cache memory units interface their respective processing elements' requests for information to the system bus 108. The functional units also include an input and output (I/O) adapter 103, which interfaces peripheral equipment (not shown) to the system bus 108.
A main store unit 104 provides the main on-line memory capability of the computer 100. The processing elements 101-102 and the I/O adapter 103 make use of the memory as a resource. They issue tasks to the main store unit 104 via the system bus 108. In turn, the main store unit 104 stores data received from the units 101-103 and returns requested data to the initiating unit 101-103 via the system bus 108.
Accesses by units to the bus 108 and data transfers between units on the system bus 108 are made under the control of a system bus arbiter 105. A unit wishing to communicate on the bus 108 requests a bus cycle from the arbiter 105. When the bus cycle is granted, the requesting unit becomes the "master" and is able to address any other unit in the system as the "slave". In the case of those bus transactions which require a response (e.g., memory read operations), when the slave is ready to respond (e.g., obtains the requested information), it assumes the role of "master" and initiates the transfer of information to the requesting unit.