Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-01-10
2002-01-22
Banankhah, Majid (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C709S241000
Reexamination Certificate
active
06341301
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
The present invention relates generally to the processing of data and in particular to a multi-processor data processing system. Still more particularly, the present invention relates to a method and apparatus for handling queues in a multi-processor data processing system.
2. Description of the Related Art
Multiprocessor data processing systems contain multiple processors that each can operate on its own data. Typically, these processors operate independently of each other, normally on autonomous tasks or significant portions of large tasks. Multiprocessor systems typically fall into two categories: shared-memory systems and distributed-memory systems. In shared memory systems, the processors communicate by reading and writing data to a shared memory location in a common address space. Additionally, shared memory usually implies a shared bus, but such is not necessarily the case. Within the shared memory, communications between various processors are usually performed through queues. Typically, a large number of queues are commonly used by the data processing system to control usable hardware and software resources within the data processing system, including the queues, which are themselves system resources.
Computer systems with multiple central processing units coupled to a memory system often performed queued operations to organize related blocks of stored data. Queues are data structures used to organize sets of data blocks in memory by means of pointers associated with each data block in a queue. Each queue typically includes a number of elements in which each element is a unit of the queue. Queues may be classified into several general types according to the relative locations of the elements in the queue. Contiguous queues have elements physically located next to each other while linear chained queues are queues with elements physically disbursed anywhere within main or virtual storage. Hierarchical chained queues are queues that speed up queue operation by using hierarchical searching.
The data blocks within queues, whether located physically next to each other or disbursed within main or virtual storage, are associated with each other through linked lists. A “doubly linked” list has two pointers in each element, pointing to the next and previous elements in the list. In the case of “singly linked” queues, the pointers reference the addresses of successive data blocks in the queue. A singly linked queue is a queue in which each element includes a pointer to its successor in the queue.
Many software systems use queues to store multiple tasks for processing. In some environments, an event or condition encountered during processing requires a context switch to act on the special condition using a different processing algorithm. A context switch is when a processor begins executing in a different software environment, which could include data types, execution priority, interrupt level, or special algorithms. It is possible to have many types of special conditions, each with a separate algorithm for processing. In many software systems, these special events cannot be handled immediately and multiple occurrences must be queued for subsequent processing, requiring support of multiple queues. For execution speed and memory efficiency, however, it is a benefit to utilize as much common software for queue entry handling (e.g., reading/writing queue entries and updating queue pointers) as possible. This use of common software is especially important for environments with limited processing resources, such as embedded processor subsystems.
Therefore, it would be advantageous to have a method and apparatus for multiple queue handling using a common processing algorithm.
SUMMARY OF THE INVENTION
The present invention is implemented in a multi-processor data processing system and provides a method for handling a plurality of queues within the data processing system. Each queue is associated with a pointer. A first queue is designated as the current queue along with a first pointer associated with the first queue. This first pointer is designated as a current pointer. Entries are read within the current queue using the current pointer. In response to a condition requiring a change in queues, the current pointer is stored and another pointer is designated or loaded for use as the current pointer. Entries are read with the new current pointer within a queue associated with that pointer.
REFERENCES:
patent: 4038642 (1977-07-01), Bouknecht et al.
patent: 4429360 (1984-01-01), Hoffman et al.
patent: 4663706 (1987-05-01), Allen et al.
patent: 4807111 (1989-02-01), Cohen et al.
patent: 4821170 (1989-04-01), Bernick et al.
patent: 4945548 (1990-07-01), Iannarone et al.
patent: 5003464 (1991-03-01), Ely et al.
patent: 5023776 (1991-06-01), Gregor
patent: 5224215 (1993-06-01), Disbrow
patent: 5239634 (1993-08-01), Buch et al.
patent: 5274823 (1993-12-01), Brenner et al.
patent: 5313587 (1994-05-01), Patel et al.
patent: 5313638 (1994-05-01), Ogle et al.
patent: 5315707 (1994-05-01), Seaman et al.
patent: 5319778 (1994-06-01), Catino
patent: 5325526 (1994-06-01), Cameron et al.
patent: 5327536 (1994-07-01), Suzuki
patent: 5341491 (1994-08-01), Ramanujan
patent: 5363497 (1994-11-01), Baker et al.
patent: 5381413 (1995-01-01), Tobagi et al.
patent: 5386514 (1995-01-01), Lary et al.
patent: 5388215 (1995-02-01), Baker et al.
patent: 5394547 (1995-02-01), Correnti et al.
patent: 5404521 (1995-04-01), Murray
patent: 5442730 (1995-08-01), Bigus
patent: 5459839 (1995-10-01), Swarts et al.
patent: 5485626 (1996-01-01), Lawlor et al.
patent: 5519883 (1996-05-01), White et al.
patent: 5539893 (1996-07-01), Thompson et al.
patent: 5541912 (1996-07-01), Choudhury et al.
patent: 5546391 (1996-08-01), Hochschild et al.
patent: 5551001 (1996-08-01), Cohen et al.
patent: 5555396 (1996-09-01), Alferness et al.
patent: 5555405 (1996-09-01), Griesmer et al.
patent: 5560034 (1996-09-01), Goldstein
patent: 5579504 (1996-11-01), Callander et al.
patent: 5581734 (1996-12-01), DiBrino et al.
patent: 5588132 (1996-12-01), Cardoza
patent: 5604866 (1997-02-01), Kolb et al.
patent: 5623449 (1997-04-01), Fischer et al.
patent: 5740467 (1998-04-01), Chmielecki, Jr. et al.
patent: 5774745 (1998-06-01), Ecclesine
LandOfFree
Exclusive multiple queue handling using a common processing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Exclusive multiple queue handling using a common processing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Exclusive multiple queue handling using a common processing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2843455