Electrical computers and digital processing systems: virtual mac – Task management or control
Reexamination Certificate
1998-09-16
2004-08-17
Lee, Thomas (Department: 2126)
Electrical computers and digital processing systems: virtual mac
Task management or control
C718S102000
Reexamination Certificate
active
06779180
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention generally relates to computer system resource management and more specifically relates to memory management in a multi-threaded programming environment.
2. Background Art
The development of the EDVAC computer system of 1948 is often cited as the beginning of the computer era. Since that time, computer systems have evolved into extremely sophisticated devices, and computer systems may be found in many different settings. Computer systems typically include a combination of hardware (e.g., semiconductors, circuit boards, etc.) and software (e.g., computer programs). As advances in semiconductor processing and computer architecture push the performance of the computer hardware higher, more sophisticated computer software has evolved to take advantage of the higher performance of the hardware, resulting in computer systems today that are much more powerful than just a few years ago.
Computer systems typically include operating system software that controls the basic function of the computer, and one or more software application programs that run under the control of the operating system to perform desired tasks. For example, a typical IBM Personal Computer may run the OS/2 operating system, and under the control of the OS/2 operating system, a user may execute an application program, such as a word processor. As the capabilities of computers have increased, the application programs designed for high performance computer systems have become extremely powerful.
As a computer system is utilized to accomplish the various tasks for which it was designed, it uses an electronic memory storage area in order to perform the necessary calculations and manipulations associated with the processes at hand. The “stack” is a dedicated portion of the computer system's memory storage area used by the computer system to store the state of the computer system, to pass variables between functions, and to store return addresses so that the system can return to its original location before function calls. Thus, the stack serves as a temporary storage location where the computer can place interim information while performing various processing operations. As a part of the processing associated with the normal operations of the computer system, the computer system will issue “function calls” for various procedures. Whenever the system calls a function as part of accomplishing a task, the current state of the computer (if needed), a return address, and variables being passed to and from the function are placed into an area of the stack known as a “stack frame” and placed onto the stack for use by the system.
Because computer systems are designed in a multitude of different ways, stacks are also implemented in several ways. Portions of an operating system, which control most computer systems these days, may use more than one stack. Furthermore, stacks can be implemented in a fixed size, wherein stacks can only grow so large, or stacks can be implemented in an “infinite” size, wherein stacks can use hard drive or other space to grow until the hard drive or other space is completely full. If the size of the stack is fixed, care must be exercised so as not to exceed the boundaries of the stack. If more stack frames are placed onto the stack than can be accommodated within the preestablished limits of the stack, then the stack “overflows” and the entire system can crash as the instructions stored on the stack overwrite other areas of the computer system's memory storage area. This type of memory error will commonly cause loss of data and other significant problems. In addition, some systems will completely and irretrievable lock if the stack is overflowed. Most systems will, at a minimum, generate stack exceptions. Even those systems that have an infinite stack will suffer a performance hit if the stack grows too large because most of the stack will be on the hard disk, and hard disks are substantially slower than memory.
As a general rule, each different function call, processed during the computer's normal operation, will generate a stack frame that will be placed on the stack for eventual removal by the computer system. One function call generally creates one stack frame on the stack and 10 function calls will generate 10 stack frames on the stack. If too many function calls are made and too many stack frames are generated, the stack frames can exceed the logical limits of the stack boundaries and overrun the limits of the stack portion of the memory as described above. Furthermore, even if the stack size is not fixed, the system will suffer a serious performance hit because the stack will be paged into and out of disk memory.
These stack overflow errors are possible when an asynchronous function, particularly a subsystem function, completes its task “synchronously.” In this scenario, a system would ask a subsystem function to perform a task by calling the function and handing it a variable that indicates what task is to be performed. The system will also generally pass a callback entry point (the address of a callback function) to the subsystem function. The callback entry point acts as a notice to the subsystem that the subsystem needs to call the system back when the task has been completed, and that the subsystem should call a particular callback function that is pointed to by the callback entry point. A stack frame is placed on the stack with the call to the subsystem function. The subsystem knows that it can immediately complete its task, and it does so. This completion is termed “synchronous” because the task was completed in the same computer state. The subsystem may call other sub-functions or subsystems that help it complete the task. Each of these sub-functions will generally result in stack frames being placed on the stack. Some of these stack frames may still be on the stack when the subsystem function calls back the system by calling the callback function. This is particularly true if a sub-function of the subsystem function performs the call to the callback function, because the call to the sub-function will generate another stack frame. The callback function causes yet another stack frame to be placed on the stack.
Therein lies the potential stack problem. There are many stack frames on the stack, and the stack has not had a chance to “unwind.” Unwinding, also called unwrapping, a stack is basically the process of allowing the system to “catch up” to the multitude of stack frames on the stack. Functions are returned from and each return unwinds or unwraps the stack by removing the stack frame, associated with the function being return from, off the stack. For instance, if no more functions are called at this point in the scenario, normal processing would incur a return from the callback function, returns from all of the sub-functions called by the subsystem, and a return from the subsystem function. The stack would then be at its starting point. The problem arises when these multiple frames are on the stack and more calls to similar subsystems or the same subsystem occur. Or, if a function is looping through a repetitive series of similar asynchronous function calls that complete in a synchronous fashion, it is quite possible that the accumulated callback functions can quickly cause the stack to overflow. This looping causes a problem because each call to an asynchronous function that completes synchronously causes more stack frames to be placed on the stack, with no opportunity to unwind the stack. This looping can happen, for example, if large amounts of data are being moved from a disk drive to memory.
There are several possible solutions to this stack dilemma known to those skilled in the art. For example, it is possible to have the system treat every function call in the same manner and wait for the task to be completed before processing the next function call. While ensuring that the stack will not overflow, this approach is extremely inefficient from a processing point of view. Alternatively, it is possible to
Ho The Thanh
Lee Thomas
Payne Leslie J.
Schmeiser Olsen & Watts
LandOfFree
Apparatus and method for preventing stack overflow from... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Apparatus and method for preventing stack overflow from..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Apparatus and method for preventing stack overflow from... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3360350