Dynamic queue width system and method

Details Dynamic queue width system and method Dynamic queue width system and method

2000-08-30

2004-08-24

Follansbee, John (Department: 2154)

Electrical computers and digital processing systems: virtual mac

Task management or control

Process scheduling

C718S102000, C710S054000

Reexamination Certificate

active

06782535

ABSTRACT:

FIELD OF THE INVENTION
This invention relates generally to a distributed resource utilization system with a plurality of resource processing subsystems and, more particularly, to an optimized workflow system which efficiently allocates resources through the use of a variable width queue to manage resource allocation for the various resource processing subsystems.
BACKGROUND OF THE INVENTION
In accordance with a standard model of distributed resource utilization systems, a job is developed at a client and delivered to a resource device, by way of a server, for the purpose of executing the job. One exemplary model of a distributed resource utilization system is a network-printing environment. One such network-printing environment suited for the present invention is the ADOBE® EXTREME™ (“Extreme”) network-printing environment from Adobe Systems Incorporated of San Jose, Calif.
Extreme is composed of a set of process modules and a communication framework for queuing these process modules and automating/coordinating the transfer of data from process module to process module. Extreme process modules are known as Job Ticket Processors (“JTP”). JTPs get information from a Job Ticket, which is an extended set of processing information about a Portable Document Format (“PDF”) document written in Portable Job Ticket Format (“PJTF”), which is based on the PDF language. A PDF document and its associated Job Ticket contain essentially all the information (content, graphics, production specs, etc.) required for viewing processing and outputting a file in a self-contained package. Because a PDF document contains this important information, it can be thought of as a Digital Master, i.e., a complete and reliable description of a file's content and processing requirements.
PJTF extends the finctionality of PDF by carrying history, instructions and process control about both the content and the document itself. A Job Ticket collects information about the state of the document and what needs to happen to it. A Job Ticket may be included in a PDF document or exist as a separate entity. Thus, a Job Ticket is an independent part of a PDF document, and by separating the processing information from the content, a Job Ticket becomes an unambiguous job process management tool. The Job Ticket knows what needs to be done, and the Job Ticket Processor knows how to do it. One important benefit to this structure is that Portable Job Ticket Format and Job Ticket Processors can both be independently extended as new processing technology evolves and as business markets expand.
The JTP is the smallest working unit in the Extreme architecture. When components are added or removed from an Extreme system, they are in the form of a JTP. JTPs provide independent functionality. There are different types of JTPs that are called into play by the specifications contained in the Job Ticket. Modular Job Ticket Processors provide a way to “mix-and-match” required steps from an inventory of functionality. For example, a trapping engine (mechanism) is a JTP, imposition is effected by a JTP and even output is handled by an output JTP. In Extreme, JTPs can be sequenced flexibly so that if different jobs require different manufacturing plans, the same system can be used to structure the required processing sequences. The most important JTPs are the Sequencer, Coordinator, Normalizer, and Renderer (or printer JTP). Together, these JTPs form the key pieces of the Extreme architecture.
As a PDF document is built and moves through its required processes, information about these processes can be specified and collected in its Job Ticket. The Job Ticket can be examined, edited and enhanced. In an Extreme environment, the Job Ticket Processors can act on this information and, in turn, pass these specifications (or new specifications) over to other Job Ticket Processors. A Job Ticket is also an audit trail of what has happened along the way, and it is possible to use this information to configure JTPs for following steps.
Underneath it all, the communication framework of Extreme uses a coordinator, which sends information to and receives information from the JTPs. The coordinator determines which Job Ticket Processors are required and passes instructions between JTPs. The coordinator contains a Sequencer that defines the internal Extreme workflow. The Sequencer reads information from Job Tickets, sets up a JTP sequence, makes process choices, and then updates Job Tickets as information is returned from each JTP. Thus rather than being a hard-wired flowchart of steps, the process itself becomes much more flexible and responsive to the real-time results of the processing.
One shortcoming of previous systems, including the Extreme system, is that each resource has its own queue of unprocessed tasks while it is busy processing a current task. This means that interchangeable resources may be under/over utilized depending on how tasks are allocated to the resource(s) and how quickly or slowly each resource finishes each task. Therefore, there is a need for a resource contention management and optimization method and system wherein resources are more efficiently utilized. Preferably, such a system would be able to be integrated into any existing system with minimal impact to either cost or performance. Furthermore, it is desirable that tasks requiring multiple resources be able to proceed more quickly. Therefore, a method and system are desired that allows concurrent use of resources by a single task. Finally, there is a need for a resource contention management method and optimization system wherein tasks are assigned to resources based on the priority of the task.
SUMMARY OF THE INVENTION
The present invention provides a distributed computing system and method wherein resources are efficiently allocated. Resource allocation begins after retrieving a task from a task queue and adding the task to a variable width queue. The task is then examined to determine what resource or resources it requires. The required resources are then examined to determine if they are available. If any required resource is available, then it is allocated to the task. The required resources are then repeatedly checked until all have been assigned to the task that needs them.
In accordance with one aspect of the present invention, the tasks in the task queue may be rearranged according to a predetermined order, such as by priority or by size. In accordance with another aspect of the current invention, when allocating a resource to a task, the status of the resource is changed from “unallocated” to “allocatedd”, which in turn allows a resource subsystem in accordance with the present invention to determine if a resource is available or not by examining its allocation status.
In yet another aspect of the current invention, when a task no longer requires a resource and deallocates it, the deallocated resource changes its status to “unallocated”. Which, when any task has changed all its required resource or resources to “unallocated”, lets the resource subsystem remove the task from the variable, width queue.
The approach of the current invention is flexible and may be used in any number of distributed printing environments having a need for load balancing in a prioritized, flexible and efficient manner. Additionally, the current invention may be applied more generally to data processing environments where task turn around time and overall system throughput may be positively affected by granting more resources to tasks that can concurrently use them and keep resources from laying idle.


REFERENCES:
patent: 6339801 (2002-01-01), Hefferon et al.
patent: 6373585 (2002-04-01), Mastie et al.
patent: 6640300 (2003-10-01), Raza
patent: 6680933 (2004-01-01), Cheesman et al.

Affiliated with

Also associated with

Rating

Dynamic queue width system and method does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dynamic queue width system and method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic queue width system and method will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3359804