Data control system for a computer's main memory for efficiently realizing virtualization of list structure data living across a real memory space and a virtual memory space

• US 5,694,599 A
• Filed: 05/15/1996
• Issued: 12/02/1997
• Est. Priority Date: 12/14/1988
• Status: Expired due to Fees

• Current Assignee: Sony Corporation (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.)
• Inventors: Maegawa, Hirotoshi, Yasuda, Hiroyuki
• Primary Examiner(s): Robertson, David L.
• Application Number:
  US08/649,775
• Time in Patent Office: 566 Days
• Field of Search: 395/481, 395/492, 395/493, 395/413, 395/622
• US Class Current: 711/6
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 12/10 Address translation
• CPC Class Codes: G06F 13/4022 using switching circuits, e.g. switching matrix, connection or expansion network G06F13/4009 takes precedence
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

In controlling data by a computer, pointers are represented by addresses in the real memory space RM in the real memory space RM and by addresses in the virtual memory space IM and by addresses to said real memory space RM in the virtual memory space, and nodes in the virtual memory space IM are indirectly referenced from the nodes in the real memory space RM so that data of a structure in which the nodes are linked by pointers are represented across the real memory space RM and the virtual memory space IM. The data of the structure in which the nodes are linked by the pointers are shifted between the real memory space RM and the virtual memory space IM with the list structures U₀, U₁, U₂, U₁₀ employing the link information as units. In this manner, the virtual memory technique may be efficiently realized in the case of the list structure data which are basic and indispensable in the field of symbol manipulation such as artificial intelligence, formula manipulation or natural language manipulation.

Claims

1. A data control system for a computer'"'"'s main memory for efficiently realizing virtualization of list structure data lying across a real memory space and a virtual memory space, comprising:

a real memory space having nodes linked by pointers, with the pointers being represented by addresses in the real memory space;

a virtual memory space having nodes linked by pointers, with the pointers being represented by addresses in the virtual memory space and addresses to the real memory space, and wherein the nodes in the virtual memory space are referenced to the nodes in the real memory space by indirect pointers represented by addresses of pointers in the real memory space and addresses of pointers in the virtual memory space;

means for moving the list structure data between the real memory space and the virtual memory space as list structure units; and

monitoring means for monitoring the number of the free nodes in the real memory space and, when the free nodes in the real memory space have become depleted, recovering unnecessary nodes as free nodes by way of a garbage collecting operation.

2. A data control system for a computer'"'"'s main memory according to claim 1, further comprising:

reverting means controlled by the monitoring means for causing the computer to revert to a data processing operation when the number of the free nodes exceeds a predetermined threshold value Sh as a result of the garbage collection;

extracting means controlled by the monitoring means for detecting when the number of the free nodes does not exceed the predetermined threshold value Sh as a result of the garbage collection, extracting pointers to the unnecessary list data in the real memory space and performing a list-out operation in the real memory space for swapping out data of the list structure units from the real memory space to the virtual memory space;

listing out means controlled by the monitoring means for detecting when the number of data of the list structure units listed out in the real memory space is less than a predetermined threshold Ss and listing out pointers to the unnecessary list data in the real memory space and repeatedly listing out the new list data in the real memory space, and

swapping means controlled by the monitoring means for detecting when the number of data of the list structure units listed out in the real memory space reaches the threshold value Ss, swapping the data of the list structure units listed out in the real memory space from the real memory space into the virtual memory space and terminating the listing-out operation.