Abstract:
A processing method has been claimed for reducing the average wait time of requests in a queue in a system environment where garbage collection may occur. In the method, a computer system treats as a unit each request in a queue and a completion time of garbage collection that may occur at the time of processing the request, and processes requests preferentially and systematically in ascending order of the processing times of the units including the garbage collection times, thereby, reducing the average wait time of the requests. While, the computer system managing the queue knows the remaining amount of heap just before processing a certain request, the computer system statistically calculates in advance the amounts of heap to be consumed on a request type basis and holds the values.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims priority under 35 U.S.C. §119(a) to Japanese Patent Application Number 2010-110655, filed May 12, 2010, entitled “REQUEST PROCESSING SYSTEM, METHOD AND PROGRAM PRODUCT”, the entirety of which is incorporated herein by reference. 
       FIELD OF THE INVENTION 
       [0002]    The present invention relates to a computer system which sequentially receives requests, enqueues the requests in a queue and then processes the requests, like a web server. More specifically, the present invention relates to an increase in the efficiency of the processing of the requests waiting in the queue. 
       BACKGROUND OF THE INVENTION 
       [0003]    In recent years, the number of web servers located on the Internet and accessible from client systems has been increasing along with prosperity in the development of the Internet technology. Normally, a web server receives processing requests from a large number of client computers via the Internet but cannot process the requests at once. Thus, the web server once enqueues the requests in a queue and then sequentially processes the requests. 
         [0004]    Accordingly, a technique to process such requests in the queue as promptly as possible in a well-organized manner is in demand. However, a Java (trademark) based server often used as a web server lately executes garbage collection when the server attempts to process a certain request but finds that the remaining amount of heap is not sufficient to process the request. While the garbage collection is executed, all the application threads are stopped and resumed when the garbage collection is completed. Here, such a phenomenon of garbage collection causing all the application threads to stop once is called “Stop the world.” 
         [0005]    If such occurrence of garbage collection is taken into consideration, the queuing schemes of the aforementioned conventional techniques cannot achieve the objective to reduce the average wait time of the requests. This is because these queuing schemes are not made in consideration of at which time point and which request causes garbage collection. 
       SUMMARY OF THE INVENTION 
       [0006]    In accordance with an embodiment of the invention, a method is provided for processing requests preferentially and systematically in ascending order of processing times of units including garbage collection times by treating, as a unit, each request in a queue and a completion time of garbage collection that may occur at the time of processing the request. The computer system managing the queue, such as a web server, knows the remaining amount of heap just before processing a certain request. Meanwhile, the computer system statistically calculates in advance the amounts of heap to be consumed on a request type basis and then holds the values. 
         [0007]    Accordingly, before processing a certain request, the computer system can predict whether or not the processing of the request will cause garbage collection, in consideration of an estimated heap consumption of the request and the remaining amount of heap in the memory. 
         [0008]    This is a rationale for treating, as a single unit, a request and a completion time of garbage collection that may occur at the time of processing the request. 
         [0009]    Here, the processing time of a request itself is preferably taken into consideration as well. However, the garbage collection time is longer than the processing time of the request by far in general. Thus, while only the garbage collection time is focused, requests may be processed preferentially in ascending order of the processing times of the units. 
         [0010]    As described above, according to the present invention, units are set in a system environment where garbage collection may occur, in such a manner that a single unit includes each request in a queue and a completion time of garbage collection that may occur at the time of processing the request. Then, among these units, processing of a unit determined to involve a short processing time including the garbage collection time is preferentially and systematically executed. This brings about an effect that the average wait time of the requests in a queue can be reduced. 
         [0011]    Thus, as many requests as possible can be preferentially processed before garbage collection occurs by selecting the requests requiring only light processing, because the occurrence of garbage collection is unavoidable sooner or later. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0012]      FIG. 1  is a diagram showing how client computers are connected to an application server via the Internet. 
           [0013]      FIG. 2  is a diagram showing a hardware configuration of the client computers. 
           [0014]      FIG. 3  is a diagram showing a hardware configuration of the application server. 
           [0015]      FIG. 4  is a functional block diagram of an embodiment of the present invention. 
           [0016]      FIG. 5  is a diagram showing a flowchart of processing performed when a request arrives in a queue. 
           [0017]      FIG. 6  is a flowchart of processing to categorize requests into heap consumption classes. 
           [0018]      FIG. 7  is a flowchart of processing performed when a request is deleted from a queue, and processing is performed. 
           [0019]      FIG. 8  is a flowchart of processing to measure a heap consumption of a request. 
           [0020]      FIG. 9  is a diagram for describing processing to determine the order of processing requests in consideration of the remaining amount of heap, heap consumptions and heap consumption classes of the requests. 
           [0021]      FIG. 10  is a diagram for describing processing to determine the order of processing requests in consideration of the remaining amount of heap, heap consumptions and heap consumption classes of the requests. 
           [0022]      FIG. 11  is a diagram for describing processing to determine the order of processing requests in consideration of the remaining amount of heap, heap consumptions and heap consumption classes of the requests. 
       
    
    
     DETAILED DESCRIPTION 
       [0023]    Hereinafter, an embodiment of the present invention will be described with reference to the drawings. Unless noted otherwise, the same reference numerals are used to denote the same targets throughout the drawings. In addition, it should be noted that the embodiment to be described below is only an embodiment of the present invention and is not intended to limit the present invention to the content described in this embodiment. 
         [0024]    In  FIG. 1 , an application server  102  having a web server function as well receives requests from multiple client computers  106   a,    106   b,  . . . and  106   z  via the Internet  104  by use of a protocol such as HTTP. In the system shown in  FIG. 1 , the users of the client computers log into the application server  102  through a Web browser via a line of the Internet  104 . Specifically, the users input a predetermined URL into a Web browser to display a predetermined page. Note that, the users may log into the application server  102  by use of a predetermined dedicated client application program instead of using the Web browser. 
         [0025]    Next, a description will be given, with reference to  FIG. 2 , of a hardware block diagram of the client computers denoted by reference numerals  106   a,    106   b,  . . . and  106   z  in  FIG. 1 . In  FIG. 2 , the client computer includes a main memory  206 , a CPU  204 , and an IDE controller  208 , and these components are connected to a bus  202 . Furthermore, a display controller  214 , a communication interface  218 , a USB interface  220 , an audio interface  222  and a keyboard and mouse controller  228  are connected to the bus  202 . A hard disk drive (HDD)  210  and a DVD drive  212  are connected to the IDE controller  208 . The DVD drive  212  is used as appropriate to install a program from a CD-ROM or a DVD. A display apparatus  216  having an LCD screen is preferably connected to the display controller  214 . An application screen is displayed on the display apparatus  216  through a Web browser. 
         [0026]    A device such as an extended hard disk is connectable to the USB interface  220  as needed. 
         [0027]    A keyboard  230  and a mouse  232  are connected to the keyboard and mouse controller  228 . The keyboard  230  is used for inputting a predetermined request message, a password and the like. 
         [0028]    The CPU  204  may be any CPU based on a 32-bit architecture or a 64-bit architecture, and Pentium 4 (trademark of Intel Corporation) and Core (trademark) 2 Duo from Intel Corporation, Athlon (trademark) from AMD Inc., or the like can be used. 
         [0029]    In the hard disk drive  210 , at least an operating system and a browser (not shown) operating on the operating system are installed. Then, when the system is started, the operating system is loaded in the main memory  206 . Windows XP (trademark of Microsoft Corporation), Windows Vista (trademark of Microsoft Corporation), Windows 7 (trademark of Microsoft Corporation), Linux (trademark of Linus Torvalds) or the like can be used as the operating system. In addition, any browser such as Internet Explorer from Microsoft Corporation or Mozilla FireFox from Mozilla Foundation can be used as the Web browser. 
         [0030]    The communication interface  218  communicates with the application server  102  by an Ethernet (trademark) protocol or the like while using a TCP/IP communication function provided by the operating system. 
         [0031]      FIG. 3  is a schematic block diagram of a hardware configuration of the application server  102 . As shown in  FIG. 3 , the client computers  106   a,    106   b,  . . . and  106   z  are connected to a communication interface  302  of the application server  102  via the Internet  104 . The communication interface  302  is further connected to a bus  304 . In addition, a CPU  306 , a main memory (RAM)  308  and a hard disk drive (HDD)  310  are connected to the bus  304 . 
         [0032]    Although not shown, a keyboard, a mouse and a display are connected to the application server  102 . The management and maintenance operation of the entire application server  102  may be performed by using these components. 
         [0033]    An operating system and a user ID and password correspondence table used for login management of the client computers  106   a,    106   b,  . . . and  106   z  are stored in the hard disk drive  310  of the application server  102 . In addition, software such as Apache for causing the application server  102  to function as a Web server, Java EE for implementing a Java virtual environment, and a later described processing program according to the present invention, which operates on a Java virtual environment, are saved in the hard disk drive  310 . These software programs are loaded in the main memory  308  at the time of starting the application server  102  and then operate. Thus, the client computers  106   a,    106   b,  . . . and  106   z  can access the application server  102  by TCP/IP protocols. 
         [0034]    Incidentally, as the aforementioned application server  102 , a server model such as IBM (trademark of International Business Machine Corporation) System X, System i, or System P, which can be purchased from IBM, can be used. Examples of usable operating systems in this case include AIX (trademark of IBM), UNIX (trademark of The Open Group), Linux (trademark), Windows (trademark) 2003 Server and the like. 
         [0035]    Next, a logical configuration of the embodiment of the present invention will be described with reference to a functional block diagram of  FIG. 4 . 
         [0036]    In  FIG. 4 , a request reception module  402  is actually a part of software such as Apache, which operates as a Web server, and receives requests sent from the client computers  106   a,    106   b,  . . . and  106   z  by a protocol such as HTTP and then enqueues the requests in a queue  404 . The queue  404  preferably corresponds to a memory region allocated on the main memory  308 . The requests can be sequentially dequeued from the queue  404 , and the order of the requests in the queue  404  can be changed by an operation of a processing scheduler  406  for a request processing module  408 . 
         [0037]    Here, the request processing module  408  may be actually considered as a group of programs which are written in Java and which perform various functions. In other words, a different program is called in accordance with a request type. 
         [0038]    A heap region  410  is allocated on the main memory  308 . In the heap region  410 , memory is consumed every time the request processing module  408  processes a request. A heap remaining amount monitoring module  412  monitors the remaining amount of useable heap, and when the remaining amount runs short, the heap remaining amount monitoring module  412  calls a garbage collection function  414  and reallocate a region for the capacity of the heap region  410 . Here, the garbage collection function  414  performs “Stop the world” type garbage collection and is a basic function of the Java virtual machine. 
         [0039]    Note that, the processor scheduler  406 , the request processing module  408  and the heap remaining amount monitoring module  412  are programs written in Java and are preferably configured as threads operating in parallel when the application server  102  is started. 
         [0040]    A heap consumption database  416  is a database used for recording an estimated heap consumption for each request type. The estimated consumptions are preferably recorded in the hard disk drive  310 , permanently, but may be stored in the main memory  308 . Note that, a request in this embodiment is to display an ordinary Web page, to process a search, to display a layout of multiple Web pages or the like, for example. In addition, a request type is a character string such as browse.jsp?id=123 specified as a parameter in a URL transmitted from a client computer. Such a character string is extracted by syntax parsing by Java middleware. In accordance with such a parameter, a corresponding Java program is called. 
         [0041]    The processing scheduler  406  processes the queue  404  on the basis of the information from the heap remaining amount monitoring module  412  and the heap consumption database  416  and sends a request to the request processing module  408 . More details of the processing will be described with reference to a flowchart shown in  FIG. 5  and below. 
         [0042]    The processing result of the request processing module  408  is sent via a processing result transmission module  418  to the client computer that has made the request. The processing result transmission module  418  is preferably implemented as a part of software such as Apache, which operates as a Web server. 
         [0043]      FIG. 5  is a flowchart of processing performed by the processing scheduler  406  when a request R arrives in the queue  404  (hereinafter, also referred to as a queue Q). When the request R enters the queue Q in step  502 , the processing scheduler  406  parses a request type T by use of a syntax parsing function of middleware. 
         [0044]    Next, in step  504 , the processing scheduler  406  accesses the database  416  and then attempts to acquire an estimated average heap consumption H at the time of processing of the request type T. When it is determined in step  506  that H cannot be acquired, i.e., the request is a type that has not been yet processed by the processing scheduler  406 , the processing scheduler  406  sets a heap consumption statistic flag L of the request R in step  508  and then returns to step  502  where the processing waits for the next request to arrive in the queue. This leads to measurement of a heap consumption of the request R by different processing, and registration of a heap consumption required for the type T of the request in the database  416 . 
         [0045]    Upon returning to step  506 , when the average heap consumption H at the time of processing of T is acquired, the processing scheduler  406  calculates a class C corresponding to the average heap consumption H. Next, in step  512 , H and C are associated with the request R, and then, the processing returns to step  502  where the processing waits for the next request to arrive in the queue. 
         [0046]      FIG. 6  is a flowchart showing detailed processing of step  510 . In step  602 , the processing scheduler  406  determines whether or not the average heap consumption H acquired in step  504  is larger than a certain threshold E. If yes, the processing scheduler  406  sets the class of the average heap consumption H to be Clarge in step  604 . If no, the processing scheduler  406  sets the class of the average heap consumption H to be Csmall in step  606 . 
         [0047]      FIG. 7  is a flowchart showing processing in which the processing scheduler  406  deletes and then processes a request from the queue Q. 
         [0048]    In step  702 , the processing scheduler  406  sends a query to the request processing module  408  and determines whether or not request processing is prepared. If yes, the processing scheduler  406  acquires H and C of the request R at the top of the queue Q. These values are acquired in the processing in the flowchart of  FIG. 5  when the request is enqueued in the queue Q. 
         [0049]    In step  704 , the processing scheduler  406  determines whether or not the heap consumption class C of the request R at the top of the queue is Clarge and whether or not H is larger than a heap remaining amount F. Here, the heap remaining amount F is acquired from the heap remaining amount monitoring module  412 . 
         [0050]    If the result of the determination in step  704  is positive, a request whose consumption class is Csmall in the queue Q is moved so as to be positioned in front of the request R in the queue Q. Accordingly, the request whose consumption class is Csmall is positioned at the top of the queue Q. Then, the processing proceeds to step  708 . 
         [0051]    If the result of the determination in step  704  is negative, the processing immediately proceeds to step  708 . 
         [0052]    In step  708 , the processing scheduler  406  deletes the request at the top of the queue Q and calls processing in the flowchart of  FIG. 8 . Then, the processing returns to step  702 . 
         [0053]    Next, processing after deletion of the request in step  708  of  FIG. 7  will be described in more detail with reference to the flowchart of  FIG. 8 . In  FIG. 8 , a worker thread (not shown) different from the processing scheduler  406  determines in step  802  whether or not an unprocessed instruction exists. If yes, the processing proceeds to step  804  and the worker thread determines whether or not the instruction is for heap allocation. If yes, the processing proceeds to step  806  and the worker thread determines whether or not the flag L of the request is set. The flag L of the request is supposed to be set in accordance with a condition in the processing of step  508  in the flowchart of  FIG. 5 , and setting of the flag L means that a heap consumption statistic of the request is to be measured and recorded. 
         [0054]    Accordingly, in step  808 , the worker thread associates the heap allocation amount of the current instruction with the type T of the request and proceeds to execution of the instruction in step  810 . 
         [0055]    Even in a case where the instruction is not for heap allocation in step  804 , or where the flag L of the request is not set in step  806 , the processing directly proceeds to step  810 . 
         [0056]    Upon returning to step  802 , when it is determined that there is no unprocessed instruction, the processing proceeds to step  812 , and the worker thread determines whether or not the flag L of a request is set. If yes, in step  814  the worker thread saves the heap allocation amount associated with the type T in the database  416  as the heap consumption of T, and then returns to step  708 . If no flag L of a request is set, the processing immediately returns to step  708 . 
         [0057]    For the purpose of achieving understanding of the processing of the embodiment in more details, the operation will be described through the overall processing. Firstly, when the user of the client computer  106 a calls a Web browser on the display  216  and clicks a predetermined operation button (not shown), a request including a predetermined URL and an additional parameter indicating a request type is sent to the application server  102  in accordance with an HTTP protocol via the Internet line. Here, an assumption is made that the request is to display layout of a Web page list. 
         [0058]    The request sent from the client computer  106 a is received by the reception module  402  of the application server  102  and then is enqueued in the queue  404 . At this time, as described in step  502 , the additional parameter indicating a request type is extracted by syntax parsing by the middleware. 
         [0059]    In step  504 , based on the request type T, the processing scheduler  406  accesses the heap consumption database  416  and attempts to acquire a heap consumption H of the request type T. Here, if the request type T is one that has already been processed, the heap consumption H can be acquired. Accordingly, an assumption is made that the request is determined to be Clarge by the processing of the flowchart in  FIG. 6  on the basis of the value of H. The request is set to a request 1. 
         [0060]    Similarly, suppose that another request is subsequently sent to the request reception module  402  of the application server  102  from the client computer  106 b. The request is then enqueued in the queue  404 . At this time, as described in step  502 , the additional parameter indicating a request type is extracted by syntax parsing by the middleware. An assumption is made that the request is to display a simple Web page in this case. 
         [0061]    In step  504 , based on the request type T, the processing scheduler  406  accesses the heap consumption database  416  and attempts to acquire a heap consumption H of the request type T. Here, if the request type T is one that has already been processed, the heap consumption H can be acquired. Accordingly, an assumption is made that the request is determined to be Csmall by the processing of the flowchart in  FIG. 6  based on the value of H. The request is set to a request 2. 
         [0062]    Then, as shown in  FIG. 9 , the request 1, which is the request to display layout of a Web page list, from the client computer  106   a  is positioned at the top of the queue  404 , the request 2, which is the request to display a simple Web page, from the client computer  106   b  is positioned at the second position from the top in the queue  404 . 
         [0063]    However, when it is determined in step  704  that the request 1 at the top of the queue is Clarge and also that the heap consumption H of the request 1 is larger than the heap remaining amount F acquired from the heap remaining amount monitoring module  412 , and if the request 1 is executed without any processing to avoid garbage collection, garbage collection surely occurs as it can be seen from  FIG. 9 . 
         [0064]    Thus, in step  706 , the processing scheduler  406  searches the queue  404  from the top of the requests to find a request that is Csmall. Then, since the next request 2 is Csmall incidentally, the processing scheduler  406  moves the request 2 to the top of the queue  404  and causes the request processing module  408  to process the request 2 as shown in  FIG. 10 . Thus, since the heap consumption H is smaller than the heap remaining amount F, occurrence of garbage collection can be avoided at this moment. In this manner, the number of requests to be processed before occurrence of garbage collection can be increased to the utmost extent. 
         [0065]    When the request 2 is processed, the request 1 is positioned at the top of the queue  404  as shown in  FIG. 11 . The heap remaining amount F is further reduced because of the execution of the request 2. Here, since the heap consumption H of the request 1 is obviously larger than the heap remaining amount F, a request that is a Csmall is searched for in accordance with the determination in step  706 . Here, since the next request is Csmall, processing to move the request 3 to the top of the queue  404 , which results in moving the request 1 to the second position, is performed. 
         [0066]    As described above, according to the present invention, when it is predicted that execution of a Clarge request causes garbage collection, a Csmall request is executed preferentially. As the heap remaining amount F decreases, there eventually comes a point where garbage collection is no longer avoidable even with execution of a Csmall request. However, the present invention can reduce the average wait time of requests, because as many requests as possible can be processed before occurrence of garbage collection. 
         [0067]    Note that, in a case where the average heap consumption H cannot be acquired in step  506  because the target request is a request type that has not been processed so far, the heap consumption statistic flag L for the request is set in step  508 , but the average heap consumption H cannot be acquired immediately. 
         [0068]    Specifically, the timing when the average heap consumption H of the request is acquired and then recorded in the database  416  is after the request is processed as shown in the flowchart of  FIG. 8 . Accordingly, when such a request becomes ready for processing and is subjected to the determination processing in step  704 , both the consumption class C and the average heap consumption H are unknown. Accordingly, processing for a request whose consumption class C and average heap consumption H are unknown may be proceeded while assuming that the class is Clarge and that the average heap consumption H is an average of the overall Clarge classes in step  704 . 
         [0069]    After the request is processed, the average heap consumption H of the request type is recorded in the database  416 . Accordingly, the consumption class C and the average heap consumption H appropriate to the request of the request type are assigned for the next processing. 
         [0070]    Note that, in the aforementioned embodiment, requests are categorized into Csmall and Clarge in accordance with the types, but the requests may not be categorized into classes in particular. In this case, a request that is determined to be a request not causing garbage collection, on the basis of only the average heap consumption H and the heap remaining amount F in step  704  may be moved to the top of the requests and then processed preferentially. 
         [0071]    In addition, it is to be understood that although the aforementioned embodiment is described on the basis of Java VM implementation, the present invention is applicable to a standalone environment regardless of whether or not the system is a server-client environment, as long as the system has a processing queue and garbage collection may occur in the system. In addition, the present invention is not limited to a particular OS or application either as a matter of course. 
       REFERENCE SIGNS LIST 
       [0072]      102  . . . application server,  104  . . . Internet,  202  . . . bus,  206  . . . main memory,  204  . . . CPU,  208  . . . IDE controller,  212  . . . DVD drive,  214  . . . display controller,  218  . . . communication interface,  220  . . . USB interface,  222  . . . audio interface,  228  . . . keyboard and mouse controller,  216  . . . display apparatus,  230  . . . keyboard,  232  . . . mouse,  210  . . . hard disk drive,  302  . . . communication interface,  304  . . . bus,  306  . . . CPU,  310  . . . hard disk drive,  308  . . . main memory,  402  . . . request reception module,  404  . . . queue,  406  . . . processing scheduler,  408  . . . request processing module,  410  . . . heap region,  412  . . . heap remaining amount monitoring module,  414  . . . garbage collection function,  416  . . . heap consumption database,  418  . . . processing result transmission module.