Meta garbage collection for functional code

• US 8,650,538 B2
• Filed: 05/01/2012
• Issued: 02/11/2014
• Est. Priority Date: 05/01/2012
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Concurix Corporation
• Inventors: Gounares, Alexander G.
• Primary Examiner(s): CHAVIS, JOHN Q
• Application Number:
  US13/461,740
• Publication Number:
  US 20120233592A1
• Time in Patent Office: 651 Days
• Field of Search: 717/114
• US Class Current: 717/114
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 13/00 Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units interface circuits for specific input/output devices G06F3/00 ; multiprogram control therefor G06F9/46; multiprocessor systems G06F15/16
• CPC Class Codes: G06F 13/28 using burst mode transfer, e.g. direct memory access DMA, cycle steal G06F13/32 takes precedence
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: G06F 8/311 Functional or applicative languages; Rewrite languages
• CPC Class Codes: G06F 9/06 using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
• CPC Class Codes: G06F 9/44 Arrangements for executing specific programs

Abstract

An execution environment for functional code may treat application segments as individual programs for memory management. A larger program of application may be segmented into functional blocks that receive an input and return a value, but operate without changing state of other memory objects. The program segments may have memory pages allocated to the segments by the operating system as other full programs, and may deallocate memory pages when the segments finish operating. Functional programming languages and imperative programming languages may define program segments explicitly or implicitly, and the program segments may be identified at compile time or runtime.

Claims

1. A method comprising:

receiving an application to execute;

identifying a plurality of program segments within said application, said program segments having at least one function and receive an input and return an output without changing state to items that are not said input and said output;

executing a first program segment, said first program segment calling a second program segment;

launching said second program segment within an operating system, said operating system having a memory page table having a page identifier, a process identifier, and a page state for each of a plurality of memory pages;

requesting a first memory page from an operating system, said first memory page being allocated to said second program segment;

executing said second program segment using said first memory page and passing said input to said second program segment and receiving said output from said second program segment;

determining that said second program segment has completed execution and ending said second program in said operating system such that said operating system releases said first memory page.

2. The method of claim 1, said plurality of segments being identified when said application is compiled from a source code.

3. The method of claim 2, said source code comprising source code identifiers identifying a beginning and end to said second program segment.

4. The method of claim 3, said source code identifiers comprising commands in said source code.

5. The method of claim 2, said source code being analyzed by said compiler to identify a beginning and an end to said program segment.

6. The method of claim 1, said source code being written in a functional language.

7. The method of claim 1, said source code being written in an imperative language.

8. The method of claim 1 further comprising:

requesting a second memory page from said operating system and allocating said second memory page to said second program segment.

9. The method of claim 1, said plurality of segments being identified when said application is linked after compiling.

10. The method of claim 1, said plurality of segments being identified at runtime.

11. The method of claim 1, said operating system having a range of logical memory addresses larger than a range of physical memory addresses.

12. The method of claim 1, said second program segment being executed within said operating system as a separate program from said first program segment.

13. A system comprising:

at least one processor;

a functional block analyzer that identifies functional blocks of an application program;

an operating system having a memory page table having a page identifier, a process identifier, and a page state for each of a plurality of memory pages, said operating system that further allocates pages to executing code;

an operating environment executing on said at least one processor, said operating environment that;

receives an application to execute;

executes a first program segment, said first program segment calling a first functional block;

launches said first functional block within an operating system, causing a first memory page to be allocated from said operating system;

executes said first functional block using said first memory page and passing said input to said first functional block and receiving said output from said first functional block;

determines that said first functional block has completed execution and ending said first functional block in said operating system such that said operating system releases said first memory page.

14. The system of claim 13, said operating environment that executes said first program segment as a separate program within said operating system from said first functional block.

15. The system of claim 13, said operating environment that links said first program segment to said first functional block at runtime.

16. The system of claim 13, said operating environment that further:

identifies a second functional block as part of said application;

launches said second functional block within said operating system, said operating system allocating a second memory page to said second functional block;

executes said second functional block using said second memory page;

determines that said second functional block has completed execution and ending said second functional block in said operating system such that said operating system releases said second memory page.

17. The system of claim 16, said second functional block being called from said first functional block.

18. The system of claim 13, said functional block analyzer identifying said functional blocks at compile time.

19. The system of claim 13, said functional block analyzer identifying said functional blocks at runtime.

20. The system of claim 13, said operating system having no virtual mapping of memory.

21. A method comprising:

receiving an application to execute;

identifying a plurality of program segments within said application;

executing a first program segment, said first program segment calling a second program segment;

launching said second program segment within an operating system as an independent application, said operating system having a memory page table having a page identifier, a process identifier, and a page state for each of a plurality of memory pages;

requesting a first memory page from an operating system, said first memory page being allocated to said second program segment;

executing said second program segment using said first memory page and passing said input to said second program segment and receiving said output from said second program segment;

determining that said second program segment has completed execution and ending said second program in said operating system such that said operating system releases said first memory page.

22. A system comprising:

an operating system having a memory page table having a page identifier, a process identifier, and a page state for each of a plurality of memory pages, said operating system that further allocates pages to executing code;

an operating environment executing on said at least one processor, said operating environment that;

receives an application to execute;

executes a first program segment, said first program segment calling a first functional block;

launches said first functional block within an operating system, causing a first memory page to be allocated from said operating system;

executes said first functional block using said first memory page and passing said input to said first functional block and receiving said output from said first functional block;

determines that said first functional block has completed execution and ending said first functional block in said operating system such that said operating system releases said first memory page.