Apparatus and method for managing stacks for efficient memory usage

An apparatus and method for managing stacks for efficient memory usage. The apparatus includes a fault cause analysis unit to recognize a page fault caused by a marking page; a control unit to set the marking page, to request compression of a first stack page depending on whether a page fault occurs, to release a mapping of a second stack page that becomes empty due to the compression, and to return the second stack page; a memory allocation unit to receive the second stack page and to allocate a new stack page to the control unit upon completion of the compression; and a compression unit to compresses the first stack page at the request of the control unit.

CROSS-REFERENCE TO RELATED APPLICATION

This application claims the benefit of Korean Patent Application No. 2007-4340, filed in the Korean Intellectual Property Office on Jan. 15, 2007, the disclosure of which is incorporated herein by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

Aspects of the present invention relate to efficient management of stacks of an application for efficient memory acquisition for an operating system and, more particularly, to an apparatus and method that can ensure large capacity memory acquisition for an operating system by storing a stack region exceeding a predetermined range in a compressed format.

2. Description of the Related Art

Conventionally, securing memory has been carried out by retrieval of data in a read-only region, retrieval of a dirty page, or retrieval of an anonymous page using a swap space. The retrieval of the data in the read-only region uses the characteristics of the data in the read-only region. Since a code of an application to be executed is read-only, the code is not changed during the execution of the application. An image of an execution file can be temporarily erased from a memory because the image has already been stored. Thus, by retrieving the data in the read-only region, free space in the memory can be acquired efficiently.

The operating system does not immediately write a page in a file, change the page in the memory, and mark the page as a dirty (changed) page. Instead, when there is insufficient memory space, free space of the memory is acquired by writing the dirty page in a file and retrieving the dirty page.

The anonymous page indicates a page, such as a heap or a stack, that is not related to an image of a file and is dynamically generated during the execution of an application. If a space that can be swapped exists in a system, a free space of the memory can be acquired such that the anonymous page of the application swaps out, referred to as the retrieval of the anonymous page using the swap space.

FIG. 1is a conceptual view illustrating memory allocation during the execution of an application according to the prior art. In general, once a specific function101of an application is compiled and is executed in assembly language, a predetermined stack103of a memory is allocated for the execution of the application according to assembly language. Similarly, upon execution of another function102, a predetermined stack104is allocated according to interpreted assembly language. In this way, if an application is executed, only a portion of the entire region of the memory, instead of the entire region of the memory, is intensively used, which is called locality. Currently used embedded systems do not include a swap space and thus cannot use retrieval of an anonymous page, nor do currently used methods consider a usage pattern of a stack having strong locality.

FIGS. 2A and 2Bare conceptual views illustrating stack usage of an application according to the prior art. InFIG. 2A, a first region220indicates currently used stack pages in a memory and a second region230indicates a stack page that has not yet been allocated. A current stack pointer210is positioned at a boundary between the first region220and the second region230, i.e., between the last allocated stack page and a non-allocated stack page. Upon execution of an application, more stack pages are allocated as the number of functions to be processed increases, as illustrated inFIG. 2B.

InFIG. 2B, a first region240indicates currently used stack pages in a memory and a second region250indicates frequently referred stack pages. The current stack pointer210is positioned between the last allocated stack page and a non-allocated stack page. The first region240is used, but is not frequently referred to, unlike the second region250. Thus, the memory space that is available to the operating system decreases due to the first region240.

SUMMARY OF THE INVENTION

Aspects of the present invention provide an apparatus and method for managing stacks for efficient memory usage, in which a larger free memory space for an operating system is acquired by minimizing the size of a stack page in a memory used by an application.

According to an aspect of the present invention, an apparatus to manage stacks for efficient memory usage is provided. The apparatus includes a fault cause analysis unit to recognize a page fault caused by a marking page, a control unit to set the marking page, to request compression of a first stack page depending on whether a page fault occurs, to release a mapping of a second stack page that becomes empty due to the compression, and to return the second stack page; a memory allocation unit to receive the second stack page from the control unit and to allocate a new stack page to the control unit upon completion of the compression; and a compression unit to compress the first stack page at the request of the control unit.

According to another aspect of the present invention, a method for managing stacks for efficient memory usage is provided. The method includes setting a marking page in a first stack page, generating a page fault due to the marking page, requesting compression of a second stack page depending on whether a page fault occurs and compressing the second stack page in response to the request, and releasing a mapping of a third stack page that becomes empty due to the compression and returning the third stack page.

DETAILED DESCRIPTION OF THE EMBODIMENTS

FIG. 3is a block diagram of an apparatus300for managing stacks for efficient memory usage according to an embodiment of the present invention. The apparatus300includes a memory management unit (MMU)310, a page fault handler320, a control unit330, a memory allocation unit340, and a compression unit350. According to other aspects of the invention, the apparatus may include additional units as well. The apparatus300may be a part of a computer, portable computer, digital camera, mobile phone, personal digital assistant, personal entertainment device, embedded system, or any device where memory is at a premium.

The term ‘unit’, as used herein, refers to, but is not limited to, a software component that is capable of being executed by a processor or a hardware component that performs certain tasks, such as a Field Programmable Gate Array (FPGA) or an Application Specific Integrated Circuit (ASIC). A unit may advantageously be configured to reside on the addressable storage medium and configured to execute on one or more processors. Thus, a unit may include, by way of example, components, such as software components, object-oriented software components, class components and task components, processes, functions, attributes, procedures, subroutines, segments of program code, drivers, firmware, microcode, circuitry, data, databases, data structures, tables, arrays, and variables. The functionality provided for in the components and units may be combined into fewer components and units or further separated into additional components and units. In addition, the components and units may be implemented such that they execute on one or more computers in a communication system.

The memory management unit310is a hardware component for managing a memory system such as a virtual memory system. The memory management unit310may be implemented as a separate chip or may be implemented as part of a central processing unit (CPU) according to the design needs of the apparatus300or the device into which the apparatus300is incorporated. The memory management unit310has a small-capacity memory in order to hold a table required for mapping a virtual memory to a real memory.

The page fault handler320manages an occurring page fault. A page fault is an interrupt to software, which is generated by hardware when a program accesses a page that is not mapped to a physical memory. The page fault handler320manages such a page fault when the page fault occurs.

The interrupt is a signal coming from a device mounted on a computer or program in the computer and causes the operating system to stop the current ongoing task and then to determine which task is to be performed next. These days, most personal computers or large-scale computers are interrupt-based systems: once a computer command in a program starts, the computer cannot continue the ongoing task or execute commands until an interrupt signal is detected. If the interrupt signal is detected, the computer resumes execution of an ongoing program or starts execution of another program. Although a single computer can execute a single computer command at a time, the computer can also execute another program or command at that time due to the interrupt signal. Such an operation is called multi-tasking, which enables a user to perform several tasks at a time.

The page fault handler320includes a fault cause analysis unit321. The apparatus300generates a fault when a current stack pointer points to a marking page. The fault cause analysis unit321recognizes that the generated fault is caused by the marking page. The marking page will be described later with respect to the control unit330.

The control unit330requests the memory allocation unit340to allocate a new stack page, manages the marking page, and requests the compression unit250to compress or decompress a currently used stack page.

InFIG. 4A, a first region420indicates currently used stack pages, a second region430indicates a non-allocated stack page, and a third region440(marked with black) indicates a marking page. A current stack pointer410points to a stack page scheduled to be allocated by the memory allocation unit340to a process of an application at the request of the application. The process of the application is an instance of a program that is being executed in the computer, and is similar to the term “task” used in several operating systems. In other operating systems such as UNIX, a process starts with a start of a program. Like a task, the process is a program that is being executed in association with a particular data set for tracking and managing the process.

The control unit330sets the marking page by marking a page as a read-only region, maintaining the page as unmapped, and generating a hardware fault when the page is written in a region that is set as the marking page. The marking page serves to indicate a compression point of time of a stack page. The marking page may be at least one of an unmapped stack page, a read-only stack page, and a page that is set to cause the generation of the page fault when being written. As used herein, “at least one of” refers to any combination of one or more items. Thus, for example, the marking page may be any one of an unmapped stack page, read-only stack page, or stack page set to cause the generation of the page fault when being written, any two, or all three.

FIGS. 4A through 4Care conceptual views illustrating management of a marking page with a control unit according to an embodiment of the present invention. InFIG. 4A, since the current stack pointer410is a pointer for the second region430including the non-allocated stack pages, the memory allocation unit340allocates a stack page included in the second region430to an application.

InFIG. 4B, a first region450indicates currently used stack pages and a second region440indicates a marking page. As shown inFIG. 4B, an application has been allocated another stack page. The current stack pointer410is a pointer for the second region440and indicates the marking page. Since the current stack pointer410points to the marking page, the memory management unit310generates a page fault and the fault cause analysis unit321recognizes that the generated page fault is caused by the marking page. The control unit330requests the compression unit350to compress a stack to a predetermined size from the start of a stack page allocated to the application. The operation of the compression unit350will be described later.

InFIG. 4C, a first region460indicates compressed stack pages, a second region470indicates a stack page that is empty due to compression, a third region480indicates currently used stack pages, a fourth region490indicates a non-allocated stack page, and a fifth region440indicates a marking page. As shown inFIG. 4C, the control unit330has requested compression from the compression unit350. Stack pages compressed by the compression unit350are held in the first region460of the memory. The control unit330updates a page table for a stack page that becomes empty due to compression so as to release mapping information, and returns the first region460to the memory allocation unit340. The control unit330is allocated a new page by the memory allocation unit340, sets a new making page, updates the page table, and returns the right for control to the process of the application. The page table is used to control the memory in the operating system and is a data structure used in a virtual memory system of a computer operating system for storing the mapping between a virtual address and a physical address of the memory. The operating system can allocate another process to the second region470by indicating the stack page that becomes empty due to compression, thereby improving efficiency in memory usage.

The control unit330manages decompression of the compressed stack page. When the process of the application accesses the compressed stack pages in the memory, a currently referred memory is not mapped in the page table and thus the memory management unit310generates the page fault. Such an access may be made when the process of the application executes a pop command.

Upon the generation of the page fault, the fault cause analysis unit321recognizes that the fault is caused by the compressed stack pages. The control unit330then requests the compression unit350to decompress the compressed stack pages. At the request of the control unit330, the compression unit350decompresses the compressed stack pages and the control unit330is allocated a physical memory where decompressed stack pages are to be located. The control unit330disposes the allocated new stack pages in logically consecutive places, performs mapping in the page table, and returns the right for control to the process of the application.

The memory allocation unit340exists in a kernel and allocates memory to a particular process of an application or an operating system. According to an embodiment of the present invention, for stack compression, the control unit330requests the compression unit350to compress a particular stack page, updates the page table for a stack page that becomes empty due to compression to release mapping information, and returns the stack page to the memory allocation unit340. For stack decompression, the control unit330requests the memory allocation unit340to allocate physical memory where decompressed stack pages are to be located.

The compression unit350compresses a currently used stack page or decompresses a compressed stack page at the request of the control unit330. The compression unit350may compress the stack page using any compression technique.

FIG. 5is a flowchart of a technique of compressing a stack page according to an embodiment of the present invention. The control unit330sets a marking page in a stack page of a memory in operation S510. If a process of an application uses a greater number of stack pages, the current stack pointer410points to the marking page and thus the memory management unit310generates a page fault in operation S520. Once the fault cause analysis unit321recognizes that the page fault is caused by the marking page, the compression unit350compresses a stack to a predetermined size from the start of a stack page allocated to the application in operation S530.

The control unit330then holds the compressed stack page in a specific region of memory in operation S540. In operation S550, the control unit330updates a page table for a stack page that becomes empty due to compression to release mapping information and returns the empty stack page to the memory allocation unit340. The control unit330is also allocated a new page by the memory allocation unit340and sets a new marking page for the new stack page in operation S560.

FIG. 6is a flowchart of a technique of decompressing a stack page according to an embodiment of the present invention. A process of an application accesses a compressed stack page of a memory in operation S610. Since the referred memory is not mapped to a page table, the memory management unit310generates a page fault in operation S620. Once the fault cause analysis unit321recognizes that the page fault is caused by a compressed empty stack page, the control unit330requests the compression unit350to decompress the compressed stack page. In operation S630, the decompression unit350decompresses the compressed stack page. The control unit330is allocated a memory where decompressed stack pages are to be located in operation S640. The allocated new stack pages are disposed in logically consecutive places and mapping is performed in the page table in operation S650. Thereafter, the right for control is returned to the process of the application.

Memory management techniques according to aspects of the present invention may be recorded in computer-readable storage media including program instructions to implement various operations embodied by a computer. The media may also include, alone or in combination with the program instructions, data files, data structures, and the like. Examples of computer-readable storage media include magnetic media such as hard disks, floppy disks, and magnetic tape; optical media such as CDs and DVDs; magneto-optical media such as optical disks; and hardware devices that are specially configured to store and perform program instructions, such as read-only memory (ROM), random access memory (RAM), flash memory, and the like. The memory management techniques described above may also be embodied by transmission media, for example, a computer data signal embodied in a carrier wave comprising a compression source code segment and an encryption source code segment (such as data transmission through the Internet). The computer readable storage media can also be distributed over network coupled computer systems so that the computer readable code is stored and executed in a distributed fashion. Examples of program instructions include both machine code, such as produced by a compiler, and files containing higher level code that may be executed by the computer using an interpreter. The described hardware devices may be configured to act as one or more software modules in order to perform the operations of the above-described embodiments of the present invention.

As described above, according to aspects of the present invention, the operating system can acquire larger memory by stack page compression. The acquired memory can be used for other purposes, thereby allowing efficient memory usage and thus enabling a greater number of sub systems, middleware, and applications to use a larger memory space.