Efficient write-watch mechanism useful for garbage...

Details Efficient write-watch mechanism useful for garbage... Efficient write-watch mechanism useful for garbage...

2000-07-31

2004-05-18

Bragdon, Reginald G. (Department: 2188)

Electrical computers and digital processing systems: memory

Storage accessing and control

Control technique

C711S156000, C711S170000, C707S793000

Reexamination Certificate

active

06738875

ABSTRACT:

FIELD OF THE INVENTION
The invention relates generally to computer systems, and more particularly to memory management in computer systems.
BACKGROUND OF THE INVENTION
Application programs often allocate memory that is not used, or is used briefly and then unused thereafter. As memory is a resource that may become scarce, application programs are supposed to deallocate memory that is no longer needed. However, applications often fail to do so, and this memory misuse leads to low memory conditions and otherwise degrades system performance. Applications also tend to access memory after they manually free it, which also causes major problems.
The concept of “garbage collection” has been developed to automatically manage application memory by reclaiming memory space allocated to applications that is not being used. Garbage collection operates on behalf of the application, without the application's assistance, to look for objects that are unused. A garbage collector operates, by scanning for cross-generation pointers in memory, which indicate an object still in use. One type of garbage collection is sequential in nature, wherein a garbage collection mechanism runs whenever memory is needed. While the collection mechanism is run to analyze the memory (e.g., a set of allocated objects) that is not being used, the application is temporarily halted so that it cannot be modifying memory. A significant problem with sequential garbage collection is that the application often experiences inconvenient and/or undesirable pauses during the collection operation.
Another type of garbage collection is concurrent in nature, wherein the garbage collectors run at the same time as the application and collect only a portion of unused memory at a time. Only when the collector has done the bulk of its work is the application temporarily halted to prevent it from writing to memory just as that memory is being freed, whereby the application is not significantly paused. To look for objects that are unused, the garbage collector enumerates locations that have been written into so it can scan for the cross-generation pointers, i.e., rather than scan large amounts of system memory, only changed memory is examined. However, this requires a more complex collector to concurrently track memory that is being actively used by an application, and also requires multiple passes to locate any memory earlier determined to be unused but that an application has since used while the collector was performing other work.
To track which memory has changed with contemporary operating systems and microprocessors, write-protect and write-watch are techniques that have been attempted. Write-protect generally operates by protecting sections of memory (e.g., pages) allocated to an application. Then, whenever the application writes to a protected page, a page fault is triggered. By the page fault, the collector thus knows that this page was written to, and can record the page as changed, e.g., in some data structure used for tracking changed pages. The collector then unprotects the page to allow the change and allow the application to use it. Some time later, the collector will free unused memory and reset the tracking process. Conventional write-watch is somewhat similar to write-protect, except that write-watch tracks memory usage without protecting the page and generating the page fault exception.
While write-protect and write-watch thus enable concurrent garbage collection mechanisms, such mechanisms have heretofore been highly inefficient. Indeed, write-protect is significantly slower than write-watch. At the same time, past write-watch techniques have degraded system performance so significantly that that a number of write-watch garbage collection efforts have been abandoned.
SUMMARY OF THE INVENTIONS
Briefly, the present invention provides a method and system that enables an efficient write-watch mechanism, while adding as little as one bit per virtual page address being watched, and that operates without substantially degrading performance even on large address ranges. To this end, a bitmap is associated with the Virtual Address Descriptor (VAD) for a process, one bit for each virtual page address allocated to a process with write-watch enabled. As part of the write-watch mechanism if a virtual address is trimmed to disk and that virtual address page is marked as modified, then the corresponding bit in the VAD is set for that virtual address page. Only when a modified page is trimmed is the bitmap accessed during normal system operation, providing extremely fast write watching.
The memory manager may receive an API call (e g., from a garbage collection mechanism) seeking to know which virtual addresses in a process have been modified since last checked, e.g., since the last time the garbage collection mechanism asked. To determine this, the memory manager walks the bitmap in the relevant VAD for the specified virtual address range for the requested process. If a bit is set, then the page corresponding to that bit is known to have been modified since last asked. The bit is cleared in the VAD bitmap (if specified by the API), and a result returned for that page, (e.g., the page number is added to an array that is returned).
If the bit is not set, then there is still a chance that the page was modified, just not trimmed. To determine if the page was modified, the page table entry (PTE) is checked for that page, and if the PTE indicates the page was modified, a corresponding bit is set in the PFN database, the modified bit in the PTE is cleared, (if reset is requested by the API, any other processors are interrupted and the result may be returned for that virtual page address. Otherwise that page is known to be unmodified since the last call.
One enhancement to the present invention looks at the page directory tables corresponding to the write-watched pages for that process for which status has been requested, each of which indicates whether a group of (e.g., 1024) pages have been trimmed. If the pages have been trimmed, then any zero bits in the VAD corresponding to this group are known to be unmodified, since any moidfied, trimmed page would have had its bit set in the VAD when trimmed. The portion of the VAD bitmap corresponding to the trimmed page directory thus reflects the modified state of pages in this page directory, whereby the PTE need not be checked for that portion. An appropriate result is returned to the caller, and the bitmap portion cleared (if requested) so that it will reflect whether it has been modified since the time last asked.


REFERENCES:
patent: 4989134 (1991-01-01), Shaw
patent: 5237673 (1993-08-01), Orbits et al.
patent: 5842016 (1998-11-01), Toutonghi et al.
patent: 5845298 (1998-12-01), O'Connor et al.
patent: 5848423 (1998-12-01), Ebrahim et al.
patent: 5857210 (1999-01-01), Tremblay et al.
patent: 5873104 (1999-02-01), Tremblay et al.
patent: 5873105 (1999-02-01), Tremblay et al.
patent: 5900001 (1999-05-01), Wolczko et al.
patent: 5903899 (1999-05-01), Steele, Jr.
patent: 5903900 (1999-05-01), Knippel et al.
patent: 5909579 (1999-06-01), Agesen et al.
patent: 5911144 (1999-06-01), Schwartz et al.
patent: 5915255 (1999-06-01), Schwartz et al.
patent: 5920876 (1999-07-01), Ungar et al.
patent: 5930807 (1999-07-01), Ebrahim et al.
patent: 5953736 (1999-09-01), O'Connor et al.
patent: 6249793 (2001-06-01), Printezis et al.
Anonymous, “A Comparison of Inferno and Java,”Computing Sciences Research of Bell Labs,www.lucent-inferno.com/Page...tion/White_Papers/infernojava.html printed Jul. 12, 1999.
Anonymous, “Blue —What is it,” www.sd.monash.edu.au/blue/what-is-it.html printed Jul. 9, 1999.
Anonymous, “Cmm and Java Compared: A Comparison of Modern Languages for the Internet and Worldwide Web,” (1997), nombas.com/us/otherdoc/javavcmm.html printed Jul. 12, 1999.
Anonymous, “Elements of Comparison Java/Hotjava vs. Cam1/MMM,” pauillac.inria.fr/~rouaix/mmm/currentjavacomp.html printed May 28, 1999.
Anonymous, “Garbage Collection for ISC Eiffel: An Overview,”ISE Technical Report,TR-EI-56/GC,

Affiliated with

Also associated with

Rating

Efficient write-watch mechanism useful for garbage... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Efficient write-watch mechanism useful for garbage..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient write-watch mechanism useful for garbage... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3230562