Multiprocessor system implementing virtual memory using a shared memory, and a page replacement method for maintaining paged memory coherence

• US 6,684,305 B1
• Filed: 04/24/2001
• Issued: 01/27/2004
• Est. Priority Date: 04/24/2001
• Status: Active Grant

• Current Assignee: Globalfoundries US Incorporated (GlobalFoundries, Inc.)
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Deneau, Thomas M.
• Primary Examiner(s): NGUYEN, THAN VINH
• Application Number:
  US09/841,469
• Time in Patent Office: 1,008 Days
• Field of Search: 711/147, 711/155, 711/156, 711/159, 711/160, 711/133, 711/141
• US Class Current: 711/159
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/1027 using associative or pseudo-associative address translation means, e.g. translation look-aside buffer [TLB]
• CPC Class Codes: G06F 12/1072 Decentralised address translation, e.g. in distributed shared memory systems
• CPC Class Codes: G06F 2212/302 In image processor or graphics adapter

Abstract

A computer system including a first processor, a second processor in communication with the first processor, a memory coupled to the first and second processors (i.e., a shared memory) and including multiple memory locations, and a storage device coupled to the first processor. The first and second processors implement virtual memory using the memory. The first processor maintains a first set of page tables and a second set of page tables in the memory. The first processor uses the first set of page tables to access the memory locations within the memory. The second processor uses the second set of page tables, maintained by the first processor, to access the memory locations within the memory. A virtual memory page replacement method is described for use in the computer system, wherein the virtual memory page replacement method is designed to help maintain paged memory coherence within the multiprocessor computer system.

Claims

1. A virtual memory page replacement method for use in a multiprocessor system comprising a first processor and a second processor, the method comprising:

accessing a set of page table entries of the second processor, wherein each of the set of page table entries corresponds to a different page of a set of pages of the second processor, and wherein each page of the set of pages of the second processor is stored in a memory and corresponds to a first page of the first processor to be removed from the memory, and wherein each page table entry of the second processor comprises a present bit and a dirty bit, and wherein the present bit has a value indicating whether the corresponding page of the second processor is present in the memory, and wherein the dirty bit has a value indicating whether the corresponding page of the second processor needs to be written to a storage;

changing a value of the present bit of each of the set of page table entries to indicate that the corresponding page of the second processor is not present in the memory, wherein the changing is performed such that the value of the dirty bit of each of the set of page table entries is not changed;

informing the second processor of a need to remove any entry of a buffer of the second processor corresponding to a page of the set of pages, wherein the buffer includes multiple entries;

reading each of the set of page table entries;

wherein the read is performed after the informing;

reading a page table entry corresponding to the first page of the first processor, wherein the page table entry comprises a dirty bit indicating whether or not the first bit needs to be written to the storage; and

writing the first page of the first processor from the memory to the storage if;

(i) a dirty bit of at least one of the set of page table entries obtained during the reading of each of the set of page table entries indicates the corresponding page of the second processor needs to be written to the storage, or (ii) the dirty bit of the page table entry obtained during the reading of the page table entry of the first processor indicates the first page of the first processor needs to be written to the storage.

2. The virtual memory page replacement method as recited in claim 1, wherein the informing comprises:

informing the second processor of a need to remove any entry of a buffer of the second processor corresponding to a page of the set of pages, wherein the buffer includes multiple entries, and wherein each entry of the buffer comprises a dirty bit indicating whether or not a corresponding page of the second processor needs to be written to the storage;

and wherein the virtual memory page replacement method further comprises;

responding to the informing by;

locating an entry of the buffer corresponding to a page of the set of pages;

if the dirty bit of the entry corresponding to the page of the set of pages indicates the page of the set of pages needs to be written to the storage, updating the dirty bit of the page table entry of the second processor corresponding to the page of the set of pages to indicate that the page of the set of pages needs to be written to the storage; and

clearing the entry corresponding to the page of the set of pages.

3. The virtual memory page replacement method as recited in claim 1, wherein the informing the second processor comprises:

sending a message to the second processor indicating a need to clear any entry of the buffer of the second processor corresponding to a page of the set of pages.

4. The virtual memory page replacement method as recited in claim 1, further comprising:

receiving an indication of a page fault condition in the second processor; and

determining that a first page of the first processor, stored in the memory, must be replaced by a second page of the first processor, stored in the storage, to clear the page fault condition in the second processor.

5. The virtual memory page replacement method as recited in claim 4, wherein the receiving the indication comprises:

receiving a message from the second processor indicating a page fault condition in the second processor.

6. A virtual memory page replacement method for use in a multiprocessor system comprising a first processor and a second processor, the method comprising:

performing a first read of each of a set of page table entries of the second processor, wherein each of the set of page table entries corresponds to a different page of a set of pages of the second processor, wherein each page of the set of pages of the second processor is stored in a memory and corresponds to a first page of the first processor to be removed from the memory, and wherein each page table entry of the second processor comprises a dirty bit indicating whether or not the corresponding page of the second processor needs to be written to a storage;

marking each page table entry of the set of page table entries to indicate the corresponding page of the second processor is not present in the memory;

informing the second processor of a need to remove any entry of a buffer of the second processor corresponding to a page of the set of pages, wherein the buffer includes multiple entries, and wherein each entry of the buffer comprises a dirty bit indicating whether or not a corresponding page of the second processor needs to be written to the storage;

performing a second read of each of the set of page table entries, wherein the second read is performed after the informing;

performing a read of a page table entry corresponding to the first page of the first processor, wherein the page table entry comprises a dirty bit indicating whether or not the first bit needs to be written to the storage; and

writing the first page of the first processor from the memory to the storage if;

(i) a dirty bit of at least one of the set of page table entries obtained during the first read of each of the set of page table entries of the second processor indicates the corresponding page of the second processor needs to be written to the storage, or (ii) a dirty bit of at least one of the set of page table entries obtained during the second read of each of the set of page table entries of the second processor indicates the corresponding page of the second processor needs to be written to the storage, or (iii) the dirty bit of the page table entry obtained during the read of the page table entry of the first processor indicates the first page of the first processor needs to be written to the storage.

7. The virtual memory page replacement method as recited in claim 6, further comprising:

responding to the informing by;

locating an entry of the buffer corresponding to a page of the set of pages;

if the dirty bit of the entry corresponding to the page of the set of pages indicates the page of the set of pages needs to be written to the storage, updating the dirty bit of the page table entry of the second processor corresponding to the page of the set of pages to indicate that the page of the set of pages needs to be written to the storage; and

clearing the entry corresponding to the page of the set of pages.

8. The virtual memory page replacement method as recited in claim 6, wherein the informing the second processor comprises:

sending a message to the second processor indicating a need to clear any entry of the buffer of the second processor corresponding to a page of the set of pages.

9. The virtual memory page replacement method as recited in claim 6, further comprising:

receiving an indication of a page fault condition in the second processor; and

determining that a first page of the first processor, stored in the memory, must be replaced by a second page of the first processor, stored in the storage, to clear the page fault condition in the second processor.

10. The virtual memory page replacement method as recited in claim 9, wherein the receiving the indication comprises:

receiving a message from the second processor indicating a page fault condition in the second processor.

14. The carrier medium as recited in claim 8, wherein the computer-readable storage medium is a floppy disk or a compact disk read only memory (CD-ROM) disk.

11. A virtual memory page replacement method for use in a multiprocessor system comprising a first processor and a second processor, the method comprising:

receiving a message from the second processor indicating a page fault condition in the second processor;

determining that a first page of the first processor, stored in the memory, must be replaced by a second page of the first processor, stored in the storage, to clear the page fault condition in the second processor;

performing a first read of each of a set of page table entries of the second processor, wherein each of the set of page table entries corresponds to a different page of a set of pages of the second processor, wherein each page of the set of pages of the second processor is stored in the memory and corresponds to the first page of the first processor, and wherein each page table entry of the second processor comprises a dirty bit indicating whether or not the corresponding page of the second processor needs to be written to the storage;

marking each of the set of page table entries to indicate the corresponding page of the second processor is not present in the memory;

sending a message to the second processor indicating a need to remove any entry of a buffer of the second processor corresponding to a page of the set of pages, wherein the buffer includes multiple entries, and wherein each entry of the buffer comprises a dirty bit indicating whether or not a corresponding page of the second processor needs to be written to the storage;

performing a second read of each of the set of page table entries, wherein the second read is performed after the sending of the message;

performing a read of a page table entry corresponding to the first page of the first processor, wherein the page table entry comprises a dirty bit indicating whether or not the first bit needs to be written to the storage; and

writing the first page of the first processor from the memory to the storage if;

(i) a dirty bit of at least one of the set of page table entries obtained during the first read of the set of page table entries of the second processor indicates the corresponding page of the second processor needs to be written to the storage, or (ii) a dirty bit of at least one of the set of page table entries obtained during the second read of each of the set of page table entries of the second processor indicates the corresponding page of the second processor needs to be written to the storage, or (iii) the dirty bit of the page table entry obtained during the read of the page table entry of the first processor indicates the first page of the first processor needs to be written to the storage.

12. A carrier medium comprising program instructions for carrying out a virtual memory page replacement method in a multiprocessor system comprising a fist processor and a second processor, wherein the program instructions are operable to implement:

accessing a set of page table entries of the second processor, wherein each of the set of page table entries corresponds to a different page of a set of pages of the second processor, and wherein each page of the set of pages of the second processor is stored in a memory and corresponds to a first page of the first processor to be removed from the memory, and wherein each page table entry of the second processor comprises a present bit and a dirty bit, and wherein the present bit has a value indicating whether the corresponding page of the second processor is present in the memory, and wherein the dirty bit has a value indicating whether the corresponding page of the second processor needs to be written to a storage;

changing a value of the present bit of each of the set of page table entries to indicate that the corresponding page of the second processor is not present in the memory, wherein the changing is performed such that the value of the dirty bit of each of the set of page table entries is not changed;

informing the second processor of a need to remove any entry of a buffer of the second processor corresponding to a page of the set of pages, wherein the buffer includes multiple entries;

reading each of the set of page table entries;

wherein the read is performed after the informing;

reading a page table entry corresponding to the first page of the first processor, wherein the page table entry comprises a dirty bit indicating whether or not the first bit needs to be written to the storage; and

writing the first page of the first processor from the memory to the storage if;

(i) a dirty bit of at least one of the set of page table entries obtained during the reading of each of the set of page table entries indicates the corresponding page of the second processor to be written to the storage, or (ii) the dirty bit of the page table entry obtained during the reading of the page table entry of the first processor indicates the first page of the first processor needs to be written to the storage.

13. The carrier medium as recited in claim 12, wherein the carrier medium is a computer-readable storage medium.

15. A system, comprising:

a first processor;

a second processor in communication with the first processor;

a memory operably coupled to the first and second processors;

a storage device operably coupled to the first processor;

means for accessing a set of page table entries of the second processor, wherein each of the set of page table entries corresponds to a different page of a set of pages of the second processor, and wherein each page of the set of pages of the second processor is stored in the memory and corresponds to a first page of the first processor to be removed from the memory, and wherein each page table entry of the second processor comprises a present bit and a dirty bit, and wherein the present bit has a value indicating whether the corresponding page of the second processor is present in the memory, and wherein the dirty bit has a value indicating whether the corresponding page of the second processor needs to be written to the storage device;

means for changing a value of the present bit of each of the set of page table entries to indicate that the corresponding page of the second processor is not present in the memory, wherein the changing is performed such that the value of the dirty bit of each of the set of page table entries is not changed;

informing the second processor of a need to remove any entry of a buffer of the second processor corresponding to a page of the set of pages, wherein the buffer includes multiple entries;

means for reading each of the set of page table entries;

wherein the read is performed after the informing;

means for reading a page table entry corresponding to the first page of the first processor, wherein the page table entry comprises a dirty bit indicating whether or not the first bit needs to be written to the storage device; and

means for writing the first page of the first processor from the memory to the storage device if;

(i) a dirty bit of at least one of the set of page table entries obtained during the reading of each of the set of page table entries indicates the corresponding page of the second processor needs to be written to the storage device, or (ii) the dirty bit of the page table entry obtained during the reading of the page table entry of the first processor indicates the fire page of the first processor needs to be written to the storage device.