US4761737A — Method to automatically increase the segment size…

Claim 1

Independent Claim 541 words

In a page segmented virtual memory data processing system comprising, (A) a main memory, (B) a secondary storage device having a plurality of locations each of which stores a block of data comprising at least one virtual page, each of said locations having a different block address, (C) a UNIX type operating system (UOS), (D) an application program for processing UNIX files, each said file being stored on said device at identified block addresses, (E) a memory manager for managing: (1) the allocation of virtual address space in said system, and (2) the transfer of information between said secondary storage device and said main memory, said memory manager including, (3) an external page table (XPT) including a plurality of XPT entries for correlating each said block address to at least one virtual page address, each said entry including a status field for indicating to said system the status of the corresponding virtual system, and (F) means for selectively mapping said files to designated segments of the virtual address space of said virtual memory, a method to automatically manage the size of each said designated segment through allocation of increments of XPT entries in accordance with the addresses in the instructions of said application program that are executed during said processing of a UNIX file, said method comprising the combination of the following sequential steps, (1) establishing for said system with said operating system, an allocatable increment of sequential virtual addresses comprising a fixed plurality of XPT entries, each said increment having a virtual address that defines the Upper Boundary of said increment, (2) allocating, with said operating system, a number of said increments to provide at least one XPT entry for each block on said device that contains information associated with said file being processed resulting in the current size of said segment being defined by said Upper Boundary of said last allocated segment, (3) establishing in each said XPT entry a status field for indicating to said system one of a plurality of processing states of the virtual page corresponding to said entry, (4) mapping said file to correlate the address of said each block to the virtual page address corresponding to the associated said one XPT entry, including the steps of; (a) setting the status field of each said associated XPT entry to a first value, and (b) setting the status fields of said XPT entries between the virtual address representing the End of File (EOF) and the virtual address representing the end of the current segment, to a second value to indicate allocated, unmapped XPT entries, (5) interrupting the current instruction being executed in said application program when said current instruction involves a virtual address contained on an unmapped virtual page to indicate to said system that one of a plurality of predetermined protection exceptions has occurred, (6) automatically allocating with said operating system sufficient said increments when a first of said predetermined exceptions has been indicated, to accommodate said virtual address involved with said current instruction, (7) automatically mapping with said operating system at least one newly allocated disk block to one of said unmapped XPT entries when a second one of said predetermined exceptions has been indicated, and (I) reissuing said current instruction that was interrupted.

Claim 2

Dependent Claim 541 words

In a page segmented virtual memory data processing system comprising, (A) a main memory, (B) a secondary storage device having a plurality of locations each of which stores a block of data comprising at least one virtual page, each of said locations having a different block address, (C) a UNIX type operating system (UOS), (D) an application program for processing UNIX files, each said file being stored on said device at identified block addresses, (E) a memory manager for managing: (1) the allocation of virtual address space in said system, and (2) the transfer of information between said secondary storage device and said main memory, said memory manager including, (3) an external page table (XPT) including a plurality of XPT entries for correlating each said block address to at least one virtual page address, each said entry including a status field for indicating to said system the status of the corresponding virtual system, and (F) means for selectively mapping said files to designated segments of the virtual address space of said virtual memory, a method to automatically manage the size of each said designated segment through allocation of increments of XPT entries in accordance with the addresses in the instructions of said application program that are executed during said processing of a UNIX file, said method comprising the combination of the following sequential steps, (1) establishing for said system with said operating system, an allocatable increment of sequential virtual addresses comprising a fixed plurality of XPT entries, each said increment having a virtual address that defines the Upper Boundary of said increment, (2) allocating, with said operating system, a number of said increments to provide at least one XPT entry for each block on said device that contains information associated with said file being processed resulting in the current size of said segment being defined by said Upper Boundary of said last allocated segment, (3) establishing in each said XPT entry a status field for indicating to said system one of a plurality of processing states of the virtual page corresponding to said entry, (4) mapping said file to correlate the address of said each block to the virtual page address corresponding to the associated said one XPT entry, including the steps of; (a) setting the status field of each said associated XPT entry to a first value, and (b) setting the status fields of said XPT entries between the virtual address representing the End of File (EOF) and the virtual address representing the end of the current segment, to a second value to indicate allocated, unmapped XPT entries, (5) interrupting the current instruction being executed in said application program when said current instruction involves a virtual address contained on an unmapped virtual page to indicate to said system that one of a plurality of predetermined protection exceptions has occurred, (6) automatically allocating with said operating system sufficient said increments when a first of said predetermined exceptions has been indicated, to accommodate said virtual address involved with said current instruction, (7) automatically mapping with said operating system at least one newly allocated disk block to one of said unmapped XPT entries when a second one of said predetermined exceptions has been indicated, and (I) reissuing said current instruction that was interrupted.

Claim 3

Dependent Claim 121 words

The method recited in claim 1 in which said main memory includes a plurality of page frames, each of which stores one virtual page comprising a plurality of sequential byte locations, each of which has a different virtual address, further including the step of, (A) determining with said memory manager that said current instruction is attempting to write to a virtual address location that is beyond said EOF address, and that the XPT entry corresponding to the virtual page containing said virtual address has been allocated but has not been mapped to cause said current instruction to be interrupted with said step of interrupting and said second one of said plurality of predetermined protection exceptions to be indicated to said system.

Claim 4

Dependent Claim 124 words

The method recited in claim 2 in which said memory manager includes a page faulting mechanism including means to convert a virtual address associated with said instruction to the storage location of the corresponding XPT entry only when said virtual address is contained on a virtual page that has been mapped, and in which said step of determining includes the further steps of, (A) invoking said page faulting mechanism in response to not locating said virtual address of said current instruction in said main memory, (B) converting said virtual address to the said location of said corresponding XPT entry, and (C) reading the status field of said corresponding XPT entry to determine that said XPT entry has been allocated but has not been mapped.

Claim 5

Dependent Claim 79 words

The method recited in claim 3 in which said memory manager further includes an Inverted Page Table having a separate entry for each page frame in said main memory for correlating virtual page addresses to page frame addresses in said main memory, including the further step of, (A) allocating a new page frame in main memory, and (B) protecting the corresponding said IPT entry to permit only read operations on said page frame prior to reissuing said interrupted instruction.

Claim 6

Dependent Claim 98 words

The method recited in claim 4 including the further steps of, (A) interrupting said reissued instruction when said memory manager determines that said new virtual page in said new page frame is protected read only, (B) allocating a new block location on said device for storing said new virtual page, (C) mapping the address of said new block to said corresponding unmapped XPT entry, (D) updating said protected IPT and XPT entries to permit said new virtual page to be written into, and (E) reissuing said interrupted instruction a second time to write into said new virtual page.

Claim 7

Dependent Claim 98 words

The method recited in claim 1 in which said memory manager further includes an Inverted Page Table (IPT) having an IPT entry for each said page frame for correlating the address of said page frame to the virtual address of the virtual page stored in said page frame, and said step of indicating includes the further step of, (A) determining with said memory manager that an instruction is attempting to write into a virtual address location that is beyond said Upper Boundary so said first one of said plurality of predetermined protection exceptions is indicated to said system.

Claim 8

Dependent Claim 124 words

The method recited in claim 6 in which said step of determining includes the further steps of, (A) checking said IPT with said memory manager to determine if a page fault has occurred because no page frame in main memory is storing a virtual page containing said protected virtual address, (B) checking said XPT with said memory manager when said step of checking said IPT indicates that a page fault has occurred, to determine if an allocated XPT entry has an associated virtual page that contains said protected virtual address, and (C) indicating to said system that said protected address is beyond said Upper Boundary if said steps of checking do not find an XPT entry having a virtual page containing said protected address,

Claim 9

Dependent Claim 160 words

The method recited in claim 7 in which said memory manager further includes a page fault handling mechanism for resolving page faults that occur in said system, including means to convert a virtual address associated with said instruction being executed to the storage location of the corresponding XPT entry only when said virtual address is contained on a virtual page that has been mapped, and in which said steps of checking include the further steps of, (A) invoking said page faulting mechanism after said first checking step in response to said page fault, (B) converting said virtual address to a table address where the address of a corresponding XPT would be located if an XPT entry had been allocated for that virtual address, and (C) invoking said step of indicating after concluding that an XPT entry has not been allocated for said virtual address that caused said page fault when said virtual address is not located at said table address.

Claim 10

Dependent Claim 53 words

The method recited in claim 8 in which said step of converting includes the further steps of, (A) hashing said virtual address to provide said table address, and (B) storing at said table address the addresses in a chained fashion of all XPT entries whose corresponding virtual pages hash to that table address.

Claim 11

Dependent Claim 69 words

The method recited in claim 9 in which said step of automatically allocating includes the further steps of, (A) increasing the size of said segment to accommodate the faulting virtual address by allocating additional increments of XPT entries sufficient to establish a new Upper Boundary beyond said faulting virtual address in response to an indication by said step of indicating that a first said protection exception has been indicated.

Claim 12

Dependent Claim 104 words

The method recited in claim 10 further including the step of, (A) interrupting the reissued instruction to indicate to said system that a second one of said predetermined protection exceptions has occurred because the value of the status field of the XPT entry associated with said faulting address indicates that said entry has not been mapped, and (B) issuing said instruction a third time after a page frame in main memory has been allocated, a disk block has been allocated, and a new EOF has been established and the appropriate entries in said XPT and IPT have been updated to correct said protection exception.

Annuity Stage	Window Opens	Payment Deadline	Surcharge Period Until	Estimated Fee	Status
3.5 Years (Year 4)	1991-08-02	1992-02-01	1992-08-02	$2000.00	Window Closed / Lapsed
7.5 Years (Year 8)	1995-08-02	1996-02-01	1996-08-02	$3760.00	Window Closed / Lapsed
11.5 Years (Year 12)	1999-08-02	2000-02-01	2000-08-02	$7700.00	Window Closed / Lapsed

Method to automatically increase the segment size of unix files in a page segmented virtual memory data processing system

Abstract

Inventors

Bibliographic Details

Claims Analysis

References Cited (Backward Citations)

USPTO Annuity & Maintenance Windows

Assigned Categories & Tags

Assign Category Tag