Method for allocation of address space in a virtual memory system

• US 6,119,214 A
• Filed: 04/25/1994
• Issued: 09/12/2000
• Est. Priority Date: 04/25/1994
• Status: Expired due to Term

• Current Assignee: Apple Inc.
• Original Assignee: Apple Computer Incorporated (Apple Inc.)
• Inventors: Dirks, Patrick W. Penzias
• Primary Examiner(s): LANE, JOHN A
• Application Number:
  US08/231,657
• Time in Patent Office: 2,332 Days
• Field of Search: 395/486, 395/497.03, 395/412, 395/419, 395/497.01, 395/497.02, 395/600
• US Class Current: 711/206
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/10 Address translation

Abstract

A memory manager for a virtual memory system maintains three lists of virtual addresses: those which are free to be mapped to a program, those which are currently mapped but no longer being used, and those which are being removed from a page table, i.e. unmapped. The allocation of free addresses to programs proceeds in parallel with the removal of old entries from the page table, such that new free addresses are guaranteed to be available at all times. Each time that a new address is allocated to a program, a limited number of entries in the page table are examined, to determine whether the addresses associated with those entries are no longer in use, and the entries can be removed from the page table. By the time that all of the available addresses in the free list have been allocated, the entire page table will have been examined and all addresses which are no longer in use will have had their corresponding page table entries removed, so that they are available as free addresses. As a result, a constant supply of free addresses are provided with only a limited amount of processing time at regular intervals during the operation of a computer.

Claims

1. A method for allocating address space in a virtual memory system for a computer, comprising the steps of:

maintaining a list of available addresses that are free to be allocated to a program;

allocating addresses to a program in response to requests for address space;

recording entries in a page table relating to addresses that have been allocated;

upon each allocation of an available address, examining a number of entries in the page table, which number is less than the total number of entries in the table, to determine whether the entries have been identified as no longer active;

removing the entries from the table which have been determined to be no longer active, and maintaining a list of the addresses associated with the entries being removed; and

transferring the list of addresses associated with removed entries to the list of allocatable addresses.

2. The method of claim 1 wherein said transferring step is carried out after all of the entries in the table have been examined.

3. The method of claim 1 wherein said number of entries that are examined upon each allocation equals p/x, where p is the total number of available addresses, and x is the maximum number of addresses that can be active at any given time.

4. The method of claim 3 wherein said examining step is initiated after x addresses have been identified as inactive.

5. The method of claim 1 wherein said number of entries that are examined upon each allocation is variable from one allocation to another.

6. In a computer system of the type in which ranges of logical addresses are assigned to programs and the assigned addresses are mapped to physical memory through entries in a page table, a method for removing entries from the page table when a range of addresses is deleted, comprising the steps of:

a) maintaining a list of addresses that have been deleted;

b) upon the occurrence of a predetermined event, examining a defined number of entries in the page table to determine whether those entries are associated with any of the addresses on said list;

c) removing each examined entry from the page table which is associated with an address on said list;

d) repeating steps b and c upon the occurrence of said event until all of the entries in the page table have been examined; and

e) identifying the addresses in said list as addresses which are available to be assigned to programs.

7. The method of claim 6 wherein said predetermined event is the assignment of an address from those which are identified as being available.

8. The method of claim 6 wherein said defined number is related to the ratio of the number of addresses available to be assigned to programs relative to the number of entries in the page table.

9. The method of claim 6 wherein said defined number is variable.

10. The method of claim 6 wherein the step of maintaining a list of addresses includes the steps of identifying addresses that have been deleted as being in an inactive state, and transferring the inactive addresses to a recycle state.

11. The method of claim 10 wherein said examining step determines whether the examined entries are associated with addresses in the recycle state.

12. The method of claim 11, wherein said examining step also determines whether the examined entries are also associated with addresses in the inactive state.

13. The method of claim 10 wherein the state of a logical address is indicated by an associated identifier stored in a data structure.

14. The method of claim 13 wherein said data structure is a bitmap.

15. The method of claim 6, further including the step of processing each examined entry which is not associated with an address on said list to enhance the efficiency of the page table.

16. The method of claim 15 wherein said processing includes the step of optimizing the entry'"'"'s location within the page table.

17. A system for managing memory in a computer, comprising:

means for allocating ranges of logical addresses to provide access to the memory of the computer;

a page table containing entries which map allocated logical addresses to physical addresses for the memory;

means for indicating that a range of logical addresses has been deallocated;

means responsive to the occurrence of a predetermined event for examining a limited number of the entries in the page table to determine whether they are associated with an address that has been deallocated, and for removing each such entry from the page table; and

means for indicating that addresses whose entries have been removed from the page table are available for further allocation.

18. The memory management system of claim 17, wherein said indicating means comprise a data structure containing a list of logical addresses and an indicator associated with each address which identifies whether the address is available for allocation or has been deallocated.

19. The memory manager of claim 18 wherein said data structure identifies addresses as being in one of three states which respectively indicate whether the address is available for allocation, deallocated, or being processed for further availability, and further including means for changing the state of addresses from being processed to available in response to a predetermined occurrence.

20. The memory manager of claim 19 wherein said predetermined occurrence is the examination of all entries in the page table.

21. The memory manager of claim 20 wherein said processing includes optimization of the location of the examined entry in the page table.

22. The memory manager of claim 17 wherein said predetermined event is the allocation of a range of logical addresses.

23. The memory manager of claim 17 further including means for processing each examined entry in the page table that is not associated with a deallocated address to enhance the efficiency of the page table.