Method for reducing disk I/O accesses in a multi-processor clustered type data processing system

Abstract

A method for minimizing I/O mechanical assess operations on secondary storage devices in a data processing system having a plurality of processor units interconnected in a cluster configuration to permit each processor unit to request and obtain data that is resident only on a secondary storage device of one processor unit. The method involves the steps of maintaining at each processor unit information about each copy of data that has been sent from the unit to another unit to permit a second request to the unit to be serviced by transferring a copy of the data from the main memory which is storing the data to the requesting unit rather than servicing the request with a relatively slow I/O accessing operation to a secondary storage device.

Claims

We claim:

1. A method to minimize I/O access operations in a data processing system having

A) a plurality of processor units comprising a first processor unit with a first main memory, first operating systems, and first secondary storage device; a second processor unit with a second main memory and second operating system; and a third processor unit with a third main memory and third operating system; and

B) a switch for selectively interconnecting any pair of said units in a data transferring relationship to permit data that is stored in said first memory to be transferred to said third main memory in response to request from said third unit to said first unit, said method comprising the following steps in combination;

A) maintaining by each said first, second and third operating system,

(a) a list of each of the files stored in said data processing system, and

(b) an indication of which of said processor units is the access coordinator for said each of said files,

B) opening one of said files, stored at said first processor unit as identified by said indication in response to a request to said first processor unit for specified information from said second said processor unit,

C) transferring from said first secondary storage device of said first processor unit to said first main memory and thereafter transferring from said first main memory to said second main memory said specified information from said one of said files in response to said request by said second processor unit, and discarding said specified information from said first main memory, and

D) thereafter transferring said specified information from said second main memory to said third main memory in response to a request from said first operating system to said second operating system, that was prompted by a request to said first operating system from said third operating system for said specified information.

2. The method set forth in claim 1 in which said step of maintaining by each said first, second and third operating system further comprises the step of

(a) maintaining by said each first, second, and third operating system a corresponding Virtual Shared Memory (VSM) Table one said VSM Table identifying which of said processor units has a copy of said specified information that is being coordinated by said access coordinator.

3. The method set forth in claim 2 in which said step of transferring from said first main memory to said second main memory further comprises the step of

(a) updating said VSM Table of said first operating system to reflect that said specified information is stored in said second main memory.

4. The method set forth in claim 3 in which said step of transferring said specified information from said second main memory to said third main memory included the further step of

(a) updating sad VSM Table of said first processor unit to indicate that a copy of said specified information is stored in said third main memory.

5. A method in a data processing system having

a first processor unit with a first main memory, first operating system, and first secondary storage device; a second processor unit with a second main memory and second operating system; and a third processor unit with a third main memory and third operating system, said first, second, and third processing units being interconnected by a communication link, said method comprising the following steps;

A) maintaining by each said first, second, and third operating system indications of which of said processor units coordinates access for a file in the data processing system;

B) maintaining by said first operating system information which indicates that a copy of said file is currently maintained in said second main memory and is not currently maintained in said first main memory, and

C) servicing a request by said third processor unit to said first processor unit for a copy of said file, said request being directed to said first processor unit by one of said indications indicating at said third processor unit that said first processor unit coordinates access to the identified data, said servicing causing said second processor unit to transfer a copy of said file to said third main memory, rather than said first unit servicing said request by an I/O operation to said first secondary storage device if said file is not in said first main memory.

6. The method recited in claim 5 in which said system further includes a second and third secondary storage device for said second and third processor unit respectively, and wherein

(a) said first, second, and third main memory and said respective first, second, and third secondary storage device of each said respective first, second, and third processor unit comprise a virtual memory for said respective first, second, and third processor unit, each said virtual memory having the same virtual address range, that includes a plurality of contiguous segments, each of which includes a plurality of virtual page addresses,

(b) said first, second, and third secondary storage device comprises, respectively, a plurality of block addressable storage locations each of which stores a page of data,

(c) said first, second, and third main memory comprises, respectively, a plurality of page frames for storing a page of data,

(d) each of said first, second, and third processor units having the same operating system including a memory manager having a page fault handling mechanism for resolving page faults that occur in response to requests from an application program to process a page of data that is not in main memory, and

(e) a switch is activated by said first, second and third processing units for selectively interconnecting any two of said first, second, and third processor units, said method including the further steps of

storing in each said respective virtual memory a copy of said same operating system and further storing at least one application program in a corresponding said virtual memory of at least one of said first, second, and third processor units, and

coordinating access requests to said at least one application program from other of said first, second, and third processor units by one of said first, second, an third processor units controlling one of said segments of said corresponding said virtual memory where said at least one application program is stored.

7. The method recite in claim 6 in which said step of maintaining information by said first operating system includes the further steps of

(a) establishing a first data structure having a plurality of entries for storing a unique identifier for each said at least one application program stored in said system, and a processor unit ID to designate an Accessor Coordinator (AC) for each said stored at least one application program, and

(b) storing said first data structure in said first, second, and third main memory.

8. The method recited in claim 7 in which said step of maintaining information by said first operating system includes the further steps of

(a) establishing a second data structure having a plurality of entries, each of which stores an indication of the virtual address of a page of data transferred from a file being coordinated by said first processor unit, and the identity of a remaining said second or third processor unit that has a copy of said transferred page.

(b) storing said second data structure in said first, second and third main memory, and

(c) updating said first and second data structures as pages of data are transferred between said first, second, and third processing unit during said step of servicing.

9. The method recited in claim 8 including the further step of

(a) resolving local page faults in one of said first, second, and third processor units with said memory manager by first determining from said second data structure whether a copy of the page which caused the local fault is stored in a corresponding first, second or third main memory of another of said first, second or third processor units before resoling said fault with said page fault handling mechanism of said first, second, or third one of said processor units.

Description

FIELD OF THE INVENTION

This invention relates in general to virtual memory data processing systems comprising a plurality of similar interconnected data processing units which share the same virtual memory addressing space and in particular to an improved method for reducing disk I/O access by each of the processing units.

RELATED APPLICATIONS

U.S. Application Ser. No. 06/819,458 filed Jan. 16, 1986, in the name of Duvall et. al, entitled "Method to Control I/O Accesses in a Multi-Tasking Virtual Memory Virtual Machine Type Data Processing System", now U.S. Pat. No. 4,742,477, is directed to a method for use in a multi-user page segmented virtual memory data processing system in which a mapped file data structure is selectively created to permit all I/O operations to the secondary storage devices to be executed by simple load and store instructions under the control of the page fault handler.

BACKGROUND ART

The prior art has disclosed a number of virtual memory data processing systems which employ a single stand alone Central Processing Unit (CPU). These systems generally employ a main memory having a plurality of individually addressable storage locations, each of which stores one byte of data and a secondary storage device such as a Disk File which includes a plurality of block addressable storage locations each of which stores a block of data. For discussions purposes it is convenient to assume that each block address of the disk file stores a page of data comprising for example 2K (2048) bytes of data. The virtual memory concept involves what is sometimes referred to as a single-level store. In a single-level store, the maximum address range of the system is generally much larger than the real capacity of the main memory. The main memory is made to appear much larger by the use of a paging mechanism and a secondary storage device which cooperate to keep the data required by the application program in main memory.

The function of the paging mechanism is to transfer a page of data from the disk file to main memory whenever a page which is addressed by the application program is not in main memory. This is called a page fault. Transferring the page of data from the disk file to main memory is called page fault handling.

The performance of a virtual memory data processing system is directly related to the number of disk accesses that occur in servicing page faults since accessing a disk is a relatively slow process typically requiring several milliseconds, whereas accessing main memory typically involves less than a single microsecond. Prior art virtual memory systems therefore employ various techniques to reduce disk accesses and increase the percentage of "hits" that are made in addressing virtual memory. A hit is made in addressing virtual memory if data addressed by an application program is in main memory at the time the application program addressed the data. The hit ratio r of a virtual memory system is the number of hits h in addressing virtual memory divided by the number of hits h plus misses m, or

r=h/ (h+m)

The prior art has also disclosed a number of multi-processor system configurations that are sometimes employed to obtain increased data processing power. A multi-processor system configuration may be thought of as a plurality of Processing units sharing a logical communication channel. The logical communication channel may take the form of memory shared among the processing units into which messages from one processing unit to another processing unit may be placed. Additionally, the logical communication channel may take the form of a communication network through which messages from one processing unit to another processing unit may travel.

In some prior art multi-processor system configurations referred to as tightly-coupled multi-processor configurations, the processing units in the configuration share some amount of memory which any of the processing units in the configuration may access, and each processing unit may have some amount of private memory which only it and no other processing unit may access.

Computing systems arranged in a tightly-coupled multi-processor configuration have the benefit of rapid communication via shared memory and may also exploit the shared memory as a disk cache. A page fault may occur when an application program executing on one of the processing units in a tightly-coupled multi-processor configuration addresses a page of data that is not in main memory. During page fault handling, the appropriate secondary storage device connected to the configuration is commanded to place the appropriate page of data into the shared memory. Once the page of data has been placed in the shared memory it may be addressed by any of the processing units in the configuration.

If the plurality of processing units in a multi-processor configuration are working on a common problem, it is normal for the data they access to be accessed in such a way as to experience "locality of reference". The term locality of reference is used when there is some non-zero probability that a page of data retrieved from secondary storage and placed in shared memory to satisfy a page fault resulting from an access to virtual memory by an application program executing on one processing unit in the configuration will also be accessed by another application program executing on another processing unit in the configuration before the page frame in shared memory holding that page of data has been re-used by the configuration to hold another page of data. If such an access by another application program executing on another processing unit in the configuration occurs, the configuration may avoid a disk access by satisfying the page fault with that page of data already in shared memory.

A practical limit however is reached for tightly-coupled multi-processor configurations when the contention for access to shared memory among the processing units in the configuration exceeds the benefit provided by the shared memory when used as a disk cache. For instance, one processing unit in the configuration may attempt to change the contents of a page of data while another processing unit is attempting to examine the contents of the same page of data. Some mechanism must normally be provided by the configuration to lock out one of the processing units in favor of the other so that the two processing units see a consistent view of the data. Various methods exist in the prior art to enforce a consistent view of data upon the processing units in a tightly-coupled multi-processor configuration. These methods involve idling one of the processing units in the configuration until the other processing unit has completed its access to shared memory. The processing unit that has been idled cannot be idle and also perform useful work; thus, contention for access to shared memory inevitably results in some loss of processing power for the configuration when considered as a whole. For these reasons, the number of processing units in a single tightly coupled multi-processor configuration rarely exceeds six.

In some other prior art multi-processor system configurations referred to as closely-coupled multi-processor configurations, the plurality of processing units is connected via a communications network and each processing unit may access its own memory directly and no other processing unit has access to that memory. The processing units in a closely-coupled multi-processor configuration may share data by sending messages via the communications network to other processing units within the configuration. A variation on the closely-coupled multi-processor configuration distinguishes one of the processing units in the configuration as a shared memory processing unit. The main memory attached to the shared memory processing unit is used as a disk cache managed by the shared memory processing unit. The shared memory processing unit is assigned the function of controlling which of the other processing units can have access to what area of the shared memory at what time and under what configurations. When the shared memory is a virtual memory involving a fast main memory and a relatively slow secondary storage device, the size of the main memory which is required to obtain a respectable hit ratio is directly related to the total number of instructions that are being executed by the multi-processor configuration per second. Individual processing units are sometimes rated in Millions of Instructions Per Seconds (MIPS). If two 4 MIPS processing units and a third shared memory processing unit are employed in a closely-coupled multi-processor configuration, the main memory associated with the configuration must have approximately 80 megabytes of byte addressable memory to obtain a respectable hit ratio. The rule of thumb that is used is that 10 megabytes of byte addressable main memory per MIPS is required to obtain an 85 percent hit ratio in the shared memory. Therefore, if another 4 MlPS processing unit is added to the multi-processor configuration, another 40 megabytes of byte addressable memory should be added to the main memory of the shared memory processing unit to maintain the 85 percent hit ratio. A practical limit however is reached in the number of processing units that can be added to the configuration before the cost parameters and performance reach the point of diminishing returns.

More recently the prior art has begun to configure stand alone personal computers or stand alone engineering work stations into a local area network. In such an arrangement, which is called a loosely-coupled multiprocessor configuration or a distributed system configuration or a cluster configuration, any work station can communicate with another work station employing standard communication protocols. The motivation that exists for establishing the cluster configuration is not necessarily more data processing power, but simply one of the convenience of exchanging information electronically vs. non-electronic exchange. However, it has been found in some situations that the individual work stations are running the same operating system and at times run the same application programs. A paper entitled "Memory Coherence in Shared Virtual Storage Systems" authored by Kai Li and Paul Hudak and presented at the 5th Annual Association for Computing Machinery Symposium on Principles of Distributed Computing 1986, discloses a plurality of virtual memory data processing units interconnected in a cluster configuration. In this arrangement all units have the same operating system and address the same virtual address space. Each unit is the owner of a different set of files which is stored in that owner's memory system. A non-owner running an application program obtains access to the other unit's memory system through a suitable communication link, which causes requests to the file owner for virtual pages of data which are then returned to the requester.

Each unit of the cluster configuration therefore shares the set of files in its virtual memory system with the other units in the configuration. Page faults resulting from requests are serviced by the file owner. If the request is local, that is from the owner, the requested page is transferred from the owner's secondary storage directly to the owner's main memory. If the request is from a remote unit, the page is transferred from the owner's secondary storage to the requester's main memory through the communication link. A system protocol is established to control what happens to pages of data after the requesting unit is finished with them. This protocol addresses such issues as, when to return a page to the owner, how to manage concurrent requests for the same page if one unit wants to write to that page while other units want to read from that page, and various other situations that are common to functions that share stored data.

The sharing by each processing unit of its virtual memory with other processing units in the cluster has some potential advantages in that the size or capacity of the secondary storage devices can be reduced since the total umber of files available to the cluster is spread out among a number of secondary storage devices. This would permit the use of devices with faster access times and/or lower cost. A potential disadvantage is that concurrent requests from a number of different units to an owning unit will each result in a number of disk accesses to occur in sequence. While the requests are generally serviced in an overlapped manner, a disk access is a relatively time consuming operation for the unit and could severely impact the performance of the owning unit which is perhaps executing an unrelated application program, that is competing for the services of the secondary storage device.

The present invention is directed to a novel method for use by a shared virtual memory, cluster configured, data processing system in which the number of page faults requiring access to the secondary storage devices is considerably reduced.

SUMMARY OF INVENTION

The new method for reducing disk I/0 access operations in a shared virtual memory type data processing system comprising a plurality of virtual memory type data processing units interconnected in a cluster configuration, is based on the realization that when a request to the access coordinator or owner of a page of data results in a page fault, considerable time can be saved in servicing that page fault, if a copy of the page is in the main memory of one of the other units in the cluster. For example, assume that Page P is from a file owned by Unit A and that a request by a non-owner such as Unit B is made for Page P to Unit A who is the access coordinator in the system for the segment containing that page. Assume also that the request to A required Unit A to get Page P from its secondary storage device by use of its page fault handling mechanism. Assume further that a copy of Page P was sent to the Unit B and is in the main memory of Unit B when another request is made to Unit A for Page P from Unit C. If Unit A can ask Unit B to send the copy of Page P to Unit C, a page fault handling operation involving an I/O operation to the secondary storage device of Unit A is avoided.

In accordance with the new method, the individual processor units within a cluster of multi-processors, individually coordinate access to multiple segments of the common virtual memory address space. Each segment of virtual memory is logically composed of 128K (131,072) pages, each of which is composed of 2K (2048) bytes of memory. The processor units within the cluster share these virtual memory segments among other processor units within the cluster. A single processor unit serves as the access coordinator of a given file of data assigned to a specified virtual memory segment. Other processor units that use the virtual memory segment are individually called "using processor units". The strategy of the method to implement consistent access to cached pages of virtual memory basically comprises four important aspects.

1. The ownership of a page changes dynamically with its use; thus the right to update a page may be assigned by the access coordinator for the segment containing the page to a given using processor unit and remains with that processor unit until contention for the page requires it to be revoked by the access coordinator for the segment containing that page and assigned to another processor unit.

2. Ownership of one portion of a page implies ownership of the entire page. If, for example, a processor unit accesses the first byte on a page and that unit is granted the capability of accessing that byte, it is also granted the capability of accessing the entire page.

3. The coordination of access to a page is assigned statically and is the processor unit coordinating the segment containing the page.

4. The access coordinator for a given page records in the Virtual Shared Memory Table (VSMT) which processor units have a copy of the page, the access rights individual processor units hold (e.g., read only vs. read/write) and a list of other processor units that are seeking access to the page. The method involves recording at a segment's access coordinator, which pages of the segment are resident in the memory of which using processor unit. The using processor unit requesting access to a page avoids disk I/O by reading the page from a processor unit that has it in its memory system, rather than reading it from disk. In this way, the private memories attached to the individual processor units within the cluster are virtually shared among each other.

The number of entries in the VSMT table are determined at cluster IPL time or at execution time, based on performance measurements and requirements. The number of VSMT entries is always bounded by the number of page frames of real storage in the cluster. For example, if a cluster consists of 16 processor units each of which has 16 megabytes of memory directly attached to it, there is a total of 2**17 frames in the cluster. If an entry for each frame were allocated to the VSMT in each processor unit, then 11 megabytes of storage would have to be allocated in each processor unit for the VSMT table. For practical purposes, the VSMT table never needs to be that large. The VSMT table does not need to represent pages in the real memory of the access coordinator since these pages are already represented in its page table. Only those pages of those segments, both code and data that are actually shared across the cluster and are in real memory at any given time, need to be represented in the VSMT table. Thus, only a fraction of physical memory frames will contain pages of shared segments at any given time, other frames containing non-shared pages need not be represented in the VSMT table.

The strategy to determine the number of entries in the VSMT table is to create it initially with a small number of entries and to let the number of entries grow with use.

The method further employs "Triangular I/O" which is a scheme for performing I/O among two or more processors. In the unit processor view of the world, I/O is performed between a master unit, the processor and a "slave unit" (a control unit). The master sends requests to the slave, which processes them and responds to them. For example, a processor might send a request for a virtual page to some control unit for a set of disks. The control unit would handle the request by locating the appropriate blocks of data on its disks and transferring them back to the requesting processor. In a cluster, the concept of master and slave units is less clear. For example, a processor unit R might send a request to some other processor unit Q for a page P stored on a disk device connected directly to processor unit Q. Processor unit Q might handle the request in the same way the control unit would or it might try to avoid a disk I/O by forwarding the request to another processor unit T that has a copy of the requested page in physical memory attached to it. Processor unit T might send the requested page to processor unit R rather than having to send it through processor unit Q. In this sense processor units R, Q and T were involved in a "Triangular I/O" with page P. Interprocess communication was reduced and a second I/O operation to a disk device was avoided.

It is therefore an object of the present invention to provide an improved method for reducing the number of access operations to secondary memory devices in a virtual memory type data processing system.

Another object of the present invention is to provide an improved method for use in a data processing system having a plurality of interconnected virtual memory type processing units in which I/O access operations to resolve page faults are minimized.

A still further object of the present invention is to provide in a multi-processor cluster environment, an improved method for resolving page faults which occurs when a requested page is not in the main memory of the requesting processor unit.

BRIEF DESCRIPTION OF THE DRAWING

FIG. 1 is a Functional Block Diagram of a plurality of processor units interconnected in a cluster configuration, in which the method of the present invention may be advantageously employed.

FIG. 2 is a Block diagram of one of the processor units shown in FIG. 1, illustrating the various functions that are incorporated in one of the units.

FIG. 3 is a Block diagram of one of the processing units shown in FIG. 1 illustrating the various software functions that are incorporated in the unit of FIGS. 2 and 3.

FIG. 4 illustrates an External Page Table (XPT) data structure employed by the Virtual Memory Manager function of the unit shown in FIGS. 2 and 3.

FIG. 5 illustrates an Inverted Page Table data structure employed by the Virtual Memory Manager function of the unit shown in FIGS. 2 and 3.

FIG. 6 illustrates the Global and Local Segment Identifier data structures which uniquely identify virtual memory segments.

FIG. 7 illustrates the Virtual Shared Memory Table (VSMT) data structure employed by the method of the present invention.

FIG. 8 illustrates the VSMT hash anchor table.

FIG. 9 shows a model of a shared map file and the segments associated with it.

FIG. 10 is a block diagram of a basic cluster configuration which is one environment employed to describe some typical operations that are performed by the method of the present invention.

FIG. 11 is a flow chart illustrating the steps for creating a new file that is stored on one of the processing units in the cluster.

FIGS. 12aand 12b is a flow chart illustrating how an existing file is opened by an application program running on a processing unit within the cluster.

FIG. 13 is a flow chart illustrating how an existing file is loaded int o the virtual memory shared in a cluster configuration.

FIG. 14 is a flow chart illustrating the steps performed by the access coordinator when a using processing unit wishes to page-in a copy of a page that is not in the memory of any of the processing units in the configuration.

FIG. 15a and 15b is a flow chart illustrating the detailed steps of how the VSMT is updated by the access coordinator when a page of data is transferred from one processing unit to another processing unit.

FIG. 16 is a flow chart illustrating the steps performed by the access coordinator when a using processing unit sends a request to cast a page out of its main memory and there is a copy of the page in the memory of another processing unit.

FIG. 17 is a flow chart illustrating the steps performed by the access coordinator when a using processing unit sends a request to cast a page out of its main memory and there isn't a copy of the page in the memory of any other processing unit.

FIG. 18 is a flow chart illustrating the steps performed by the access coordinator when it determines that a given page of data must be cached by a shared memory processing unit.

DESCRIPTION OF THE PREFERRED EMBODIMENT

FIG. 1 is a block diagram of a multi-processor cluster configured data processing system in which the method of the present invention may be advantageously employed. As shown in FIG. 1, the data processing system comprises a plurality of processor units 10, a switch 11 and a plurality of communication links 12, each of which connects one processor unit 10 to switch 11. The function of switch 11 is to permit any processor unit 10 to communicate with any other processor unit. The specific details of the witch and the communication links are not considered relevant to an understanding of the present invention and hence are neither shown or described in detail. Examples of the switching arrangement that may be employed may be found in U.S. Pat. Nos. 4,635,250; 4,633,394; 4,630,015; 4,605,928.

FIG. 2 illustrates in detail one of the processor units 10 shown in FIG. 1. Processor unit 10 may be a high function personal computer or an engineering work station such as the IBM RT PC# running an operating system based on the UNIX operating system such as the IBM AIX# operating system. The processor unit 10, as shown in FIG. 2, comprises a microprocessor 16, a main memory 17, a memory management unit 18 which controls the transfer of data between the processor 16 and memory 17, and a plurality of I/O adapters or ports 20A-20E. Ports 20A and 20B function to connect display type terminals 21 and 22 to the system. Port 20C connects a printer to the system while port 20D connects disk drive 24 to the system. The communication port 20E is employed to connect the processor unit 10 to the communication link 12.

For purposes of discussion, processor unit 10 corresponds generally to the virtual memory data processing system that is described in detail in cross referenced application Ser. No. 819,458. As described in that application, the processor has a 32 bit effective address that is converted into a 40 bit virtual address by employing the 4 high order bits 31-28 to select one of 16 segment registers, each of which stores a 12 bit segment address that defines one of 4096 unique segments. Each segment comprises 256 megabytes of storage (2**28). If a page includes 2K bytes of data, then a segment contains 128K pages. On the other hand, if a page includes 4K bytes of data, the segment then has 64K pages, or more precisely, 64K virtual addresses which may be used to identify pages of data that are currently assigned to that segment.

As explained in the cross reference to application, an operating system based on he UNIX operating system is employed for the processor unit so that application programs and data employed by these programs are organized in accordance with the UNIX file system type of organization. Existing files are stored on the secondary storage devices of the processor unit which may be assumed to be a disk file. The unit of storage or addressability of the disk file is a disk block, which for purposes of discussion, will be assumed to store one page of data. Read and write system calls function to control the transfer of data between main memory and disk storage.

In a virtual memory organization, the memory manager and a page fault handling mechanism also function to control the transfer of pages between the disk file and main memory in response to load and store type of instructions being executed by the application program. In the system disclosed in the cross referenced application, the operating system is provided with a Map Page Range Service (MPRS) which functions to map a file into an assigned segment of the *Trademark of ATT; #Trademark of IBM virtual address space. The MPRS employs an External Page Table (XPT) data structure in which the disk block address containing a page of a file is assigned a virtual address in the assigned segment.

The memory manager also employs an Inverted Page Table (IPT) data structure for correlating real addresses in main memory where a page of data is stored to a virtual address assigned to that page. The system disclosed in the cross referenced application also employed a way to convert read and write system calls in the operating system to load and store instructions having virtual address which reflected the system call parameters and the Unix offset pointer in the file. All disk I/O operations were therefore under control of the memory manager and page fault handling mechanism in the system of the cross referenced application.

The operation of the processor unit 10 in executing an instruction for an application program is briefly as follows. The virtual address of the instruction is hashed with a suitable hashing algorithm to provide an index into a Hash Anchor Table (HAT). The indexed entry in the HAT contains a pointer to the first entry in a list of virtual addresses that hash to the same value. If a page having a virtual address that would hash to the value that provides the pointer to the list is in real memory, then the virtual address is in the list. The page frame in real memory where the page of data is stored is obtained from the entry in the list containing the virtual address. If the virtual address is not on the list, the corresponding page is not in real memory and a page fault has occurred.

The page fault handling mechanism is then activated. By referencing the XPT entry created when the file was mapped, the page fault handling mechanism locates the disk block address where the page having the requested virtual address is stored. Since the XPT is not pinned in memory, the page fault handling mechanism may encounter a page fault when it first references the XPT. However, once the appropriate page of XPT entries is paged into memory, the original page fault can be serviced. The page is transferred to a page frame in memory that has been made available and the application process is restarted.

It should be understood that the virtual memory manager operation summarized above is just one of the many prior art virtual memory management functions that can be used in the processor unit shown in FIG. 1 and on which the method of the present invention relies.

As indicated in FIG. 1, the units are interconnected by switch 10 and communication links 12 to permit one unit to be selectively interconnected in a data transferring relationship with one other unit. As stated earlier, communication port 20E is the normal interface to communication link 12 that is connected to the switch 11. A remote memory manager function is added to each unit 10 and provides an interface between port 20E and the native memory manager function 18. The function of the remote memory manager of processor unit 10A for example, is to process a request for a virtual page P of data from the remote memory manager function of processor unit 10B. The request is sent to processor unit 10A because 10A has been assigned as the access coordinator for that page and file. To process the request for page P, the remote memory manager function first determines if the requested page is in the main memory of the unit 10A. If the page P is there, a copy Pb is returned to unit 10B and a data structure referred to as the Virtual Shared Memory Table (VSMT) and shown in FIG. 7, records the fact that unit 10B has a copy of the requested page in its main memory. The remote request was initiated by unit 10B when an instruction having a virtual address was executed by unit 10B and recognized as involving a file that was stored at unit A. The manner in which the Access Coordinator of a file or a virtual page is recognized is discussed in detail later on the specification.

The above operation is a simple direct request and transfer operation involving two processor units. A slightly more involved operation occurs if it is assumed that the requested page Pa is paged out of the main memory of unit A so that the only copy in any main memory is the copy Pb that was previously sent to unit B. Assume now that unit C requests a copy of the same page from unit A. Unit A does have a copy of the requested page P on disk, but this would require a relatively long disk I/O operation to retrieve it and forward it to unit C. The remote memory manager of unit A in servicing the request from unit C would first check unit 10A's inverted page table and determine that it was not in the main memory of unit 10A. At this point, prior art systems would take the page fault and retrieve the page from disk. The new method, however, merely checks the SVMT data structure for the virtual address of the requested page Pb and is advised that a copy Pb is still in the main memory of unit 10B. The remote memory manager of unit 10A therefore sends a message to the remote memory manager of unit 10B, requesting that unit 10B send a copy of the page Pb to the remote memory manger of unit 10C. The initial request by unit 10C is said to have been serviced by a "triangular I/O operation." While a triangular I/O operation involves a number of messages including the transfer of a page of data, the time involved is at least 2 orders of magnitude faster with present day storage and communication technologies than would be involved in retrieving the requested page from unit 10A's disk file.

It should be noted that in the cluster shown in FIG. 1, each unit is running the same operating system and that preferably only one copy of each file exists in the cluster. Each file is assigned a processor unit which acts as the Access Coordinator for that file. The file is stored on the processor unit's secondary storage device. The file/access coordinator assignment can be established by the name given to the file similar to the convention employed by the PC-DOS operating system which uses drive and path parameters in the full name of the file. Alternately, a simple access coordinator table could be employed listing each file in the cluster along with the current access coordinator.

It should be assumed that in the following discussion, a page of data comprises 2**11 or 2K bytes (2048), that a segment consists of 2**17 or 1284K pages (131,072). Since the virtual address space employed by the cluster is used by each processor unit, two new data structures and identifiers are employed. The Local Segment Identifier (LSID) shown in FIG. 6 uniquely identifies a segment with its access coordinator. The LSID comprises 12 bits.

The Global Segment Identifier (GSID) shown in FIG. 6 comprises 19 bits which uniquely identify the processor unit within the segment. The GSID comprises an 7 bit processor ID portion and the 12 bit LSID.

The VSMT data structure is shown in FIG. 7 and is similar in many respects and functions to an inverted page table used by each processor unit.

Each entry of the VSMT includes the following fields:

    ______________________________________
    State Indicator          4     bits
    Local Segment ID         24    bits
    Page Number Within Local Segment
                             16    bits
    Last Entry Indicator     1     bit
    Processor ID             8     bits
    Index of Next Entry on Hash Chain
                             31    bits
    ______________________________________

• Inventors
  Blount, Marion L.; Morgan, Stephen P.; Rader, Katalin A. V.;
• Assignee
  International Business Machines Corporation (Armonk, NY)
• Published
  Aug-24-1993
• Current US Classes:
  707/102
  707/200
• Application #
  732949
• International Classes
  G06F 013/14; G06F 012/08
• Field of Search
  364/DIG. 395/425 395/600 395/650 395/200 395/800 395/275 371/10 371/13
• Examiner
  Kulik; Paul V.
• Agent
  Carwell; Robert M., Smith; Marilyn D.
• US Patent References:
  4078254
  4432057
  4445174
  4577274
  4635189
  4730249
  4742447
  4742450
  4851988
  4914571
  5109515