Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
1998-09-17
2001-05-15
Thai, Tuan V. (Department: 2186)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S206000, C711S207000, C711S111000
Reexamination Certificate
active
06233666
ABSTRACT:
TECHNICAL FIELD
The present invention is directed to page memory used to implement virtual memory in which the computer's disk drive storage device functions as an extension of the computer system's main memory (RAM). More particularly, it is concerned with the deferred allocation of space in the disk drive until pages in RAM are ready to be transferred to the disk drive.
BACKGROUND OF THE INVENTION
As computer operations increase in complexity and with the rapidly increasing demands on computer systems for graphics and image processing, there is an increasing demand for computer memory. At present, although main computer memory hardware supports in the order of hundreds of Mbytes, most present computer architectures are well beyond supporting 4 Gbytes of real storage. Through virtual memory the main memory (RAM) of the computer is expanded via its secondary storage, e.g. disk drive, so as to transparently appear to have several Gbytes of available memory. In such virtual memory systems the location of data is specified on a page of a memory page table rather than by the physical location of the data. This makes it possible to store memory pages wherever memory space on the disk drive becomes available. Access to memory is performed using these segments or pages which are 4 Kbytes in size. Each page is assigned a number or an address. In present virtual memory systems, it is possible to load more programs into the memory system than actually fit. At one time, only a portion of a given program may actually be used; the rest of it is dormant. Such dormant program routines do not have to be in the system's real memory until actually used. Virtual memory systems write out the pages of the dormant routines to the disk drive where the pages may be stored until needed. This writing out is referred to as paging out. Then as long as a page is not modified, it need be paged out only once irrespective of the number of times it is paged back into real memory. Of course, if the page is modified, it must again be paged out to disk drive storage. On the other hand, when the operating system detects that a portion of a program not currently in real memory is needed, known as a page fault, the result is that the pages needed will be paged into real memory. The page being paged into memory is accessed by means of the virtual address of its space on the disk drive. The operating system must translate this virtual address into the address where the page is loaded. This is performed by means of page tables. Since these page tables increase in size with the increase in size of virtual memory, page tables have become very large.
Because the management of virtual memory operations has increased its demand upon operating system resources, i.e. operating system overhead, there has been a trend in many virtual memory management systems to defer the allocation of disk drive storage space, i.e. a paging disk page block for a virtual page until that particular page is actually removed or paged out from the real memory of the computer system into the disk drive. This amounts to a significant savings in overhead since the tracking path lengths in databases are unnecessary for pages not paged out of memory.
However, such deferred allocation has encountered performance penalties when paging out of memory is finally necessary. At this point not only must a paging space disk block in the secondary storage means, e.g. disk drive must be allocated, but the address of this disk block must be saved in a page table such as an External Page Table (XTP) so that the page may be paged back into the real or basic computer memory when needed, i.e. responsive to a page fault. However, as set forth above, page tables have so greatly increased in size, and often the addresses for particular virtual pages contain references to more than one table page. Page tables generally are indirectly referenced as pageable structures and, as such, may require more than one page to find the proper places in the table to store the newly allocated disk block addresses. This requires many table pages to be paged into and out of the real or basic computer memory in order that the operating system kernel (base operating system), which controls the pageins and pageouts of memory pages between the memory and disk drive, properly record the addresses of virtual pages in the page tables.
Existing systems using deferred allocation of disk drive space, all also use external processes separate and independent of the base operating system or kernel to drive the pageins of table pages to the computer memory in the event of table page faults, i.e. a table page needed for the recording of the virtual address of an allocated real memory page is not in the computer memory (RAM). In such instances the separate table process is called (awakened); it points to a table page which paged into memory. At this point, based upon operating system efficiency protocols, the separate table process is interrupted (put to sleep) while the table page is processed. Such processing may require the input of up to several referenced subsequent table pages into memory requiring several corresponding awakenings and interrupts for the table process before the number of table pages sufficient to record the address of an allocated page is completed. This implementation of deferred allocation has been found to require the handling of queues of pageouts for the address table pages required, as well as significant context management for interrupts as the separate or external process for table page driving is put to sleep and subsequently awakened. This complexity in the handling of the address table pages makes this system substantially nonscalable, i.e. the computer system may not be readily expanded to add other components, particularly additional processors in multiprocessing computer environments.
SUMMARY OF THE INVENTION
The present invention overcomes these prior art problems in deferred allocation of space in disk drives until memory pages are to be out paged to the disk drive. It does so through a system which eliminates the use of a separate or external process for driving the pageins of table pages to real memory during the recording of the addresses of allocated spaces. Thus, the need for sequences of table page process awakenings and process interrupts is eliminated, as well as the attendant management of table pageout queues.
Briefly stated, the present invention is directed to a data processor controlled system for providing virtual memory comprising a data processor memory storing a plurality of real memory pages, secondary storage means and means for moving said real memory pages into and out of said secondary storage means, wherein each real memory page is respectively stored as a virtual memory page. The invention provides a system and method for deferred allocation of space for a real memory pagein the secondary storage means for recording the address of the space in a table having a plurality of table pages for recording the secondary storage addresses of each of said virtual memory pages. The system includes means responsive to the moving of a memory page into the secondary storage for determining whether the initial table page for recording said address of moved pages is present in said data processor memory. It further has means responsive to said determining means for moving, without any separate or external process interrupts, the initial table page into said data processor memory if said initial table page is not present, and means for recording said address of said moved page into said initial table page.
Since the address table is likely to be indirectly referenced and, thus, may have to access more than that one page to complete the address recording, the system may also include means for determining from the initial table page whether a subsequent table page is required for recording said address of said moved page, and means, responsive to a determination that a subsequent table page is required, for providing, without any interrupts for
Mathews Thomas Stanley
Nallapati Kumar V.
Sheffield David William
Emile Volel
International Business Machines - Corporation
Kraft J. B.
Thai Tuan V.
LandOfFree
Deferred disk drive space allocation for virtual memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Deferred disk drive space allocation for virtual memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Deferred disk drive space allocation for virtual memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2559218