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

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.

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.

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.

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.