Electrical computers and digital processing systems: memory – Storage accessing and control – Memory configuring
Reexamination Certificate
2001-03-02
2003-09-23
Sparks, Donald (Department: 2187)
Electrical computers and digital processing systems: memory
Storage accessing and control
Memory configuring
C370S412000, C709S241000
Reexamination Certificate
active
06625709
ABSTRACT:
TECHNICAL FIELD
This invention relates generally to resource allocation and, more particularly, relates to the allocation of memory among one or more network communication devices.
BACKGROUND OF THE INVENTION
As the complexity of modern computer software increases, ever greater demands are placed on the computer hardware on which this software is run. One such demand is the need for ever increasing Random Access Memory (RAM) space. The computer's memory provides the necessary space for the software to use while it is running on the computer. The memory is used by the computer to store the data required by the software. Varying software programs require varying amounts of memory, and even the same software program may require different amounts of memory at different times during its operational cycle. Software and hardware manufacturers have come up with a number of different schemes to allow computer hardware with limited memory to run software of increasing complexity. Once such scheme is known as “virtual memory”, and operates by moving data which has not been recently accessed from the limited memory storage to more available hard drive space. One difficulty with such a system is the inefficiency introduced by the transfer of data to and from memory as it is needed by a computer program. Another difficulty is limited speed with which information can be written to and read from a hard drive as compared to the read/write speed of a computer's memory.
To alleviate the need to resort to inefficient schemes such as virtual memory, computer software and hardware manufacturers have attempted to make more efficient use of the existing memory. Because the need for memory can be transient, a dynamic memory allocation scheme can allocate memory from software which does not currently require it to software currently in need of it. The difficulty, however, with such a dynamic memory allocation scheme is selecting an efficient set of rules for granting memory. Should the memory be granted too freely, all of the available memory will be quickly used up, leaving none for other software packages to perform even the most simple of tasks. Should the memory be granted too restrictively, the advantage of a dynamic memory allocation scheme is lost since memory requests will be denied too often, resulting in poor performance.
Dynamic allocation of memory is generally most helpful when the memory requirements are continually changing. For example, network interface devices, such as a network interface card (NIC), require a constantly changing amount of memory to use as a buffer to temporarily store the packets they are sending and receiving. A packet to be sent across a network is placed in the buffer of a NIC. The NIC then reads the data from the buffer and sends it across the network, and the buffer is subsequently cleared to make room for the next packet to be sent. Generally, there is sufficient buffer space to store more than one packet. This allows the software sending the packets to continue sending packets at a steady rate, even if the NIC is not able to always transmit the packets immediately. Should the network become congested, the NIC will transmit the packets at a slower rate, and the packets being sent by the software will be queued in the buffer for transmission at a later time when the network congestion is resolved, and the NIC can resume sending the packets at an optimal rate. When the NIC does resume sending the packets at an optimal rate, it may be able to send the packets faster than they are being added to the buffer by the software, eventually clearing the buffer of all queued packets.
Other subsystems of a modern personal computer likewise have continually changing memory requirements. For example, printer drivers are similar to NICs in their need for an ever changing amount of buffer storage. Given such transient memory requirements, a dynamic memory allocation scheme can increase the efficiency of the memory usage, increasing the amount of memory given to a requester under certain circumstances. However, as stated above, the difficulty with such a dynamic memory allocation scheme is selecting an efficient set of rules for granting memory. It is inefficient to merely grant memory to a first requestor whenever available memory exists, as such a scheme would allow the first requestor to use up all of the available memory, leaving none for a second requestor to use even if it only needed a minimal amount. Conversely, a scheme which would reserve extra memory for the second requester will also be inefficient, because the second requestor may never need the space. It is difficult to properly balance the need to freely grant a memory request with the need to conserve resources for future requests from other sources.
SUMMARY OF THE INVENTION
Accordingly, the present invention provides a method for dynamically allocating resources among different requesters.
The present invention also provides a method for determining when to allocate a resource to a requester.
The present invention additionally provides a system which can grant a disproportionately large amount of resources to a single requestor while maintaining resources in reserve to assure fairness among many requesters.
The invention solves the above difficulties of memory allocation by providing a novel dynamic resource allocation scheme which allows one requestor to be granted a significant part of the available free resources, while maintaining a sufficient safety buffer to satisfy other requestors over a period of time. While the present invention can solve the above memory allocation problems, it is equally useful with any shared resource, such as processor cycles, and the like. Because of the transient nature of some resource requirements, the invention can meet disproportionately large resource requests of limited duration while maintaining overall fairness in the amount of resources provided to each requestor. By maintaining a buffer, the system can temporarily satisfy requests from other requestors. When such other requests increase, the invention can deny continuing requests from a requestor who has been granted too many resources and thereby diminish that requestor's resource consumption and increase the resources available to satisfy the other requests. Thus, the invention minimizes the number of times a request for resources must be denied and thereby facilitates the operation of a software in an environment of limited resources. By minimizing the number of times a request for resources must be denied, the present invention can also increase the network throughput and increases the stability of the entire computer system.
The dynamic resource allocation scheme contemplated by the present invention is based on two simple rules. Initially, the available resources are mathematically divided among the requesters. Each requestor's share is known as that requestor's “fair share”. Furthermore, a certain amount of resources, or a percentage of the total resources, are set aside as a “safety buffer”. The size of the safety buffer can vary from application to application, depending, among other things, on the nature of the resource requirements of the particular application. The first rule of the scheme contemplated by the present invention is that the requester is granted resources so long as there are resources available and the requestor has not consumed more than its fair share. The second rule is that the requestor is granted resources, even if it has exceeded its fair share, so long as the safety buffer remains unused.
The interaction of these two rules can best be analyzed temporally. Consider the situation where one requestor initially needs a lot of resources. Resources will be granted to it until its fair share is used up. After that, the first requestor will continue to be granted resources, should it need them, until all available resources, minus the safety buffer, are used. Now consider a second requestor which also needs resources. Initially it will be granted the resources from th
Aiken Mark A.
O'Donnell Ryan
Leydig , Voit & Mayer, Ltd.
Moazzami Nasser
Sparks Donald
LandOfFree
Fair share dynamic resource allocation scheme with a safety... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fair share dynamic resource allocation scheme with a safety..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fair share dynamic resource allocation scheme with a safety... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3093902