Electrical computers and digital data processing systems: input/ – Input/output data processing – Input/output access regulation
Reexamination Certificate
2000-01-06
2004-06-01
Gaffin, Jeffrey (Department: 2182)
Electrical computers and digital data processing systems: input/
Input/output data processing
Input/output access regulation
C710S036000, C710S039000, C710S054000, C711S120000
Reexamination Certificate
active
06745262
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a system, method, program, and data structure for queuing requests capable of having different priority levels.
2. Description of the Related Art
In prior art servers, the server receives input/output (I/O) requests from multiple clients and queues the requests in the order received to execute against the storage device. In certain prior art network systems, the client does not transmit to the server the priority of the I/O request. Instead, each client would internally prioritize requests and send the higher priority requests before its lower priority requests. Clients withhold sending low priority requests because if the server does not know of the priority, then sending low priority requests before high priority could cause the server to queue the low priority requests before the high priority ones. Thus, the client delays sending low priority requests until all high priority requests have been sent. This technique of having each client individually prioritize I/O requests is problematic for at least two reasons. First is that a server may be capable of concurrently processing I/O requests that utilize different server resources. Thus, the server may be able to concurrently process a high priority request and low priority request requiring different resources when it would not be able to concurrently process two high priority requests. Because clients do not know the processing capabilities and resource availability at the server, the client may only transmit the high priority requests and withhold the low priorities when in fact the server could optimize throughput by concurrently processing both. Further, it may be more efficient for the server to process a low priority request before a high priority if the low and high priority requests are stored at physically adjacent locations in the storage medium. Processing the low priority before the high priority would avoid the need to seek and move back to the low priority storage location when the disk head is already adjacent to such location.
Another problem with client prioritization of requests is that there is no prioritization of requests between clients. For instance, if client A has I/O requests of priority
1
and
2
and client B has I/O requests of priority
3
, then if both send their highest priority I/O requests, client A will send the requests of priority
1
and client B will send requests of priority
3
. Client A will withhold the priority
2
requests until all priority
1
requests have been sent. If client A sends the priority
2
I/O requests after client B sends the priority
3
request, then the server will process the priority
3
requests first. This situation is non-optimal because the server will complete client B's priority
3
I/O requests before processing the later sent priority
2
requests from client A.
Given the above inefficiencies with allowing clients to do their own prioritizing, prior art techniques have been developed to allow clients to transmit priority information along with an I/O request. For instance, the Small Computer System Interface (SCSI) allows for two priorities, high and low, and the International Business Machines Corporation's (IBM**) Enterprise System Connection (ESCON**) allows the server to communicate 256 different priority levels. In SCSI, the server would maintain a queue for I/O requests having a head and a tail. High priority requests are enqueued at the head of the queue and low priority requests are enqueued at the tail. The SCSI server dequeues requests from the head. One problem with the SCSI prior art priority system is that if the SCSI server receives a lengthy stream of high priority requests, then it may not reach the low priority requests for a significant period of time; enough, in fact, to cause the low priority requests to time out, otherwise referred to as starvation. In the prior art ESCON** system, the ESCON** server maintains a separate queue for each of the 256 priorities and accesses I/O requests from the highest priority queue having pending I/O requests. In ESCON**, as with SCSI, a steady stream of high priority I/O requests could significantly delay the processing of the low priority requests.
One prior art solution to this problem of starvation of the low priority I/O requests is to occasionally increase the priority of the low priority requests by moving the low priority requests to a higher priority queue. For instance, after enqueuing a predetermined number of high priority requests, the server may move low priority requests to a higher priority queue. This technique works somewhat effectively when there are only a few levels of priority. However, as the number of possible priorities the server tracks increases, moving priorities from one queue to another, i.e., dequeuing and enqueuing I/O requests, can consume substantial memory resources to the point of significantly degrading memory performance. If the server, e.g., I/O processor, maintains multiple priority queues, then the server may have to move the low priority request each time the priority of lower priority requests is increased. For instance, if a low priority request is in the 256
th
priority queue, then it is conceivable such request could be moved 255 times before being processed. If there are numerous requests being moved about, then the memory operations to move the I/O requests, i.e., enqueue and dequeue, between queues can significantly degrade overall memory performance.
Thus, as the number of priority queues managed by the server increases, with prior art techniques, the memory burden is twofold. First, the server must manage numerous priority queues and, second, there is a substantial increase in the dequeue and enqueue operations needed to move a low priority request from queue-to-queue as priority is adjusted upward to avoid starvation.
Thus, there is a need in the art to provide an improved mechanism for increasing priority of low priority I/O requests when a client communicates priority with the I/O request in a manner that does not impose substantial burdens on memory.
SUMMARY OF THE PREFERRED EMBODIMENTS
To overcome the limitations in the prior art described above, preferred embodiments disclose a method, system, program, and data structure for queuing requests. Each request is associated with one of a plurality of priority levels. A queue is generated including a plurality of entries. Each entry corresponds to a priority level and a plurality of requests can be queued at one entry. When a new request having an associated priority is received to enqueue on the queue, a determination is made of an entry pointed to by a pointer. The priority associated with the new request is adjusted by a value such that the adjusted priority is associated with an entry different from the entry pointed to by the pointer. The new request is queued at one entry associated with the adjusted priority.
In further embodiments, to process queued requests, a determination is made of an entry at which requests are queued. The pointer is modified to point to the determined entry and the requests queued at the entry pointed to by the pointer are processed.
In further embodiments, adjusting the priority comprises determining the priority of the entry pointed to by the pointer and adding the determined priority to the priority of the request to determine the adjusted priority. In embodiments where the last entry of the queue points to the first entry of the queue, adjusting the priority further comprises determining whether the adjusted priority is greater than the number of entries in the queue. If so, the adjusted priority is set to the adjusted priority modulo the number of entries in the queue.
Preferred embodiments provide a mechanism for queuing I/O requests that effectively reduces the priority of new requests relative to currently pending requests having lower priority. With preferred embodiments, priority of new requests are modified to prevent starvation of the lower priority requests
Benhase Michael Thomas
Chen James Chienchiung
Gaffin Jeffrey
International Business Machines - Corporation
Konrad Raynes & Victor LLP
Patel Niketa
Victor David W.
LandOfFree
Method, system, program, and data structure for queuing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method, system, program, and data structure for queuing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method, system, program, and data structure for queuing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3297035