Sign In to Follow Application
View All Documents & Correspondence

"Print Job Queuing And Scheduling Systems And Methods"

Abstract: Printing systems and methods are described in which the priorities of print jobs are programmable. A scheduler component oversees print job management and scheduling, and works in concert with components called prioritizers, to provide for ease of programming and customization. In at least some embodiments, an interface to the system is provided to allow prioritizers to be programmed and inserted to customize the behavior of the scheduler according to different print job properties. In at least some embodiments, the system utilizes a model for the relative prioritization of print queues in the system to enforce a fair balancing of system resources between print queues. In at least some embodiments, the system can independently schedule the rendering and printing operations when printing a job and can use a heuristic known as "starvation risk" to help ensure that throttling rendering in the system does not result in device starvation.

Get Free WhatsApp Updates!
Notices, Deadlines & Correspondence

Patent Information

Application #
Filing Date
20 January 2006
Publication Number
33/2007
Publication Type
INA
Invention Field
COMPUTER SCIENCE
Status
Email
Parent Application

Applicants

MICROSOFT CORPORATION
ONE MICROSOFT WAY, REDMOND, WASHINGTON 98052, USA.

Inventors

1. ADRIAN F. MAXA
ONE MICROSOFT WAY, REDMOND, WASHINGTON 98052, USA.
2. FENG YUE
ONE MICROSOFT WAY, REDMOND, WASHINGTON 98052, USA.
3. MARK A. LAWRENCE
ONE MICROSOFT WAY, REDMOND, WASHINGTON 98052, USA.

Specification

This invention relates to print job queuing and scheduling systems and methods. BACKGROUND A print server typically schedules jobs to be printed to a set of physical or logical printers. Since some print jobs can typically be relatively large and can consume a large amount of resources, the perceived and actual performance of a print server can be dramatically impacted when the system allows a job to be printed. For example, if a sufficient number of jobs are scheduled to be rendered or printed, the physical memory of the computer can be exhausted which can lead to what is known as "thrashing". Thrashing is a condition that occurs when virtual memory is repeatedly written to and from the hard disk. This, in turn, can lead to a situation in which less progress is made, with regard to processing the print jobs, than if the jobs which resulted in the system thrashing were not scheduled. In this situation, a scheduling decision can affect the actual performance of the system. Similarly, if enough data is read independently from multiple files on a hard disk, performance can actually be degraded since this induces extra head movement on the disk. In another example, consider that a large job and a set of smaller jobs need to be printed. In this situation, more users will receive their jobs more quickly if the large job is printed after the smaller jobs. In this situation, the perceived performance, rather than actual performance, is degraded since the throughput of the server may be no lower in either case. Since print jobs can tend to vary in size and/or desired priority it would be desirable to provide a means that allows print server administrators to control the priority of the jobs in the system, and to also schedule jobs at certain times. In addition, it would be desirable to be able to provide users with the ability to change the priority of their jobs, if they are approved by an administrator for doing so. Accordingly, this invention arose out of concerns associated with providing improved print job queuing and scheduling systems and methods. SUMMARY Printing systems and methods are described in which the priorities of print jobs are programmable. In one embodiment, a scheduler component oversees print job management and scheduling, and works in concert with components called prioritizers to provide for ease of programming and customization. In at least some embodiments, an interface to the system is provided to allow prioritizers to be programmed and inserted to customize the behavior of the scheduler according to different print job properties. In at least some embodiments, the system utilizes a model for the relative prioritization of print queues in the system to enforce a fair balancing of system resources between print queues. In at least some embodiments, the system can independently schedule the rendering and printing operations when printing a job and can use a heuristic known as "starvation risk" to help ensure that throttling rendering in the system does not result in device starvation. BRIEF DESCRIPTION OF THE DRAWINGS Fig. 1 is a high level block diagram of a computing device, components of which can be utilized to implement one or more embodiments. Fig. 2 is a block diagram that illustrates exemplary components of a client device and print server in accordance with one embodiment. Fig. 3 is a block diagram that illustrates a scheduling system including various scheduling queues in accordance with one embodiment. Fig. 4 is a block diagram of a system that illustrates the concept of pooled printers. DETAILED DESCRIPTION Overview In the embodiments described below, a printing system is described in which the relative priority of print jobs in the system is programmable. In at least some of the embodiments, a scheduler component oversees print job management and scheduling, and works in concert with" components called prioritizers to provide for ease of programming and customization. In at least some embodiments, an interface to the system is provided to allow prioritizers to be programmed and inserted to customize the behavior of the scheduler according to different print job properties. Hence, a system administrator who may not necessarily be versed in various programming languages can, in at least some embodiments, easily define custom behaviors for managing print jobs. For example, in at least some embodiments a user interface is provided to allow various parametric values for a prioritizer to be configured by an administrative user. The administrative user can also change the relative ranking of prioritizers. As such, less programmatically-skilled users have the ability to further customize the behavior of the scheduler without requiring the ability to use a programming language. In at least some embodiments, print jobs can be programmatically delayed or boosted in time based on their particular characteristics. Further, in at least some embodiments, the system utilizes a model for the relative prioritization of print queues in the system to enforce a fair (or, at the administrator's discretion - a biased) balancing of system resources between print queues. This allows the system to fairly balance job load across printers in the system. In addition, the mechanism that is used to fairly determine load across the various queues is also programmable in a manner that allows a less-experienced user to customize the system's behavior. In at least some embodiments, the system can achieve its operation with a computational complexity of O(l) in order to determine that no further processing is necessary, as will be appreciated by the skilled artisan. In at least some embodiments, the system can independently schedule the rendering and printing operations when printing a job. This allows it to achieve a desirable device throughput for the I/O-bound task of sending print output to the printers, while limiting the number of CPU and memory intensive rendering tasks in the system. In an embodiment described below, the system uses a heuristic known as "starvation risk" to help ensure that throttling rendering in the system does not result in device starvation. In at least some embodiments, the system allows a natural pooling model to be expressed. This allows both regular and administrative users of the system to see all the jobs that impact their ability to print on a particular queue, as will become apparent below. In at least some embodiments, the system achieves these goals with a CPU complexity that is O(l) in order to determine whether another job must be printed, and O(log2 J) + O(log2 P) for a scheduling decision, where J is the number of jobs in a queue, and P is the number of physical printers in the system. Thus, for example, in a system with two hundred queues and a million jobs that are evenly distributed, the system will typically utilize only 20 comparisons to reach a scheduling decision, as compared with current systems which can require 200 million comparisons to reach a scheduling decision. Exemplary Client Device/Print Server Components Preliminarily, before describing the various embodiments, the following description of a computing device is provided. The various components of the computing device can be utilized to implement both a client and a print server, as will be appreciated by the skilled artisan. As such, Fig. 1 shows an exemplary computing device that can utilize the embodiments described below. It is to be appreciated and understood that the described computing device is provided for exemplary purposes only, and is not intended to limit application of the claimed subject matter to only one particular type of computing device. Computing device 142 comprises one or more processors or processing units 144, a system memory 146, and a bus 148 that couples various system components including the system memory 146 to processors 144. The bus 148 represents one or more of any of several types of bus structures, including a memory bus or memory controller, a peripheral bus, an accelerated graphics port, and a processor or local bus using any of a variety of bus architectures. The system memory 146 comprises read only memory (ROM) 150 and random access memory (RAM) 152. A basic input/output system (BIOS) 154, containing the basic routines that help to transfer information between elements within computing device 142, such as during start-up, is stored in ROM 150. Computing device 142 can further comprise a hard disk drive 156 for reading from and writing to a hard disk (not shown), a magnetic disk drive 158 for reading from and writing to a removable magnetic disk 160, and an optical disk drive 162 for reading from or writing to a removable optical disk 164 such as a CD ROM or other optical media. The hard disk drive 156, magnetic disk drive 158, and optical disk drive 162 are connected to the bus 148 by an SCSI interface 166 or some other appropriate interface. The drives and their associated computer-readable media provide nonvolatile storage of computer-readable instructions, data structures, program modules and other data for computer 142. Although the exemplary environment described herein employs a hard disk, a removable magnetic disk 160 and a removable optical disk 164, it should be appreciated by those skilled in the art that other types of computer-readable media which can store data that is accessible by a computer, such as magnetic cassettes, flash memory cards, digital video disks, random access memories (RAMs), read only memories (ROMs)s and the like, may also be used in the exemplary operating environment. A number of program modules may be stored on the hard disk 156, magnetic disk 160, optical disk 164, ROM 150, or RAM 152, including an operating system 170, one or more application programs 172 (such as a user agent or browser), other program modules 174, and program data 176. A user may enter commands and information into computer 142 through input devices such as a keyboard 178 and a pointing device 180. Other input devices (not shown) may comprise a microphone, joystick, game pad, satellite dish, scanner, or the like. These and other input devices are connected to the processing unit 144 through an interface 182 that is coupled to the bus 148. A monitor 184 or other type of display device is also connected to the bus 148 via an interface, such as a video adapter 186. In addition to the monitor, personal computers typically comprise other peripheral output devices (not shown) such as speakers and printers. Computer 142 commonly operates in a networked environment using logical connections to one or more remote computers, such as a print server 188 which, in turn, is connected to one or more printers. The print server 188 may be another personal computer, a server, a router, a network PC, a peer device or other common network node, and typically comprises many or all of the elements described above relative to computer 142. The logical connections depicted in Fig. 1 comprise a local area network (LAN) 190 and a wide area network (WAN) 192. Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets, and the Internet. When used in a LAN networking environment, computer 142 is connected to the local network through a network interface or adapter 194. When used in a WAN networking environment, computer 142 typically comprises a modem 196 or other means for establishing communications over the wide area network 192, such as the Internet. The modem 196, which may be internal or external, is connected to the bus 148 via a serial port interface 168. In a networked environment, program modules depicted relative to the personal computer 142, or portions thereof, may be stored in the remote memory storage device. It will be appreciated that the network connections shown are exemplary and other means of establishing a communications link between the computers may be used. Generally, the data processors of computer 142 are programmed by means of instructions stored at different times in the various computer-readable storage media of the computer. Programs and operating systems are typically distributed, for example, on floppy disks or CD-ROMs. From there, they are installed or loaded into the secondary memory of a computer. At execution, they are loaded at least partially into the computer's primary electronic memory. The system described herein comprises these and other various types of computer-readable storage media when such media contain instructions or programs for implementing the blocks described, in conjunction with a microprocessor or other data processor. The system described can also comprise the computer itself when programmed according to the methods and techniques described herein. For purposes of illustration, programs and other executable program components such as the operating system are illustrated herein as discrete blocks, although it is recognized that such programs and components reside at various times in different storage components of the computer, and are executed by the data processors) of the computer.Exemplary Embodiment Overview and Description Fig. 2 shows a high level view of an exemplary system in accordance with one embodiment, generally at 200. In the description that follows, individual objects are described, along with some of their associated properties and/or characteristics each under their own headings. Following this, a section entitled "Determining a Job's Priority" describes how a particular print job's priority is represented and the role of the prioritizers in the prioritization process. Preliminarily though, before a description of the specific implementation example of Fig. 2, consider the following discussion of some principles and considerations that underlie the specific implementation described below. Specifically, in the discussion mat follows, the notion of a prioritizer or prioritizer object is introduced. The prioritizer is the programmatic mechanism that allows the printing system to be programmable. Essentially, a prioritizer looks at a particular print job and produces a -weight or a time associated with the print job. An administrator can define a sequence of prioritizers and can associate this sequence of prioritizers with a particular print queue. The sequence of prioritizers then produces, for a particular print job, a tuple which is a vector of values that can include weight values and/or time values. Each prioritizer can be specifically configured by a system administrator by providing configuration data for the prioritizer via a user interface that is described below. Tuples that are produced for a particular print job can then be interpreted and processed by a scheduler object to schedule the particular print jobs in the printing system. In operational principle then, when a system administrator wishes to program a printing system as by configuring a particular printing queue, the administrator, in a user interface-driven approach, simply selects one or more prioritizers for that particular queue. Using each prioritizer's user interface component, the system administrator can then parameterize the prioritizers and assign a priority order to the prioritizers for that particular queue. Turning now to a discussion of Fig. 2, a specific system 200 is presented that embodies the principles discussed just above. It is to be appreciated and understood that the description that follows constitutes but one example and is not intended to limit application of the claimed subject matter to this particular system. Accordingly, system 200 includes, in this example, one or more client devices 242 and one or more print servers 288. Here, client device 242 and print server 288 can include components that are the same as or similar to those described in connection with Fig. 1. However, for purposes of simplicity, these components are not shown in the Fig. 2 example. In accordance with one embodiment, client device 242 comprises a prioritizer user interface 244. User interface 244 is configured to permit a system administrator (or other user) to program or otherwise configure prioritizers, as mentioned above. In the illustrated and described embodiment, user interface 244 displays a customized user interface to represent prioritization data (described below) for a printer or printers. The prioritizer user interface supports the following methods: • Name - As well as its logical ID, the prioritizer user interface has a human readable display name. » AppComponentLD - This is a prioritizer user interface's unique component id. A prioritizer can be invoked to either acquire its initial configuration data, or to change an existing configuration. These operations are supported by GetConfiguration and ChangeConfiguration commands that each prioritizer supports. In the illustrated and described embodiment, print server 288 comprises one or more of the following objects, each of which is described below: a scheduler object 252, a print job object 254, a printer object 256, a logical server object 258, a priority order object 260, prioritizer data object 262 and a prioritizer object 268. In addition, a data interface component 270 provides a mechanism by which the client device 242 and the print server 288 can communicate. Any suitable data interface and protocol can be utilized. Scheduler Object In the illustrated and described embodiment, the scheduler object 252 is responsible for selecting print jobs to send to a particular printer. To do so, the scheduler object processes the data that are produced by the prioritizers. In addition, the scheduler object ensures that priorities on print jobs, as described below, are honored. Further, the scheduler object manages print jobs in an effort to ensure a desirable throughput through the system. Hence, the scheduler object is charged with the responsibility of attempting to provide all print devices with the appropriate data at appropriate times to avoid any undue delays. Further, as will be discussed below, the scheduler object attempts to ensure some level of fairness if the priorities otherwise lead to job starvation. In the illustrated and described embodiment, the scheduler object is configured to be able to select from a large number of print jobs on a large number of physical devices, without incurring a significant overhead. As it is desirable to maintain a flexible set of priorities, the queues are based on a skew-heap implementation of a priority queue having the following properties: O(log2 N) for both insertion and removal; Intrusive implementation — No memory is required for insertion or removal - hence items can always be inserted or removed from the queue. A skew heap always remains statistically balanced. A vector based heap is guaranteed to remain balanced but requires an external vector in order to function. For a given priority, the system maintains a First-In-First-Out (FIFO) queue of print jobs at that particular priority. This is useful for reducing the overhead for scheduling jobs at the same priority. In addition, in accordance with one embodiment, the system maintains three logical types of priority queue—a time priority queue, a printer priority queue and a resource arbitration queue, each of which is described in more detail in Fig. 3. Preliminarily, however, consider the following. A time priority queue is a priority queue that uses, as its priority, the time that the job should be rescheduled. For example, if a print device went into an error state, the job would go into the time queue with the desired time that it should be removed (e.g., in 5 seconds) as its priority. The times are not stored as deltas (or changes), but rather as absolute times to prevent drift caused by small delays in the scheduler object. A printer priority queue is a queue that represents the relative prioritization in the queue against a device. A resource arbitration queue is a queue of printer queues whose goal is to balance load fairly amongst printer queues. All of this is discussed below in more detail. Print Job Object A print job object 254 is created and represents a particular print output request. Each print job object supports two commands: a ChangePriority command and a ChangeScheduleTime command that are not accessible from clients. A prioritizer object (described below) can call commands to change the priority or scheduled time of the associated job. As a result, the job will be automatically moved in its scheduling queue when these commands are called. Both commands take the new time or priority, and a prioritizer's unique component id (described below) and the system uses these to work out which field of the priority n-tuple to change, as will become apparent below. Printej-Object The printer object 256 is the logical unit of scheduling in the print system. Hence, it is also the object that stores the prioritizer's configuration data. In the illustrated and described embodiment, a printer object has a one-to-one correspondence to an interface to a physical printer. Logical Server Object Prioritizer objects are installed on a logical server. A logical server also has a set of priority orders created by an administrator. One reason that a logical server object is provided is that in some cases, a single physical server can have more than one logical server. For example, a print cluster has a number of logical servers that move between the nodes in the cluster at the discretion of the administrator or due to failures of the physical cluster nodes. Priority Order Object A priority order object 260 is used to define the priority order of a sequence of one or more prioritizer objects. In the illustrated and described embodiment., a prioritizer can only assign a weight to a job or schedule it forward in time. How this weight is determined is parameterized both by its corresponding data in the queue, and by other data associated with the job, such as its so-called job ticket. An administrator can change the queue data and can change the relative precedence of the prioritizers. For example, given one prioritizer that prioritizes jobs submitted by executives over jobs submitted by normal staff members, and another that decreases the priority of large jobs, the administrator can specify one priority order of and another of , and . The starvation risk is an indication of how likely it is that a given printer will idle. Starvation risk data is used by a rendering component upstream of the device scheduler to prioritize its jobs. It will preferentially start rendering jobs that are destined for queues that are at a higher starvation risk than others, regardless of the other job priorities. This is used to prevent high priority jobs from always swamping other jobs in a system. Hence, if a queue has a large number of high priority jobs, it will eventually fill and its starvation risk will drop. At that point, other queues will preferentially receive jobs until the starvation risk exceeds theirs again. Any suitable method can be used to calculate the starvation risk. In but one embodiment, the printer throughput is first estimated. This is done by sampling the rate at which the device consumes data over a time interval, and then calculating the throughput for that interval as follows: Rin = /

Documents

Orders

Section Controller Decision Date

Application Documents

# Name Date
1 155-DEL-2006-Correspondence-090919.pdf 2019-09-12
1 155-del-2006-Form-18-(04-02-2009).pdf 2009-02-04
2 155-del-2006-Correspondence-others-(04-02-2009).pdf 2009-02-04
2 155-DEL-2006-Power of Attorney-090919.pdf 2019-09-12
3 155-DEL-2006-Written submissions and relevant documents (MANDATORY) [05-09-2019(online)].pdf 2019-09-05
3 155-del-2006-Form-13-(17-06-2010).pdf 2010-06-17
4 155-del-2006-GPA-(18-06-2010).pdf 2010-06-18
4 155-DEL-2006-FORM 3 [28-08-2019(online)].pdf 2019-08-28
5 155-DEL-2006-HearingNoticeLetter21-08-2019.pdf 2019-08-21
5 155-del-2006-Correspondence-others-(18-06-2010).pdf 2010-06-18
6 155-DEL-2006-Form-1-(24-12-2010).pdf 2010-12-24
6 155-DEL-2006-Correspondence to notify the Controller (Mandatory) [25-07-2019(online)].pdf 2019-07-25
7 155-DEL-2006_EXAMREPORT.pdf 2016-06-30
7 155-DEL-2006-Correspondence-Others-(24-12-2010).pdf 2010-12-24
8 Abstract_Clean copy.pdf 2015-04-15
8 155-del-2006-gpa.pdf 2011-08-21
9 155-del-2006-form-5.pdf 2011-08-21
9 amended claims_tracked-abstract.pdf 2015-04-15
10 155-del-2006-form-3.pdf 2011-08-21
10 Clean copy of claims.pdf 2015-04-15
11 155-del-2006-form-2.pdf 2011-08-21
11 Details under sec 8.pdf 2015-04-15
12 155-del-2006-form-1.pdf 2011-08-21
12 Response 155 DEL 2006.pdf 2015-04-15
13 155-del-2006-drawings.pdf 2011-08-21
13 FORM-6-701-800(MLK).88.pdf 2015-03-13
14 155-del-2006-description (complete).pdf 2011-08-21
14 MS to MTL Assignment.pdf 2015-03-13
15 155-del-2006-correspondence-others.pdf 2011-08-21
15 MTL-GPOA - MLK1.pdf 2015-03-13
16 155-del-2006-claims.pdf 2011-08-21
16 FORM-6-701-800(MLK).88.pdf ONLINE 2015-03-05
17 MS to MTL Assignment.pdf ONLINE 2015-03-05
17 155-del-2006-abstract.pdf 2011-08-21
18 MTL-GPOA - MLK1.pdf ONLINE 2015-03-05
19 155-del-2006-abstract.pdf 2011-08-21
19 MS to MTL Assignment.pdf ONLINE 2015-03-05
20 155-del-2006-claims.pdf 2011-08-21
20 FORM-6-701-800(MLK).88.pdf ONLINE 2015-03-05
21 155-del-2006-correspondence-others.pdf 2011-08-21
21 MTL-GPOA - MLK1.pdf 2015-03-13
22 155-del-2006-description (complete).pdf 2011-08-21
22 MS to MTL Assignment.pdf 2015-03-13
23 155-del-2006-drawings.pdf 2011-08-21
23 FORM-6-701-800(MLK).88.pdf 2015-03-13
24 Response 155 DEL 2006.pdf 2015-04-15
24 155-del-2006-form-1.pdf 2011-08-21
25 155-del-2006-form-2.pdf 2011-08-21
25 Details under sec 8.pdf 2015-04-15
26 155-del-2006-form-3.pdf 2011-08-21
26 Clean copy of claims.pdf 2015-04-15
27 155-del-2006-form-5.pdf 2011-08-21
27 amended claims_tracked-abstract.pdf 2015-04-15
28 155-del-2006-gpa.pdf 2011-08-21
28 Abstract_Clean copy.pdf 2015-04-15
29 155-DEL-2006-Correspondence-Others-(24-12-2010).pdf 2010-12-24
29 155-DEL-2006_EXAMREPORT.pdf 2016-06-30
30 155-DEL-2006-Correspondence to notify the Controller (Mandatory) [25-07-2019(online)].pdf 2019-07-25
30 155-DEL-2006-Form-1-(24-12-2010).pdf 2010-12-24
31 155-DEL-2006-HearingNoticeLetter21-08-2019.pdf 2019-08-21
31 155-del-2006-Correspondence-others-(18-06-2010).pdf 2010-06-18
32 155-del-2006-GPA-(18-06-2010).pdf 2010-06-18
32 155-DEL-2006-FORM 3 [28-08-2019(online)].pdf 2019-08-28
33 155-DEL-2006-Written submissions and relevant documents (MANDATORY) [05-09-2019(online)].pdf 2019-09-05
33 155-del-2006-Form-13-(17-06-2010).pdf 2010-06-17
34 155-DEL-2006-Power of Attorney-090919.pdf 2019-09-12
34 155-del-2006-Correspondence-others-(04-02-2009).pdf 2009-02-04
35 155-del-2006-Form-18-(04-02-2009).pdf 2009-02-04
35 155-DEL-2006-Correspondence-090919.pdf 2019-09-12