Electrical computers and digital processing systems: virtual mac – Task management or control – Process scheduling
Reexamination Certificate
1999-07-22
2004-11-16
Follansbee, John (Department: 2154)
Electrical computers and digital processing systems: virtual mac
Task management or control
Process scheduling
Reexamination Certificate
active
06820262
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to databases and, more specifically, to methods and apparatus for computing the degree of parallelism in a multi-user environment.
BACKGROUND OF THE INVENTION
The central processing unit (“CPU”) is the brains of the computer and represents the computing power of the computer. Thus, a computer program can run faster if there are two CPUs executing the computer program rather than if only one CPU is executing it. The simultaneous use of more than one CPU to execute the computer program is known as parallel processing or parallel computing. Parallel processing works by dividing a computer program into several individual processes to be parceled out to available CPUs. Parallel processing is one way to improve the efficient use of the computer's brain power by not allowing any of the computer's CPUs to remain idle. Thus, in general, parallel processing is preferred over serial processing when the goal is to execute a computer program faster and when there is more than one CPU available to execute the computer program.
An example of an instance where more than one CPU is available for executing a computer program is that some large computers house several CPUs. Another example is a computer cluster where several single-CPU computers are connected in such a way as to behave like a single computer. A cluster is a good example a system in which several relatively cheap computers are purposely coupled to achieve comparable computing power of a powerful but expensive single-CPU computer. Clustering also enables companies to leverage the investment already made in PCs and workstations. Moreover, new CPUs can be easily added by adding a new PC or workstation to the cluster. The cluster may comprise several nodes located at various sites, as in local-area-networks (LANs)
While parallel processing is a highly useful concept, it is no panacea. In fact, parallel processing has its own set of problems. When more than one user attempts to perform parallel processing to use all of the available CPUs, the users are in competition for the same CPUs. Each user will attempt to monopolize all the CPUs. Thus, the computer quickly becomes overstressed because there is no cooperation in managing the CPUs of the computer. In one approach, the users' computer tasks (“jobs”) are queued as they arrive, and only a very small number of parallel jobs are allowed to run at any given time.
One environment in which efficient parallel processing techniques are critical is within database systems. For the purposes of illustration, one approach to parallel processing is described herein in the context of parallel execution of queries and database operations. In typical database systems, users store, update and retrieve information by submitting commands to a database server. To be correctly processed, the commands must comply with the database language that is supported by the database server. One popular database language is known as Structured Query Language (SQL). Database commands submitted to database servers that support the SQL language are typically in the form of SQL statements.
A SQL statement comprises either a query or a combination of a query and data manipulation operations to be performed on a database. The query portion and the data manipulation operations are herein referred to as “operations”. Thus, an “operation” in a parallel execution environment is hereafter referred to as a “parallel operation”. For purposes of simplification, a user that submits a parallel operation is hereafter referred to as a “parallel user”.
With parallel execution, multiple parallel server processes work together simultaneously to execute a single SQL statement. The number of parallel server processes, also known as “slave processes”, assigned to perform a single parallel operation is referred to as the degree of parallelism for that operation. It is possible for multiple slave processes to work on a single parallel operation because the parallel operation is divided into multiple portions, hereafter referred to as “work granules”. By assigning a degree of parallelism to each parallel operation that is entering the system, the database system dictates how the work to be done is shared among the CPUs.
To efficiently process a SQL statements, an efficient technique for determining the degree of parallelism is required. If the degree of parallelism assigned to incoming operations is too high, then the operations must contend for the same CPUs. If the degree of parallelism assigned to incoming operations is too low, then some CPUs that could be used for processing the operations may remain idle.
According to one approach for assigning degrees of parallelism to operations, the degree of parallelism assignment mechanism assigns each parallel operation seeking entry into the system a degree of parallelism equal to the number of CPUs divided by X, where X equals the total number of parallel operations present on the system plus the number of parallel operations that are presently seeking entry into the system. However, this approach is unable to accommodate both parallel and serial jobs simultaneously.
In yet another approach, a maximum number of parallel server processes and an allocation unit is predetermined for a given system. Assume that the number of parallel server processes is set at 100 and the allocation unit is set at 10. Each parallel operation that enters the system is assigned a degree of parallelism equal to the allocation unit, 10. However, as the system is close to exhausting the maximum number of parallel server processes, subsequent parallel operations entering the system are assigned a diminished degree of parallelism. For purposes of illustration, assume that once 90% of the parallel server processes have been exhausted, subsequent parallel operations entering the system are assigned a diminished degree of parallelism. For example, the first 9 parallel operations to enter the system will each be assigned a degree of parallelism of 10. The tenth and eleventh parallel operation entering the system may only be assigned a degree of parallelism of 6 and 4 respectively.
One drawback to this approach is that the first parallel operation to enter the system uses only a small fraction of the available resources (e.g. only 10 of 100 available CPUs) even if it remains the only parallel operation on the system. Instead, as in our example, the first parallel operation is assigned only 10 degrees of parallelism. Even if no other parallel operation seeks to enter the system, the degree of parallelism remains equal to the allocation unit. Thus, in the case where there is only one parallel operation on the system, 90% of the resources remain unused. This approach makes for inefficient use of system resources in cases where there are low numbers of parallel operations on the system.
Another drawback to this approach is a lack of fairness in allocating the degree of parallelism to parallel operations. Referring to our example above, assume that the eighth and ninth parallel operations terminate while parallel operations 1 to 7 and 10 to 11 remain active in the system. The next four parallel operations that seek entry into the system will be assigned 10, 10, 1, 1 degrees of parallelism respectively, even if they entered the system at approximately the same time. Thus, the third and fourth parallel operations that just entered the system will perceive the system to be unfair.
Based on the foregoing, there is a need for a method or mechanism for computing the degree of parallelism in a multi-user environment with the goal of maximizing the use of available system resources.
SUMMARY OF THE INVENTION
The foregoing needs and objects, and other needs and objects that will become apparent from the following description, are achieved by the present invention, which comprises, in one aspect, a method for computing degrees of parallelism in a multi-user environment for a computer system, the method comprising receiving an operation associated with a requested degree of parallel
Dageville Benoit
Tellez Juan
Becker Edward A.
Follansbee John
Hickman Palermo & Truong & Becker LLP
Nguyen Dustin
Oracle International Corporation
LandOfFree
Method for computing the degree of parallelism in a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for computing the degree of parallelism in a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for computing the degree of parallelism in a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3362875