Shared request grouping in a computing system

A queuing module is configured to determine the presence of at least one shared request in a request queue, and in the event at least one shared request is determined to be present in the queue; determine the presence of a waiting exclusive request located in the queue after the at least one shared request, and in the event a waiting exclusive request is determined to be located in the queue after the at least one shared request: determine whether grouping a new shared request with the at least one shared request violates a deferral limit of the waiting exclusive request; and, in the event grouping the new shared request with the at least one shared request does not violate the deferral limit of the waiting exclusive request, group the new shared request with the at least one shared request.

FIELD

This disclosure relates generally to the field of queuing of requests for serialization of resources in a computing system, and more specifically to grouping of shared requests in a queue of serialization requests.

DESCRIPTION OF RELATED ART

In a computing system, processes issue various requests for use of computing resources (such as processor time, memory space, or access to data) in the course of execution. Contending processes need to manage their use of a resource to prevent corruption of the resource. Usually, this is via some serial means of managing concurrent exclusive and shared requesters. Some resource management techniques include polling for resource availability, or queuing of requests for use of the resource. Without knowing how the resource is used, the serialization system may process the received requests in a first come, first served (FIFO) order. FIFO ordering ensures that if multiple consecutive resource requests are requested in the proper order (as defined by the design of the resource) that deadlock does not occur (i.e., a first request waiting for a first resource that cannot be granted due to a second request holding the first resource, while the second request waits for a second resource that is held by the first request), and that starvation (i.e., one request waiting indefinitely for a use of a resource that is repeatedly granted to other requests) of requests also does not occur.

In a z/OS global resource serialization (GRS) system, a request may have one of two scopes of resource ownership: exclusive or shared. Control of computing resources may be granted to one and only one exclusive request during execution of the exclusive request. Shared requests, on the other hand, may run in parallel with each other; control of the computing resources may be shared by multiple shared requests at a time. An exclusive request may be followed by an operation that changes the system environment or a system resource, such as a write operation; a shared request may include a request that does not change any system resource, but needs to ensure that the system environment does not change while it is processing, such as a read operation.

SUMMARY

In one aspect, a method for shared request grouping in a computing system includes receiving a new shared request for placement in a request queue by a queuing module; determining the presence of at least one shared request in the request queue by the queuing module, and in the event at least one shared request is determined to be present in the queue: determining the presence of a waiting exclusive request located in the queue after the at least one shared request by the queuing module, and in the event a waiting exclusive request is determined to be located in the queue after the at least one shared request: determining whether grouping the new shared request with the at least one shared request violates a deferral limit of the waiting exclusive request by the queuing module; and in the event grouping the new shared request with the at least one shared request does not violate the deferral limit of the waiting exclusive request, grouping the new shared request with the at least one shared request by the queuing module.

In another aspect, a computer program product comprising a computer readable storage medium containing computer code that, when executed by a computer, implements a method for shared request grouping, wherein the method includes receiving a new shared request for placement in a request queue; determining the presence of at least one shared request in the request queue, and in the event at least one shared request is determined to be present in the queue: determining the presence of a waiting exclusive request located in the queue after the at least one shared request, and in the event a waiting exclusive request is determined to be located in the queue after the at least one shared request: determining whether grouping the new shared request with the at least one shared request violates a deferral limit of the waiting exclusive request; and, in the event grouping the new shared request with the at least one shared request does not violate the deferral limit of the waiting exclusive request, grouping the new shared request with the at least one shared request.

In another aspect, a queuing module for a computing system is configured to: receive a new shared request for placement in a request queue; determine the presence of at least one shared request in the request queue, and in the event at least one shared request is determined to be present in the queue; determine the presence of a waiting exclusive request located in the queue after the at least one shared request, and in the event a waiting exclusive request is determined to be located in the queue after the at least one shared request: determine whether grouping the new shared request with the at least one shared request violates a deferral limit of the waiting exclusive request; and, in the event grouping the new shared request with the at least one shared request does not violate the deferral limit of the waiting exclusive request, group the new shared request with the at least one shared request.

Additional features are realized through the techniques of the present exemplary embodiment. Other embodiments are described in detail herein and are considered a part of what is claimed. For a better understanding of the features of the exemplary embodiment, refer to the description and to the drawings.

DETAILED DESCRIPTION

Embodiments of methods for shared request grouping for a queuing module in a computing system are provided, with exemplary embodiments being discussed below in detail. If exclusive and shared requests arrive alternately in a first come, first served queuing system, low parallelism of shared request execution may result, with many shared requests executing alone due to placement in the queue between two exclusive requests. This may significantly slow process execution and reduce efficiency of use of resources in the computing system. However, expediting of grouping shared requests together may ensure that multiple shared requests are executed in parallel, improving overall request throughput. Also, if one or more shared requests are currently executing and a new shared request is added to the one or more shared requests while they are executing, overall system performance is improved, as a process issuing the new shared request may not have to change context due to the expedited execution of the new shared request. To accomplish this shared request grouping, waiting exclusive requests may be tagged as deferrable, with an associated deferral limit. The queuing module may group a newly received shared request with one or more shared requests that are located in the request queue in front of a waiting exclusive request, so long as the deferral limit of the waiting exclusive request is not violated by grouping the new shared request with the one or more queued shared requests. The definition of deferral limits for exclusive requests avoids starvation of exclusive requests. Appropriate designation of deferral limits for exclusive requests may allow grouping of all outstanding shared requests together, making efficient use of system resources.

The deferral limit for an exclusive request may designate a maximum number of requests that are permitted to be queued ahead of the exclusive request before execution of the exclusive request in some embodiments. In some embodiments, the deferral limit may designate a number of requests permitted to be in the queue ahead of the exclusive request, regardless of when the requests ahead of the exclusive request joined the queue, or the deferral limit may refer to a number of later-arriving shared requests that are allowed to jump ahead of the exclusive request, in which case a count of later-arriving shared requests that are moved ahead of the exclusive request may be kept. In other embodiments, the deferral limit may designate a maximum total amount of time the exclusive request may wait in the queue before execution, or a maximum permitted amount of waiting time that is attributable to moving later-arriving shared requests ahead of the exclusive request. The deferral limit for an exclusive request may be designated on a per request basis (based on, for example, the process issuing the exclusive request) in some embodiments, or may be a default value for all exclusive requests in the queuing system in other embodiments.

FIG. 1illustrates an embodiment of a method100for shared request grouping. The method100may be implemented in a queuing module in a computing system. In block101, a new shared request is received by the queuing module. In block102, it is determined if there are one or more shared requests already in the queue with which the new shared request may be grouped. In various embodiments, the one or more shared requests already in the queue may be waiting in the queue, or may be currently executing. It is then determined if there are any waiting exclusive requests located in the queue after the one or more shared requests; the respective deferral limit for each waiting exclusive request located in the queue after the one or more queued shared requests is determined. The deferral limit may designate a total maximum number of requests that are permitted to be ahead of the exclusive request in the queue, or a number of shared requests that are permitted to jump ahead of the exclusive request in the queue. The deferral limit may alternately designate a maximum amount of time the exclusive request is permitted to wait before execution. In various embodiments, the deferral limit for an exclusive request may be a default value for all exclusive requests in the queuing system, or may be designated for individual exclusive requests based on, for example, the process that issued the exclusive request. Then, in block103, any deferral limits determined in block102are used to determine whether grouping the new shared request with the one or more shared requests violates the deferral limit of any of the waiting exclusive requests. A number of requests in the queue ahead of each waiting exclusive request, a count of shared requests that have been moved up in the queue, or an amount of time required to execute the new shared request in parallel with the one or more shared requests, may be used to make this determination. If it is determined in block103that grouping the new shared request with the one or more shared requests does not violate the deferral limit of any waiting exclusive request, the new shared request is grouped in the queue with the one or more shared requests in block104, and the new shared request will execute with the grouped shared requests before the waiting exclusive requests. If it is determined in block103that grouping the shared request with the one or more shared requests violates the deferral limit of a waiting exclusive request, then the new shared request is placed in the queue after the waiting exclusive request in block105. This may comprise placing the new shared request at the end of the queue in some embodiments, or grouping the new shared request with one or more other shared requests that are located in the queue after the waiting exclusive request in other embodiments (i.e., subject to the determination of block103); placement of the new shared request is performed such that the deferral limit of no exclusive request in the queue is violated.

Application of method100is illustrated below with respect toFIGS. 2A-C,3A-C, and4A-D.FIG. 2Aillustrates an embodiment of a request queue200A. Request queue200A includes exclusive request201at the front of the queue200A, shared request(s)202, and waiting exclusive requests203-204. Each of exclusive requests201,203, and204has an associated deferral limit. In various embodiments, shared request(s)202may include one shared request, or a plurality of grouped shared requests. Referring again toFIG. 1, when a new shared request205is received by a queuing module for the request queue200(block101), the queuing module determines the respective deferral limits for each of waiting exclusive requests203-204(block102), as waiting exclusive requests203-204are located after shared request(s)202in the request queue200A. It is then determined if grouping the new shared request205with shared request(s)202and executing the grouped shared requests in parallel violates the respective deferral limits of either of waiting exclusive requests203-204(block103). If grouping the new shared request205with shared request(s)202and executing the grouped shared requests in parallel does not violate the respective deferral limits of either of waiting exclusive requests203-204, then the new shared request205is grouped with shared request(s)202to form grouped shared requests206(block104), as shown in updated queue200B ofFIG. 2B. The grouped shared requests206are executed in parallel when they arrive at the front of the queue (in this example, after completion of exclusive request201). Otherwise, the new shared request205is placed at the end of the queue after exclusive request204(block105), as shown in updated queue200C ofFIG. 2C. Request queue200A and updated queues200B-C are shown for illustrative purposes only; a request queue may include any number of exclusive requests, and any number of grouped or ungrouped shared requests in various embodiments, subject to the method100outlined inFIG. 1.

FIG. 3Aillustrates another embodiment of a request queue300A. Request queue300A includes shared request(s)301at the front of the queue300A (i.e., shared request(s)301are currently executing), and waiting exclusive requests302-303. Each of exclusive requests302-303has an associated deferral limit. In various embodiments, shared request(s)301may include one shared request, or a plurality of grouped shared requests. Referring again toFIG. 1, when a new shared request304is received by a queuing module for the request queue300A (block101), the queuing module determines the respective deferral limits for each of waiting exclusive requests302-303(block102), as waiting exclusive requests302-303. are located after shared request(s)301in the request queue300A. It is then determined if grouping the new shared request304with shared request(s)301and executing the grouped shared requests in parallel violates the respective deferral limits of either of waiting exclusive requests302-303(block103). If grouping the new shared request304with shared request(s)301and executing the grouped shared requests in parallel does not violate the respective deferral limits of either of waiting exclusive requests302-303, then the new shared request304is grouped with shared request(s)301to form grouped shared requests305(block104), as shown in updated queue300B ofFIG. 3B. The grouped shared requests305are executed in parallel, allowing the process issuing the new shared request304to not have to change context (i.e., suspend or resume), as the process may continue to execute with the expedited execution of new shared request304. Otherwise, the new shared request304is placed at the end of the queue after exclusive request303(block105), as shown in updated queue300C ofFIG. 3C. Request queue300A and updated queues300B-C are shown for illustrative purposes only; a request queue may include any number of exclusive requests, and any number of grouped or ungrouped shared requests in various embodiments, subject to the method100outlined inFIG. 1.

FIG. 4Aillustrates another embodiment of a request queue400A. Request queue400A includes exclusive request401at the front of the queue400A, shared request(s)402, waiting exclusive request403, shared request(s)404, and exclusive request405. Each of exclusive requests401,403, and405has an associated deferral limit. In various embodiments, each of shared request(s)402and404may include one shared request, or a plurality of grouped shared requests. Referring again toFIG. 1, when a new shared request406is received by a queuing module for the request queue400A (block101), the queuing module determines the respective deferral limits for each of waiting exclusive requests403and405(block102), as waiting exclusive requests403is located after shared request(s)402, and waiting exclusive requests405is located after shared request(s)402and404. It is then determined if grouping the new shared request406with shared request(s)402or with shared request(s)404violates the respective deferral limits of either of waiting exclusive requests403or405(block103). If grouping the new shared request406with shared request(s)402and executing the grouped shared requests in parallel does not violate the respective deferral limits of either of waiting exclusive requests403or405, then the new shared request406is grouped with shared request(s)402to form grouped shared requests407(block104), as shown in updated queue400B ofFIG. 4B. The grouped shared requests407are executed in parallel when they arrive at the front of the queue (in this example, after completion of exclusive request401, and before exclusive requests403and405). If grouping new shared request406with shared request(s)402violates the deferral limit of exclusive request403, but does not violate the deferral limit of exclusive request405, the new shared request406is grouped with shared request(s)404ahead of exclusive request405but behind exclusive request403, forming grouped shared requests408, as shown in updated queue400C ofFIG. 4C. If grouping the new shared request406with either of shared request(s)402or404violates the deferral limit of exclusive request405, the new shared request406is placed at the end of the queue after exclusive request405(block105), as shown in updated queue400D ofFIG. 4D. As illustrated byFIGS. 4A-D, a new shared request will be grouped in the queue with the first shared request(s) in the queue that may be grouped with the new shared request without violating the deferral limit of any waiting exclusive request, or the new shared request will be placed at the end of the queue. Request queue400A and updated queues400B-D are shown for illustrative purposes only; a request queue may include any number of exclusive requests, and any number of grouped or ungrouped shared requests in various embodiments, subject to the method100outlined inFIG. 1.

FIG. 5illustrates an example of a computer500which may be utilized by exemplary embodiments of a method for shared request grouping and exclusive request deferral as embodied in software. Various operations discussed above may utilize the capabilities of the computer500. One or more of the capabilities of the computer500may be incorporated in any element, module, application, and/or component discussed herein. For example, a queuing module that implements method100ofFIG. 1may be implemented in operating system550, and exclusive and shared requests handled by the queuing module may be executed by processor570.

The computer500includes, but is not limited to, personal computers (PCs), workstations, laptops, PDAs, palm devices, servers, storages, and the like. Generally, in terms of hardware architecture, the computer500may include one or more processors510, memory520, and one or more input and/or output (I/O) devices570that are communicatively coupled via a local interface (not shown). The local interface can be, for example but not limited to, one or more buses or other wired or wireless connections, as is known in the art. The local interface may have additional elements, such as controllers, buffers (caches), drivers, repeaters, and receivers, to enable communications. Further, the local interface may include address, control, and/or data connections to enable appropriate communications among the aforementioned components.

The processor510is a hardware device for executing software that can be stored in the memory520. The processor510can be virtually any custom made or commercially available processor, a central processing unit (CPU), a digital signal processor (DSP), or an auxiliary processor among several processors associated with the computer500, and the processor510may be a semiconductor based microprocessor (in the form of a microchip) or a macroprocessor.

The software in the memory520may include one or more separate programs, each of which comprises an ordered listing of executable instructions for implementing logical functions. The software in the memory520includes a suitable operating system (O/S)550, compiler540, source code530, and one or more applications560in accordance with exemplary embodiments. As illustrated, the application560comprises numerous functional components for implementing the features and operations of the exemplary embodiments. The application560of the computer500may represent various applications, computational units, logic, functional units, processes, operations, virtual entities, and/or modules in accordance with exemplary embodiments, but the application560is not meant to be a limitation.

The operating system550controls the execution of other computer programs, and provides scheduling, input-output control, file and data management, memory management, and communication control and related services. It is contemplated by the inventors that the application560for implementing exemplary embodiments may be applicable on all commercially available operating systems.

Application560may be a source program, executable program (object code), script, or any other entity comprising a set of instructions to be performed. When a source program, then the program is usually translated via a compiler (such as the compiler540), assembler, interpreter, or the like, which may or may not be included within the memory520, so as to operate properly in connection with the O/S550. Furthermore, the application560can be written as an object oriented programming language, which has classes of data and methods, or a procedure programming language, which has routines, subroutines, and/or functions, for example but not limited to, C, C++, C#, Pascal, BASIC, API calls, HTML, XHTML, XML, ASP scripts, FORTRAN, COBOL, Perl, Java, ADA, .NET, and the like.

The I/O devices570may include input devices such as, for example but not limited to, a mouse, keyboard, scanner, microphone, camera, etc. Furthermore, the I/O devices570may also include output devices, for example but not limited to a printer, display, etc. Finally, the I/O devices570may further include devices that communicate both inputs and outputs, for instance but not limited to, a NIC or modulator/demodulator (for accessing remote devices, other files, devices, systems, or a network), a radio frequency (RF) or other transceiver, a telephonic interface, a bridge, a router, etc. The I/O devices570also include components for communicating over various networks, such as the Internet or intranet.

If the computer500is a PC, workstation, intelligent device or the like, the software in the memory520may further include a basic input output system (BIOS) (omitted for simplicity). The BIOS is a set of essential software routines that initialize and test hardware at startup, start the O/S550, and support the transfer of data among the hardware devices. The BIOS is stored in some type of read-only-memory, such as ROM, PROM, EPROM, EEPROM or the like, so that the BIOS can be executed when the computer500is activated.

When the computer500is in operation, the processor510is configured to execute software stored within the memory520, to communicate data to and from the memory520, and to generally control operations of the computer500pursuant to the software. The application560and the O/S550are read, in whole or in part, by the processor510, perhaps buffered within the processor510, and then executed.

When the application560is implemented in software it should be noted that the application560can be stored on virtually any computer readable medium for use by or in connection with any computer related system or method. In the context of this document, a computer readable medium may be an electronic, magnetic, optical, or other physical device or means that can contain or store a computer program for use by or in connection with a computer related system or method.

The application560can be embodied in any computer-readable medium for use by or in connection with an instruction execution system, apparatus, or device, such as a computer-based system, processor-containing system, or other system that can fetch the instructions from the instruction execution system, apparatus, or device and execute the instructions. In the context of this document, a “computer-readable medium” can be any means that can store, communicate, propagate, or transport the program for use by or in connection with the instruction execution system, apparatus, or device. The computer readable medium can be, for example but not limited to, an electronic, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, device, or propagation medium.

The technical effects and benefits of exemplary embodiments include improvement of parallelization and throughput in a computing system.