by Rick Compton
Under the dynamic distributed memory scheme, every processor is responsible for keeping track of the owner for each page in the local page table. A page table entry field called probOwner is used to locate the owner of each page. The probOwner may in fact be the true owner of a page or merely a starting point for a sequence of processors that lead to the true owner.
The following figure [1] helps demonstrate how the probOwner system works.
When process 1 page faults for page 3, a request is sent to the probOwner process 2. Since process 2 is not the page owner, it in turn forwards the request to probOwner process 3. Process 3 is not only a probOwner but also the page owner and acts upon the request.
As seen in the following algorithm by Li and Hudak [2] there are 4 reasons to change the value of probOwner, the receipt of an invalidation request, giving up ownership of a page, receiving a requested page, or forwarding a page request.
Write fault handler:
Lock ( PTable[ p ].lock );
ask PTable[ p ].probOwner for write access to page p;
Invalidate ( p, PTable[ p ].copyset );
PTable[ p ].probOwner := self;
PTable[ p ].access := write;
PTable[ p ].copyset := {};
Unlock ( PTable[ p ].lock );
Write server:
Lock ( PTable[ p ].lock );
IF I am owner THEN BEGIN
PTable[ p ].access = nil;
send p and PTable[ p ].copyset;
PTable[ p ].probOwner := RequestNode;
END
ELSE BEGIN
forward request to PTable[ p ].probOwner;
PTable[ p ].probOwner := RequestNode;
END
Unlock ( PTable[ p ].lock );
Read fault handler:
Lock ( PTable[ p ].lock );
ask PTable[ p ].probOwner for read access to p;
PTable[ p ].probOwner := ReplyNode;
PTable[ p ].access := read;
Unlock ( PTable[ p ].lock );
Read server:
Lock ( PTable[ p ].lock );
IF I am owner THEN BEGIN
PTable[ p ].copyset := PTable[ p ].copyset U {RequestNode};
PTable[ p ].access := read;
send p to RequestNode;
END
ELSE BEGIN
forward request to PTable[ p ].probOwner;
PTable[ p ].probOwner := RequestNode;
END
Unlock (PTable[ p ].lock );
Let's assume that in the earlier example, process 1 has a write fault for page 3. The write server locks the PTable[ 3 ].lock for process 1 and asks process 2 for write access to page 3. The write server locks the PTable[ 3 ].lock for process 2, forwards the request to process 3, changes the probOwner for page 3 to process 1 and then unlocks its lock. The write server locks PTable[ 3 ].lock for process 3, denies itself access for page 3, sends a copy of page 3 and the copyset (a list of all processes with a copy of the page) to process 1, changes the probOwner of page 3 to process 1, and unlocks its lock. Process 1 then invalidates the copyset, makes itself the probOwner of page 3, grants itself write access, sets the copyset to empty. and unlocks its lock. A read fault is similar.
For a N process system it has been proven [2] that there will be at most (N - 1) forwarding requests and often it will be much less. Likewise, it has been proven that the addition of processors does not degrade the algorithm. There is at least one negative however. An unnecessary double fault will occur if a read fault is immediately followed by a write fault in the same processor because the page owner resends a copy of the same page.
Kessler and Livny [3] have devised a method to eliminate this double fault. A sequence number is provided for each page and incremented each time access is given to that page. If a process read faults and then write faults, its sends the sequence number to the page owner as well as the write request. The page owner compares the sequence number for that page and if they are the same, the write permission is passed but not a copy of the page.
STUDY QUESTIONS
1. What is the difference between a probOwner and an actual page owner?
2. What is a copyset?
3, What is the maximum number of forwards to reach a page owner?
4. What creates an unnecessary double fault and how might it be eliminated?
REFERENCES
1. Singhal, Mukesh, and Niranjan G. Shivaratri, Advanced Concepts in Operating Systems, pp. 250-251.
2. Li, K., and P Hudak, "Memory Coherence in Shared Virtual Memory Systems," ACM Transactions on Computer Systems, vol. 7, no. 4, Nov. 1989.
3. Kessler, R.E.., and M. Livny, "An Analysis of Distributed Shared Memory Algorithms," Proceedings of the 9th International Conference on Distributed Computing Systems, 1989, pp. 498-505.