US 4,758,951 AGrant
Method for Translating Virtual Addresses Into Real Addresses
Issue Date:1988-07-19
•11 Claims
•11 Drawing Sheets
Abstract
A disk operating system converts virtual storage space locations of one or more processes into real disk or core memory storage space locations of a computer system. Real and virtual storage space are divided into equal sized pages. Real storage pages are grouped into variable sized segments and a separate segment page table is provided for each real storage segment, each entry therein characterizing the nature and location of a page. A separate process map list is provided for each process, each entry therein mapping an area of contiguous virtual storage pages onto a segment page table. Before a process executes a program, the operating system uses the associated process map list, along with the segment page tables mapped by the list, to create a process page table which directly maps virtual storage pages of a process into real storage pages. The operating system then uses the process page table to translate virtual storage addresses into real storage addresses whenever an associated process attempts to access a virtual storage location.
Metadata
Assignee
- Tektronix, Inc.
Inventor
- Edward W. Sznyter, III
Application Information
Application Number:US 7215304
Filing Date:1985-04-09
Priority Date:1985-04-09
Art Unit:231
Classifications
IPC:
G06F 1208
Field of Search:
364200
Patent Drawings (11 sheets)
Description
Background of the Invention
The present invention relates in general to disk operating systems and in particular to a method for mapping the virtual address space of a process into real core and disk storage space.
In multi-programming computer operating systems a number of independent processes share the use of the central processing hardware of a computer system according to a time sharing allocation method. While the program associated with the process may appear to a user to run continuously, the process normally has continuous use of the system processing hardware only for a short period, long enough to execute a portion of the program, and then relinquishes use of the processor to another process. Thus, when several processes are active, each may gain and lose control of the central processor many times before it can completely run a program. In disk operating systems like Unix, each process writes and reads data to and from its own "virtual" memory address space and the operating system actually stores the data for each process either in core memory at real addresses unrelated to the virtual addresses or on a disk. When an active process attempts to access a virtual address for a read or write operation, the operating system translates the virtual address to a real core memory address. If the data is on disk, the operating system must read it into core before the process can access it. Virtual addresses are mapped into real storage locations on a block-by-block basis with a block of contiguous virtual addresses corresponding to a block of contiguous real addresses. Data is also moved or "swapped" between core memory and disk files on a block-by-block basis and the virtual address space of the process is made up of a set of contiguous blocks of virtual addresses. Some of the associated blocks of real storage may reside in core and others may currently reside on disk, but in either place the blocks need not be contiguous nor stored in any particular order.
Since the virtual storage space of a process need not be mapped into a contiguous core area and may at any moment be mapped into secondary disk storage, real storage may be allocated among several processes in an efficient manner and the combined virtual address space of any one or several active processes may exceed the core address space of the system. In the prior art, block mapping has typically been accomplished using paging, segmentation and combination paging/segmentation methods. In a pure paging system, real and virtual storage blocks comprise pages of contiguous address locations of a fixed size with pages of virtual storage being mapped onto corresponding size pages of real storage. The use of fixed size pages minimizes the operating system overhead because it can maintain simple lists of available blocks of memory and disk addresses and need not compare the size of each block being swapped in or out of memory with the size of the available blocks for receiving it. The virtual address space of a process is mapped into the real storage space by a page list. The pure paging method is somewhat wasteful, however, in that not every page may be filled with data and therefore not every block of core memory or disk storage space will be fully utilized. This problems can be ameliorated if the pages are small, but making the pages too small requires the use of lengthy page lists which increases the load on core storage.
In a segmentation system, each block is a "segment" of continuous address space of variable size, sufficient to store a specified section of data associated with the process. The virtual address space of the process is mapped into the real storage space by a segment map table comprising a list of pointers to the real storage location of the first address of each segment. This method makes better use of each block of memory then the pure paging method but requires more operating system overhead to match segment sizes when transferring segments between core and disk storage.
In a combined segmentation/paging system, real storage is divided into equal sized pages while virtual storage is divided into variable sized segments. Each segment covers a virtual address space which can be mapped onto a whole number of real storage pages. The operating system locates a real address location corresponding to a virtual address by first utilizing a process map list to locate a segment page table and then using the page list to locate the real storage location of the page within the segment. Two independent processes can share the same segment if their process map lists point to the same page table which can save core or disk space when two processes are, for instance, running the same program text. This method has a disadvantage over pure paging and pure segmentation methods in requiring the operating system to perform two table lookups to translate a virtual address. However, a combined segmentation/paging method has an advantage over the other methods in that one process may copy large sections of data used by another process simply by establishing a process map list entry which points to an existing segment page table. The sharing of memory pages by more than one process is limited to cases where the data is "read only" in the sense that no process can change the data. Typically this may be the text portion rather than the data or stacked portions of a program. In the prior art, separate processes can share only entire segments; a process cannot map only into selected pages of a segment.
In systems such as Unix, a new process is initiated by a "fork" operation wherein a process is split into two independent concurrent processes called the "parent" and the "child" process. The parent and child do not share primary storage but do share pen disk files. Copies of all writable data segments must be made for the child at the time of the fork.
It would be advantageous to have a virtual memory system which employs both segmentation and paging but which requires only a single table lookup to translate virtual addresses into the storage locations. Such a system would also advantageously permit sharing of both read only and writable data segments by more than one process. This would eliminate the need for copying writable data segments for a child until such time as the child or the parent actually intends to access the data segments. The need for core space and therefore the need for disk operations to free core space would be reduced. Further savings in core and disk storage space could result if a process virtual space could map onto only a portion of a segment used by another.
Summary of the Invention
According to a first aspect of the present invention, a multiple programming disk operating system organizes the virtual storage space of each process into sets of virtually contiguous pages, each containing a fixed number of contiguous virtual addresses. At the same time, the core and disk storage space accessed by the system is also divided into pages having the same fixed number of real storage locations as the virtual pages. These real storage pages are organized into real storage segments characterized by a set of segment page tables. Each page table entry maps the location of a real store page while a separate map list, associated with each process, maps blocks of virtual storage pages onto all or any contiguous portion of a segment page table. Two or more processes may map onto selected portions of the same segment page table, thereby permitting processes to share portions of core space and disk files mapped by each segment page table.
According to a second aspect of the invention, a separate process page table is created for each process, using the data stored in the associated process map list and the segment page tables. The process page tables directly map pages of the process virtual address space onto real core or disk storage pages. The process map list associated with each process, along with the individual segment page tables, are swapped in and out of core memory as needed. The process page tables, however, are created in core as needed and destroyed when not needed and are not swapped into disk storage. Thus, while the present invention uses a combined segmentation/paging system to set up virtual to real space mapping, it uses a pure paging system to perform the actual virtual to real address translation which allows processes to share the same segment while permitting virtual to real address translation with a single table lookup.
According to a third aspect of the present invention, in a fork operation, the operating system creates a new process map list for the child, mapping the read only portions of virtual space of the child onto the existing page tables of the parent. The operating system also creates a duplicate, "privated" segment page table for the child for any writable segments pointing to the parent's segment page tables. Flags associated with the parent's page tables are set to indicate that a privated mapping has been made. When the parent or child process attempts to write to the existing pages, a new copy is brought into core for the child and the child's segment page table entries and redirected to that page. In this way a fork operation occurs without any disk access operation and no subsequent disk access is required until a shared page is to be changed. In the prior art pages were copies and new memory allocated for the child process.
It is accordingly an object of the present invention to write a new and improved disk operating system wherein the processes may share selected portions of the same core and disk storage.
It is another object of the invention to provide a new and improved virtual memory system wherein virtual to real address translation can be accomplished with a single table lookup operation.
It is a further aspect of the present invention to provide a new and improved virtual memory system wherein separate processes may share writable segments as well as read only segments.
It is a still further aspect of the present invention to provide a virtual memory system wherein a fork operation is accomplished with a minimum of copying.
The subject matter of the present invention is particularly pointed out and distinctly claimed in the concluding portion of this specification. However, both the organization and method of operation together with further advantages and objects thereof may be understood by reference to the following description taken in conjunction with the accompanying drawings wherein like reference characters refer to like elements.
Drawings
FIG. 1 is a diagram illustrating several tables and files used according to the virtual memory system of the present invention for memory mapping two example processes;
FIG. 2A is a diagram of tables and files associated with a single parent process prior to a fork operation;
FIG. 2B is a diagram of tables and files used to memory map the parent process of FIG. 2A and a child process following a fork operation;
FIG. 2C is a diagram of the virtual space arrangement of a typical Unix program file; and
FIGS. 3 through 29 are flow charts of procedures implementing the present invention as an improvement to a Unix operating system.
Detailed Description
Referring to FIG. 1, there are illustrated various tables, lists and files used according to a virtual memory system of the present invention to memory map several processes running on a multi-process disk operating system. The virtual memory system is adapted to permit each process on a computer system to access its own virtual address space. In the preferred embodiment the virtual memory system is an improvement to the Berkley Standard B.S.D 4.2 Unix disk operating system and is intended to run on a Tektronix 6000 computer. However the present invention, in its broader aspects, is not limited to use in conjunction with Unix operating systems or Vax model computers.
Existing Unix systems maintain a page list for each process wherein each entry on a page list may map a block of contiguous virtual address space of the associated process onto a similar sized block of real address space in core memory, or onto a similar sized block of space on a disk. Two processes may map onto the same real storage space but may only do so in order to share the same read only text.
In the present invention, as in prior art Unix operating systems, virtual and real address space are paginated with equal sized pages of contiguous address space. Virtual address space is mapped into core and disk space using a process page table for each process. Two such process pabe tables 10 are shown in FIG. 1. However in the present invention, core and disk storage pages are grouped into variable sized storage segments. Segment page tables 12 are provided to keep track of the real core or disk storage location of each page. In FIG. 1 three segment page tables, designated tables A, B and C are shown, although in practice a much larger number of segment tables may exist. The segment A page table has six page table entries, the segment B page table has five entries, and the segment C table has two page table entries.
There are five types of segment page table entries. A "PG TEXT" entry, such as entry 1 of the semgnet A page table, points to the storage location A of a page in a file area 14 of a disk 16. A "PG FCORE" page table entry, such as entry 2 of segment A page table 12 points to the first address B of a page in a non-physical (i.e., non-memory mapped I/O) area 17 of core memory 18. A "PG FSWAP" entry, such as entry 3 of segment A page table 12, points to a storage location C of a page in a swap area 20 of disk 16. The swap area 20 is used to temporarily hold pages of data transferred out of core memory 18. A "PG FZERO" page table entry, such as entries 4 and 5 of the segment A page table, points nowhere (as indicated by dashes) and signifies that the page does not exist in core or on disk but that it may be created in core and filled with zeros when needed. A "PG FSEG" entry such as entry 3 of the segment B page table points to another page table entry. PG FSEG type entries are discussed in more detail hereinbelow.
Most Unix operating systems, including the preferred embodiment of the present invention, move pages in and out of core memory or disk in "clusters" of two or more contiguous pages. Thus while for simplicity in FIG. 1, contiguous pages in the segment and process page tables are shown as being of randomly different types, in practice the tables will comprise clusters of two or more contiguous page table entries of the same type.
A segment file 26 associated with each segment page table is maintained in core memory. The segment file stores useful data concerning the segment including the location of the associated segment page table 12 on the disk 14 and the starting core memory address of the segment page table, if the page table is currently in core. For instance, a segment A of FIG. 1 points to the first address P of the segment A page table, while the segment B and C files point to the first address Q and R of the segment B and C page tables.
A process map list 22 is provided for each process. In the example of FIG. 1 two processes, 1 and 2, are active in the system. Each entry on a process map list 22 maps a set of contiguous virtual address space pages of the process onto one or more contiguous entries on a segment page table 12. Each entry of a process map list 22 points to the starting address of a segment file 26 which in turn points to the disk or core location of a segment page table 12. Each mapping entry of map list 22 also contains the number of the first virtual space page mapped by the entry, the number of the first segment page table entry, and the total number of segment page table entries included in the mapping. For instance, mapping entry 1 of the map list 22 for process 1 maps a segment of the process 1 virtual space onto all of the page table entries of the segment A page table 12 entries. The mapping entry (L, 1, 1, 6) points to the first address L of the segment A file 26 which in turn points to the first address P of the segment A page table 12. According to the data included in the mapping entry, the mapping starts at virtual space page 1, indicated by the first numeral 1 following the L in the map list entry. The first segment A page table entry included in the mapping is entry 1 as indicated by the second numeral 1 following the L in the map list entry. A total of 6 page table entries are also included in the mapping as indicated by the numeral 6 in the map list entry. Thus the first entry in the process 1 map list maps six contiguous pages of virtual memory of process 1.
Process 1 map list 22 mapping entry 2 maps another segment of the process 1 virtual space, virtual space pages 7 and 8, onto entries 2 and 3 of the segment B page table list 12 by pointing to the first address of the segment B file 26 and storing a "2" for the first and displacement and another "2" for the total number of entries included. The segment B file 26 further points to the first address Q of the segment B page list, if the segment B page list is in core. Otherwise it points to the location Q of the page list on disk. Thus, unlike combined segmentation and paging systems of the prior art, an entry of a map list 22 may map a virtual segment onto only a portion of a segment page table 12 rather than onto the entire page table, thereby increasing the opportunity for two or more processes to share the same real storage space.
Two process map list 22 entries may map onto same segment page table 12. For example mapping entry 1 of the process 2 map list 22 maps a segment of the process 2 virtual space onto all of the segment B page tablet list 12, while entry 2 of the process 1 map lists 22 maps a portion of its virtual space onto entries 2 and 3 of the segment B page table list 12. Thus the virtual spaces of processes 1 and 2 both share the pages of core or disk storage represented by entries 2 and 3 of the segment B page list.
When a process is running a program requiring direct access to the physical memory of the computer system, as for instance when the program seeks to access a memory mapped I/O port, the addresses of the corresponding virtual and core memory pages must be identical. In this case the map list entry points not to a segment page table 12 but points nowhere as indicated by a the dash symbol in the entry. No segment page table is necessary to keep track of a page of physical memory since the location of that page in core never changes. Mapping entry 3 of the process 1 map list and entry 3 of the process 2 map list are examples of physical memory mappings.
The starting address of each process map list 22 is stored in a process table 24, maintained in core by the operating system. In the example of FIG. 1, the process table 24 has two entries because there are two active processes in the system. Process table entry 1 points to the location X in core or disk of the first mapping in the process 1 map list 22, while process table entry 2 points to the location Y of the first entry of the process 2 map list. While the process map lists 22, process table 24, and segment files 26 are always maintained in core storage, segment lists 12 may be swapped back and forth between core memory 18 and disk 16 on an as needed basis.
When a process is ready to run a portion of a program, the operating system locates the associated process map list 22 using the process table 24. It then swaps into core any segment page tables 12 referenced by the map list which are not already in core. The page table 10 for the process is then constructed from the data contained in the map list 22, the segment file 26 and the appropriate segment tables 12. The first page table entry in the page list 10 for process 1 points to page A in file area 14 of disk 16 because the first entry on the process 1 map list maps all of the entries in the segment A page table and the first entry in the segment A page table points to the page A. Successive page table entries of process 1 page table 10 are constructed following a similar procedure. The entries in the process page table 10 appear in the same order as the pages appear in the virtual space of the process. If the process map list 22 entry does not point to a segment page table 12, then the mapping is directed to a page in physical memory and a "PG PHYS" entry is made in the corresponding process page table 10 indicating that the virtual and real address for the page are identical. For instance, entry 3 of the process 1 map list resulted in entry 9 of the process 1 page list pointing to a page J of the physical area 24 of core memory 18.
Also, if a virtual space page is not mapped, a "PG FNONE" entry is made in the process page table 10. For instance, process map list 1, entry 3 maps one page of virtual space, page 9. The next map list entry, entry 4, starts with virtual space page 11. Therefore virtual space page 10 is not mapped and entry 10 of the process page table 10 is PG FNONE.
When a process attempts to access a memory location in virtual space, the high order bits of the virtual address indicate the page number while the lower order bits indicate the displacement of the accessed address from the lowest address in the page. The system uses the process page table 10 to convert the page number into the real storage location of the page. If the page is in core, the process page table 10 entry (PG FCORE) contains the higher order bits of the starting real address of the page. Since the real and virtual memory pages have the same number of contiguous address locations, the operating system can concentrate the real address high order bits and the virtual address low order bits to generate the real address corresponding to the virtual address.
When a process attempts to access a virtual address of a page stored in the swap area 20 or the file area 14 of disk 16, a corresponding PG FSWAP or PG FTEXT page table entry of the process page list, such as entries 3 and 7 of the process 1 page table 10, contains the location on the disk of the page. The operating system then brings the page into core, modifies the appropriate process and segment page table 12 entries to be PG FCORE, and then translates the virtual address to a real core memory address. If a process tries to access a virtual address in a page which is PG FZERO, the operating system locates an unused page in core memory, sets the data stored at every address t zero, and changes the corresponding process and segment page table entries to PG FCORE.
When a process accesses a virtual address which is also a physical address, such as a memory mapped I/O port, the process page table entry contains the same address since the virtual address and the physical address for physical memory must be the same.
In UNIX, a new process is initiated by a "fork" procedure wherein an existing process is split into two independent concurrent processes, called a "parent" and a "child" process. In the prior art, the parent and child processes do not share primary storage but do share open disk files. However, copies of all writable data segments must be made for the child at the time of the fork to prevent one process from modifying a data segment used by another. This copying may require a disk operation to read the file from disk to core and ties up core space.
According to the present invention, however, parent and child initially share all data segments and no segments are copied until one process attempts to modify a shared writable segment. It is initially necessary for the operating system to create only a new process map list 22 for the child and new segment page tables 12 for any writable segments. The system does not copy any shared pages until the parent or child seeks to modify them. If the pages represent "read-only" data which cannot be modified by parent or child, then no copy is ever made for the child and the parent and child mapping are included in a "shared list" of all mappings sharing the read only segment. If the pages are writable, the parent and child mappings are placed on a "private list" of all mappings sharing the same writable segment. A new copy of the pages in the privated segment is made for the child when parent or child requires access to the segment.
Each mapping entry of the process map list 22 contains a number of variables and flags including:
m procp: A pointer to the process list 24 entry of the process using this mapping;
m pstart: The process page table 10 entry number where the mapped area begins;
m sstart: the segment page table 12 entry number where the mapped area begins;
m len: the number of segment page table 12 entries in the mapped area;
m prot: a variable indicating whether a process can read or write to the mapped area and who may map it;
m flags: a flag bit set if a process page table 10 exists in core for this mapped area;
m next: a pointer (C) to next entry in this map list (this allows the map list 22 to be a linked list so that entries may be stored in any order);
m segp: a pointer to the first address of a segment file 26 (null if this is a mapping of physical memory);
m nextshared: a pointer to the next process map list entry in a linked list of shared mappings;
m nextprivate: a pointer to the next process map list entry in a linked list of privated mappings.
Each segment file also contains a number of variables and flags including:
seg iptr: a pointer to a disk inode corresponding to the file represented by the segment page list if the segment maps a disk file 20:
seg addr: the swap area disk page where the segment page table 12 begins;
seg shared: a pointer to the first mapping in a "shared" list; (this pointer along with the mnextshared pointer of the map list entries create the linked "shared list" of all mappings sharing the segment);
seg private: a pointer to the first mapping in a "privated" list (this pointer along with the mnext-privated pointers of the map list entries create the linked "privated list" of all privated mappings of the segment);
seg flags: flag bits (see below);
seg bp: a pointer to the first address of the segment page table 12 if it is in core;
seg segp: a pointer to a parent segment file 26 if this segment was made by a private mapping; and
seg sstart; the page number in the parent segment where the private mapping begins.
Each bit in the segflags variable comprises a flag as follows:
SEG LOCKED: true (logical 1) if a process has been granted sole use of the segment;
SEG WANTED: true if another process requires use of a locked segment;
SEG DIRTY: true if the segment page table 12 has been modified;
Each entry in a segment page table 12 also contains variables and flags including:
pg v: a flag which is true if the page is in core and valid (i.e. is a PFFCORE type page which has not been privated);
pg prot a variable which indicates whether the operating system or a user process or both can read or write to the page;
pg r: a flag which is true if the page was read by a process or the operating system;
pg m: a flag which is true if the page was modified by the process or the operating system;
pg privated: a flag which is true if another process wants a copy of the page before it is modified;
pg fileno: a variable which indicates the page type (PG FZERO, PG FTEXT, PG FSWAP, PG FCORE, PG FSEG, or PG FPHYS);
pg blockno: a variable indicating the location of the page in core or disk.
Referring to FIG. 2A, a parent process map list 22 entry 5 maps a portion of the virtual space of the parent process through a segment A file 26 into segment A page table 12 entries 2-5 of a segment page table A prior to a fork operation. The segment A page table 12 entries are all of the PG FCORE type in this example but could be of some other type. Process map list 22 entry 6 maps another portion of the process virtual space through a segment B file into page table entries 1-3 of a segment B page table 12. For simplicity, other map list 22 entries of the parent process are not shown.
Variables contained in each process map list 22 entry relevant during a fork operation are shown in FIG. 2A. The m segp variable of the parent process map entry 5 points to address A, the beginning address of the segment A file 26. The m sstart variable is set to 2 while the m len variable is set to 3, indicating that the mapping includes segment A page table 12 entries 2 through 4. The m nextprivate and m nextshared variables are set to 0, indicating that no other map list entries are linked in a shared or privated list for segment A. In map list entry 6 the m segp variable points to address B, the beginning address of the segment B file 26. The m sstart variable is set to 1 while the m len variable is set to 3, indicating that the mapping includes segment B page table 12 entries 1 through 3. The m nextprivate and mnextshared variables are also set to 0, indicating that no other map list entries are linked to a shared or privated list.
In the segment A file, the seg bp variable points to the first address C of the segment A map list. The seg locked flag is false (logical 0), indicating that any process may access the segment, and the seg private flag is also false, indicating that no process has a privated mapping. The seg shared variable is W, the starting address of the parent process map list entry 5, indicating that entry 5 is the first mapping of a shared list for segment A.
In the segment B file, the seg Bp variable points to the starting address D of the segment B page table 12 while the seg shared variable points to address X, the starting address of entry 6 of the parent process map list 22.
The result of a fork operation on the parent process of FIG. 2A is illustrated in FIG. 2B. Assuming entry 5 of the parent process map list pointed to a writable segment, a privated segment C table 12 is created for the child process, along with its associated segment C file 26. The seg segp pointer of the segment C file 26 is set to point to the address A of the original segment A file 26 and the seg sstart variable of the segment C file 26 is set to 2, indicating that the first page of the privated page table corresponds to the second entry in page table A. The seg bp variable of the segment C file is set to point to the first address H of the privated segment C page table. Each entry of the segment C page table 12 is made a PG FSEG type, locating a page by referring to another segment. A child process map list 22 entry is created starting at address Y with its m segp variable pointing to the first address G of the new segment C file. The seg privated variable of the segment A file is changed to point to the address Y of the corresponding child map list entry, thereby creating a linked privated list allowing the operating system to determine all of the processes which have privated segment A.
At the start of the fork operation, the seg locked flag in the segment A is set true to prevent any other process from accessing the segment until the fork operation is complete. At the completion of the fork operation, the seg locked flag is reset to false to allow access to the segment by other processes. The seg privated variable is set to point to address Y of the child, process map list entry 5 privating the segment so that the operating system will know that the segment must be copied for for the child process before it is modified by the parent. Entry 5 of the child process map list is therefore the first mapping in the privated list of segment A. Assuming the parent process map list 22 entry 6 is of a non-writable area of the process virtual space, then segment B may be shared, rather than privated by the child process. A new map list entry 6 is made for the child process map list 22 mapping the same virtual space area of the child process onto segment B. the seg shared variable of the segment B file 26 is changed to point to address Z of entry 6 of the child process, indicating that the entry is the first in the shared list for the segment. In the child process map list entry 6, the m next shared variable is set to point to the parent process map list entry 6, indicating that the parent map list entry is the next mapping in the shared list. The m segp variable and the child map list entry 6 point to the address B of the segment B file while the m sstart and m len variables indicate that the first three pages in the segment page table are mapped. The m next privated variable is null since there is no privating mapping.
FIG. 3 is a flow chart for a "procdup()" procedure called during a fork operation to create the new map list 22, and any new privated segment page tables 12 required for the child process. Referring to FIG, 3, the procdup() procedure begins in block 100. In block 102 a "mapdup()" procedure creates a new map list entry for the child process corresponding to the first map list entry of the parent process, and creates a new privated segment page table 12 if the segment is writable. Next, block 104 directs program flow to block 106 if the current parent map list entry is not the last. In block 106 the next parent map list entry is found and the flow is directed back to block 102 where a second map list entry is created for the child process corresponding to the second map list entry of the parent process. When all of the parent process map list entries have been duplicated, block 104 directs flow to block 108 where the procdup() procedure ends and returns to the calling procedure.
FIG. 4 is a flow chart of the mapdup() procedure. Beginning in block 110, the procedure passes to block 112 which directs flow to block 114 if the current parent map list entry points to a read only segment (as indicated by the pg prot variable of the segment file). In block 114, a "NewMap()" procedure is called to add a new map list entry to the child segment pointing to the same segment as the corresponding parent map list entry. Next, in block 116, the process page table entries for the child process are created by copying the page table entries of the parent. Then, in block 118, the mapping is marked as "APPLIED" (anm flags bit set true) to indicate that the page table entries for the child's map list entry have been created. The process then returns to the calling process in block 120. If the parent map list entry points to a writable segment, then block 112 directs program flow to block 122 where a "PrivateMap()" procedure is called to create a new privated segment table 12 for the child, each entry of which is a P FSEG type referring to a corresponding page table entry of the parent segment table 12. PrivateMap() also creates the process page table 10 entries for the child process and sets m flags to indicate the mapping is applied. The mapdup() procedure then returns in block 124.
The PrivateMap() procedure is flow charted in FIG. 5. Starting in block 122, the procedure moves to block 124 where the segment is locked (the seg locked indicator of the segment file is set true) so that no other process can access the segment until the fork operation is complete. Then in block 126 a "NewSegment()" procedure creates a new privated segment page table 12. Next, in block 128, the seg segp pointer of the privating segment file is set to point to the first address of the original segment file 26. The NewMap() procedure is then begun in block 130 to create an entry in the child's process map list 22 which points to the new privating segment file 26. Procedure flow passes to block 132 wherein the privating segment page table 12 entries are all set to PG FSEG, to indicate that the real storage location of the pages associated with the entries are to be found by checking the corresponding page table entries of the original segment page table. Then in block 134 the pg v flag in each privated entry of the original segment page table 12 is set false to indicate that the page stored in core is "invalid" and must be copied prior to use. Also in block 134, the pg privated bit of each original page table entry is set to indicate that the entry cannot be destroyed until a copy is made for the privating segment. Finally the seg locked flag of the original segment file is set false in block 136 to allow access to the segment by other processes. The procedure returns in block 138.
The NewMap() procedure is flow charted in FIG. 6. Starting in block 140, the procedure flows to block 142 in which an unused mapping entry is found and then to block 144 where the map list entry variables are set up. Flow is then directed by block 146 to block 148 if the mapping is not of physical memory. In block 148, the mapping is added to the segment shafed list by adjusting the m nextshared pointer of the last mapping of the list to point to the new mapping entry. Then in block 150, the new mapping entry is added to the process mapping list 22 by adjusting the m next pointer of the last entry in the list to point to the new entry. The procedure then returns to the caller in block 152. If the mapping is of a portion of physical memory, then block 146 directs program flow to block 156 in which the m segp pointer of the new entry is set to null (i.e., points nowhere). Procedure flow then passes to block 150 where the map entry is added to the process map list and then to block 152 wherein the NewMap() procedure ends and returns to the caller.
The NewSegment() procedure is flow charted in more detail in in FIG. 7. Beginning in block 158, and moving to block 160, the procedure determines the number of page table entries required and then in block 162 obtains the necessary swap disk space for the segment table. Finally, the seg segp pointer to the address of the new segment is returned to the caller in block 166.
FIG. 2C illustrates how the virtual space of a process in a Unix operating system is usually arranged. The text storage area 30 of the program extends from th lowest address A of the virtual space to the starting address B of a data storage area 32. The data storage area 32 extends to address C. The stack area 34 of the program begins at the largest address E of the virtual space and grows toward the data space 32 as much as needed. In this case the stack has grown to address D. The area 36 between the stack and the data areas is reserved for future growth of the stack and data areas.
After a fork operation, the parent and child are identical processes in the sense that each has the same sized virtual address space filled with the same information. The primitive "exec" enables a process to execute a new program file by causing the current text and data segments of the process to be replaced with the new text and data segments specified in the file. This changes the program the process is executing but not the process itself.
During an exec operation a "getxfile()" procedure is called to remove the old program file from the virtual space of a procedure and to replace it with a new program file. The getxfile() procedure is flow charted in FIG. 8. The procedure starts in block 167 and then passes to block 168 where a "vrelvm()" procedure is called to delete the process map list and page table entries for the process undergoing the exec operation, thereby clearing the virtual memory of the process. Next, in block 169, a "vgetvm( )" procedure adjusts the size of the virtual memory of the procedure to suit the requirements of the new program file. Then in block 170 a "MapZeroI()" procedure creates a new segment page table 12 for the stack area of the process, setting each entry therein to be a PG FZERO type so that when the process later attempts to write to the stack, a new zero filled page will be created in core. The MapZeroI() procedure also creates a new process map list 22 entry mapping the stack portion of the program onto the new segment and creates new process page table 10 entries for the stack segment. When the stack area is set up by MapZeroI(), block 171 then passes program flow to block 172 if the program text is "fill-on-demand" indicating that the text is in a disk file and is not to be swapped into core until needed.
In block 172, the MapZeroI() procedure again creates a new zero filled segment page table 12, a new process map list 22 entry, and new process page table 10 entries for the data segment. Then in block 173 the data portion of the new program is read from the file into core memory and the new data segment page table 12 entries are adjusted as necessary to point to the data pages in core. In block 174, the getxfile() procedure next calls a "fileseg()" procedure which either finds an existing segment corresponding to the text file or, if such a segment does not exist, creates a new PG FTEXT segment pointing into the text file. Then in block 176 the NewMap() procedure creates a new process map list entry for the process, mapping the text virtual space onto the text segment. The ApplyMap() procedure is then called in block 178 to create the process page table entries for the text segment. Finally, the getxfile() procedure returns to the caller in block 180.
If in block 171 the program file called does not include fill-on-demand text, program flow is directed to block 182 where the MapZeroI() procedure creates a new zero filled segment table, a new process map list entry, and new process page table entries for the data area. Then in block 184 the data portion of the new program is read from the file into core memory and the new data segment page table entries are adjusted as necessary to point to the data pages in core. If there is no text in the program file, block 186 passes procedure flow to block 188 where the getxfile() procedure is returned. If there is text in the program file, block 186 directs flow to block 190 where the MapZeroI() procedure is called again to create and map a segment to receive the text data from the file. The text data is then read into core from the file in block 192 and the program returns to caller in block 194.
The vrelvm() procedure called by the getxfile() procedure to clear the existing program from the virtual space of the process is flow charted in FIG. 9. Starting in block 196, process flow is directed to block 198 where the first process map list entry is checked to see if it is a physical mapping. If it is not, program operation passes to block 200 where a "killptes()" procedure deletes the page table entries corresponding to the map list entry. Then block 202 directs program flow to block 204 if the last process map list entry has not been checked. In block 204 the next map list entry is found and then program flow reverts to block 198. If a map list entry is a physical mapping, then block 198 directs progtam flow to block 206 where a "releaseMap()" procedure is called to delete the map list entry, removing it from the segment shared or privated lists if the segment is shared or privated. ReleaseMap() also deletes the segment if the segment is neither shared nor privated. Program flow then passes to block 202. If the current map list entry is the last map list entry for the process, then block 202 passes program flow to block 208 where the procedure is returned to the caller.
The ReleaseMap() procedure, called to remove a mapping entry from a map list, is flow charted in FIG. 10. Starting in block 210, the ReleaseMap() procedure flows to block 212 and then to block 214 if the process map list entry maps a privated segment. In block 214 the map list entry is removed from the privated list by modifying the m nextprivated pointer of the previous mapping of the privated list. From block 212, if the mapping is not on a privated list, or otherwise from block 214, program flow passes to block 216 which further passes program flow to block 218 if the map list entry is on a shared list. In block 218 the map list entry is removed from the shared list by modifying the m nextshared pointer of the previous mapping on the shared list. From block 216, if the segment is not shared, or otherwise from block 218, the program moves to block 220 where a "MayBeFreeSeg()" procedure is called to allow reuse of the segment if no more mappings point to it. In block 222, the ReleaseMap() procedure then returns to the caller.
The killptes() procedure is called to release the real memory behind the virtual memory area associated with a process map list entry when the associated process is being swapped out of core or eliminated altogether. The procedure is flow charted in FIG. 11. A "kill" argument of procedure is set true if the pages in memory are no longer wanted and is set false if the pages in memory are merely to be swapped to the swap area of the disk. Starting in block 224 the killptes() procedure flow passes to block 226 which further directs flow to block 228 if the process map list entry is a physical mapping. Program flow is directed by block 228 to block 230 if the kill argument is true, indicating that the pages are no longer needed for the process. Block 230 calls the ReleaseMap() procedure to delete the map list entry for the process. From block 228, if the kill argument is false, or otherwise from block 230, flow passes to block 232 wherein the valid bit, p gv of the page table entries associated with the segment are set to false so that the pages in physical core are "invalidated" and not again accessed by a process through these page table entries. The killptes() procedure then returns to the caller in block 234.
If the map list entry is not a physical mapping, then block 226 of FIG. 11 directs program flow to block 236 in which the SEGLOCKED flag of the mapped segment file is set true to prohibit access to the segment by other processes until the killptes() procedure is finished. If the kill argument is true, block 238 directs flow to block 240 where a "GiveAwayPrivated()" procedure checks all of the process page table entries to be deleted to see if any are privated. If any page table entries are privated they are copied for the privaters requiring it. From block 240, or from block 238 if the kill argument if false, process flow passes to block 242 which further directs procedure flow to block 244 if there are no other page table entries in core pointing to the same page as the page table entries being deleted. In block 244 the core pages are freed, since they are no longer needed. Then program flow is directed by block 246 to block 248 if the kill argument is true. In block 248 the pages are also deleted from the swap area of the disk. From block 248, or from block 246 if the kill argument is false, procedure flow passes to block 250 wherein the memory mapping associated with the killed page table entries is marked as not applied. Then the segment is unlocked in block 252. Next, block 254 directs process flow to block 256 if the kill argument is true and in block 256 the ReleaseMap() procedure is called to delete the mapping from the process map list. From block 256, or from block 254 if the kill argument is false, flow passes to block 258 and the procedure returns to the caller.
The MapZeroI() procedure, called to create a new zero filled segment, is flow charted in FIG. 12. Starting in block 260, flow passes to block 262 in which the NewSegment() procedure is called to obtain disk space for a new segment page table. Then in block 264 the NewMap() procedure adds a new mapping entry to the process map list for the new segment. Next, in block 266, new PG FZERO segment and process page table entries are created and in block 268 the mapping is marked as applied. The process returns to caller in block 270.
The fileseg() procedure is flow charted in FIG. 13. This procedure is called when a process wants to bring new fill-on-demand text on a disk into its virtual space. The fileseg() procedure starts in block 272 and then in block 274 the procedure looks for another segment page table pointing to the same disk file. If another segment is not found, then block 276 directs process flow to block 278 in which the NewSegment() procedure creates a new segment page table and then to block 280 where a "vinifod()" procedure makes the page table entries of the new segment page table point to the disk file. Then in block 282 the pointer to the new segment is returned to the caller. If another segment page table points to the disk file, then block 276 directs program flow directly to block 282 for returning a pointer to the existing segment to the caller.
The ApplyMap() procedure, called to set up the process page table 10 entries corresponding to a map list entry, is flow charted in FIG. 14. Starting in block 284, flow is directed to block 286 which further directs flow to block 288 if the mapping is of physical memory. In block 288 the page table entries for the physical mapping are added to the process page table. In block 290 the procedure returns to the caller. If the mapping is not of physical memory, then block 286 directs flow to block 292 wherein the segment referenced by the mapping is locked. If the page table entries are not available in other segments currently residing in core, then block 294 directs program flow to block 296 and the segment page table containing the desired page table entries is read into core from the disk and then to block 298 where the page table entries in the segment page table are copied into the process page table. The segment is then unlocked in block 300 and the process returns to caller in block 302. If another segment page table residing in core has the desired page table entries, then block 294 directs program flow to block 304 with these page table entries being copied into the process page table, thereby avoiding a disk access. From block 304 the process moves to block 300 to unlock the segment and then to block 302 where it returns to the caller.
The GiveAwayPrivated() procedure, called to generate a copy of privated page table entries when the page table entries of a mapping are being killed, is flow charted in FIG. 15. Starting in block 306 the process flows to block 308 in which the first page table entry of the mapping is checked to see if it has been privated. If it has been privated, then in block 310 the entry is checked to see if another process has requested a copy. If so, then block 310 directs process flow to block 312 where the segment is unlocked and then to block 314 where a copy of the page table entry is made for the requesting process. Next, in block 316 the segment is locked and process flow is directed by block 318 to block 320 if the page table entry just checked is the last entry of the mapping. In block 320 the next page table entry is located and program flow is redirected back to block 308 for checking the new page table entry. When no other process has requested a copy of the page table entry, block 310 directs program flow directly to block 318 and no copy of the entry is made. If the last page table entry of the mapping has been checked and copied if necessary, block 318 directs process flow to block 322 for returning the process to the caller.
The MapPhysical() procedure, called when a new map list entry mapping physical memory is to be added, is flow charted in FIG. 16. Starting in block 324, the MapPhysical() procedure first calls the NewMap() procedure in block 326 which adds the new map list entry with the m segp pointer set null since no segment is referenced. Then in block 328 the ApplyMap() procedure creates the process page table entries associated with the mapping. The procedure then returns to the caller in block 330.
A "bringitin()" procedure is called to read a page from the disk into core memory whenever a process attempts to access a page which is not currently in core memory, as when the page is of the PG FTEXT or PG SWAP type. This procedure is not new in Unix but in the present invention a section is added at the end of the prior art procedure to handle the situation where the page is of the PG FSEG type in which the page table entry references a page table entry in another segment. The added section of the bringitin() procedure is flow charted in FIG. 17. The new section of bringitin() begins in block 332 which directs flow to block 334 if the page table entry is of the PG FSEG type. In block 334 the original page table entry of the privated list is found and in block 336 the page is brought into core from the disk, if not already there. Then in block 338 the page table entry is modified to point to the page in core. The procedure then returns to the caller in block 340. If the page was not of the PG FSEG type, then the page was of a PG FZERO, PG CORE, PG TEXT, of PG SWAP type and the prior art portion of the bringitin() procedure located and brought in the page. In this case block 332 would direct flow directly to block 340 to return the procedure.
A "GiveToPrivaters()" procedure, called to give copies of a page to privateers when a page is brought into core, is flow charted in FIG. 18. Starting in block 342, the procedure moves to block 344 in which the first private mapping is located and then to block 346 for directing the procedure to block 348 if the private mapping requires a copy. In block 348 the core space is reserved to receive the copy and then in block 350 the copy is copied into the core reserved space. If the current private mapping is not the last in the privated list, block 352 directs the process flow to block 354 wherein the next privated mapping is located and then back to block 346. Block 346 passes flow directly to block 352 if no copy is required by the privater. If the private mapping just checked is the last in the privated list, block 352 further passes process flow to block 356 where the procedure ends and returns to the caller.
When a process is swapped into core, a "swapin()" procedure is called to create the process page table. The procedure, flow charted in FIG. 19, begins in block 358 and then in block 360 calls the ApplyMap() procedure to create the process page table entries for the first mapping of the process map list. Block 362 then directs program flow to block 364 if the mapping is not the last mapping in the map list. The next mapping is located in block 364 and then flow is directed back to block 360 for calling the ApplyMap procedure for the next mapping. When the page table entries have been set up for all maplist entries, block 362 directs flow to block 366 so that the procedure returns to the caller.
When a process is to be swapped out of core, a "swapout()" procedure is called to kill the associated page table entries. The swapout() procedure is flow charted in FIG. 20. The procedure begins in block 368 and then block 370 directs program flow to block 372 if the mapping is not physical. In block 372 the killptes() procedure deletes the process page table entries associated with the first map list entry and then block 374 directs program flow to block 378 if the map list entry is not the last in the map list. In block 378 the next map list entry is located and flow is directed back to block 370. If the map list entry is a physical mapping, block 370 further directs flow to block 374 and the page table entries are not killed. If the map list entry is the last, then block 374 directs flow to block 380 where the procedure returns to the caller.
An "m fmap()" procedure, called to map the virtual address space of a process into a disk file, is flow charted in FIG. 21. Starting in block 382 the procedure passes to block 384 where file parameters, including its size, are checked. Then in block 386 the procedure determines if the virtual address space of a process is sufficient to receive the file and adds more virtual space to the process if necessary. Next, in block 388, a "MapFile()" procedure creates and applies the new mapping. The procedure ends in block 390, returning to the caller.
The MapFile() procedure, flow charted in FIG. 22, begins in block 392, calls the NewMap() procedure in block 394 to create the new map list entry and then calls the ApplyMap() procedure in block 396 to create the associated process page table entries. The process then returns to the caller in block 398.
An "m map()" procedure is called to add pages to the virtual space of a process. These may be either zero filled pages, physical memory, copies of another part of the same virtual space, or a copies of portion of another process' virtual space. The m map() procedure, flow charted in FIG. 23, begins in block 400 and then block 402 directs process flow to block 404 to end the procedure if certain parameters passed by the calling procedure are incorrect. these parameters are incorrect if the process wants to acquire new material in other than cluster sized sections, wants to place new material in an area that is already filled, or wants to place material outside the limits of the process' allowable virtual space. If the parameters are acceptable, block 402 directs program flow to block 406 wherein virtual space is added to the process if necessary and then to block 408 where flow is redirected to block 410 if the segment to be added comprises pages of the PG FZERO type. Block 410 calls the MapZeroI() procedure to create the zero filled segments, to create the map list entry mapping the segments, and to create the process page table entries. Then in block 412 the page table entries are flushed from a page table entry cache and the process returns to caller in block 414.
The page table entry cache is a fast access memory used to store often accessed page table entries which are also located in core. When accessing page table entries for virtual-to-real address translation, the operating system checks to see if the page table entries are in the cache before attempting to access them in normal core memory. The cache is "flushed" or emptied whenever page table entries elsewhere are destroyed or modified to prevent the operating system from accessing obsolete page table entries therein.
If the mapping to be added does not include PG FZERO pages, then block 408 directs flow to block 416which in turn directs flow to block 418 if the mapping is of physical memory. In block 418 the MapPhysical() procedure creates the map list entry and the process page table entries. Then in block 420 the page table entries are flushed from the page table entry cache and in block 422 the procedure returns to the caller. If the mapping is not of physical memory, block 416 directs process flow to block 424 which redirects flow to block 426 if the data is read protected against the process. The procedure ends in block 426 and returns to the caller without creating the new mapping. If the data is not read protected, flow passes from block 424 to block 428 so the process' right to access the new material can be checked. If the process has no right to access the material then flow is directed to block 430 for return to the caller. If the process has the right to access the material, block 428 passes process control to block 432 which further passes the process to block 434 if the new pages are writable and should be privated. In block 434, the PrivateMap() procedure creates a private mapping and then in block 436 the procedure returns to caller. If the material is not to be privated, then block 432 directs process flow to block 438 and the NewMap() procedure creates a new segment table and a map list entry for the material. Then in block 440 the ApplyMap() procedure creates the process page table entries for the mapping. The procedure is then returned to the caller in block 442.
An "m remap()" procedure, called to move material in one area of virtual space to another area of the virtual space of the same process, is flow charted in FIG. 24. Starting in block 444, the procedure flows to block 446 in which parameters describing the relocation passed by the calling procedure are checked to see that the relocation requested is valid, and then to block 447 to return the procedure if the the parameters are invalid. If the parameters are valid, more virtual space is added to the process in block 448 if necessary to accommodate the move. Next, in block 450, an "extractrange()" procedure makes a list of the map list entries that are to be relocated, splitting map list entries if necessary to line up the virtual space boundaries at the area to be relocated with the boundaries of the map list entry. Then in block 452 the virtual space starting addresses of the relocated mappings are adjusted and in block 454 an "insertmappings()" procedure places the mappings back into the process mapping list. The original page table entries are then copied into their new page table locations in block 456 and the old page table entries are zeroed in block 458. The page table entry cache is flushed in block 460 with the process returning to the caller in block 462.
An "m munmap()" procedure, called when a process wants to remove a portion of a program, is flow charted in FIG. 25. Starting in block 464 the procedure passes to block 466 wherein the parameters specifying the portion to be moved are checked for validity. If they specify an invalid move, block 466 directs process flow to block 467 so the process is returned to the caller. If the parameters are valid, block 466 passes flow to block 468 where a "munmap()" procedure is called and then to block 470 where the m munmap() procedure returns to the caller.
The munmap() procedure, flow charted in FIG. 26, begins in block 472 and then in block 474 calls the extractrange() procedure to make a list of map list entries that cover the area to be removed, splitting first or last map entries if necessary to line up the boundaries of the area to be moved with the boundaries of a map list entry. Next an "insertrange()" procedure returns the extracted map list entries to the map list. The killptes() procedure in block 478 releases the real memory behind the virtual memory space to be vacated and the page table entry cache is flushed in block 480. The procedure then returns to the caller in block 482.
In Unix systems of the prior art, an "obreak()" procedure is used whenever more virtual space is required for the data area of the program. The space is obtained by appropriating portions of the empty virtual space between the data area and the stack area of virtual memory and the space added had to be contiguous to the existing data area. In the present invention, the obreak() procedure is modified to operate within the mapping framework of the present invention.
The obreak() procedure of the present invention is flow charted in FIG. 27. Starting in block 484 the procedure moves to block 486 in which the available core and swap space is checked. If there is not enough available core or swap space for the new data area, then in block 487 the procedure returns to caller. If there is sufficient space then in block 488 the last mapping of the data area is found. Process flow continues to block 490 where it is diverted to block 492 if the last mapping can be appended (expanded) to accommodate the new data. In block 492 an expand() procedure is called to expand the area of virtual space mapped by the last data mapping and to add page table entries to the segment and process page tables. Then in block 494 the new page table entries are set to the PG FZERO type. The page table entries are then flushed from the page table entry cache in block 496 and the process returns to the caller in block 498. If the last data area mapping cannot be appended, block 490 directs program flow to block 500 whereby the MapZeroI() procedure is called to create a new zero filled mapping for the additional data area. The page table entry cache is then flushed in block 502 with the process returning to the caller in block 498.
A "GetPagingCluster()" procedure, flow charted in FIG. 28, is employed to find the first free cluster in the swap area of a disk. Starting in block 504, the procedure moves to block 506 for scanning a bit map of clusters in the swap area for indicating which clusters are free. If a free cluster is found, then block 508 directs flow to block 510 and the swap area bit map is marked to indicate the cluster is no longer free and then to block 512 where the procedure returns the first block number of the cluster to the caller. If no cluster is available, block 508 directs flow to block 514 and the procedure returns a 0 to the caller.
A "FreePagingCluster()" procedure, flow charted in FIG. 29, is used when a swap area cluster is no longer being used. Starting in block 516 the process flows to block 518 for changing the bit in the bit map associated with the cluster being freed, the cluster number having been passed to the procedure by the caller. In block 520 the procedure returns to the caller.
A "C" language listing of the procedures flow charted in FIGS. 3 through 29, along with procedures called thereby, is included in Appendix I to this specification.
Thus the virtual memory method of the present invention allows two or more processes to share only selected portions of the same segment, rather than the entire segment, and allows such sharing even if the segment is writable. The virtual memory method also allows fork operations without requiring copies to be made for the child process. These features permit reductions in the amount of core and disk space needed to accommodate the processes and reductions in the number of disk accesses required during fork operations and process execution. Further, these features are provided without sacrificing the ability to perform fast virtual-to-real address translation using only a single page table access.
While a preferred embodiment of the present invention has been shown and described, it will be apparent to those skilled in the art that many changes and modifications may be made without departing from the invention in its broader aspects. The appended claims are therefore intended to cover all such changes and modifications as fall within the true spirit and scope of the invention. ##SPC1##
Claims
I claim:
1. For use with a computer having a memory for storing data at real addresses within a real address space and having processor means for executing a process accessing data stored in said memory by referencing virtual addresses within a virtual address space, and wherein virtual addresses are grouped into virtual address pages, a method for determining a particular real address corresponding to a particular virtual address referenced by said process, the method comprising the steps of: storing segment page tables in said computer memory, each corresponding to a separate one of a plurality of segments of said memory, each of said segments comprising a plurality of real address pages, each real address page comprising a plurality of real addresses within said real address space, each virtual address page corresponding to a separate one of said real address pages, each segment page table comprising data referencing addresses in said computer memory of the real address pages comprising a segment corresponding to said each segment page table; storing a process map list in said computer memory, said process map list comprising data referencing addresses in said computer memory of all of said segment page tables which correspond to segments of said memory comprising real addresses corresponding to virtual addresses within said virtual address space; and creating and storing in said computer memory a process page table comprising data referencing addresses in said comupter memory of each real address page corresponding to a virtual address page, said process page table being created immediately prior to execution of said process, the process page table including data contained in said process map list and in segment page tables having addresses in said computer memory referenced by said process map list.
2. The method in accordance with claim 1 further comprising the step of determining by means of said computer addresses in said computer memory of a particular real address page corresponding to a particular virtual address page referenced by data included in said process page table when said process references addresses of said particular virtual address included in said particular virtual address page.
3. The method in accordance with claim 1 further comprising the steps of: determining by means of said computer addresses in said computer memory of a particular virtual address page containing said particular virtual address referenced by said process during execution of said process, the determination of said particular virtual address page being made by reading data included a first portion of said particular virtual address; determining by means of said computer addresses in said computer memory of a particular real address page corresponding to said particular virtual address page by reading data included in said process page table; determining by means of said computer said particular real address within said particular real address page which particular real address corresponds to said particular virtual address, the determination of said particular real address being made by reading data included in a second portion of said particular virtual address.
4. The method in accordance with claim 1 wherein each of said real address pages comprises a plurality of consecutive real addresses and wherein said segment page table and said process page table determine addresses in said computer memory of real address pages by referencing the first real address thereof.
5. For use with a computer having a memory for storing data at real addresses within a real address space and having processor means for sequentially executing a plurality of processes accessing data stored in said memory by referencing virtual addresses within a virtual address space, and wherein virtual addresses are grouped into virtual address pages, a method for determining a particular real address corresponding to particular virtual addresses referenced by any one of said processes during execution thereof, wherein: said computer stores, in said memory, segment page tables, each corresponding to a separate one of a plurality of segments of said memory, each of said segments comprising a plurality of real address pages, each real address page comprising a plurality of real addresses within said real address space, each segment page table comprising data identifying addresses in said computer memory of the real address pages comprising a segment corresponding to the segment page table; said computer stores, in said memory, a plurality of process map lists, each process map list corresponding to a separate one of said processes and comprising data identifying addresses in said computer memory of all of said segment page tables which correspond to segments of said memory comprising real addresses corresponding to virtual addresses within the virtual address space of the corresponding process; and wherein said computer creates and stores, in said memory, immediately prior to execution of one of said plurality of processes, a process page table comprising data referencing addresses in said computer memory of each real address page corresponding to a virtual address page, said process page table including data included in a particular one of said process map lists corresponding to said one process to be executed, and data included in said segment page tables referenced by data of said process map list.
6. The method in accordance with claim 5 further comprising said computer determining during execution of said one process addresses in said computer memory of a particular real address page corresponding to a particular virtual address page data included in said process page table when said one process references said particular virtual address included in said particular virtual address page.
7. The method in accordance with claim 6 further comprising the step of said computer deleting said process page table from said memory immediately prior to execution of a next one of said plurality of processes.
8. For use with a computer having a primary memory for storing data at real addresses within a real address space, having a secondary memory for storing data at a plurality of storage locations in said computer memory, and having processor means for sequentially executing a plurality of processes accessing data stored in said primary and secondary memories by referencing virtual addresses within a virtual address space, wherein virtual addresses are grouped into virtual address pages, real address space is grouped into real address pages, and secondary memory storage locations are grouped into secondary storage pages, a method for determining a particular one of said real addresses corresponding to a particular virtual address referenced by any one said processes during execution thereof, wherein: said computer stores, in said secondary memory, segment page tables, each corresponding to a separate one of a plurality of segments of said primary and secondary memories, each of said segments comprising at least one of said real address and secondary storage pages, each segment page table comprising data referencing addresses in said computer memory of the real address and secondary storage pages comprising a segment corresponding to the segment page table; said computer stores, in said secondary memory, a plurality of process map lists, each process map list corresponding to a separate one of said processes and comprising data referencing addresses in said computer memory of all of said segment page tables which correspond to segments of said primary and secondary memories comprising at least one of said real address and secondary storage pages corresponding to virtual address pages of the corresponding process; and wherein said computer creates and stores, in said primary memory, immediately prior to execution of one of said plurality of processes, a process page table comprising data referencing addresses in said computer memory of each real address and secondary storage page corresponding to a virtual address page, said process page table including data included in a particular one of said process map lists corresponding to said one process to be executed, and including data included in said segment page tables having addresses referenced by said process map list.
9. The method in accordance with claim 8 further comprising the step of determining with said computer during execution of said one process addresses in said computer memory of a particular one of said real address and secondary storage pages corresponding to a particular virtual address page by reading data included in said process page table when said one process references said particular virtual address included in said particular virtual address page.
10. The method in accordance with claim 9 further comprising the steps of: generating by means of said computer a copy of said particular one of said real address and secondary storage pages when said particular one of said real address and secondary storage pages is a secondary storage page; storing said copy of said particular secondary storage page as a particular real address page in said primary memory; and modifying said process page table to reference addresses in said computer memory of said particular real address page as corresponding to said particular virtual address page.
11. The method in accordance with claim 10 further comprising the step of modifying one of said segment page tables referenced by the process map list corresponding to said one process and referencing said particular secondary storage page as being included in a segment corresponding to said one segment page table so that said one segment page table references said particular real address page rather than said particular secondary storage page as being included in its corresponding segment.