Garbage collection based on functional block size

• US 8,995,070 B2
• Filed: 10/08/2013
• Issued: 03/31/2015
• 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): Ben, Loha
• Application Number:
  US14/049,016
• Publication Number:
  US 20140040591A1
• Time in Patent Office: 539 Days
• Field of Search: 359/896, 359/900, 711/100, 711170-172, 717/114, 717120-122, 717/127, 717/128, 717/130, 717/131, 717/158
• US Class Current: 359/896
• 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 receiving an input and returning an output;

determining that a first program segment will consume greater than a predetermined amount of memory and launching said first program segment such that a virtual machine garbage collection mechanism manages memory for said first program segment;

determining that a second program segment will consume less than said predetermined amount of memory and 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 the 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 segment 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 by a compiler from a source code.

3. The method of claim 2, said source code comprising source code identifiers identifying a beginning and an 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 2, said source code being written in a functional language.

7. The method of claim 2, 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;

determines that a first functional block will consume greater than a predetermined amount of memory and launches said first functional block such that a virtual machine garbage collection mechanism manages memory for said first functional block;

determines that a second functional block will consume less than said predetermined amount of memory and launches said second functional block within said operating system, causing a first memory page to be allocated to said second functional block, and releasing said first memory page to be released after determining that said second functional block has completed execution.

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 third functional block as part of said application;

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

executes said third functional block using said second memory page;

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

17. The system of claim 16, said third functional block being called from said second 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.